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