• bearophile <bearophileHUGS lycos.com> Jun 15 2009

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:


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