3 ms·
If you translate your language to use Continuation Passing Style [0], then you get tail-calls for every function, which effectively obviates the stack. This te
by sinistersnare 6y ago
If you translate your language to use Continuation Passing Style [0], then you get tail-calls for every function, which effectively obviates the stack.
This technique is used by functional language compilers, see Compiling With Continuations for more info on the underlying theory
[0]: https://en.wikipedia.org/wiki/Continuation-passing_style https://en.wikipedia.org/wiki/Continuation-passing_style
[1]: https://books.google.com/books/about/Compiling_with_Continuations.html?id=0Uoecu9ju4AC https://books.google.com/books/about/Compiling_with_Continua...
- siraben 6y ago> then you get tail-calls for every function, which effectively obviates the stack. This is true, however CPS moves the work from the stack to the heap, so a deep enough recursion would exhaust the heap instead. Using a trampoline[0] in conjunction with CPS ensure constant stack usage for tail-recursive functions. [0] https://en.wikipedia.org/wiki/Trampoline_(computing) https://en.wikipedia.org/wiki/Trampoline_(computing)