Simple trampoline code
    bearophile 
    bearophileHUGS at lycos.com
       
    Thu Jun 11 05:22:17 PDT 2009
    
    
  
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
    
    
More information about the Digitalmars-d-learn
mailing list