Lambda Calculus
Volume Number: 7
Issue Number: 5
Column Tag: Lisp Listener
By André van Meulebrouck, Chatsworth, CA
“A Calculus for the Algebraic-like Manipulation of Computer Code”, or “Why Oh
Why Oh Y?”
“People who like this sort of thing will find that this is the sort of thing they
like.” Abe Lincoln
[André van Meulebrouck is a consultant who makes his base camp in Southern
California. When not cloistered in front of a keyboard, you’ll most likely find him
donning a Zippy T-shirt in the great out-of-doors, or pursuing various athletic
endeavors. (And listening to Pat Metheny music, no doubt.)]
Note to the Überprogrammer and disclaimer: I will be endeavoring to write so
simply that everyone should be able to get something out of this article. Such
tutorialness should not be taken as an insult to anyone’s intelligence.
Wouldn’t it be nice to be able to manipulate computer code in the same sort of
clean mathematical way that one does algebra? Usually computer code is too ad hoc to
allow much of that, but what if we had a super clean model that we could work with?
Even if such a model wasn’t practical, it would certainly still be interesting, and what
could be found out from it might be mappable back into computer languages which don’t
have as neat a set of “algebraic-like” properties.
Most people have heard of the Turing machine, as it’s now tantamount to being
the measuring stick by which computability is judged. If something is computable on a
Turing machine, it is considered computable; if something isn’t computable on a Turing
machine it’s considered uncomputable.
There is however, another model, equally as powerful, that is quite different. It
has no concept of Turing machine style “state”, and it has some very nice
algebraic-like properties. It’s called the l-calculus.
This article will introduce l-calculus and combinators, and show some
similarity between l-calculus and the programming language LISP. An attempt will
then be made to use l-calculus as a programming language in its own right to code a
popular function in an effort to show the clean, algebraic-like properties of l-calculus
and to consider (in a small way) if l-calculus might serve as a “light unto the
footsteps” to guide the way to computing without gratuitous complexity.
Intro to l-calculus
l-calculus is a calculus which expresses “computation” via anonymous
functions. l-calculus preceded LISP and LISP drew from it to some extent. l is the
anonymous function in l-calculus, and lambda is the anonymous function in LISP.
LISP 101
What follows will be a crash course in LISP. (This will be just enough to “make
you dangerous”.)
Let’s start with a some arbitrary function and convert it from how you’d see it
in a math book or C program to how it would look in LISP. Let’s pick the sine function
as it would look if applied to the numerical argument 3: sin(3). Let’s tuck sin into the
list of arguments and use spaces instead of commas if there is more than one argument:
(sin 3). This form of prefix notation is the chosen syntax of LISP. Let’s stick to this
syntax for everything, lest the syntax get so unwieldy that parsing become a science in
and of itself. So, 2 + 2 will be (+ 2 2). Note that with this style of syntax, it is easy
to represent + with an arbitrary numbers of arguments: (+ 1 2 3 4 5).
Further, let’s say that every top level position of a list gets one round of
evaluation. Specifically, the function position gets evaluated, then each argument
position gets evaluated, then, the evaluated function gets applied to the evaluated
arguments. The “one round of evaluation” can be used to invoke a function call from
any position:
>>>
(+ (+ 2 3)
(+ 3 5))
13
or even
>>>
(+ (+ (+ 1 2)
(* 3 4))
(* 5 2))
25
because a list in any position can have a function position and argument positions of its
own, and so on, to arbitrary depth.
Note: In the Scheme dialect of LISP, the function position is treated precisely the
same as the argument positions. Let me motivate an example of that by first showing
the if function (which in LISP is a true function). if has the form:
(if ). If is true, is evaluated and returned,
otherwise is evaluated and returned. zero? is a function (called a predicate) that
is used to determine whether a number is 0 or not. Consider this example:
>>> ((if (zero? 0) + -) 3 4)
7
The next thing we need is a way to abstract out common process patterns into
descriptions. This is done via lambda, the anonymous function. For instance,
(lambda (x) (+ x 1)) is a function that takes in an evaluated argument, binds it with
x, and then computes the body of the lambda form with the understanding that any
occurrence of parameter x in the body will refer to the value of x bound by the lambda
form. In this case, the returned result will be the argument plus one, and the
argument will not be side effected. To invoke an anonymous function, we simply invoke
it like any other function. We invoked sine like this: (sin 3). Invoking
(lambda (x) (+ x 1)) on the argument 3 would look like this:
>>> ((lambda (x) (+ x 1)) 3)
4
To define something we do this: (define foo 3). Thereafter, typing foo at the
MacScheme prompt, we find it evaluates to 3.
>>> (define foo 3)
foo
>>> foo
3
Here’s an example of naming an anonymous function:
>>>
(define plus-one
(lambda (x)
(+ x 1)))
plus-one
>>> (plus-one 3)
4
Currying
l-calculus is very economical. It has only a few syntactic constructs yet it can
still express everything that is computable [Peyton Jones, 1987]. Anything it lacks
can be bootstrapped.