News for hackers. Stuff that matters.

A comment on Making a programming language using Rust. Parent comment

Re:Making a programming language using Rust by sinistersnare on Monday November 09, 2020 @12:04AM (#25031630)
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

[1]: https://books.google.com/books/about/Compiling_with_Continua...

[ Parent | on HN ]
Re:Making a programming language using Rust by siraben on Monday November 09, 2020 @04:38AM (#25033042)
> 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)

[ Parent | on HN ]