A Lambda Calculus Reducer

Sunday, February 24, 2008

About a month ago I decided to buy some time from society by doing a trial run of graduate studies - I took some Computer Science courses at Stony Brook University. The first homework for the Programming Languages course was to write a lambda calculus reducer - a task I happily jumped on. A few hours later I had it implemented in 105 lines of Haskell code (for short tasks like these I find that Haskell is a better tool than Common Lisp).

The reducer expects a lambda expression. It echos back the way the expression was parsed, and then proceeds to print reductions until it finds a normal form. Here is a trace of an argument applied to an identity function:

runhaskell reducer.hs
> (\d.d)a
((\d.d) a)

Writing a short tool like this is an excellent way to get a reasonably good understanding of lambda calculus, functions as first class objects, purity, and laziness. For example, a snippet below provides a great illustration for partial evaluation:

> (\a.\b.c a b)i
((\a.(\b.((c a) b))) i)
(\b.((c i) b))

Normally when I learn a new programming language I write a Lisp interpreter in it - it's a reasonably small, self contained task that doesn't take too much time, yet it is complex enough to afford a reasonably good understanding of the new language by the time you're done. I think for quick introductions I'll replace Lisp interpreters with lambda calculus reducers (of course one could argue they're two sides of the same coin) - they're slightly less time consuming and contain enough complexity to give a good overview of a programming language in question.


If you have any questions, comments, or suggestions, please drop a note at coffeemug@gmail.com. I'll be glad to hear your feedback.