Lambda the Ultimate

Lambda lifting is the identity transformation on C programs, because all free variables in C are at global scope. Not having looked at the paper, I wonder what they can possibly be talking about.

Looks fun: related (but uncited) reading giving a good motivation for this project is the Carpaccio series of work. Despite all of their support, they some reason stopped just short of CPS'ing for the programming interface, requiring something like explicit passing of state if I recall correctly.

An interesting question is whether, for these performance-sensitive programs, continuations are the right abstraction. If you take a security perspective, that means a function you call might take away your thread of control! In the explicitly cooperative model (e.g., AJAX script), by convention** of manually passing around a continuation, that won't happen. Given that we write C code for tricky performance reasons, it's not actually clear that the traditional continuation primitives, without addressing this, are a good idea!

The paper uses a 'cps' annotation for convertible functions and only allows an annotated funtion to be called from other ones; I've mostly observed this choice to be made for safe or guided compilation, but it is also a potential stab at the problem.

**Control passing can be baked in without requiring convention: e.g., in some parallel or otherwise resource-oriented programming models, execution units are reified in some way that is explicitly sharable.

(This post mainly aims to give you a reason why someone would want to do something like this.)

I've been thinking about something similar: compiling to C with cps, implemented in C, using manual cactus stacks, a trampoline, cooperative lightweight green threads, and optional integration with a dynamic language implemented on top (something like interpreted Lisp and/or Smalltalk).

If you write something like networking code, and want to process many thousands of flows in the same user address space, you avoid native threads and implement some ad hoc event scheme or async callback system to represent thousands of independently multiplexed activities efficiently. And when you roll it all by hand, it gets really complicated.

For example, it's conceptually easy to implement pipes once you have an okay async infrastructure. But if you rolled everything by hand, code for pipes can look very complex, in the sense it takes a long time to reason about just a few things that seem simple in concept. Basically, you end up with operating system responsibilities when normally you can ignore this in a synchronous language.

It's very hard to test async components intended to plug into other complex async environments. To write a good (read: meaningful) standalone unit test of an async library with non-trivial semantics, you might need to write a simulation of the expected execution environment, which costs much more than your library. In fact, a good test for sophisticated async modules might always cost more than writing the module, in general.

So there's a strong motivation to go with some systematic scheme, just to control costs. Ideally, instead of hand-rolling gnarly async C, you might instead write a description in a higher level language which compiles to the same gnarly async C you would have written by hand, but without nearly as many dumb errors. And then you could write a high level description of the simulated external environment to drive the module under tests. You'd compile that to C as well.

The idea of compiling to C everywhere is largely driven by a need to permit dev peers to review code at the same level they would have written by hand without any system. It's to maximize challenges to code which criticize whether it works as expected. You want aggressive desk checking by folks who only want to read C. And you want aggressive unit testing that actually causes every block to be reached via condition injection (which is more general than error injection).

If you do it right, you can emit async C modules with no dependencies (depending only on themselves). But you can implement a larger execution environment, that might have a dynamic language, used for unit testing at first, then more after you figure out, by experimenting, that it's a nice setup.

Among other things, the larger environment can present a web server view of module runtime and stats. (The same way you write tests because you doubt production code, you also doubt tests themselves, so you need to inspect what happens under test in detail.)

That would be cheaper than trampolining, because the return cost is only paid once for every stackful of CPSed calls rather than for every call. Of course, longjmp() is less efficient than return, but if the effective stack is big enough (Chicken uses a 64K stack by default, even though the C stack is much larger), that difference is readily overcome.

We did not try Cheney on the MTA, mostly because:
- we want to keep things straightforward to understand and debug them easily (and longjmp is definitely not straightforward),
- we want to compile to something looking like event-driven programming,
- trampolining is not too inefficient so we can live with it,
- life is too short too implement every possible optimization ;-)

But you are right that this would be an interesting trick to consider (although I have learned the hard way that some "optimizations" sometimes do not perform as well as expected and shall therefore always be benchmarked).

The paper does not address it at all. Is the code transformation still safe in the presence of longjmp? Is a cps function allowed to use setjmp?