Fun with Lambda Calculus

[stopachka]

In 1935, a gentleman called Alonzo Church came up with a simple scheme that could compute…just about anything. His scheme was called Lambda Calculus. It was a phenomenal innovation, given that there weren’t even computers for him to test out his ideas. Even cooler is that those very ideas affect us today: anytime you use a function, you owe a hat tip to Mr. Church.

Lambda Calculus is so cool that many hackers use it as their secret handshake — a “discreet signal” if you will. The most famous, of course, is PG’s Y Combinator. In this essay, we’ll find out what it’s all about, and do things with functions that we’d never have imagined. In the end you’ll have built just about every programming concept: numbers, booleans, you name it…just with functions.

0: Intuition with Pairs

City dwellers who drive SUVs rarely consider their cars as ferocious machines that traverse rocky deserts and flooded rivers. It’s the same with programmers and functions. Here’s what we think functions do:

(def square (fn [x] (* x x)))

Safe, clean, and useful. We’re so accustomed that it would surprise us to find the myriad of ways we can bend functions to do just about anything.

Let’s step out into the wilderness a bit. Say you wanted to make a data structure for pairs:

(def pair (make-pair 0 1))
(first pair) ; => 0
(second pair) ; => 1

How would you do it? It’s sensible to use a map or a class or a record to represent a pair. But…you could use functions too.

Here’s one way we can make a pair:

(def church-pair (fn [a b]
                   (fn [selector]
                     (selector a b))))

No maps or classes…it just returns a function!

(def ex-pair (church-pair 0 1))
ex-pair
; => #object[church_factorial$church_pair...

Now our ex-pair takes a selector argument. What if we ran ex-pair with this selector:

(ex-pair (fn [a b] a))

Well, (ex-pair (fn [a b] a)) would expand too:

((fn [a b] a) a b)

Which would return… a!

That just gave us the first value of our pair! We can use that to write a church-first function:

(def take-first-arg (fn [a b] a))
(def church-first (fn [pair]
                    (pair take-first-arg)))

(church-first ex-pair)
; => 0

And do something similar for second:

(def take-second-arg (fn [a b] b))
(def church-second (fn [pair]
                     (pair take-second-arg)))

(church-second ex-pair)
; => 1

We just used functions to represent pairs. Now, since the grammar for Lisp is just a bunch of pairs plopped together, that also means we can represent the grammar of Lisp…with just functions!

1: Factorial

What we just did was analogous to a city dweller driving their SUV…on a snowy day. It gets a lot crazier.

We said we could represent everything. Let’s go ahead and try it!

Here’s what can do. Let’s take a function we know and love, and implement it from top-to-bottom in Lambda Calculus.

Here’s factorial:

(defn factorial-clj [n]
  (if (zero? n)
    1 
    (* n (factorial-clj (dec n)))))

(factorial-clj 5)
; => 120

By the end of this essay, we’ll have built factorial, only with functions.

2: Rules

To do this, I want to come up front and say I am cheating a little bit. In Church’s Lambda Calculus, there is no def, and all functions take one argument. Here’s all he says:

In his rules, you define anonymous functions by popping a little λ in front. What follows is the argument, following by a . .After the . is the application.

This is very much akin to a single-argument anonymous function in Clojure: λ x. x => (fn [x] x)

We could follow those rules, but writing factorial like that is going to get hard to reason about very quickly. Let’s tweak the rules just a little bit. The changes won’t affect the essence of Lambda Calculus but will make it easier for us to think about our code. Here it goes:

1) for a single argument function, (fn [x] x) maps pretty well to Church’s encoding. We can go ahead and use it as is.

2) Since Church’s lambdas only take one argument, For him to express a function with two arguments, he has to write two anonymous functions:

(λ f. λ x. f x)

This would map to:

(fn [f] (fn [x] (f x))

But, nesting our functions like this can get annoying in Clojure [^1]. To make life easier for us, we’ll allow for multi-argument functions:

(fn [f x] (f x))

3) Finally, Church has no concepts of variables outside of what’s provided by a function definition.

For him to express

(make-pair a b)

He would have to “unwrap” make-pair

((λ a. λ b. λ selector . selector a b)
 a b)

