The Little Schemer

如何跟上真正的黑客的步伐,这是个问题!

如果没有认真阅读前言,那么你将觉得本书晦涩难懂,完全不知所云。为了从繁复的代码中剥离出简明的递归片段,本书预先设置了诸多约束条件。只有明了了这些约束条件,才能跟上黑客的步伐。

不要纠结于使用哪一种Scheme实现(Chez SchemeMIT/GNU Scheme),因为在这两种实现里,eq?过程可以对“数字”与“字符串”进行比较。重要的事情是:在一问一答的过程中,跟紧黑客,并在VIMLisp模式下编写代码。

虽然本书没有讲解“宏”,但是”Scheme五法十诫“也是道不错的开胃菜。

通过高阶函数实现柯里化偏函数后,本书论证了停机问题。在阅读应用序Y组合子的演算过程中,你的头脑会过载,但你将掌握“对匿名函数进行递归调用”的方法:

(define Y
  (lambda (f)
    ((lambda (g) (g g))
     (lambda (g)
       (f (lambda (x) ((g g) x)))))))

; 通过”应用序Y组合子“,求阶乘13的值
(let ((n 13))
  (printf "factorial ~s => ~s\n" n ((Y (lambda (f)
                                         (lambda (n)
                                           (if (= n 1)
                                             1
                                             (* n (f (- n 1))))))) n)))

Scheme作为Lisp的一种方言,有着极其简单的语法与语义。在本书最后,作者将通过将“符号”映射到“值”,实现了一个简单的“解释器”,阐明了计算的一般本质——模式识别

文摘

Scheme 十诫

第一诫

当对一个原子列表lat进行递归调用时,询问两个有关lat的问题:(null? lat)else

当对一个数字n 进行递归调用时,询问两个有关n 的问题:(zero? n)else

当对一个S-表达式列表l 进行递归调用时,询问三个有关l 的问题:(null? lat)(atom? (car l))else

第二诫

使用cons 来构建列表

第三诫

构建一个列表的时候, 描述第一个典型元素,之后cons 该元素到一般性递归(natural recursion)上。

第四诫

在递归时总是改变至少一个参数。当对一个原子列表lat 进行递归调用时,使用(cdr lat) 。当对一个数字n 进行递归调用时,使用(sub1 n) 。当对一个 S-表达式l 进行递归调用时, 只要(null? l)(atom? (car l)) 都不为true ,那么就同时使用(car l)(cdr l)

在递归时改变的参数,必须向着不断接近结束条件而改变。改变的参数必须在结束条件中得以测试:

当使用cdr 时,用null? 测试是否结束;

当使用sub1 时,用zero? 测试否结束。

第五诫

在用 + 构建一个值时,总是使用0 作为结束代码行的值,因为加上0 不会改变加法的值。

在用 × 构建一个值时,总是使用1 作为结束代码行的值,因为乘以1 不会改变乘法的值。

在用cons 构建一个值时,总是考虑把() 作为结束代码行的值。

第六诫

简化工作只在功能正确之后开展。

第七诫

对具有相同性质的subparts(子部件)进行递归调用:

  • 列表的子列表;

  • 算术表达式的子表达式。

第八诫

使用辅助函数来抽象表示方法。

第九诫

用函数来抽象通用模式。

第十诫

构建函数,一次收集多个值。

Scheme 五法

第一法 ——car 之法则

基本元件car 仅定义为针对非空列表

第二法 ——cdr 之法则

基本元件cdr 仅定义为针对非空列表。任意非空列表的cdr 总是另一个列表。

第三法 ——cons 之法则

基本元件cons 需要两个参数。第二个参数必须是个列表。结果是个列表。

第四法 ——null? 之法则

基本元件null? 仅定义为针对列表。

第五法 ——eq? 之法则

基本元件eq? 需要两个参数。每个参数都必须是一个非数字的原子。