CPS and RTL

[Noah Lavine]

Hello,

I've had several conversations on this list about using continuation-passing style in Guile. I recently decided to take the hint and implement it. I've pushed a new branch called wip-rtl-cps that I'd appreciate comments on (but I do not necessarily think that this is the branch that will be merged with master - it's still pretty rough).

The branch contains a CPS data structure based on the paper "Compiling with Continuations, Continued", by Andrew Kennedy. It lives in module/language/cps.scm. The branch is based on the RTL branch, and there's a CPS->RTL compiler in module/language/cps/compile-rtl.scm. There are also tests for it in test-suite/tests/cps.test. Here are some notes:

- It may have been a mistake to do a CPS->RTL compiler first. Even if we want to use RTL eventually, it probably would have been more sensible to do CPS->GLIL first, so the change would be independent of the switch to RTL. However, the code is already here - we can use it as-is, or change to GLIL, or something else.

- There's no Tree-IL->CPS compiler yet, mostly because I'm confident that we can do it, so I figured we could always add it later.

- There are three major language features missing from the compiler: top-level variables, closures, and anything to do with the dynamic environment. Those are all pretty major features - that's why I said this was rough.

- Right now the register allocation pass operates directly on the CPS. I have been thinking about making some higher-order functions for traversing it, similar to tree-il-fold, but I haven't done it yet.

Basically, I have a very rough compiler. I'd like to show it to people now, even though it's not fully formed, so that you can point out any issues, and so that we can see if this is something that could eventually wind up in mainline Guile. I'd rather fix problems now than later on. (And of course I would appreciate help from anyone else who wants to contribute.)

Thanks,

Noah