Thursday, October 21, 2010

SICP 2.4: Implementing cons, car, and cdr

From SICP section 2.1.3 What Is Meant by Data?

Exercise 2.4 gives us the following alternative procedual implementation for creating pairs.
(define (cons x y)
(lambda (m) (m x y)))

(define (car z)
(z (lambda (p q) p)))

Using this implementation, we are told to verify that (car (cons x y)) yields x for any objects x and y using the substitution model from section 1.1.5.

Once we've done that, we need to write the corresponding definition of cdr.

Our first step to verifying that this implementation for cons and car work should be to put the code in a Scheme interpreter and see them work.
> (car (cons 2 3))
2
> (car (cons 15 "Hello"))
15
> (car (cons "Hi!" 42))
"Hi!"

Now let's use the substitution model to show that the following always yields x
(car (cons x y))

First we retrieve the body of cons
(lambda (m) (m x y))

We could replace the formal parameters x and y with the arguments 2 and 3 (or any others that we choose) at this point, but I'm going to keep working with x and y. Let's substitute the body of cons.
(car (lambda (m) (m x y)))

Now we can retrieve the body of car and substitute it.
((z (lambda (p q) p)) (lambda (m) (m x y)))

The car procedure takes a procedure z as an argument and applies it to (lambda (p q) p), so there's one more substitution we need to do here before this step is really done. We need to take the second lambda in the expression above and replace z with it.
((lambda (m) (m x y)) (lambda (p q) p))

That might look scary, but it's just a procedure applied to another procedure. Since the procedure on the left takes one formal parameter, we can substitute the procedure on the right for that parameter.
((lambda (p q) p) x y)

Now it should be clear that this expression is a procedure that takes two parameters p and q, and passes two parameters to it. The procedure returns the first of the two parameters passed to it, so this expression simplifies to x.

The definition for cdr that corresponds to the above implementation of car is simply
(define (cdr z)
(z (lambda (p q) q)))

We can test it out the same way we originally tested the code provided in the text,
by running it in the interpreter.
>  (cdr (cons 2 3))
3
> (cdr (cons 15 "Hello"))
"Hello"
> (cdr (cons "Hi!" 42))
42


Related:

For links to all of the SICP lecture notes and exercises that I've done so far, see The SICP Challenge.

10 comments:

Tim Kington said...

Fantastically mind-bending. This kind of thing is the reason SICP is worth working through.

Bill the Lizard said...

Tim,

When I saw this comment in my email I thought for sure you were talking about 2.5. It applies equally well to 2.6.

SICP is definitely making me think in new ways. :)

jie liu said...

it seems that cdr should return a list not the second value in general. But at this point the book only explains pairs.

Mark said...

@jieliu

cdr always returns the second item of a cons cell - sometimes that second item is another cons cell.

valjok said...

I have translated that into Scala, http://valjok.blogspot.com/2014/06/213-what-is-meant-by-data-in-scala.html

Nazim G said...

TIANQU XS809W Foldable RC Quadcopter – RTF – BLACK WITH THREE BATTERIES, 2MP CAMERA + AIR...

RC Quadcopter

Mahmoud Ababneh said...

nice post.
smartphoneforsale

mohammed ababneh said...


Thank you for sharing this post


https://3-things-you-must-remember-when-posting.html

Beard Czar said...

Why is Rapid Tone Weight Loss So Effective?
Other weight loss products rely on mixing a lot of different ingredients together to try and create a formula that will target different weight loss issues. Unfortunately when your body detects all of these different ingredients it can cause problems and make them less effective. With Rapid Tone Weight Loss, though, there is only a single—extremely powerful—active ingredient.
When you take Rapid Tone Weight Loss your body will start to produce two different enzymes: one is known as cAMP and the other is lipase. When both of these chemical compounds are increased in your body at the same time, your body experiences a dramatic increase in metabolism and fat blocking power. What that ultimately means is that you are able to keep fat from storing and the fat you already have is melted away faster than ever before.


Why is Rapid Tone Weight Loss So Effective?
Other weight loss products rely on mixing a lot of different ingredients together to try and create a formula that will target different weight loss issues. Unfortunately when your body detects all of these different ingredients it can cause problems and make them less effective. With Rapid Tone Weight Loss, though, there is only a single—extremely powerful—active ingredient.
When you take Rapid Tone Weight Loss your body will start to produce two different enzymes: one is known as cAMP and the other is lipase. When both of these chemical compounds are increased in your body at the same time, your body experiences a dramatic increase in metabolism and fat blocking power. What that ultimately means is that you are able to keep fat from storing and the fat you already have is melted away faster than ever before.

Emely John said...

Fabulous site! Do you have any tips and indicates for trying authors? I'm wanting to begin my own particular site soon yet I'm somewhat lost on everything. Would you propose beginning with a free stage like WordPress or go for a paid choice? There are such a variety of choices out there that I'm totally overpowered .. Any recommendations? Much obliged!
Content Management Development