Compiling (stackful) coroutines as continuations is such a nice strategy. The thing I like most about it is that you don’t need to manage any stacks in the runtime implementation, since all of the data is captured in continuations’ closures; this means you can build compilers that target e.g. JavaScript where you have no runtime control of the stack. Throw defunctionalization to get rid of closure allocation on top of that and you have a pretty efficient implementation!
Can you shed some light on how to use defunctionalization here to get rid of closure allocation? I’ve been thinking about it, but not been able to figure it out.
Sure. One idea is to do a pass after a CPS conversion and name all closures under function types. This way you explicitly enumerate exactly what functions a closure can resolve to. Then, when you compile the program, you can use that enumeration to compile calls to closures into switches where each branch of the switch calls a named function, with an unboxed closure environment, instead of having to follow a function pointer and a boxed environment.
For example, if you have
n = 5
m = 2
add1 = \() -> n + 1
mul6PlusM = \() -> n * 6 + m
foo = if True then add1 else mul6PlusM
you can compile foo as the data type Mul6PlusM { n: Int, m: Int} | Add1 { n: Int }, and calls to foo like foo () become
match foo with
| Mul6PlusM {n, m} -> mul6PlusM () {n, m}
| Add1 {n} -> add1 () {n}
If I understand correctly this might be a bit tricky out-of-the gate for Co, since your implementation does CPS conversion on-the-fly during interpretation (let me know if this is wrong).
By the way, this is not my idea - this paper is the earliest related idea I know of, and we implement this kind of defunctionalization in Roc following a model from an unpublished paper by William Brandon.
This is really great PL implementation content. Thank you for writing it so well.
Compiling (stackful) coroutines as continuations is such a nice strategy. The thing I like most about it is that you don’t need to manage any stacks in the runtime implementation, since all of the data is captured in continuations’ closures; this means you can build compilers that target e.g. JavaScript where you have no runtime control of the stack. Throw defunctionalization to get rid of closure allocation on top of that and you have a pretty efficient implementation!
Can you shed some light on how to use defunctionalization here to get rid of closure allocation? I’ve been thinking about it, but not been able to figure it out.
Sure. One idea is to do a pass after a CPS conversion and name all closures under function types. This way you explicitly enumerate exactly what functions a closure can resolve to. Then, when you compile the program, you can use that enumeration to compile calls to closures into switches where each branch of the switch calls a named function, with an unboxed closure environment, instead of having to follow a function pointer and a boxed environment.
For example, if you have
you can compile
fooas the data typeMul6PlusM { n: Int, m: Int} | Add1 { n: Int }, and calls to foo likefoo ()becomeIf I understand correctly this might be a bit tricky out-of-the gate for Co, since your implementation does CPS conversion on-the-fly during interpretation (let me know if this is wrong).
By the way, this is not my idea - this paper is the earliest related idea I know of, and we implement this kind of defunctionalization in Roc following a model from an unpublished paper by William Brandon.