Lambda Calculus
We are using the lambda calculus (in both its abstract mathematical sense and its practical usage in the Scheme programming language) in my Programming Language Theory course to study the design and implementation of algorithms and data structures.
Our latest assignment demonstrated the power and limitations of the pure mathematical λ-calculus by writing expressions for basic logic, arithmetic, repetition, and recursion. Dr. Schreiner provided an interpreter written in Java recognizing a mini-language that matches the “pure” λ-calculus. This lets you actually test lambda expressions and see the result without doing all the substitutions and reductions by hand. This is important, since just asking for 3 × 3 results in six full lines of text after six levels of transformation — before compressing through 36 transformations into a simple representation of the number 9.
Since the only things you have to work with are abstract symbols and the one-pararmeter lambda expression (analogous to a function), the λ-calculus has no native representation of arithmetic or even numbers themselves. You have to somehow create representations of numbers, and implement counting and arithmetic, using lambda expressions.
The fun really begins when you learn why λ m. λ n. λ f. m (n f) achieves multiplication (see the Wikipedia article) and you derive that expression on your own. It is intriguing how Church numerals and a few more expressions allow you to use the lambda calculus to express any natural number for which there exists a finite arithmetic expresssion.