An SICP exercise in implementing cons, car, and cdr

I started working my way through the Structure and Interpretation of Computer Programs this week.

Contemporary “intro to programming concepts” texts tend to focus on real-world examples in areas like business and web-based applications. In contrast, SICP involves a lot of math problems. I’m liking this about the book. Math is particularly good for illustrating the difference between declarative and imperative knowledge, between “describing properties of things and describing how to do things.” You may know, formally, what a square root is, but coming up with a procedure for calculating the square root of a number is another matter. Bridging these two kinds of knowledge is the essence of what computer programming is about.

The second section, “Building Abstractions with Data,” starts by discussing different ways to implement an abstraction for rational numbers. The text walks through using a Lisp cons cell to store a numerator and denominator pair, and using car and cdr as selectors. Then it provides this exercise, which I found particularly intriguing:

Exercise 2.5. Show that we can represent pairs of nonnegative integers using only numbers and arithmetic operations if we represent the pair a and b as the integer that is the product 2a3b. Give the corresponding definitions of the procedures cons, car, and cdr.

That’s a really clever way to store a pair! But perhaps I only think so because I’m not a math person.

At any rate, I wrote a solution in Common Lisp, with some helper lambdas to calculate log and pow arithmetically.

I’m finding that thinking about math problems and learning Lisp are helping me think more algorithmically about solving problems in the code I write for work. Maybe I’m starting to experience what Eric S Raymond famously wrote about Lisp: that it “will make you a better programmer for the rest of your days, even if you never actually use Lisp itself a lot.” I’m holding out hope for that last part though…

Leave a Reply

Your email address will not be published. Required fields are marked *