看 SICP 不如先看 The Little Schemer

函数式入门圣经——王垠力荐《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+33*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》的内容,对于一个刚入门学计算机的,没有接触过函数式编程的,我是极力推荐的。

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

其实理解完除了最后两章的内容,上手 SICP 就非常简单了,只不过习题还需多加努力。

看 SICP 不如先看 The Little Schemer

上一篇:c – 无法在两台以上的计算机上运行OpenMPI


下一篇:SICP 课程总结 & 复习