Lambda Calculator

The calculator is a simple read-eval-print loop. Users type in lambda-terms, and the calculator manipulates them in several ways. It perform single-step beta-reduction, or multi-step beta-reduction. Users can name terms, and the calculator doesn't expand named terms unless they are necessary to take a step. In class we wrote a wide variety of terms: zero, one, two (Church encodings), add, mult, the Y combinator, pair, fst, snd, if, true, false, succ, pred, ifZero, and two version of factorial.

Here is a partial transcript of executing the addition of 2+2.

prompt> add #2 #2
add #2 #2

(\ x . \ y . \ z . \ s . x (y z s) s) #2 #2

(\ y . \ z . \ s . #2 (y z s) s) #2

\ z . \ s . #2 (#2 z s) s

\ z . \ s . (\ z0 . \ s0 . s0 (s0 z0)) (#2 z s) s

\ z . \ s . (\ s0 . s0 (s0 (#2 z s))) s

\ z . \ s . s (s (#2 z s))

\ z . \ s . s (s (s (s z)))

Note how the named terms, 'add', and '#2' are not expanded to their lambda terms unless they are needed to take the next step in the computation. This really helps when tracing large computations.

To download the Calculator, get the zipped file Unzip the file to get a directory. In the directory is the source and a small powerpoint lecture describing the power of the Lambda Calculus.

Running the Lambda Calculator. The Lambda Calculator is a Haskell Program. Compile it and run the 'main' function.

Have fun!

This page has been translated into Swedish.