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?

Rhnegative

You might be interested in How is set! defined in scheme? where the accepted answer shows how to implement a cell that stores one value. It's the same sort of idea. Also see Lambda Calculus CONS Pair implementation with Lisp which has a definition like yours: pair ≡ λx.λy.λz.z x y. – Particiaparticipant

Answer 1

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)))))

Nunnery

Thanks. I think I get it (but it makes my brain hurt). This is much more complicated that the other alternate version they describe of the form: (define (cons x y) (define (dispatch m) (cond ((= m 0) x) ((= m 1) y))) dispatch) (define (car z) (z 0)) Looks like I need to understand closures - thanks for the reference to them. – Rhnegative

The other alternative is more complicated, conceptually. It requires conditionals, comparisons, functions and function application - whereas this alternative only requires functions and function application. – Marquess

Maybe because I am not familiar with functional languages yet, the second seems simpler to me. To my mind, in the 'dispatch' alternative, cons produces a function that is lurking in wait to produce the correct output when asked nicely - this seems simple. But in the 'lambda' alternative cons, produces a phantom that can only be made sense of when it is "boot-strapped" by car. – Rhnegative

In both cases there's a function lurking, waiting to be asked nicely :) – Marquess

@ÓscarLópez SO made me wait 24 hours to award the 250pt bounty, also I submitted an edit adding info about nested cdadrs, hope you approve ;) – Apparition

Answer 2

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".

Printmaking

I put the bounty up to reward the current answer, but I have to wait 24 hours because reasons. – Apparition

@Apparition : I hope the answer is useful to anyone else, then :) – Printmaking

Answer 3

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.

Outhouse