The mathematical theory behind `LISP`

is the λ-calculus (pronounced lambda-calculus).

The amazing thing about `λ-calculus`

is that it is possible to represent numbers and the arithmetic operations (`successor`

, `addition`

and `multiplication`

) as functions.

Once you have arithmetics, you have almost all the mathematics and the computer science.

In this article, we are going to show this representation using `clojure`

.

By the way, this is the signification of the `λ`

sign in the clojure logo:

# Numbers representation in λ-calculus

Like everything in `λ-calculus`

, numbers are functions.

A number `n`

is a function that receives as argument a `1-arity`

function `f`

and returns a function that applies `f`

`n`

times.

Let’s define the first natural numbers, manually:

```
(defn zero [f]
(fn [x] x))
(defn one [f]
(fn [x]
(f x)))
(defn two [f]
(fn [x]
(f (f x))))
(defn three [f]
(fn [x]
(f (f (f x)))))
```

# Numbers in action

In order to see the numbers in action, we need to execute them on a function and to execute the resulting function on a value.

All the code snippets on this article are live and interactive: feel free to modify the code and it will evaluate instantaneously!

The code snippets are powered by the Klipse plugin.

We could take the increment function `inc`

, and execute the result on `42`

:

```
((zero inc) 42)
```

```
((one inc) 42)
```

```
((two inc) 42)
```

```
((three inc) 42)
```

But, in order to make it more visual, we are going to define a custom function:

```
(defn visual [x]
(list 'f x))
```

Let’s see what happens when we pass it to a lambda number:

```
((two visual) 'x)
```

Nice! Now, we see visually the definition of the number `two`

: Application of a function twice.

In order to make things more convenient, let’s define a helper function `view`

:

```
(defn view [f]
((f visual) 'x))
```

And let’s view the lambda numbers we have defined so far:

```
(map view [zero one two three])
```

# Generating any lambda number

Let’s write a function that receives a regular number `n`

and returns the corresponding `lambda-number`

, using `clojure`

functions `comp`

, `repeat`

and `apply`

:

```
(defn lambda-num [n]
(fn [f]
(fn [x]
((apply comp (repeat n f)) x))))
```

Let’s view the lambda-number `6`

:

```
(view (lambda-num 6))
```

And we can easily view a range of lambda-numbers:

```
(map view (map lambda-num (range 5)))
```

# Equality

Two `lambda-numbers`

are equal if they are the same functions from a mathematical perspective.

It is disappointing that a `lambda-number`

is not equal to itself:

```
(= (lambda-num 6) (lambda-num 6))
```

The reason, is that from a `clojure`

perspective they are two different functions with the same code.

We will use the function `view`

for equality test:

```
(defn eq? [m n]
(= (view m) (view n)))
```

It works as expected:

```
(eq? (lambda-num 6) (lambda-num 6))
```

```
(eq? (lambda-num 4) (lambda-num 6))
```

# Type definition for lambda

Let’s define a `clojure`

type to customize the viewability and equality of lambda numbers. Our type will have the following properties:

- It is callable as a function
- It is viewable with
`view`

- It redefines equality with
`view`

For that purpose, we need to implement three `clojure`

protocols:

`IFn`

`IPrintWithWriter`

`IEquiv`

Let’s define a type named `Lambda`

:

(If you are not familiar with the details of `clojure`

protocols, you can skip the following code snippet.)

```
(deftype Lambda [f]
Object
(toString [_] (str (view f)))
IPrintWithWriter
(-pr-writer [this writer _] (-write writer (str (view f))))
IEquiv
(-equiv [this other]
(= (view this) (view other)))
IFn
(-invoke [this g]
(f g)))
```

And a function that converts a regular number to a typed lambda number:

```
(defn lambda-typed-num [n]
(Lambda. (lambda-num n)))
```

Now, lambda numbers are viewable:

```
(map lambda-typed-num (range 5))
```

And comparable:

```
(= (lambda-typed-num 6) (lambda-typed-num 6))
```

```
(= (lambda-typed-num 4) (lambda-typed-num 6))
```

Now that we have defined lambda numbers and that they are viewable and comparable, we can introduce the basic arithmetic operations: successor, addition and multiplication.

# The successor operation

Here is how one implements the `successor`

function in `λ-calculus`

. Successor is a function that receives a number `n`

and returns `n+1`

.

```
(defn successor [m]
(fn [f]
(fn [x]
(f ((m f) x)))))
```

The code basically means: apply the function `f`

`m`

times and then another time.

Now, lets’ wrap it with our `Lambda`

type

```
(defn succ [m]
(Lambda. (successor m)))
```

Let’s check it works fine:

```
(succ (lambda-typed-num 1))
```

```
(= (succ (lambda-typed-num 8)) (lambda-typed-num 9))
```

## The addition operation

Here is how one implements the `addition`

function in `λ-calculus`

. Addition is a function that receives two numbers and returns the result of their addition:

```
(defn add [m n]
(Lambda.
(fn [f]
(fn [x]
((n f) ((m f) x))))))
```

The code basically means: apply the function `f`

`m`

times and then `n`

times.

Let’s check it works fine:

```
(add (lambda-typed-num 3) (lambda-typed-num 2))
```

Make sure that `3+2`

equals 5:

```
(= (add (lambda-typed-num 3) (lambda-typed-num 2))
(lambda-typed-num 5))
```

# The multiplication operation

Here is how one implements the `multiplication`

function in `λ-calculus`

. Multiplication is a function that receives two numbers and returns the result of their multiplication:

```
(defn mult [m n]
(Lambda.
(fn [f]
(m (n f)))))
```

The code basically means: compose the function `f`

`n`

times and then `m`

times.

Let’s check it works fine:

```
(mult (lambda-typed-num 3) (lambda-typed-num 2))
```

Make sure that `3*2`

equals 6:

```
(= (mult (lambda-typed-num 3) (lambda-typed-num 2))
(lambda-typed-num 6))
```

# Conclusion

It is really amazing to see concretely how powerful is the `λ-calculus`

. With a very limited set of characters and concepts we can build the arithmetics.

In the next article, we are going to show how to define the booleans and their basic operations.

Let us know what you think about this lambda-calculus tutorial in the comments below….