Wednesday, April 10, 2013

The Lambda Calculus: A Quick Primer

The λ-Calculus Series
  1. A Brief History
  2. A Quick Primer for λ-Calculus
  3. Reduction Explained
  4. Church Numerals
  5. Arithmetic
  6. Logic
  7. Pairs and Lists
  8. Combinators
To the untrained eye, the notation used in λ-calculus can be a bit confusing. And by "untrained", I mean your average programmer. This is a travesty: reading the notation of λ-calculus should be as easy to do as recognizing that the following phrase demonstrates variable assignation:
x = 123
So how do we arrive at a state of familiarity and clarity from a starting state of confusion? Let's dive in with some examples, and take it step at a time :-) Once we've got our heads wrapped around Alonzo Church's notation, we'll be able to easily read it -- and thus convert it into code! (We will have lots of practice in the coming posts to do just that.)

A Quick Primer for λ-Calculus

Here's one of the simplest definitions in λ-calculus that you're going to see: the identity function:
This reads as "Here is a function that takes x as an argument and returns x." Let's do some more:
"Here is a function that takes x and y as arguments and returns only x."
"An outer function takes x as an argument and an inner function takes y as an argument, returning the x and the y." Note that this is exactly equivalent to the following (by convention):
Let's up the ante with a function application:
λf.λx.f x
"Here is a function that takes a function f as its argument; the inner function takes x as its argument; return the result of the function f when given the argument x." For example, if we pass a function f which returns its input multiplied by 2, and we supplied a value for x as 6, then we would see an output of 12.

Let's take that a little further:
λf.λx.f (f (f x))
"Here is a function that takes a function f as its argument; the inner function takes x as its argument. Apply the function f to the argument x; take that result and apply f to it. Then do it a third time, returning that result." If we had the same function as the example above and passed the same value, our result this time would be 48 (i.e., 6 * 2 * 2 * 2).

That's most of what you need to read λ-calculus expressions. Next we'll take a peek into the murky waters of  λ-calculus reduction and find that it's quite drinkable, that we were just being fooled by the shadows.

No comments: