Exercise 2.6 of SICP

Exercise 2.6: In case representing pairs as procedures wasn’t mind-boggling enough, consider that, in a language that can manipulate procedures, we can get by without numbers (at least insofar as nonnegative integers are concerned) by implementing 0 and the operation of adding 1 as

This representation is known as Church numerals, after its inventor, Alonzo Church, the logician who invented the calculus.

Define one and two directly (not in terms of zero and add-1). (Hint: Use substitution to evaluate (add-1 zero)). Give a direct definition of the addition procedure + (not in terms of repeated application of add-1).

In order to check these I will use the fact that Church numerals appear to be repeated function composition.
If I use the familiar inc function and pass an argument of 0 I should get the number I am looking for:

> ((one inc) 0)
1
> ((two inc) 0)
2
> (((add-1 two) inc) 0)
3

Now that I am convinced that my functions work it’s time to move on and create an addition function.

Now to check that it works properly:
> (((add one one) inc) 0)
2
> (((add two one) inc) 0)
3
> (((add two two) inc) 0)
4

Just for fun multiply looks like this:

Leave a Reply