In this post, I’ll be discussing the untyped λ-calculus (lambda calculus). λ-calculus forms the basis of all functional programming languages and is one of the three theoretical models of computing, the other two being Turing Machines and Recursive Function Theory.

Alonso Church created λ-calculus in the 1930s as a formal system of mathematical logic for computation based on function abstraction and application. Church envisioned a simple language which contains only functions. λ-calculus doesn’t even have Boolean values or numbers. We’ll explore how to represent Boolean values using only functions below and we’ll cover representing numbers using only functions in a later post.

The most important distinction between imperative languages and functional languages is how they perform abstraction. In an imperative language, abstraction is performed by assigning names to variables which can change value over time. This is similar to how the parts of a Turing Machine can change over time; e.g. the tape of the machine can move. In functional programming languages, abstraction is performed by assigning names to values and functions which never change and computing new values by applying functions to values. In λ-calculus, functions are immutable values which we can name.

For example, here is the identity function:

λi.i

The function starts with the **λ** symbol, followed by a name, representing the **argument** of the function. A **period** separates the argument of the function from the **body** of the function. The body of the function can be any λ-calculus expression. Names in λ-calculus can be any string of characters except spaces, parentheses, **.** and **λ**.

For convenience, we can give names to our functions (technically this is an extension of the λ-calculus). Let’s define a few example functions so you can get used to the syntax:

identity = λi.i

self_application = λi.ii

apply = λx.(λy.xy)

Don’t worry too much about what these do just yet, you’ll probably be able to figure out what they do after you learn about β-reduction below.

Notice that the body of a function can also contain other functions. Functions are first class in λ-calculus, just like in any other functional programming language!

In the identity function above, **i** is used to form an abstraction. In the function, **i** can refer to anything until the function is specialized by application. For example, suppose we have a name, **G**, we could apply the **identity** function to the name **G** to specialize the function. We indicate that we want to apply the function by placing it in front of the argument **G** in parentheses:

(λi.i G)

In order to actually apply the value, we replace the instances of **i** in the function body with the argument, **G**. In this case, we get the result **G**:

=> G

The process we performed above is an **operation**. We use **=>** to indicate that an operation was performed on **(λi.i G)** to compute **G**. We could also write the steps above like this:

(λi.i G) => G

Operations advance an algorithm to its next step, eventually resulting in a solution. In imperative languages, there are many operations, each of which alter the value of variables or the program counter. In λ-calculus there are only four operations:

- λ-abstraction (lambda abstraction)
- β-reduction (beta reduction)
- α-conversion (alpha conversion)
- η-conversion (eta conversion)

It’s important to note that naming functions is not an operation. Function names are assigned statically, they can not be used inside their own function definition. They are simply an alias for the function and can’t be used for recursion.

# Operations in the λ-calculus

## λ-abstraction

λ-abstraction is simply the introduction of a lambda function. For example, we could create a new function using the λ-abstraction operation:

λx.xy

Also, notice that there are two names, **x** and **y**, in the body of the function but only **x** appears in the function argument. This is a valid λ-calculus expression.

We say that the name **x** is **bound** and the name **y** is **free**. A function which has no free variables is called a combinator and a function with at least one free variable is called a closure.

Sometimes the parentheses are excluded from nested functions like this:

apply = λx.λy.xy

In this case, you can always add parentheses by following the rule that lambda abstractions are right-associative.

## β-reduction

β-reduction is process of applying a function to a value, as we saw above:

(λi.ij G) => Gj

For convenience, the parentheses are often excluded. If they are not used, you can always add them by using the rule that function applications are left-associative.

## α-conversion

α-conversion allows us to rename an argument to avoid a name collision. To do this, we choose a different name for the argument and replace the old name with the new one wherever it exists in the function body:

λi.ij => λp.pj

For example, the two instances of **j** in this expression refer to different values, so we need to rename them using α-conversion before applying β-reduction:

(λi.iji λj.j) => (λi.iji λx.x) => (λx.x jλx.x) => jλx.x

## η-conversion

η-conversion is used when the argument of a function only appears as the last term of the function body. In this case, the function can be simplified to remove the argument:

λi.RWCi => RWC

# Applicative versus normal order reduction

Unlike in imperative languages, in λ-calculus, the order in which these operations are performed is undefined. For example when a function has an argument which contains an expression which could be simplified by β-reduction, we can choose which β-reduction to apply first. Consider the following expression:

(λi.ij (λx.xy G))

Here we apply β-reduction to the argument first. This is called **applicative order reduction**:

(λi.ij (λx.xy G)) => (λi.ij Gy) => Gyj

Here we apply β-reduction to the left-most function first. This is called **normal order reduction**:

(λi.ij (λx.xy G)) => (λx.xy G)j => Gyj

Church and Rosser showed that all evaluation orders of an expression in λ-calculus result in the same value.

