数据的过程性表示-白红宇

夜里睡不着看起了 SICP，这里是第二章《构造数据抽象》的笔记。

知识点一：序对

(cons x y) 表示一个序对，记为 z。(car z) 可以获取 z 的第一个元素 x。(cdr z) 可以获取 z 的第二个元素 y。复制代码

cons（读作控死）、car（读作卡）和 cdr（读作酷得儿）

翻译成 JS 风格的伪代码就是

z = cons x ycar z // 值为 xcdr z // 值为 y复制代码

知识点二：数据的过程性表示

有没有可能 cons、car 和 cdr 其实是三个过程（也就是函数）呢？

只要 cons、car 和 cdr 三个函数满足上面的要求即可，下面是这三个函数的写法：

(define (cons x y)  (define (dispatch m)    (cond ((= m 0) x)          ((= m 1) y)          (else (error "argument not 0 or 1 -- cons" m))))  despatch)(define (car z) (z 0))(define (cdr z) (z 1))复制代码

翻译成 JS 大概是这样的：

function cons(x, y){  // 直接返回一个函数  return function dispatch(m){    if(m===0){
   return x}    if(m===1){
   return y}    throw new Error('argument not 0 or 1 -- cons' + m)  }}function car(z){  return z(0)}function cdr(z){  return z(1)}复制代码

这里令人惊奇的地方就在于 cons 直接返回了一个函数，并没有返回一个数组之类的玩意。

不过这只是一种模拟，语言内部并不是这样实现的。这种程序设计风格叫做「消息传递」。

知识点三

还可以这样定义 cons、car、cdr

(define (cons x y)  (lambda (m) (m x y)))(define (car z)  (z (lambda (a b) a)))(define (cdr z)  (z (lambda (a b) b))复制代码

翻译成 JS 是这样

cons = (x, y)=> {  return (m) => m(x, y)}car = z => {  return z((a, b) => a)}cdr = z => {  return z((a, b) => b)}复制代码

写成这样还挺烧脑的。

知识点四

上面的知识点说明其实可以抛弃复合数据结构，全用函数就行了。

但是如果我告诉你，连数字都可以不需要呢？（假设只考虑非负整数，而且这种语言允许我们对函数进行任何操作）

0 用一个函数来表示

zero = f => x => x // 这里的 f 看起来没有意义，要到下面才能理解复制代码

加1操作用另一个函数来表示

add1 = n => f => x => f(n(f)(x))复制代码

1、2 的表示方法见。

zero= f => x => xone = f => x => f(x)two = f => x => f(f(x))复制代码

这样定义了之后，可以证明

add1(zero) 得到的函数跟 one 是一模一样的（但不是同一个函数）；

add1(one) 得到的函数跟 two 是一模一样的（但不是同一个函数）；

虽然我不知道这样做有什么意义，不过还是很震撼的。

知识点五：cons 的闭包性质（与 JS 的闭包不是同一个术语）

一般来说，某种组合数据对象的操作满足闭包性质是指：通过它组合起数据对象得到的结果本身还可以通过同样的操作再进行组合。

换句话说：组合式的成员本身还可以是组合式的。

比如

(const (cons 1 2)        (cons 3 4))复制代码

cons 组合 1、2 得到的数据，还可以作为 cons 的元素，所以说 cons 满足闭包性质。

知识点六：链表

(cons 1   (cons 2 (    cons 3 (      cons 4 nil))))复制代码

通过 cons 的这种性质，很容易用 cons 表示一个链表。

这种语法可以简化为

(list 1 2 3 4)复制代码

注意 (list 1 2 3 4) 是一个函数调用，其返回值为(1 2 3 4)。假设 one-to-four = (list 1 2 3 4)

(define one-to-four (list 1 2 3 4))复制代码

car one-to-four 就是获取表头，cdr one-to-four 就是获取表头之外的节点。

我们可以用 cons 来在链表中插入节点

(cons 10 one-to-four)复制代码

结果为(10 1 2 3 4)。

还挺有意思的。

未完待续……

第三章的笔记：