At a small gathering of WPI alums in the summer of 2004, Brad Kidwell handed me a Zilog Z8 Encore! microcontroller evaluation board and development kit. He had gotten it as an unsolicited sample in the mail from Mouser Electronics, and thought it might make a good platform for project work for someone with too much time on their hands.
The board turned out to be a 20MHz 8-bit Z8F640x Encore! microcontroller, 4kB of register RAM, 64kB of flash RAM, some serial ports, and a small LED display. More importantly, it also turned out to be a tremendously fun toy to hack on.
For my first project, I decided to make the LED's print out a "thank you" message to Brad for giving me the kit. It scrolls the phrase "2 4 6 8 WHO DO WE APPRECIATE BRAD BRAD BRAD" across the LED display in a visually appealing fashion.
Nearly a year later, I decided that what the board really needed was a Lambda Calculus reducer. After all, the Encore board was comparable in power to my first general-purpose microcomputer---what could be more appropriate than to give it an interpreter for what might be considered the most general programming language? A picture of the EZ8 Encore board using a vintage Digital Equipment Corportation VT520 serial terminal for console input/output is shown at right. At the moment the picture was taken, the board had just completed calculating the answer to the equation 1 + 1 = 2 using Church numerals in the Lambda Calculus. Click on the image to obtain a higher-resolution picture of the screen where the output is readable.
The Lambda Calculus was described by Alonzo Church in a seminal 1941 report as a formal tool for the study of the general properties of functions. Like the notion of a Turing Machine, the Lambda Calculus can be used to reason about what functions are efficiently computable. It's also a useful tool for reasoning about type systems in programming languages. Programming languages like LISP and O'Caml are closely based on the Lambda Calculus. There are many Lambda Calculus tutorials on the web; here is a short summary that is sufficient to make the pictured output understandable:
The syntax of the Lambda Calculus is very simple: it has variables like x and functions like (\x.x). This function, for example, takes one argument x and returns the value of that argument---it's the identity function. In Church's original syntax, the \ would be a lambda. The period is a little syntactic sugar to make the function more readable by visually separating parameters from body. The Lambda Calculus also includes applications of functions. For example, ((\x.x) A) applies the above identity function to the argument A. Reducing expressions, at least in the simplest cases, amounts to syntactically substituting arguments for formal parameters in function bodies, like so:
((\x.x) A) -> A \>
To reduce, we match the argument A with the formal parameter x, and then replace all occurrences of x in the body with A. The -> symbol indicates one step of reduction, the \> symbol indicates no further reduction is possible.
In it's most basic form, there are no numbers or strings in the Lambda Calculus---only functions. However, you can invent conventions on how to encode numbers as functions. One such convention called "Church numerals" encodes numbers as follows:
0 = (\s.(\z.z)) 1 = (\s.(\z.(s z))) 2 = (\s.(\z.(s (s z))))
Every number is represented by a distinct function of two arguments: s and z. The number of applications of s encodes the numeric value: zero for 0, one for 1, two for 2 and so on. Using this convention, you encode the operation M + N as follows:
(\M.(\N.(\s.(\z.(M (s (N (s z))))))))
So when asked to calculate 1 + 1 = 2, the Z8 Encore board produces the following output:
Enter formula: (( (\M.(\N.(\s.(\z.((M s) ((N s) z)))))) (\s.(\z.(s z)))) (\s.(\z.(s z)))) ;; -> ((\N.(\s.(\z.(((\s.(\z.(sz)))s)((Ns)z)))))(\s.(\z.(sz)))) -> (\s.(\z.(((\s.(\z.(sz)))s)(((\s.(\z.(sz)))s)z)))) -> (\s.(\z.(((\s.(\z.(sz)))s)((\z.(sz))z)))) -> (\s.(\z.(((\s.(\z.(sz)))s)(sz)))) -> (\s.(\z.((\z.(sz))(sz)))) -> (\s.(\z.(s(sz)))) /> Nodes used (out of 256): 00040 Variables used: MNsz
Tim Fraser's homepage at the WPI alumni site
$Id: z8encore.html,v 1.3 2005/07/04 23:38:20 tim Exp $