archives

Pure Pattern Calculus

Came across the Pure Pattern Calculus a little while ago, and it seemed to provide a simple, yet promising synthesis of many diverse language patterns. I haven't seen it discussed here, so perhaps it will be of interest:

Abstract. The pure pattern calculus generalises the pure lambda-calculus by basing computation on pattern-matching instead of beta-reduction. The simplicity and power of the calculus derive from allowing any term to be a pattern. As well as supporting a uniform approach to functions, it supports a uniform approach to data structures which underpins two new forms of polymorphism. Path polymorphism supports searches or queries along all paths through an arbitrary data structure. Pattern polymorphism supports the dynamic creation and evaluation of patterns, so that queries can be customised in reaction to new information about the structures to be encountered. In combination, these features provide a natural account of tasks such as programming with XML paths.
As the variables used in matching can now be eliminated by reduction it is necessary to separate them from the binding variables used to control scope. Then standard techniques suffice to ensure that reduction progresses and to establish confluence of reduction.

Bondi is their experimental programming language based on the pure pattern calculus.

Early retirement?

Are all the editors on vacation, or is this a case of mass early retirement?

It has been awhile since we had a decent curry-howard story, but at this point I am sure any good link you have lying around is going to be appreciated.

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.