This property of λ-calculus and functional programming languages in general is called **execution order independence**. Execution order independence enables the parallel execution of many lambda calculus expressions.

# Making decisions

In order to model general computation, we need a way to choose from two alternatives. In order to do this, we introduce the **select_first** and **select_second** functions:

select_first = λfirst.λsecond.first

select_second = λfirst.λsecond.second

**select_first** consumes one argument, and then a second, and discards the second argument:

select_first A B

=> ((λfirst.λsecond.first A) B

=> (λsecond.A B)

=> A

**select_second** chooses the second argument:

select_second A B

=> ((λfirst.λsecond.second A) B

=> (λsecond.second B)

=> B

Consider the structure of an if-then statement in an imperative language.

if condition then A else B

If the **condition** is true, then we want to evaluate the first expression, **A**, and if the condition is false, then we want to evaluate the second expression, **B**.

But **select_first** has the behavior of evaluating the first expression!

select_first A B => A

We can rename **select_first** to **true**:

true A B => A

This performs a behavior equivalent to:

if true then A else B

We can similarly use **select_second** to represent **false**:

false A B => B

This performs a behavior equivalent to:

if false then A else B

## Cond

Then the whole if-then statement can be expressed as a function **cond** that takes another function, **c**, which chooses either the expression **a** or the expression **b**:

cond = λa.λb.λc.((c a) b)

Let’s evaluate **cond** with **true** as an argument:

cond A B true

=> λa.λb.λc.((c a) b) A B λfirst.λsecond.first

=> λb.λc.((c A) b) B λfirst.λsecond.first

=> λc.((c A) B) λfirst.λsecond.first

=> ((λfirst.λsecond.first A) B)

=> (λsecond.A B)

=> A

It’s easy to see how passing **false **to **cond** will produce the desired behavior of evaluating to **B**.

## Not

**Not** can be expressed as:

if condition then false else true

So we can simply apply **false** and **true** to **cond** to get a definition for **not**:

not = λx.(((cond false) true) x)

Applying **not** to **true**, we get:

not true

=> λx.(((cond false) true) x) true

=> (((cond false) true) true)

=> λa.λb.λc.((c a) b) false true true

=> λb.λc.((c false) b) true true

=> λc.((c false) true) true

=> ((true false) true)

=> ((λfirst.λsecond.first false) true)

=> (λsecond.false true)

=> false

## And

**And** can be expressed as:

if A then B else false

If **A** is **true** then the expression is **true** if **B** is **true**, otherwise it’s **false**. If **A** is **false**, then it doesn’t matter what value **B** is, the expression is **false**.

and = λx.λy.((x y) false)

Applying **true** and **true** to this function we get:

and true true

=> ((λx.λy.((x y) false) true) true)

=> (λy.((true y) false) true)

=> ((true true) false)

=> ((λfirst.λsecond.first true) false)

=> (λsecond.true false)

=> true

## Or

Or can be expressed as:

if A then true else B

If **A** is **true** then it doesn’t matter what **B** is, the expression is **true**. If **A** is **false**, then the expression is **true** if **B** is **true**, otherwise it’s **false**.

or = λx.λy.(((cond true) y) x)

Let’s apply **false** and **true** to **or**:

or false true => ((λx.λy.(((cond true) y) x) false) true) => (λy.(((cond true) y) false) true) => (((cond true) true) false) => (((λa.λb.λc.((c a) b) true) true) false) => ((λb.λc.((c true) b) true) false) => (λc.((c true) true) false) => ((false true) true) => ((λfirst.λsecond.second true) true) => (λsecond.second true) => true

# Conclusion

At this point, you have a good enough grasp of the concepts of λ-calculus to make simple, non-recursive functions which act on Boolean values.

Next time we’ll cover how to represent numbers in the λ-calculus and how to perform recursion using the Y-combinator!

You can continue reading part 2 of this series here.

# A side note on computability

A function which can be evaluated in the λ-calculus with a finite number of operations is called λ-computable. All λ-computable functions are computable on a Turing Machine and all Turing computable functions are λ-computable (See Church-Turing thesis). As a result, Turing Machines and the λ-calculus are equivalent in terms of what kinds of functions they can evaluate. Because of this equivalence, any problem which can be solved efficiently with an imperative programming language can also be solved efficiently with a functional programming language.

# Formal syntax of λ-calculus

<expression> := <name> | <function> | <application>

<function> := λ<name>.<expression>

<application> := (<function> <expression>)

# References

An Introduction to Functional Programming Through Lambda Calculus by Greg Michaelson

The Lambda Calculus at Stanford Encyclopedia of Philosophy

[…] from part 1 that we can’t perform recursion in λ-calculus by using function names inside function […]

LikeLike

[…] A brief introduction to the λ-calculus (part 1). ~ Laurence Emms. #LambdaCalculus […]

LikeLike