## digitalmars.D.learn - Simple trampoline code

• bearophile (44/44) Jun 11 2009 I'm trying to convert to D2 the following (quite simplified up) Python c...
• Ellery Newcomer (24/79) Jun 11 2009 How DO you define the signature of a function that returns itself?
• BCS (3/10) Jun 11 2009 Last I checked, you can't. Make it return a struct that has itself.
• Ellery Newcomer (2/17) Jun 11 2009 Thanks for reading my code
• BCS (6/24) Jun 11 2009 I never bothered understanding what the OP's code does but to answered t...
• bearophile (37/43) Jun 15 2009 I don't understand what you mean here, as far as I know DMD isn't curren...
bearophile <bearophileHUGS lycos.com> writes:
```I'm trying to convert to D2 the following (quite simplified up) Python code,
that implements a trampoline to run tail-call functions with no stack overflow:

# Python code
# *args means almost all the arguments
def trampoline(fun, *args):
thunk = lambda : fun(*args)
while True:
(thunk, result) = thunk()
if thunk is None:
return result

# a tail-recursive function
def summer(n, p = 1):
if n >= 2:
return (lambda n=n, p=p: summer(n-1, n+p), None)
else:
return (None, p)

assert trampoline(summer, 1000) == 500500

My D2 version so far (doesn't work):

// D2 + Phobos2 code
import std.typecons: tuple;
import std.stdio: writeln;

int trampoline(TyFun, TyTuple)(TyFun fun, TyTuple args) {
auto thunk = { fun(args.tupleof) };
while (true) {
auto pair = thunk();
thunk = pair.field[0];
auto result = pair.field[1];
if (thunk is null)
return result;
}
}

auto summer(int n, int p=1) {
if (n >= 2)
return tuple((int n=n, int p=p){return summer(n-1, n+p);}, 0);
else
return tuple(null, p);
}

void main() {
writeln(trampoline(summer, tuple(1000)));
}

The D2 compiler outputs:
trampoline.d(18): Error: forward reference to inferred return type of function
call summer(n - 1,n + p)
Can that D2 code be fixed?

Bye,
bearophile
```
Jun 11 2009
Ellery Newcomer <ellery-newcomer utulsa.edu> writes:
```bearophile wrote:
I'm trying to convert to D2 the following (quite simplified up) Python code,
that implements a trampoline to run tail-call functions with no stack overflow:

# Python code
# *args means almost all the arguments
def trampoline(fun, *args):
thunk = lambda : fun(*args)
while True:
(thunk, result) = thunk()
if thunk is None:
return result

# a tail-recursive function
def summer(n, p = 1):
if n >= 2:
return (lambda n=n, p=p: summer(n-1, n+p), None)
else:
return (None, p)

assert trampoline(summer, 1000) == 500500

My D2 version so far (doesn't work):

// D2 + Phobos2 code
import std.typecons: tuple;
import std.stdio: writeln;

int trampoline(TyFun, TyTuple)(TyFun fun, TyTuple args) {
auto thunk = { fun(args.tupleof) };
while (true) {
auto pair = thunk();
thunk = pair.field[0];
auto result = pair.field[1];
if (thunk is null)
return result;
}
}

auto summer(int n, int p=1) {
if (n >= 2)
return tuple((int n=n, int p=p){return summer(n-1, n+p);}, 0);
else
return tuple(null, p);
}

void main() {
writeln(trampoline(summer, tuple(1000)));
}

The D2 compiler outputs:
trampoline.d(18): Error: forward reference to inferred return type of function
call summer(n - 1,n + p)
Can that D2 code be fixed?

Bye,
bearophile

How DO you define the signature of a function that returns itself?

And FYI, dmd handles your particular example recursively just fine. But
you probably know that.

That aside, this is about the best that I can get:

int trampoline (TyFun, TyTuple) (TyFun fun, TyTuple targs){
while (1){
auto pair = fun(targs.tupleof[0..2]);
fun = pair.field[0];
int result = pair.field[1];
targs = tuple(pair.tupleof[2..4]);
if(fun is null){
return result;
}
}
}

class Durr{
alias summer opCall;
Tuple!(Durr,int,int,int) summer(int n, int p){
if (n>= 2){
return tuple(this,0,n-1,n+p);
}else return tuple(cast(Durr)null,p,0,0);
}
}
```
Jun 11 2009
BCS <none anon.com> writes:
```Hello Ellery,

bearophile wrote:

I'm trying to convert to D2 the following (quite simplified up)
Python code, that implements a trampoline to run tail-call functions
with no stack overflow:

[...]
How DO you define the signature of a function that returns itself?

Last I checked, you can't. Make it return a struct that has itself.
```
Jun 11 2009
Ellery Newcomer <ellery-newcomer utulsa.edu> writes:
```BCS wrote:
Hello Ellery,

bearophile wrote:

I'm trying to convert to D2 the following (quite simplified up)
Python code, that implements a trampoline to run tail-call functions
with no stack overflow:

[...]
How DO you define the signature of a function that returns itself?

Last I checked, you can't. Make it return a struct that has itself.

```
Jun 11 2009
BCS <none anon.com> writes:
```Hello Ellery,

BCS wrote:

Hello Ellery,

bearophile wrote:

I'm trying to convert to D2 the following (quite simplified up)
Python code, that implements a trampoline to run tail-call
functions with no stack overflow:

[...]

How DO you define the signature of a function that returns itself?

Last I checked, you can't. Make it return a struct that has itself.

I never bothered understanding what the OP's code does but to answered the
question you asked: this is the closest I have seen to a function that can
return (a pointer to) itself:

struct S { S function(int) fn; }

S foo(int i) { return S(&foo); }
```
Jun 11 2009
bearophile <bearophileHUGS lycos.com> writes:
```Ellery Newcomer:

How DO you define the signature of a function that returns itself?

You may need a language with a type system more powerful than D type system
(like Scala?).

And FYI, dmd handles your particular example recursively just fine. But
you probably know that.

I don't understand what you mean here, as far as I know DMD isn't currently
able to perform tail-call elimination by itself (LDC is able to, in simple
situations. As LLVM improvers, LDC will probably improve its recursivity
elimination).

That aside, this is about the best that I can get:

Thank you for your code. I think it's not usable in most practical situations.

-------------------

BCS:

I never bothered understanding what the OP's code does<

It's my fault, I am sorry.
The code is a very easy to understand (but not elegant) way to perform
tail-call optimizations (well, not really, but the end result is similar) in a
compiler/interpreter that's unable to do it by itself.
Instead of having a function that recursively calls itself so many times to
risk a stack overflow (on Python such stack is small, by default), you modify
the tail-recursive function in some way (there are ways to avoid this in
Python, but I have tried to kept things as simple as possible) and then you
define a trampoline() function.
Some info on trampolines:
http://en.wikipedia.org/wiki/Trampoline_(computers)
Such trampoline here calls a function in a loop, the function returns the
function to be used in the next iteration plus (at the end) the result. It's
related to the concept of continuations:
http://en.wikipedia.org/wiki/Continuation
Conceptually this is very simple, but in a statically-typed language the type
system must be flexible enough to express the type of a function that (among
other things) returns itself.

but to answered the question you asked: this is the closest I have seen to a
function that can return (a pointer to) itself:

struct S { S function(int) fn; }
S foo(int i) { return S(&foo); }
<

It's not too much bad and it works for functions:

import std.stdio: writeln;

struct S {
S function(int) fn;
int result;
}

S foo(int i) {
return S(&foo, i+1);
}

void main() {
S function(int) f = &foo;
for (int i; i < 10; i++) {
auto s = f(i);
writeln(s.result);
f = s.fn;
}
}

I have tried to adapt your code to the trampoline, but there are problems.

Bye,
bearophile
```
Jun 15 2009