To keep our code sane, we’ll allow for def, but with one rule:

You can use def , as long as you can “replace” it with an anonymous function and nothing breaks.

For example, imagine if make-pair referenced itself:

(def make-pair (fn [a b]
                 (make-pair ...)))

This would break because if we replaced (def make-pair …) with an anonymous function, there would be no variable called make-pair anymore!

That’s it, these are our rules. With that, we’re ready to make factorial!

3: Numerals

The first thing we need is the concept of a number. How can we do that?

Church thought of a pretty cool idea. What if “numbers”, were higher-order functions with two arguments: a function f, and a value v.

(def zero (fn [f v] v))

(def one (fn [f v]
           (f (zero f v))))

(def two (fn [f v]
           (f (one f v))))

We can figure out what number each function represents by “counting” the number of times f was composed.

For example, 0 would compose f zero times: it would just return v. 1, would compose f once: (f v). 2 would compose twice: (f (f v)), and so on.

To help us see these numbers in our REPL, let’s create a quick converter function:

(defn church-numeral->int [church-numeral]
  (church-numeral inc 0))

Since a church numeral composes f the number of times it is called with v as the first argument, all we need to see what number it is in Clojure, is to provide inc as f and 0 as v! Now 2 would do (inc (inc 0)) for example, and get us the corresponding Clojure number.

(map church-numeral->int [zero one two])
; => (0 1 2)

Cool!

4: Inc

Take a look at how we wrote two:

(def two (fn [f v]
           (f (one f v))))

What we did here, is delegate f’s composition to the numeral before (in this case one ), and then just called f one more time.

What if we abstracted the one out?

(def church-inc
  (fn [church-numeral]
    (fn [f v]
      (f (church-numeral f v))))) 

Voila. Give this function a numeral, and it will return a new numeral that calls f one more time. We’ve just discovered inc!

(church-numeral->int (church-inc (church-inc one)))
=> 3

Cool.

Now that we have this function, we can also write a quick helper to translate Clojure numbers to these numbers:

(def int->church-numeral
  (fn [clojure-int]
    (if (zero? clojure-int)
      zero
      (church-inc (int->church-numeral (dec clojure-int))))))

(church-numeral->int (int->church-numeral 5))
=> 5

That’ll come in handy for our REPL.

5: Dec: Intuition

Next up, we need a way to “decrement” a number. Well, with inc we create a numeral that composes f one more time. If we can make some kind of function that composes f one less time, then we’d have dec!

To do that, we’ll need to go on a short diversion.

6: Dec: shift-and-inc

Remember our pair data structure? Let’s create a function for it (we’ll use this in just a moment below): shift-and-inc. All it would do, is take pair of numbers, and “shift” the pair forward by one:

For example, applying shift-and-inc to (0 1), would produce (1 2). One more time, it would produce (2 3), and so on.

Sounds simple enough:

(def shift-and-inc (fn [pair]
                     (church-pair
                       (church-second pair)
                       (church-inc (church-second pair)))))

Bam, we take a pair. The second item is shifted over to the first positions and is replaced with its inced friend. Let’s try it out:

(let [p (shift-and-inc (church-pair one two))]
  (map church-numeral->int [(church-first p) (church-second p)]))
; => (2 3)

Works like a charm!

7: Dec: putting it together

Now that we have shift-and-inc, what if we did this:

(def church-dec
  (fn [church-numeral]
    (church-first
      (church-numeral shift-and-inc
                      (church-pair zero zero)))))

Remember that our church-numeral would call shift-and-inc N times, representing its numeral value. If we started with a pair (0, 0), then what would the result be, if we composed shift-and-inc N times?

Our result would be the pair (N-1, N). This means that if we take the first part of our pair, we have dec!

(church-numeral->int (church-dec (int->church-numeral 10)))
; => 9

Nice.

8: Multiplication

Next up, multiplication. Say we multiply a by b. We’d need to produce a church numeral that composes f, a * b times. To do that, we can leverage the following idea:

Say we made a function g, which composes f b times. If we fed that function to a, it would call g, a times.

If a was “2” and “b” was 3, how many times would f get composed? Well, g would be composed twice. Each time g is composed, f is composed 3 times. That comes out to a total of 6 times!

