SICP and Church numerals

In my free time, I’ve been reading through SICP. I found exercise 2.6 and the concept of representing numbers as procedures especially interesting and confusing (SICP actually calls the concept mind-boggling in the exercise description). Here’s my attempt at describing what’s going on using CoffeeScript (because it’s actually more terse than using a lisp). Numbers represented as functions in this way are called Church numerals.

First off, zero is just a function which takes a function as an argument and returns the identity function (a function which just returns it’s argument unchanged).

zero = (f) ->
  # takes in a function f
  (x) -> x
  # returns a function which just returns its input

add1 = (cn) ->
  # takes in a Church numeral
  (f) ->
  # returns a function which takes in a function, f,
    (x) -> f(cn(f)(x))
    # and returns a function which in an argument, x, applies the Church numeral to
    # f then applies the resulting function to x, then applies f to all of that

add1 is the other function SICP provides as a starting point for figuring out how to implement additional numbers and an add function. The easiest way to figure out how add1 works is by figuring out what the result of add1(zero) is using substitution.

add1(zero) = (f) ->
  (x) -> f(zero(f)(x))

# since zero called with any argument returns the identity function
add1(zero) = (f) ->
  (x) -> f(identity(x))

# and the identity function just returns its argument
add1(zero) = (f) ->
  (x) -> f(x)

So add1(zero) ends up returning a function which takes a function, f, as input and returns a function which applies f to it’s argument. Obviously adding one to zero produces one so we can use that as the definition for one as a Church numeral.

one = (f) ->
  (f) -> f(x)

add1(one) = (f) ->
  (x) -> f(one(f)(x))

# one takes a function as an argument, in this case f, and returns a function
# which applies f to its argument which is x
add1(one) = (f) ->
  (x) -> f(f(x))

Doing the same substitution process for add1(one) gives us two and makes it clear what the pattern is for defining any number as a Church numeral. It also makes it clear how adding two Church numerals should be implemented. If one is just a function which applies some other function once and two is a function which applies a function twice, adding two Church numerals is just applying both numerals’ in succession.

two = (f) ->
  (x) -> f(f(x))

add = (a, b) ->
  # input two Church numerals
  (f) ->
  # return a function
    (x) ->
      # which applies f b times and and then a more times
      a(f)(b(f)(x))

churchToInt = (cn) ->
  cn((n) -> n + 1)(0)

churchToInt(two) # 2
churchToInt(add1(two)) # 3
churchToInt(add(add(one, two), two)) # 5
churchToInt(add(add(one, two), add(two, two))) # 7

churchToInt is a helper (borrowed from this discussion of the solution to convert a Church numeral to an integer to verify that everything checks out. Even though the SICP exercise only says to define one, two and add, it’s should be pretty clear at this point how other arithmetic operations are created. mult, defined below, multiplies two Church numerals by changing add so that instead of applying both numerals one after another a is applied to the output b(f), so b(f), which is just f applied b times is applied a times for a total of a * b.

mult = (a, b) ->
  (f) ->
    (x) ->
      a(b(f))(x)

repl.it