The Kernel Programming Language

This page is Copyright John N. Shutt 2004–2010.  Here's what you're allowed to do with it.
Last modified: 07-Feb-10.

I'm developing a programming language called Kernel.  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, under the traditional 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 — and, more insidiously, because at that time the mainstream Lisps were dynamically scoped (a language feature that causes more problems for fexprs than it does for the less powerful macros).

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.

• The primitive constructor of operatives is an operative called $vau, which is almost the same as Scheme's lambda in both syntax and semantics, except that the combiners it constructs are operative.

• The primitive constructor of applicatives, i.e., combiners whose operands are evaluated, is an applicative called wrap.  wrap takes one argument, which must be a combiner, and constructs an applicative that passes its arguments (the results of evaluating its operands) to the specified combiner.

• The underlying combiner of any applicative can be extracted using applicative unwrap.

• There is also an operative constructor of applicatives called $lambda, that is almost exactly like Scheme's lambda — but Kernel's $lambda isn't primitive:  It can be implemented as a compound operative, using $vau and wrap.

First-class operatives aren't all there is to Kernel, just the most immediately obvious difference from most Lisps.  The mandate of the Kernel language is to have a clean design, flowing from a broad design philosophy as refined by a series of more specific design guidelines — just one of which is that all manipulable entities should be first-class.  Some other neat (IMHO) features of Kernel are

• uniform compound definiends.  (Eliminates the motive for multiple-value returns.)
• continuation guarding.  (Exception-handling "done right".)
• keyed dynamic variables.  (Fluid variables "done right".)
• encapsulation types.  (Enforced abstraction meets latent typing. Inspired by Morris's seals. Gives Kernel's implementation of promises a fundamentally different flavor than those of SRFI-45.)
• uniform handling of cyclic lists. (Without this, cyclic lists wouldn't be entirely first-class, since they couldn't be used in ways one ordinarily expects of objects, such as testing via equal?.)

On the theoretical side, take a look at Appendix C of the Kernel Report ("De-trivializing the theory of fexprs").  I gave a talk at NEPLS in fall 2007 that covered similar material in a little more depth (abstract ; slides (PDF, not meant to be printed)).  Those only describe pure vau-calculi, i.e., without side-effects; my doctoral dissertation, which I'm writing now (titled Fexprs as the basis of Lisp function application; or, $vau: the ultimate abstraction), also describes impure vau-calculi. 

There's a pseudo-prototype implementation, called SINK ("Scheme-based Interpreter for Not-quite Kernel"), meant to be mostly compatible with unextended R5R Scheme; it doesn't recognize some Kernel tokens, it's slow as molasses... it runs, which is more than I can say for the Java-based interpreter that I still haven't found time to finish.  I use SINK to debug library implementations for the Kernel Report, and to play around with guarded continuations.  For whatever it's worth, here it is as a gzipped tarball: sink-01m10.tar.gz.