Language Design

The Lambda Calculus

Church’s λ-calculus and Turing’s machine are the two roots of programming as we know it. The grandchildren of the Turing-machine are imperative languages, while their cousins under the λ-calculus are declarative (mainly functional) languages.

The λ-calculus is basically the smallest possible functional programming language. An expression in the calculus is one of three things:

• Variables: If x is a variable, x is an expression.
• Abstractions: If x is a variable and M is an expression, then (λx.M) is an expression.
• Applications: If M and N are expressions, then (M N) is an expression.

The entirety of the syntax consists of variable names, λ and . for abstractions, and ( and ) for applications. See the Wikipedia article for more.

Zen and the Art of List Processing

Code is data.

When a compiler works its magic, it first turns the source code of a program into a data structure called an abstract syntax tree (AST). (This is an involved process, so some steps are elided, but bear with me.)

The compiler might represent 1 + 2 in the AST as the node + with children 1 and 2. It might represent print "Hello, world." as the node print with the child "Hello, world.". Once it has this data structure constructed, it can decorate it (perhaps with types), rearrange it (perhaps for optimization), and turn it into different forms, eventually the compiled program.

Extending a compiler to do something new with an AST is normally an involved process. GCC (for example) is gigantic, while powerful, and you’ll need to learn quite a bit to modify it in any useful way.

What would be useful is to have the compiler provide an interface to the programmer so they could modify the compiler in their own program. This way, you could extend the compiler to recognize new syntax, or optimize code with new data types. This interface would have to use the language’s basic data types, so it could be available without a library. Lisp takes this to the logical conclusion.

Lisp is the λ-calculus with hooks into the compiler.

From the reader (which turns code into data) to the evaluator (which executes data as a program), all is available to the Lisp programmer. Code can write code purely by constructing data types before the evaluator acts on them. The reader is available for the programmer to extend. This is the Lisp nature.

For this sort of power, it makes sense to write code that looks like the AST. If the tree with + at the root and 1 and 2 as the children is what you want, write (+ 1 2). If you want to create a tree with print at the root and "Hello world." as its child, write (print "Hello, world."). Perhaps an if-statement has three children; the predicate, the true-clause, and the false-clause. You could write this as (if predicate true-clause false-clause).

Will it Blend?

If we were to create an abstract syntax tree from the λ-calculus, how would we construct it?

• Variables: If x is a variable, x is an expression.
• Abstractions: If x is a variable and M is an expression, then (λ x M) is an expression.
• Applications: If M and N are expressions, then (M N) is an expression.

Well, that was simple. Oh, but this means that (+ 1 2) doesn’t work, because abstractions can only handle one argument and applications match. We’ll make a minor adjustment:

• Abstractions: If x* represents zero or more variables and M is an expression, then (λ (x*) M) is an expression.
• Applications: If x* represents zero or more arguments and M is an expression, then (M x*) is an expression.

Also, we should probably extend the reader a little so it reads lambda as λ for people who can’t easily type in Greek. There we go, and code is data.

Well, I guess not quite.

Semantics

If code is data, we need a way of storing these things in the language itself. When the reader reads (M x y z), what does it store? It looks like we have two data types:

• Symbols: Bare words like M, x, or +.
• Trees: Groups of other types, like (M x y z) or (λ (x y) M).

For convenience, we’ll add one more type: Numbers. The λ-calculus can simulate numbers just fine, using Church encoding, but it’s somewhat difficult to read and slow to compute with, so we’ll just use Arabic numerals.

What about the evaluator? When it sees (λ (x y) M), what should it produce? We need another type, the λ. Then when the evaluator sees ((λ (x y) M) 1 2), it can evaluate the root node, producing a λ, then evaluate 1, producing 1, then evaluate 2, producing 2, and then apply the λ to the two arguments.

Also, if we’re going to make this accessible to the programmer, we should probably give these actors names. The reader can be read, the evaluator eval, and the actor that applies λs to arguments can be apply. Oh, and we need something that can write data back out – write.