SICP Exercise 2.6: Church numerals

I’ve jumped ahead some, since I’m going through the book with a local Lisp users group. They’ve decided to not go through all of the exercises, just some that we select. I may backtrack at some point to cover some of the ones I missed.

I won’t say much about this exercise. If it mystifies you from the start, look up information on “lambda calculus”. I had to review this as well before I started into it, because it had been a couple years since I last looked at stuff like this.

I found that it didn’t help at all to try to execute stuff in a Scheme interpreter. That misses the point. I found it helpful to just write down, or type out in a text editor, a walkthrough of the logic in the “zero” and “add-1” functions as I used them, to figure out part of the exercise.

Getting to “one” and “two” was pretty easy. What the exercise says to do (it says “use substitution”) is use the functions you are given to figure out what “one” and “two” are. In other words, carry out the logic and see what you get.

The challenging part is figuring out what the “+” operation should be. It helps to look at this at a conceptual level. You don’t have to do a math proof to get this, though understanding how to do an inductive proof helps in giving you ideas for how to proceed with this part (if you need practice with doing an inductive proof, try Exercise 1.13). Keep in mind that this is a computing problem, not a classical mathematics problem (though there is definitely mathematics of a sort going on as you go through the logic).

The idea of the exercise is to get a different idea of what the concept of number can mean via. computing. It helps to be familiar with mathematical logic for this one, to see what you’re really doing, though I think you can get by without it if that’s not one of your competencies. If you’ve ever seen a mathematical explanation for the existence of natural numbers, this is reminiscent of that.

I don’t want to give away the answer, except to mention an article I found, called “The Genius of Alonzo Church (rerun)”, by Mark Chu-Carroll. NOTE: Do not read this article until you’ve done the problem! It will give away the answer. I only mention it because Mark says something quite beautiful about what the answer means. It ties right into a concept in object-oriented programming.

One thought on “SICP Exercise 2.6: Church numerals

  1. Pingback: The 150th post « Tekkie

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s