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

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);
    }
}

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.

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.
> 
> 
Thanks for reading my code

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.
>> 
> Thanks for reading my code
> 

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); }