看 SICP 不如先看 The Little Schemer

2020-03-13

公众号

##函数式入门圣经——王垠力荐《The Little Schemer》

除了在知乎看到过一两次，首次正式得知《The Little Schemer》此书则是来自王垠的博客：

Dan Friedman 是 Indiana 大学的教授，程序语言领域的创始人之一。他主要的著作《The Little Schemer》（前身叫《The Little Lisper》) 是程序语言界最具影响力的书籍之一。现在很多程序语言界的元老级人物，当年都是看这本 “小人书” 学会了 Lisp/Scheme，才决心进入这一领域。

怼天怼地的王垠，在 GTF - Great Teacher Friedman 不遗余墨的表达了对 Dan Friedman 敬重与感激，文中满是对这位好老师的感激之情与知遇之恩。

恰逢我又在重新看 SICP，对，就是那本看起来不厚，习题多得要命的那本 Structure and Interpretation of Computer Programs(计算机程序的构造和解释)。当然这本书的赞誉满如繁星：https://www.zhihu.com/question/26549715/answer/34336593

过多的习题实在没有耐心，难以坚持，于是就先试试看《The Little Schemer》。

我在寒假中已把《The Little Schemer》看完，收获良多，如今重温一下，顺便写本书评。

相对于 SICP ，我更推荐各位先看《The Little Schemer》打打基础，当这是一个 tutorial，其一问一答式的写作方法会令你耳目一新的——-讲的更加循循善诱，鞭辟入里，而且没什么习题 - -。你可以很快就了解到怎么样写 scheme，递归的威力，以及了解怎么样写一个 scheme 解释器，顺带了解了丘奇计数，y 组合子等。

我顺带在这里整理下这本书讨论了啥：

####玩具总动员

引入scheme 中基本元素atom（原子）, list（列表）， car（取列表的第一项），cdr（取列表除第一项的余下作为列表），cons(把 a 元素加到 b 列表中）, null?(判断是否为空) , eq?(是否相等)。

以上就是全部了，之后的所有东西就靠以上关键字实现，包括 sheme 解释器，y 组合子，删除列表第 x 项元素。

####处理，处理，反复处理。。。

引入函数lambda以及or 关键词（if lese 作用），引入递归概念，实现函数 lat?（判断列表里是否全为 atom 原子），member？（列表是否包含xx）等为例子。

用 cons 构筑恢宏

通过实现 rember（删除列表某元素）引入 cons 构建/拼接列表，实现 first（取列表第一项），实现 insertR（在列表的某项后插入一个元素），multiinsertR（在列表的某项后插入一个列表内所有元素——听到这个用递归做是否就有点不习惯了呢）。

此章主要通过实现更多的函数，让读者更加熟悉递归实现函数的思维，以及如何写递归终止条件。

数字游戏

实现数字中的 +， -，*，/等方法，就是自己来做数字的这些功能，可能这样说对没有接触过丘奇计数的人有点奇怪，我举一个我在阿里校招中出过的一道面试题为例子：

以下C 语言程序的输出是什么？

#include <stdio.h>
int lambda(a, b) {
    if(a == 0) {
        return b;
    }else {
        a = a - 1;
        b = b + 1;
        return lambda(a, b);
    }
}

int mull_r(a, b) {
    if(a == 0) {
        return 0;
    }else {
        a = a - 1;
        return lambda(b, mull_r(a, b)) ;
    }
}

int main()
{
    int a = 88888;
    int b = 11111;
    printf("%d\n", lambda(a, b));

    int c = 300;
    int d = 400;
    printf("%d\n", mull_r(c, d));
    return 0;
}

A. 77777 120400

B. 99999 120000

C. 99998 120100

D. 99999 119600

答案是 B，以上 C 语言就是简单的实现了 + ， - 功能(某种程度上)。

同理还实现了=， <以及>，无非就是 a，b 同时递归-1，看谁先为 0之类。

接着就是实现 len(列表长度), all-nums(提取列表中所有数字），one?（判断 n是否为 1）等。

我的天！都是星星

此章中重新实现以前实现过的函数的泛化版本（都在函数名后加一个*，所以说都是星星）。

比如rember*（这次接受的第二个参数不是原子了，是列表，列表中出现过的都要删掉）；insertR*（同理）等, eqlists(判断两个列表是否全等)。就是参数都为列表了，让递归来的更猛烈一些。

如影随形

引入算术表达式，如 1+3，3*4+12 等并写算术表达式解释器，算出结果。

另外，值得一提的是又提了一遍丘奇数，如：

4 代表概念上的四。因为人们更习惯阿拉巴表示法，所以我们选择了这个符号。

但，(() () () ())也有同样效果，(I V)也可以。

我们可以用() 代表 0， 1就是 ( () )，2 就是（（）（））

那么加法就可以用 cons 做列表拼接 (cons (quote()) (quote()) ) 结果就是(())也就是 1。

作者最后用了一个函数lat来说明在做高级抽象时应该注意不适用的陷阱（阴影），也就是本章标题的含义。

朋友及关系

写一个 set?函数（判断列表是否为 set也就是没有重复出现的元素），makeset(从列表中构建一个 set)，subset（b 是否 a 的子集），eqset?， interset?等。

示例了如何抽象出一个子过程（函数），来增强代码的表达能力。

lambda 终结者

在把函数当做数据类型，作为参数传入函数使用时，引入 Curry-ing（柯里化）的概念：

(lambda (a)
    (lambda (x)
      (eq? x z))
)

如上，传入参数 apple 的时候，会返回函数

    (lambda (apple)
      (eq? apple z))

如上就可以构造出一个函数，传给 rember 函数（根据条件删除列表中元素）作为参数使用。

接着用这个抽象更高一层的函数，因为年代久远，我有些忘了。。这里描述不了了。

####。。。。周而复始。。。

这一章，作者从无到有的推导出在没有定义函数名字的时候，怎么样实现递归，也即是 Y conbinator（Y 组合子）的来由，然而实在让人头大，我看了好多遍，也只是似是而非，不能鞭辟入里的讲解出来，所以我算是不懂的。

值是什么

有了递归，有了之前写过的数字表达式解释器，而 scheme 本来就很简单，于是这一章就可以总结之前学到的所有东西，写一个 scheme 解析器了。

以上就是《The Little Schemer》的内容，对于一个刚入门学计算机的，没有接触过函数式编程的，我是极力推荐的。

努力学完理解完，一周时间勉强可以解决了，之后两章可能需要花比较长的时间去理解——难度暴涨。。。需要自己去多看看其他书了。

For The Best Thing In The World

Work Hard to Enjoy Them.