10 ms·

Any tips on implementing tail-call optimization when compiling to C? (or llvm)?

by caditinpiscinam 6y ago

ratww 6y ago
The easy way is by using goto.
siraben 6y ago
That is a good question. Although tail-call is easy to describe and understand I've haven't implemented it myself. I'd also appreciate pointers to resources.
- siraben 6y ago
  Oh, I completely forgot about[0], which talks about TCO in the imperative context (but applies to functional languages as well)! [0] https://dspace.mit.edu/bitstream/handle/1721.1/5753/AIM-443.pdf?sequence=2&isAllowed=y https://dspace.mit.edu/bitstream/handle/1721.1/5753/AIM-443....
- Joker_vD 6y ago
  See also [0], which talks about how Chicken SCHEME (which compiles to portable C) does it. [0] https://www.more-magic.net/posts/internals-gc.html#managing-data-on-the-stack https://www.more-magic.net/posts/internals-gc.html#managing-...
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)

10 ms·

Any tips on implementing tail-call optimization when compiling to C? (or llvm)?

by caditinpiscinam 6y ago

Any tips on implementing tail-call optimization when compiling to C? (or llvm)?

ratww 6y ago
The easy way is by using goto.
siraben 6y ago
That is a good question. Although tail-call is easy to describe and understand I've haven't implemented it myself. I'd also appreciate pointers to resources.
- siraben 6y ago
  Oh, I completely forgot about[0], which talks about TCO in the imperative context (but applies to functional languages as well)! [0] https://dspace.mit.edu/bitstream/handle/1721.1/5753/AIM-443.pdf?sequence=2&isAllowed=y https://dspace.mit.edu/bitstream/handle/1721.1/5753/AIM-443....
- Joker_vD 6y ago
  See also [0], which talks about how Chicken SCHEME (which compiles to portable C) does it. [0] https://www.more-magic.net/posts/internals-gc.html#managing-data-on-the-stack https://www.more-magic.net/posts/internals-gc.html#managing-...
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)