Lambda the Ultimate

This is just to note that I recently updated Parametric Higher-Order Abstract Syntax for Mechanized Semantics to reflect the fact that a draft of the paper is available, for those who might be interested.

Revisiting Coroutines, by Ana Lucia de Moura and Roberto Ierusalimschy:

This paper defends the revival of coroutines as a general control abstraction. After proposing a new classification of coroutines, we introduce the concept of full asymmetric coroutines and provide a precise definition for it through an operational semantics. We then demonstrate that full coroutines have an expressive power equivalent to one-shot continuations and oneshot partial continuations. We also show that full asymmetric coroutines and one-shot partial continuations have many similarities, and therefore present comparable benefits. Nevertheless, coroutines are easier implemented and understood, specially in the realm of procedural languages. Finally, we provide a collection of programming examples that illustrate the use of full asymmetric coroutines to support direct and concise implementations of several useful control behaviors, including cooperative multitasking.

Coroutines seem to get fairly short riff in the literature, and they have only been discussed on LTU, a couple of times. Given coroutines have such a straightforward mapping to hardware, I hope they get more attention.

Coroutines show up in many different places. For instance, the inter-process communication (IPC) facilities of microkernels, like EROS, are a faithful implementation of asymmetric coroutines, with an important difference. Essentially, yield and resume must both take an explicit coroutine argument naming the coroutine respectively yield to and resume. If the coroutine to yield to is left implicit, as it is in most treatments I've seen, then coroutines become less composable since yield returns control to the innermost resume which, given abstract types, might be the wrong one.

This problem is discussed in Section 5.6, "Avoiding Interference Between Control Actions". The paper recommends tagging coroutines to match up resume/yield pairs, but the EROS IPC system provides a more direct encoding via a "resume" capability, which is a single-use coroutine used to return control directly to a client. Each subsequent invocation of the object synthesizes a new resume capability.

Taking this to the extreme implies that yield and resume can be unified into a single "invoke" operation which accepts a coroutine argument to be used in a subsequent invoke operation. Indeed, these are "symmetric coroutines". This paper suggests that symmetric coroutines are harder to understand due to the actors/CPS-like nature of the control flow.

Here's an announcement I'm sending out. Hopefully this will be of interest to a few SoCal LtUers.

Announcing the creation of Southern California Functional Programmers (SoCalFP), a group for people in Los Angeles, Orange County, and San Diego to meet in person and/or virtually to discuss, debate, present, and learn about functional programming concepts and techniques in various languages.

You might ask, "why a functional programming group in Southern California?"

Well, SoCal, wake up and smell the lambda. There's increasing interest in bastions of functional programming like Haskell and various Lisps; popular mainstream languages like Ruby and Python have lambda (or lambda like) capabilities; hybrid OO/functional languages like F# and Scala are generating buzz; C# 3.0 has embraced core functional ideas like closures and monads; and even staid, conservative Java may get some functional goodness in the next version. Perhaps most importantly, programmers can't ignore the oncoming multi-core freight train and Erlang has shown that concurrency and functional programming go together like peanut butter and chocolate.

If you're intrigued come visit our main site and join our mailing list.