Use of lambda for cons/car/cdr definition in SICP

Question

I was just beginning to feel I had a vague understanding of the use of lambda in racket and scheme when I came across the following 'alternate' definitions for cons and car in SICP

(define (cons x y)
   (lambda (m) (m x y)))

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

(define (cdr z)
  (z (lambda (p q) q)))

For the life of me I just cannot parse them.

Can anybody explain how to parse or expand these in a way that makes sense for total neophytes?

Answer 1

This should be easy to understand with the combinatory notation (implicitly translated to Scheme as currying functions, f x y = z ==> (define f (λ (x) (λ (y) z)))):

cons x y m = m x y
car z = z _K          ; _K p q = p
cdr z = z (_K _I)     ; _I x = x     _K _I p q = _I q = q

so we get

car (cons x y) = cons x y  _K     = _K  x y   =  x
cdr (cons x y) = cons x y (_K _I) = _K _I x y = _I y = y

so the definitions do what we expect. Easy.

In English, the cons x y value is a function that says "if you'll give me a function of two arguments I'll call it with the two arguments I hold. Let it decide what to do with them, then!".

In other words, it expects a "continuation" function, and calls it with the two arguments used in its (the "pair") creation.

Answer 2

This is an interesting way to represent data: as functions. Notice that this definition of cons returns a lambda which closes over the parameters x and y, capturing their values inside. Also notice that the returned lambda receives a function m as a parameter:

;creates a closure that "remembers' 2 values
(define (cons x y)    (lambda (m) (m x y)))
;recieves a cons holding 2 values, returning the 0th value
(define (car z)       (z (lambda (p q) p)))
;recieves a cons holding 2 values, returning the 1st value
(define (cdr z)       (z (lambda (p q) q)))

In the above code z is a closure, the same that was created by cons, and in the body of the procedure we're passing it another lambda as parameter, remember m? it's just that! the function that it was expecting.

Understanding the above, it's easy to see how car and cdr work; let's dissect how car, cdr is evaluated by the interpreter one step at a time:

; lets say we started with a closure `cons`, passed in to `car`
(car (cons 1 2))

; the definition of `cons` is substituted in to `(cons 1 2)` resulting in:
(car (lambda (m) (m 1 2)))

; substitute `car` with its definition
((lambda (m) (m 1 2)) (lambda (p q) p))

; replace `m` with the passed parameter
((lambda (p q) p) 1 2)

; bind 1 to `p` and 2 to `q`, return p
1

To summarize: cons creates a closure that "remembers' two values, car receives that closure and passes it along a function that acts as a selector for the zeroth value, and cdr acts as a selector for the 1st value. The key point to understand here is that lambda acts as a closure. How cool is this? we only need functions to store and retrieve arbitrary data!

Nested Compositions of car & cdr are defined up to 4 deep in most LISPs. example:

(define caddr (lambda (x) (car (cdr (cdr x)))))

Answer 3

In my view, the definitive trick is reading the definitions from the end to the beginning, because in all three of them the free variables are always those that can be found in the lambda within the body (m, p and q). Here is an attempt to translate the code to English, from the end (bottom-right) to the beginning (top-left):

(define (cons x y)
    (lambda (m) (m x y))

Whatever m is, and we suspect it is a function because it appears right next to a (, it must be applied over both x and y: this is the definition of consing x and y.

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

Whatever p and q are, when something called z is applied, and z is something that accepts functions as its input, then the first one of p and q is selected: this is the definition of car.

For an example of "something that accepts functions as its input", we just need to look back to the definition of cons. So, this means car accepts cons as its input.

(car (cons 1 2)) ; looks indeed familiar and reassuring
(car (cons 1 (cons 2 '()))) ; is equivalent
(car '(1 2)) ; is also equivalent
(car z)
; if the previous two are equivalent, then z := '(1 2)

The last line means: a list is "something that accepts a function as its input".

Don't let your head spin at that moment! The list will only accept functions that can work on list elements, anyway. And this is the case precisely because we have re-defined cons the way that we have.

I think the main point from this exercise is "computation is bringing operations and data together, and it doesn't matter in which order you bring them together".