Lambda the Ultimate

While thinking about the expression problem and toying with (toy) language design, a simple solution to the problem came to mind. The expression problem is about extending datatypes and adding functions without recompiling the orignal code, so why not have a simple construct to extend each of these?

Every time you add a constructor to an algebraric datatype, you need to extend each of the functions on the type with a case covering the constructor. The two construcs are thus: 1) extend a datatype and 2) extend a function. Addition of completely new functions comes for free in a functional setting.

Here is some pseudo-code illustrating the idea:

# declare a new algebraric datatype Expr with one constructor
type Expr:
    case CONST(Int)

# declare a new function eval
function eval Expr -> Int:
    case CONST(x):
        x

# extend the algebraric datatype Expr with another constructor
extend type Expr:
    case ADD(Expr, Expr)

# extend the function eval with another case
extend function eval Expr -> Int:
    case ADD(x, y):
        eval(x) + eval(y)

# declare an additional operation on Expr
function toString Expr -> String:
    case CONST(x):
        intToString(x)
    case ADD(x, y):
        eval(x) ++ "+" ++ eval(y)

I realize that the implementation of extendable functions would need indirection (so no inlining), but other than that I don't see any problems with it.

My formal education in PL theory is very limited still, and I'd appreciate any comments that visualize weakness in the above constructs, or any references to languages that have similar constructs.

The paper about the Tom language accepted at RTA 07 is available on the net. Here is the abstract:

We present the Tom language that extends Java with the purpose of providing high level constructs inspired by the rewriting community. Tom furnishes a bridge between a general purpose language and higher level specifications that use rewriting. This approach was motivated by the promotion of rewriting techniques and their integration in large scale applications. Powerful matching capabilities along with a rich strategy language are among Tom's strong points, making it easy to use and competitive with other rule based languages.

Le me mention that Tom not only adds pattern-matching features to Java (or other target languages), but also proposes a strategic programming library which really brings rewriting to Java. The proposed pattern-matching algorithm is more powerful than the ones usually present in functional languages though, since it supports associative matching with neutral element and recently introduced antipatterns.
Finally, the compilation of Tom programs can generate coq proofs that the semantic of the pattern-matching algorithm is preserved.

It is actively used in both industrial and academic project, including the compiler itself, an implementation of the explicit rewriting calculus and a proof assistant for superdeduction modulo.