Simple trampoline code

[bearophile]

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