I’ve been working through Structure and Interpretation of Computer Programs lately and recently went through an interesting exercise on Church numerals. I wanted to share what I learned, so here is my simplified presentation on them!
In the beginning, there was only lambda…
Some of the most interesting exercises in SICP involve showcasing how some primitive language features can be built using nothing but lambdas. To start, I’m going to introduce some of the basics of Racket itself so that we can build a primitive system of numbers called Church numerals1 on top of it.
At its heart, Racket is a pretty simple language. To call a function
a2, simply type
(f a1 a2). For example,
(+ 4 5 (* 2 3)) => 15
This is called prefix notation, since the function name prefixes the arguments.
Also, you can define a variable
x to some value using the
(define x 5) x => 5
And define functions by adding a parameter list:
(define (square x) (* x x)) (square 5) => 25
Finally, the special keyword lambda allows you to build anonymous functions like so:
(define square (lambda (x) (* x x))) (square 2) => 4
You may notice a similarity between the last two examples. In fact, the two
square are exactly the same; the first is just syntactic
sugar2 for the second.
When we call any function via parenthesis (for example,
(square 4)), whatever values
are sent as arguments to the function are substituted in the function body’s definition and
simplified. This is called the substitution model, and it is a simple way of thinking how a
Lisp interpreter might function. For example, calling
(square 4) would substitute
the body of
square’s definition. Thus, wherever we would write
x, we instead write
(* 4 4) which is then simplified to
So with our base set, let us move on to…
What are numbers, really?
A number system has a lot of properties that we take for granted.3 For now, let’s just implement a primitive set of numbers that we can increment and add.
We start with
zero and an increment function:4
(define zero ; i.e. zero is a function with two arguments f and x (lambda (f x) x)) ; calling this function just returns x (define (inc n) (lambda (f x) (f (n f x))))
To get a better sense of what this number system actually looks like, let’s try taking a look at what actually happens when we apply the increment function using simple substitution:
(define one (inc zero)) ; evaluating... => (define one (inc (lambda (f x) x))) ; substitute value for zero as n in body of inc => (define one (lambda (f x) (f ((lambda (f x) x) f x)))) ; simplify internal term ((lambda (f x) x) f x) => (define one ; done simplifying. (lambda (f x) (f x)))
So the Church representation for one would be
(lambda (f x) (f x)). Let’s see how
two would be
(define two (inc one)) ; evaluating... => (define two (inc (lambda (f x) (f x)))) ; substitute value for one as n in body of inc => (define two (lambda (f x) (f ((lambda (f x) (f x)) f x)))) ; simplify internal term again => (define two (lambda (f x) (f (f x))))
Looking at the definitions for
two, it becomes much clearer what our increment function is
doing. Every time we increment a number, we add another application of
x. Thus, the number
zero is a function that takes in a function
f and a value
x, and applies
zero times (i.e. it just returns
one is a function that applies
exactly once, and
This is actually quite useful, as now we can test our created Church numerals as follows:
(define (plus1 x) (+ x 1)) (zero plus1 0) => 0 (two plus1 0) => 2 (define (test-numeral n) (n plus1 0)) (test-numeral one) => 1
So how could we define addition? Let’s consider first what we want: given two church numerals
b, we need to return a numeral that applies its first argument
f to its second argument
a + b times.
However, we’re in luck! The definition for a Church numeral
a is a function that applies some
a times (and same for
b). Thus, we can use this to our advantage by simply passing in
(define (add a b) (lambda (f x) ; all Church numerals are functions with two arguments (a f ; apply f a times to... (b f x)))) ; the application of f to x b times (define four (add two two)) (test-numeral four) => 4 ; it works!
Let’s try to expand our number system a bit further. Given
b, how can we return
If you consider the definition of multiplication, the problem actually becomes
similar to addition.
a*b is just
a summed to itself
b times. Or in other
a times, and then doing that process again
b times. The
only tricky part is creating a function that calculates
(define (mult a b) (lambda (f x) ; again, all Church numerals are functions (b ; apply the following function b times: (lambda (x) (a f x)) ; applies f to x a times x))) (define twelve (mult three four)) (test-numeral twelve) => 12 ; horray!
Now that we’ve designed a basic set of operations for Church numerals, you might want to try implementing more complicated procedures. Here are a few interesting exercises to try:
- Can you implement exponentiation? How about even higher-ordered procedures, like Knuth’s up-arrow operations (tetration, etc.)?
- Can you generalize operations and write a procedure that returns a general hyperoperation? (I.e.
(generate-hyperop 0)would return the
(generate-hyperop 1)would return
- Can you implement subtraction? (Hint: try implementing the predecessor
prefunction that returns the number that comes before its argument.) This is actually a lot trickier than it looks.
Syntactic sugar is just a different syntax that is easier for humans to read or write in. In most cases, defining square in the style of the first example is easier to understand. ↩
In this article, we will only consider positive numbers and zero. It is possible to do negative numbers using only lambdas, but it’s more complicated. ↩
In the book (and I believe most definitions of Church numerals), the functions are curried (they all have one argument). However, this makes it a little more complicated to understand what’s going on, so for the sake of simplicity, these definitions might not be 100% accurate. ↩
If we had a curried definition of Church numerals, we actually wouldn’t have to define this new anonymous function. ↩