Monday, February 25, 2008

Scheme: Implementing cons, car, and cdr

I'm going through Structure and Interpretation of Computer Programs per the recommendation of my buddy Mike Cheponis. I'm really enjoying it.

I always thought cons, car, and cdr were so low-level that they had to be builtins. However, interestingly enough, SICP shows how they could be implemented using a closure:
(define (my-cons a b)
(lambda (pick)
(cond ((= pick 1) a)
((= pick 2) b))))

(define (my-car x) (x 1))
(define (my-cdr x) (x 2))
It's kind of silly, but it also works in Python:
def cons(a, b):

def list(pick):
if pick == 1:
return a
elif pick == 2:
return b
else:
raise ValueError

return list

def car(list):
return list(1)

def cdr(list):
return list(2)
Neat!

It's easy to see how to extend this in Scheme to have "objects" with any number of memebers, although I'm sure it's not very efficient.

By the way, I really like DrScheme. It's relatively modern and very friendly.

10 comments:

Bill Mill said...

I'm doing SICP with DrScheme as well, and finding the environment quite pleasant. For example, it was easy to figure out how to plot the runtimes in the runtime complexity section.

Scheme, however, I'm still not all that impressed with. Maybe when I get to the macros that'll improve.

Titus Brown said...

Clobbering the 'list' type constructor, eh?

Shannon -jj Behrens said...

> Clobbering the 'list' type constructor, eh?

I wouldn't usually do it in practice, but neither would I implement cons, car, and cdr in practice. Naming it "list" makes this relatively clever code more understandable. It's a function that's treated as a list. Clever. Guess I could have named it list_.

Shannon -jj Behrens said...

> Scheme, however, I'm still not all that impressed with. Maybe when I get to the macros that'll improve.

What amazes me is that Lisp is such a powerful language from so long ago. Lisp is 40 years old!

vegashacker said...

Thanks for the post. It reminded me that there's an even wackier impl of cons, car and cdr in SICP a little ways down from there:

(define (cons x y)
  (lambda (picker-f)
    (picker-f x y)))

(define (car pair)
  (pair (lambda (x y) x)))

(define (cdr pair)
  (pair (lambda (x y) y)))

Shannon -jj Behrens said...

That's even nicer. You don't need an if statement or a cond.

Shannon -jj Behrens said...

> It reminded me that there's an even wackier impl of cons, car and cdr in SICP a little ways down from there:

I now know that that trick was created by Alonso Church in the 1930's, way before there were computers to try it on ;)

Shannon -jj Behrens said...

Actually, I think it's spelled Alonzo Church.

Mike said...

Hah. Found this through google search -- I remember being shown this trick as a freshman in CS about 12 years ago, and as I was going to sleep last night, it came to mind.

(I've been learning Haskell lately, that's probably why.)

Aha, here we go: http://mitpress.mit.edu/sicp/full-text/sicp/book/node30.html

Shannon -jj Behrens said...

Mike,

It's a cute trick. For some reason, I have Haskell stuck on my mind lately. I have a decent beginner's grasp of it, but I keep thinking I should go further. Have you read that new book "Real World Haskell", and if so, do you have any comments on it?

Thanks,
-jj