Ongoing work on Tail Calls

Self tail calls

I finally got self tail-calls working yesterday, which is a good milestone.

The work involved adding code to identify and mark the tail position, as well as figuring out if we’re tail-calling onto ourselves (self-tail).

The emitted code is a trampoline, so instead of applying the function, we throw an exception and rewrite the outer call site as a while loop.

One change that took 2 days to do is to swap the argument passing from the frame.arguments array onto using FrameSlots. The return value from the while loop also needed to be written into another FrameSlot, so that was done as well.

Boolean operators

As part of porting over some test cases, I also added support for and and or - it was nice that I could do it during the compile into KiwiNode and rewrite them as IfNodes. It’s interesting to learn that:

  • (and) returns #t
  • (or) returns #f
  • (and 1 2 3) hold onto the last non-false value, returning 3.
  • (or 1 2 3) returns the first non-false value: 1.

I think once I’m done with general tail-calls, I’ll go back to writing the macro-expander, and and and or can be implemented there instead of the compiler, which will give me a chance to simplify the expression by doing constant folding.

More hacking with RootNodes

The work on TCO helped me understand more of how RootNodes work in Truffle. With that in mind, adding delimited continuations and multiple-values now seems within reach.

Roadmap

Maybe this is the direction I’ll take next:

August: finish TCO (self tailcalls and general tailcalls)

September: port micro macro expander or implement Dybvig’s mulitple-values paper.