Lambda the Ultimate

SF-calculus builds combinators from two operators S and F that are more expressive than the usual S and K. The reduction rules are

SMNX = MX(NX)
FOMN = M if O is S or F
F(PQ)MN = NPQ if PQ is factorable

where the factorable forms are the partially applied operators, i.e. of the form S, SM, SMN, F, FM and FMN. The operators are the atoms while the factorable forms that are applications are compounds.
The calculus is confluent since atoms and compounds are stable under reduction. The ability to factorise can be used to define static pattern matching, in the sense of pattern calculus . In particular, the calculus supports a generic structural equality of arbitrary normal forms.

The factorisation combinator cannot be represented within SK-calculus, so that SF-calculus is, in this sense, more expressive than SK-calculus or pure lambda calculus. To fully appreciate this surprising, if not controversial, claim, requires a careful definition of representation.

This, and full proofs, are in our paper A combinatorial Account of Internal Structure .

Yours,
Barry Jay
Thomas Given-Wilson

The introduction of Helios (Eclipse 3.6) included the release of version 1.0 of Xtext - Language Development Framework.

With Xtext you can easily create your own programming languages and domain-specific languages (DSLs). The framework supports the development of language infrastructures including compilers and interpreters as well as full blown Eclipse-based IDE integration.

Given a grammar, Xtext derives a parser and an IDE with syntax highlighting, code completion, code folding, outline view, real-time error reporting, quick fixes among other standard IDE features. The models then can be used as an EMF Resource(ie as an interpreter) or with a little more work they can be used to generate code as well.

Check out the video clips on their website or the Webinar for a more detailed look.