Lambda Calculus Cheat Sheet

Click here to download in PDF format

The Pattern of Recursion and Fixed Point Combinators

Recursion is an interesting, and important computation tool that enables us to formulate patterns of self-similarity and express infinity, using a finite set of elements. There is a strong relation between recursion and the principle of induction in mathematics. Imperative programming languages usually allow recursion in a program to take place by letting us define a function that calls itself. Here is a simple recursive function in C++:

#include <iostream.h>

void count(int n)
{
    std::cout << "Counting: " << n << "\n";
    if (n < 5) {
        count(n+1);
    }
}

int main(int argc, char **argv)
{
    count(1);
    return 0;
}

Run this example from codepad:
http://codepad.org/YmxQcTIX

In functional programming, recursion has a much more central position. Purely functional languages do not define any looping constructs, but instead rely entirely on recursion to achieve iterative algorithms. Many data types are defined recursively. In Haskell, recursion even allows us to define (conceptually) infinite data structures:

n = 5 : n
take 3 n                -- [5, 5, 5]

Codepad: http://codepad.org/sRbFkSH5

Here, we take the first three elements from an infinite list of fives. The list n is defined as a single element, 5, followed by a list – itself.

n is a 5, followed by n, which is a 5 followed by n, which is a 5 followed …

Lambdas in C++0x, Part I

The new C++0x standard adds support for anonymous functions; so called lambda expressions. The concept of anonymous, or locally defined functions plays a central role in functional programming and has its origin in the Lambda Calculus (λ-Calculus); a theory formulated by Alonzo Church in 1936 (yes, that was before FORTRAN). The basic idea here is to treat functions as first class objects – functions can be stored in variables, passed as arguments, and be used as return values etc.

Lambda expressions are similar to functors (function objects), but with the added advantage of now being an integral part of the language. We can think of them as syntactic sugar for a functor. Just like function objects, lambdas are type-safe and can maintain state.

Using lambda expressions

The lambda term λx.3 represents the anonymous function x → 3, i.e., a function which takes a single input, x and (always) returns 3.

Using the new C++0x lambda syntax, this can be expressed as:

[](int x) { return 3; }

…where the initial square brackets ( [ ] ) are called the lambda introducer and tells the compiler that a lambda expression follows. Since x is irrelevant here, we may simply omit the parameter specification in this case. This leaves us with a very basic function that returns the value 3:

[] { return 3; }