www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Simple trampoline code

reply bearophile <bearophileHUGS lycos.com> writes:
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
Jun 11 2009
next sibling parent reply Ellery Newcomer <ellery-newcomer utulsa.edu> writes:
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); } }
Jun 11 2009
parent reply BCS <none anon.com> writes:
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.
Jun 11 2009
parent reply Ellery Newcomer <ellery-newcomer utulsa.edu> writes:
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
Jun 11 2009
parent BCS <none anon.com> writes:
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); }
Jun 11 2009
prev sibling parent bearophile <bearophileHUGS lycos.com> writes:
Ellery Newcomer:

 How DO you define the signature of a function that returns itself?
You may need a language with a type system more powerful than D type system (like Scala?).
 And FYI, dmd handles your particular example recursively just fine. But
 you probably know that.
I don't understand what you mean here, as far as I know DMD isn't currently able to perform tail-call elimination by itself (LDC is able to, in simple situations. As LLVM improvers, LDC will probably improve its recursivity elimination).
 That aside, this is about the best that I can get:
Thank you for your code. I think it's not usable in most practical situations. ------------------- BCS:
I never bothered understanding what the OP's code does<
It's my fault, I am sorry. The code is a very easy to understand (but not elegant) way to perform tail-call optimizations (well, not really, but the end result is similar) in a compiler/interpreter that's unable to do it by itself. Instead of having a function that recursively calls itself so many times to risk a stack overflow (on Python such stack is small, by default), you modify the tail-recursive function in some way (there are ways to avoid this in Python, but I have tried to kept things as simple as possible) and then you define a trampoline() function. Some info on trampolines: http://en.wikipedia.org/wiki/Trampoline_(computers) Such trampoline here calls a function in a loop, the function returns the function to be used in the next iteration plus (at the end) the result. It's related to the concept of continuations: http://en.wikipedia.org/wiki/Continuation Conceptually this is very simple, but in a statically-typed language the type system must be flexible enough to express the type of a function that (among other things) returns itself.
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); } < It's not too much bad and it works for functions: import std.stdio: writeln; struct S { S function(int) fn; int result; } S foo(int i) { return S(&foo, i+1); } void main() { S function(int) f = &foo; for (int i; i < 10; i++) { auto s = f(i); writeln(s.result); f = s.fn; } } I have tried to adapt your code to the trampoline, but there are problems. Bye, bearophile
Jun 15 2009