Continuation Passing Style

[William103]

Curse so far is extremely functional, meaning we desperately need tail-call optimization, and could benefit from other optimizations as well. I've been doing a bit of research, and I think what we would really benefit from converting to continuation-passing style (CPS) in the hir/mir.

CPS is comparable to a functional version of SSA, where execution order is much more explicit and temporaries are named. In CPS, every function takes a function as an additional argument representing the continuation i.e. what to do next, which it calls rather than returning.

For example, this haskell code

square :: Float -> Float
square a = a * a

hypotenuse :: Float -> Float -> Float
hypotenuse a b = sqrt (square a + square b)

would be transformed into this

square :: Float -> (Float -> a) -> a
square x cont = cont (x * x)

add :: Float -> Float -> (Float -> a) -> a
add x y cont = cont (x + y)

hypotenuse :: Float -> Float -> (Float -> a) -> a
hypotenuse x y cont = square x (\x2 -> square y (\y2 -> add x2 y2 (\x2py2 -> sqrt x2py2 (\hypot -> cont hypot))))

In CPS, functions never return, but instead always tail-call some other function. This means that an interpreter/compiler can effectively just maintain a "call-stack" while jumping around without ever actually recursing. A traditional tail-call would be when a function gets called (the original function or not) with the continuation it was given unchanged, which would mean that the interpreter/compiler would jump to the new function without updating the "call-stack" giving us TCO for free. Plus it would definitely work through in and of, since they don't modify the continuation. I have no idea if it would work through rec or not (tbh I still don't really understand rec), but it might.

CPS would also additionally aid a lot in eventually making a compiler and any other future optimizations, since control flow would basically become jumps, evaluation order would become explicit, and we would name temporaries.

Resources that look helpful:

• Neat presentation on converting Scheme to C, this has lots of useful tidbits besides CPS
• Someone's notes trying to understand CPS
• Blog post on CPS
• Paper outlining a fancy CPS algorithm

[William103]

Some updates: I've been making good progress on code to convert the hir into CPS. I think I have basically everything but pattern matching working, but it turns out that pattern matching is going to be quite tricky. It will require "compiling" the patterns into a decision tree that'll basically turn into a bunch of conditionals. Unfortunately the main source I have been following just says "Generating code for case statements is made easier by the fact that much of the heavy lifting has already been done by the 'match compiler,'" which they don't explain beyond what a "match compiler" is. On the plus side, apparently you get exhaustiveness and redundancy checking almost for free, which is nice.

Dumping some resources I have found helpful, for future reference, so I can clean up my tabs:

• Remarkably accessible paper describing a pragmatic algorithm for pattern match compiling
• Implementation in Rust of the above algorithm
• Simpler implementation by original author in Scala
• I have absolutely no idea what this paper is saying, but it seems to get cited a lot and might be useful?

Edit: You can see the progress I've made on my fork here if you're curious.

[QnnOkabayashi]

Make a draft PR so I can leave comments. Looks cool so far tho!