SICP Series (2) - Several Implementations of car and cdr

car and cdr are the way scheme organizes data structures, used together with cons:

(car (cons 12 34)) ; => 12
(cdr (cons 12 34)) ;=> 34

; after introducing assignment operations
; set-car! can change the first item; set-cdr! can change the second
(define y (cons 12 34))
(set-car! y 56)
(car y)  ; 56

It’s scheme’s built-in way, but of course we can implement it ourselves. SICP actually introduces several schemes; I’ve organized them to share with everyone.

Before Introducing Assignment – cons That Is Never Modified After Creation

Defining the allocator, SICP P152

(define (cons x y)
  (define (dispatch m)
    (cond ((= m 0) x)
        ((= m 1) y)
      (else (error "Argument not 0 or 1: CONS" m))
    )
  )
  dispatch
)

(define (car z) (z 0))
(define (cdr z) (z 1))

(car (cons 12 34))
(cdr (cons 12 34))

Using lambda, SICP P153

A scheme proposed by the logician Alonzo Church. The main idea: cons doesn’t exist in isolation — cons is only meaningful when paired with car and cdr, so there’s no need to give cons’s full implementation; it only needs to serve as input data for the subsequent selectors.

(define (cons a b)
  (lambda (f) (f a b))
)
(define (car c)
  (c (lambda (a b) a))
)
(define (cdr c)
  (c (lambda (a b) b))
)

(car (cons 12 34))
(cdr (cons 12 34))

After Introducing Assignment – the Corresponding Data Can Be Modified

Equivalent to adding set-car and set-cdr functions.

dispatch form, SICP P380

(define (cons x y)
  (define (set-x! v) (set! x v))
  (define (set-y! v) (set! y v))
  (define (dispatch m)
    (cond ((eq? m 'car) x)
      ((eq? m 'cdr) y)
      ((eq? m 'set-car!) set-x!)
      ((eq? m 'set-cdr!) set-y!)
      (else
    (error "Undefined operation: CONS" m))))
  dispatch
)
(define (car z) (z 'car))
(define (cdr z) (z 'cdr))
(define (set-car z new-value)
  ((z 'set-car!) new-value) z)

(define (set-cdr z new-value)
  ((z 'set-cdr!) new-value) z)

(define y (cons 12 34))
(set-car y 56)
(car y)
(cdr y)

lambda form

Mainly adds the set! function for modifying internal variables, which must be added to our lambda functions:

(define (cons a b)
  (define (sa x) (set! a x))
  (define (sb x) (set! b x))
  (lambda (f) (f a b sa sb))
)
(define (car c)
  (c (lambda (a b sa sb) a))
)
(define (cdr c)
  (c (lambda (a b sa sb) b))
)
(define (set-car c new-a)
  (c (lambda (a b sa sb) (sa new-a)))
)

(define (set-cdr c b)
  (c (lambda (a b sa sb) (sb new-a)))
)

(define y (cons 12 34))
(set-car y 56)
(car y)
(cdr y)

Summary

Before and after introducing assignment actually correspond to different ways we view the world. Before assignment, for a given function, its input and output can remain consistent; after introducing assignment, functions or other structures have internal state, becoming independent individuals. I suggest watching section 9 — assignment, state and side effects — which reminded me of function reentrancy.

Appendix: JS Implementations

let cons, car, cdr, set_car, set_cdr;

// dispatch
cons = function(x, y) {
  return (m) => {
    if(m == 0) {return x;}
    else if(m == 1) { return y;}
    else { console.log("error");}
  };
}
car = function(z){
  return z(0);
}
cdr = function(z){
  return z(1);
}

car(cons(12, 34))
cdr(cons(12, 34))

// lambda
cons = (x, y) => {
  return (f) => {return f(x, y);};
}
car = (c) => {
  return c((x, y) => x)
}
cdr = (c) => {
  return c((x, y) => y)
}
car(cons(12, 34))
cdr(cons(12, 34))

// dispatch set
cons = function(x, y) {
  let [_x, _y] = [x, y];
  return (m) => {
    if(m == 'car') {return _x;}
    else if(m == 'cdr') { return _y;}
    else if(m == 'set-car') {return (v) =>{_x = v}}
    else if(m == 'set-cdr') {return (v) =>{_y = v}}
    else { console.log("error");}
  };
}
car = function(z) {
  return z('car');
}
cdr = function(z) {
  return z('cdr');
}
set_car = function(z, v) {
  (z('set-car'))(v);
}
set_cdr = function(z, v) {
  z('set-cdr')(v);
}

c = cons(12, 34)
set_car(c, 56)
car(c)
set_cdr(c, 78)
cdr(c)

// lambda set
cons = function(x, y) {
  let [_x, _y] = [x, y];
  return (f) => {
    return f(_x, _y, (v)=>{_x=v}, (v)=>{_y=v})
  };
}
car = function(c) {
  return c((a, b, sa, sb) => a);
}
cdr = function(c){
  return c((a, b, sa, sb) => b);
}
set_car = function(c, v){
  return c((a, b, sa, sb) => {sa(v)});
}
set_cdr = function(c, v){
  return c((a, b, sa, sb) => {sb(v)});
}

c = cons(12, 34)
set_car(c, 56)
car(c)
set_cdr(c, 78)
cdr(c)