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