Thread overview | |||||||
---|---|---|---|---|---|---|---|
|
June 11, 2009 Simple trampoline code | ||||
---|---|---|---|---|
| ||||
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 |
June 12, 2009 Re: Simple trampoline code | ||||
---|---|---|---|---|
| ||||
Posted in reply to 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);
}
}
|
June 12, 2009 Re: Simple trampoline code | ||||
---|---|---|---|---|
| ||||
Posted in reply to Ellery Newcomer | 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. |
June 12, 2009 Re: Simple trampoline code | ||||
---|---|---|---|---|
| ||||
Posted in reply to BCS | 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
|
June 12, 2009 Re: Simple trampoline code | ||||
---|---|---|---|---|
| ||||
Posted in reply to Ellery Newcomer | 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); }
|
Copyright © 1999-2021 by the D Language Foundation