Decomposing lambda - the Kernel language

The Kernel Programming Language, by John N. Shutt:

Kernel is a conservative, Scheme-like dialect of Lisp in which everything is a first-class object.

"But," you may ask, "aren't all objects first-class in Scheme?" (I'm glad you asked.) No, they aren't. Special-form combiners are second-class objects. To borrow a phrase from the original description of first- and second-class objects by Christopher Strachey, they have to appear in person under their own names. (There are also several other kinds of second-class objects in Scheme, but special-form combiners are the most commonplace.)

The idea of first-class operative combiners, i.e., first-class combiners whose operands are never evaluated, has been around a long time. Such creatures were supported by mainstream Lisps through the 1970s, notably under the name FEXPRs, but they made a mess out of the language semantics because they were non-orthogonal to the ordinary variety of procedures constructed via lambda.

Kernel eliminates the non-orthogonality problem by breaking the classical lambda constructor into two orthogonal parts, one of which is the Kernel constructor for first-class operatives.

Via Shriram Krishnamurthi on c.l.scheme. The story title is from an older paper on Kernel.

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.


This sounds very close to how Steve Dekorte's io programming language works. At the lowest level, io passes all arguments as unevaluated message trees (io's equivalent of s-expressions). Combinators (such as 'method') are then built which provide applicative semantics by evaluating the message trees before passing them on.

Edit: As far as I know io doesn't provide anything like Kernel's unwrap combinator but it could be provided without changes to the core language. Instead of having the applicative combinators pass on the evaluated message trees unaltered they would create a perfect proxy for each evaluated message tree, augmenting this proxy with an 'unwrap' message handler which returns the original unevaluated message tree.

prototype version?

Has a prototype ever been available?

The link says "The finished product should materialize in the fall semester of 2006", but the "older post" references was in 2003.


The author's page on the project says that "There's a pseudo-prototype implementation...". I didn't try it out, and I would expect some dedicated effort to be required to use it, given the comments by the author.

There's lots more stuff

There's lots more stuff available, now. Take a look at this, and more generally other cool stuff going on at the Axis of Eval.