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 siraben on Sunday November 08, 2020 @09:26PM (#25030860)
If your langauge is functional (has closures), I would recommend checking out[0] which is a full end-to-end tutorial on compiling a functional language to C and could be adapted to LLVM, using Haskell as the implementation language.

Basically the only slightly non-trivial step is closure conversion[1] which lifts free (AKA "captured" in C++ terminology) variables from a closure, which lets you encode closures faithfully in a first-order language with structs.

[0] https://github.com/jozefg/pcf/

[1] http://lampwww.epfl.ch/teaching/archive/advanced_compiler/20...

[ Parent | on HN ]
Re:Making a programming language using Rust by caditinpiscinam on Sunday November 08, 2020 @10:05PM (#25031077)
Any tips on implementing tail-call optimization when compiling to C? (or llvm)?
[ Parent | on HN ]
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 ]
Re:Making a programming language using Rust by siraben on Sunday November 08, 2020 @10:26PM (#25031184)
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.
[ Parent | on HN ]
Re:Making a programming language using Rust by siraben on Sunday November 08, 2020 @10:29PM (#25031195)
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....

[ Parent | on HN ]
Re:Making a programming language using Rust by Joker_vD on Monday November 09, 2020 @06:25AM (#25033632)
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-...

[ Parent | on HN ]
Re:Making a programming language using Rust by ratww on Sunday November 08, 2020 @10:19PM (#25031148)
The easy way is by using goto.
[ Parent | on HN ]