Thursday, September 6, 2012

Mixing first-order and higher-order control

It's desirable for a language to support exceptions (preferably restartable ones), unwind protectiondynamic binding, and delimited continuations. [Adding Delimited and Composable Control to a Production Programming Environment, Delimited Dynamic Binding]

I've found a tractable way to implement these features in the language I'm currently working on, Wat.

My approach is to totally separate first-order control from higher-order control.

There is a set of Common Lisp-like first-order forms:
These forms are implemented natively using JS try/catch and finally.

Restartable exceptions are implemented in terms of these first-order forms and dynamically-bound variables, which are also provided natively.

In addition there's a completely separate set of higher-order control forms from A Monadic Framework for Delimited Continuations.

Delimited continuations are implemented using a technique similar to Exceptional Continuations: ordinary code paths run on the normal JS stack; when a continuation is captured, the stack is unwound frame by frame up to the prompt, and at each frame, a resumption is added to the continuation that is built up during the unwinding. This technique is ten times faster than a naive scheme with heap-allocated stack frames, but currently doesn't support TCO.

First-order control is used for quotidian control flow, whereas higher-order control is used for heavy control flow lifting, such as making a REPL written in direct style work in the browser's asynchronous environment.

This is a quite intuitive model: in the small, one has the usual Common Lisp control flow, including restartable exceptions, whereas in the large, behind the scenes, control flow may be arbitrarily abstracted and composed with the higher-order control forms.


Florian Loitsch said...

Perfect timing...
This Sunday, at the Scheme workshop (, Marc Feeley and Eric Thivierge will present their implementation of continuations (in their Scheme-to-JavaScript compiler). (Btw: I'm going to be there).
As part of the research for their paper they contacted me and I have therefore looked again at the exceptional continuations just recently. I had the suspicion that exceptions would destroy the performance (due to V8 not optimizing functions that contain try/catch) and therefore changed scheme2js slightly to avoid exceptions. The speedup was huge (up to *5). So try to avoid exceptions in your implementation.

Manuel Simoni said...

Thanks for the pointer!