A Lambda Calculus Reducer
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) 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.
Comments?
If you have any questions, comments, or suggestions, please drop a note at . I'll be glad to hear your feedback.