Bam, if we did that, it would represent multiplication.

(def church-*
  (fn [num-a num-b]
    (fn [f v]
      (num-a (partial num-b f) v))))

Here, (partial num-b f) represents our g function.

(church-numeral->int
    (church-* (int->church-numeral 5) (int->church-numeral 5)))
=> 25

Works like a charm!

9: Booleans

We’ve got numbers, we’ve got * and we’ve got dec. Next up…booleans!

To do this, we need to be creative about what true and false is.

Let’s say this. Booleans are two argument functions:

(def church-true (fn [when-true when-false]
                   when-true))

(def church-false (fn [when-true when-false]
                    when-false))

They take a “true” case and a “false” case. Our church-true function would return the true case, and church-false function would return the false case.

That’s it. Surprisingly this is enough to handle booleans. Here’s how we could convert them to Clojure bools.

(defn church-bool->bool [church-bool]
  (church-bool true false))

Our church-true would return the first argument (true), and our church-false would return the second one!

(church-bool->bool church-true)
; => true
(church-bool->bool church-false)
; => false

Do they look familiar? Those are our selector functions for church-first and church-second! We could interchange them if we wished 😮

10: if

If you are like me, you were a bit suspicious of those booleans. Let’s put them to use and quiet our fears. Here’s how could create an if construct:

(def church-if (fn [church-bool when-true when-false]
                 (church-bool when-true when-false)))

All we do to make if, is to simply shuffle things around and provide the when-true and when-false cases to our boolean! church-true would return the when-true case, and church-false would return the when-false case.

That would make if work pretty well:

(church-numeral->int
    (church-if church-true one two))
; => 1
(church-numeral->int
    (church-if church-false one two))
; => 2

11: zero?

We have almost all the constructs we need to implement factorial. One missing piece: zero?. We need a way to tell when a numeral is zero.

The key trick is to remember that the zero numeral never calls f.

(def zero (fn [f v] v))

We can use that to our advantage, and create a zero? predicate like this:

(def church-zero?
  (fn [church-numeral]
    (church-numeral (fn [v] church-false) church-true)))

If a number is greater than zero, f would be called, which would replace v with church-false. Otherwise, we’d return the initial value of v, church-true.

(church-bool->bool (church-zero? zero))
; => true
(church-bool->bool (church-zero? one))
; => false

Wow…I think we’re ready?

12: factorial-v0

Let’s look at factorial-clj again:

(defn factorial-clj [n]
  (if (zero? n)
    1
    (* n (factorial-clj (dec n)))))

Well, we have numerals, we have if, we have zero? we have *, we have dec. We could translate this:

(def factorial-v0
  (fn [church-numeral-n]
    ((church-if
       (church-zero? church-numeral-n)
       (fn [] one)
       (fn []
         (church-*
           church-numeral-n
           (factorial-v0 (church-dec church-numeral-n))))))))

Wow. That follows our recipe pretty much to a key.

The only weird thing is that we wrapped the when-true and when-false cases in an anonymous function. This is because our church-if is a little different than Clojure’s if. Clojure’s if only evaluates one of the when-true and when-false cases. Ours evaluates both cases, which triggers an infinite recursion. We avoid this by wrapping both cases in a lambda, which “delays” the evaluation for us. [^2]

Will it work?

(church-numeral->int (factorial-v0 (int->church-numeral 5)))
; => 120

Wow! 🤯 We did it

13: Broken rules

Okay, almost. We cheated. Remember our Rule 3: If we replace our variables with an anonymous function, everything should work well. What would happen if we wrote factorial-v0 as an anonymous function?

(fn [church-numeral-n]
  ((church-if
     (church-zero? church-numeral-n)
     (fn [] one)
     (fn []
       (church-*
         church-numeral-n
         ; :< :< :< :< uh oh
         (factorial-v0 (church-dec church-numeral-n)))))))

Dohp. factorial-v0 would not be defined.

Here’s one way we can fix it. We could update this so factorial is provided as an argument to itself.

(fn [factorial-cb]
 (fn [church-numeral-n]
   ((church-if
      (church-zero? church-numeral-n)
      (fn [] one)
      (fn []
        (church-*
          church-numeral-n
          (factorial-cb (church-dec church-numeral-n)))))))
  ????)

