11 Apr 2013 oubiwann   » (Journeyer)

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.

Syndicated 2013-04-11 04:39:00 (Updated 2013-04-11 15:55:46) from Duncan McGreggor

Latest blog entries     Older blog entries

New Advogato Features

New HTML Parser: The long-awaited libxml2 based HTML parser code is live. It needs further work but already handles most markup better than the original parser.

Keep up with the latest Advogato features by reading the Advogato status blog.

If you're a C programmer with some spare time, take a look at the mod_virgule project page and help us with one of the tasks on the ToDo list!