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:

1. It is callable as a function
2. It is viewable with view
3. It redefines equality with view

For that purpose, we need to implement three clojure protocols:

1. IFn
2. IPrintWithWriter
3. 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….