SICP系列

car, cdr是scheme语言中用来组织数据结构的方式, 需要配合cons一起使用:

1
2
3
4
5
6
7
8
(car (cons 12 34)) ; => 12
(cdr (cons 12 34)) ;=> 34

; 引入赋值操作后
; set-car!可以更改第一项, set-cdr!可以更改第二项
(define y (cons 12 34))
(set-car! y 56)
(car y)  ; 56

它是scheme内建的方式, 当然也可以由我们自己来实现, 在SICP中其实介绍了几种方案, 我也整理了一下与大家分享.

引入赋值操作前 – 创建后不再进行修改的cons

定义分配器 SICP P152

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
(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))

使用lambda SICP P153

由逻辑学家Alonzo Church提出的方案, 主要的想法是: cons并不是单独存在的, 只有搭配car,cdr的时候cons才有意义, 所以不需要完整给出cons的实现, 仅需要将其作为后续选择器的输入数据.

1
2
3
4
5
6
7
8
9
10
11
12
(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))

引入赋值操作后 – 可以修改其中对应的数据

相当于我们增加了set-car与set-cdr函数

dispatch形式 SICP P380

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
(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 形式

主要是增加了set!函数用于修改内部变量, 需要在我们的lambda函数中增加

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
(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)

总结

引入赋值操作前后其实对应着我们看待世界的不同方式. 引入赋值之前, 对于某个函数来说, 它的输入和输出是可以保持一致的, 引入赋值操作之后, 函数或是其他结构体具有了内部的状态, 成为了一个独立的个体. 建议大家可以看下第9节, 赋值状态和副作用, 让我想到了函数的可重入性.

附: JS实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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))
1
2
3
4
5
6
7
8
9
10
11
12
// 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))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
// 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)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
// 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)