June 15, 2009 Re: Simple trampoline code | ||||
---|---|---|---|---|
| ||||
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 |
Copyright © 1999-2021 by the D Language Foundation