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