That would work, but we only punt the problem down. What the heck would ???? be? We need some way to pass a reference of factorial to itself!

14: Y-Combinator: Writing it out

Let’s see if we can do make this work. First, let’s write our factorial, that accepts some kind of “injectable” version of itself:

(def injectable-factorial
  (fn [factorial-cb]
    (fn [church-numeral-n]
      ((church-if
         (church-zero? church-numeral-n)
         (fn [] one)
         (fn []
           (church-*
             church-numeral-n
             (factorial-cb (church-dec church-numeral-n)))))))))

If we can somehow provide that factorial-cb, we’d be golden.

To do that, let’s create a make-recursable function, which accepts this injectable-f

(def make-recursable
  (fn [injectable-f]
    ????))

Okay, all we did now is move the problem into this make-recursable function 😅. Bear with me.

Let’s imagine what the solution would need to look like. We’d want to call injectable-f with some factorial-cb function handles the “next call”.

(def make-recursable
  (fn [injectable-f]
    ; recursion-handler
    (injectable-f (fn [next-arg]
                    ????))))

That seems right. Note the comment recursion-handler . This is in reference to this form:

    (injectable-f (fn [next-arg]
                    ????)

If we somehow had access to this form, we can use that in ????! Well, let’s punt the problem down again:

(def make-recursable
  (fn [injectable-f]
    (????
     (fn [recursion-handler]
       (injectable-f (fn [next-arg]
                       ((recursion-handler recursion-handler) next-arg)))))))

Here, we wrap our recursion-handler into a function. If it could get a copy of itself, we’d be golden. But that means we’re back to the same problem: how could we give recursion-handler a copy of itself? Here’s one idea:

(def make-recursable
  (fn [injectable-f]
    ((fn [recursion-handler] (recursion-handler recursion-handler))
     (fn [recursion-handler]
       (injectable-f (fn [next-arg]
                       ((recursion-handler recursion-handler) next-arg)))))))

Oh ma god. What did we just do?

15: Y-Combinator: Thinking it through

Let’s walk through what happens:

The first time we called:

(make-recursable injectable-factorial)

this would run

(fn [recursion-handler] (recursion-handler recursion-handler))

recursion-handler would be:

(fn [recursion-handler]
  (injectable-f (fn [next-arg]
                  ((recursion-handler recursion-handler) next-arg))))

And recursion-handler would call itself:

(recursion-handler recursion-handler)

So now, this function would run:

(fn [recursion-handler]
       (injectable-f (fn [next-arg]
                       ((recursion-handler recursion-handler) next-arg))))

And this function’s recursion-handler argument would be…a reference to itself!

🔥🤯. Oh boy. Let’s continue on.

Now this would run:

       (injectable-f (fn [next-arg]
                       ((recursion-handler recursion-handler) next-arg))

injectable-factorial would be called, and it’s factorial-cb function would be this callback:

(fn [next-arg]
  ((recursion-handler recursion-handler) next-arg))

Whenever factorial-cb gets called with a new argument,

(recursion-handler recursion-handler)

This would end up producing a new factorial function that had a factorial-cb. Then we would call that with next-arg, and keep the party going!

Hard to believe. Let’s see if it works:

(def factorial-yc (make-recursable injectable-factorial))

(church-numeral->int (factorial-yc (int->church-numeral 5)))
; => 120
(church-numeral->int (factorial-yc (int->church-numeral 10)))
; => 3628800

Very cool!

This make-recursable function is also called the Y Combinator. You may have heard a lot of stuff about it, and this example may be hard to follow. If you want to learn more, I recommend Jim’s keynote.

16: Just Functions

Wow, we did it. We just wrote factorial, and all we used were anonymous functions. To prove the point, let’s remove some of our rules. Here’s how our code would end up looking without any variable definitions:

(church-numeral->int
  (((fn
      [injectable-f]
      ((fn [recursion-handler] (recursion-handler recursion-handler))
       (fn [recursion-handler] (injectable-f (fn [next-arg] ((recursion-handler recursion-handler) next-arg))))))
    (fn
      [factorial-cb]
      (fn
        [church-numeral-n]
        (((fn [church-bool when-true when-false] (church-bool when-true when-false))
          ((fn
             [church-numeral]
             (church-numeral (fn [v] (fn [when-true when-false] when-false)) (fn [when-true when-false] when-true)))
           church-numeral-n)
          (fn [] (fn [f v] (f ((fn [f v] v) f v))))
          (fn
            []
            ((fn [num-a num-b] (fn [f v] (num-a (partial num-b f) v)))
             church-numeral-n
             (factorial-cb
               ((fn
                  [church-numeral]
                  ((fn [pair] (pair (fn [a b] a)))
                   (church-numeral
                     (fn
                       [pair]
                       ((fn [a b] (fn [selector] (selector a b)))
                        ((fn [pair] (pair (fn [a b] b))) pair)
                        ((fn [church-numeral] (fn [f v] (f (church-numeral f v)))) ((fn [pair] (pair (fn [a b] b))) pair))))
                     ((fn [a b] (fn [selector] (selector a b))) (fn [f v] v) (fn [f v] v)))))
                church-numeral-n)))))))))
   ((fn [church-numeral] (fn [f v] (f (church-numeral f v))))
    ((fn [church-numeral] (fn [f v] (f (church-numeral f v))))
     ((fn [church-numeral] (fn [f v] (f (church-numeral f v)))) (fn [f v] (f ((fn [f v] (f ((fn [f v] v) f v))) f v))))))))

; => 120

😮

Fin

Well, we just took our functions through the Mojave desert! We made numbers, booleans, arithmetic, and recursion…all from anonymous functions. I hope you had fun! If you’d like to see the code in full, take a look at the GH repo.

Bonus: Fun with Macros

I’ll leave with you with some Clojure macro fun. When the time came to “replace” all our defs with anonymous functions, how did we do it?

In wimpier languages we might have needed to do some manual copy pastin [^3]. In lisp, we can use macros.

First, let’s rewrite def. This version will “store” the source code of every def as metadata:

(defmacro def#
  "A light wrapper around `def`, that keeps track of the
  _source code_ for each definition

  This let's us _unwrap_ all the definitions later : >"
  [name v]
  `(do
     (def ~name ~v)
     (alter-meta! (var ~name) assoc :source {:name '~name :v '~v})
     (var ~name)))

Then, we can create an unwrap function, that recursively replaces all def symbols with with their corresponding source code:

(defn expand
  "This takes a form like

  (church-numeral->int (factorial-yc (int->church-numeral 5)))

  And expands all the function definitions, to give
  us the intuition for how our 'lambda calculus' way would look!"
  [form]
  (cond
    (symbol? form)
    (if-let [source (some-> (str *ns* "/" form)
                            symbol
                            find-var
                            meta
                            :source)]
      (expand (:v source))
      form)

    (seq? form)
    (map expand form)

    :else form))

Aand…voila:

To learn about what’s going on there, check out Macros by Example

---

Thanks to Alex Reichert, Daniel Woelfel, Sean Grove, Irakli Safareli, Alex Kotliarskyi, Davit Magaltadze, Joe Averbukh for reviewing drafts of this essay

[^1]: Haskell for example treats every function in the same way as Mr. Church!

[^2]: This chapter in SICP may be a good place to get a deeper sense on what the issue is all about.

[^3]: I admit I first just did some copy-pastin. Only after I changed the code a few times did I decide to use the macros xD

[Takashiidobe]

Big fan of your blog; I have to say I've enjoyed every blog post I've read so far -- each one is filled with insight and is very fun.

When I was reading this one, I noticed that you wrote this:

What if “numbers”, where higher-order functions with two arguments: a function f, and a value v...

I think you meant something like this (where -> were): What if “numbers” were higher-order functions with two arguments: a function f, and a value v...

Anyway, keep up the good work, I've been working through the code for the risp blog and the "intuition for lisp syntax" through javascript and they're both chock full of insights :)

[stopachka]

Brought a big smile to read this, thank you for the kind words and the catch Takashi! Updated :)

---

If you're ever in NYC let's grab coffee!

[Takashiidobe]

I would love to!