Table of contents
Open Table of contents
基本介绍
最近在学习Scheme，来自 MIT 的一个著名的Lisp方言。它诞生于 1975 年，和 c 语言(1972)算是同龄，对比现在当道的 90 后语言(java, javascript, php, python, ruby… )，在这日新月异的程序界，算得上是“老掉牙”了。
那么问题来了，有这工夫，为啥不学学新潮的Go, Rust，偏偏学一个这么古老的语言？
答案很简单: Scheme 简洁优雅强大，直指编程本质。学之能去芜存精，助我们提升编程水平。
关于 Scheme 的书籍最有名的当属 MIT 的《计算机程序的构造和解释》（SICP，或“魔法书”），到 08 年为止，曾三十年为作为 MIT 计算机科学的入门课程。
不过 SICP 虽“说”是入门，其实又厚又深，所以我选择了另一本经典书籍作为入门：The Little Schemer。这本书仅仅 200 页，且通篇都由question&answer的对话构成，由浅入深，深入浅出，从 lambda 以及几个 built-in 函数出发，一路推导出各种运算方法、数据结构，并深入到 continuation，停机问题，Y-combinator, 甚至最后直接写了个简单的解释器出来，令人惊叹。
事实上，本文可算是The Little Schemer的笔记和总结。
Let’s start
我使用的 scheme 实现是Guile, 然后在emacs中使用了王垠的 scheme 配置, 配置文件在这里
Scheme 基本语法
Scheme 的语法就是 Lisp 语法，括号套括号…很多人不爽 lisp 满屏的括号，觉得可读性差。不过，可读性应该是用缩进来保证的，任何语言的 code，不用换行和缩进，都不能谈可读性。
事实上，由于 Lisp 的程序和数据是同一种表达方式(列表)——本质上就是AST的前缀表示——这给了 lisp 无与伦比的表达力和扩展性。
下面简单说一下其语法元素:
- 原子（atom）和列表（list）
表达式只有两种, atom和list, atom 是 number 或者 symbol(类似于 string), list 就是那坨括号
3 ; 数字3
1.14 ; 数字1.14
#t ; boolean True
#f ; boolean False
abc ; simbol abc
() ; empty list
(abc xyz) ; list
(+ 1 (- 3 2)) ; nested list (lambda (x)
(+ x 1))其实就是匿名函数，等同于 javascript 里的:
function(x){
return x + 1;
}- 基本操作符，built-in 函数
注意这里不是在说 Lisp 的 7 公理，也不是列出所有 scheme 的 built-in 函数，而是在The Little Schemer中必需的函数
quote
(quote x)返回 x, 等价的写法是'x,'是一个语法糖。quote 的作用是区分代码和数据，比如(+ 1 2)表示代码，执行结果为 3；而'(+ 1 2)表示数据，执行结果为(+ 1 2)这个 listcons, 用来构造 list
(cons 'a 'b)返回(a . b), 这个叫做 dotted pair。 dotted pair 是 list 的基本组成元素，(cons 'a '())返回的是(a . ()), 我们将这种结构叫做 list, 并简写为(a)；同理，(cons 'a '(b))返回(a . (b . ())), 我们简写为(a b)car, 返回 list 的第一个元素
(car '(a b)返回acdr, 返回除第一个元素的所有元素组成的表
(cdr '(a b c))返回(b c)cond, and, or, not, 条件语句
(cond (condition1 return1) (condition2 return2) ... else default)null?, 判断是否为空 list
(null? '())返回#t,(null? OTHERS)返回#feq?, 判断是否相等
atom?, 判断是否为 atom, 不是 list 的就是 atom
zero?, 判断数字是否为 0
add1, 数字加 1
sub1, 数字减 1
number?, 判断是否为数字
好了，没有了，就这些，让我们开始奇妙的编程之旅吧！
等等‼ 纳尼？就这些？它喵的，+、-、*、/、>、<都没有, for loop, while loop 也没有，这能编程？😮
别急，让我们一点点来，让我们尝试去构造它们，看看那些熟悉的编程元素，是否真的必不可少。在这个过程里，也让我们去思考也去寻找，有关编程的一些更本质的东西。
recursion(递归)
没有循环，那我们如何去处理重复操作？答案是递归。比如阶乘：
(define fact
(lambda (x)
(cond
((eq? x 1) 1)
(else (* x (fact (- x 1)))))))递归强大而易读，有简洁的数学美。我们只需要：
- 设置一个
终止条件，以便递归返回，比如(eq? x 1)则返回1 - 改变参数值，让它
朝终止条件靠近(这样才能最终结束)，比如(- x 1) - 以新的参数，递归调用自身，此时我们
假设这个函数已经是 work 的，并以此填充表达式
可以看到，递归和数学归纳法十分类似：先考虑x = 1的情况，再假设x = k - 1时是 work 的，然后考虑x = k时的情况。这个过程充分展现了强大的数学美。
然而，我们常常听到一个说法：避免递归，多用循环(迭代)。这在一般情况下（比如 c、java 程序里）是正确的，因为递归会不断进行函数调用，系统需要保存调用信息和返回地址到调用栈，这样不仅性能慢，而且容易栈溢出。
但是在函数式编程语言里，一般都支持尾递归优化（javascript 的话，ES6 将支持尾递归优化, excited!），可以很好的解决这个问题。不过在这里我们主要考虑编程的思想，优化之类的问题先不多谈。
另外，如果细心的话，你可能会发现，刚才的阶乘算法里的define, 并不在之前提到的 built-in 的 list 里。实际上，define 也可以只是一个语法糖。难道给函数命名也不是必需的？关于这一点，我们会在之后的Y-combinator一节得到答案。而现在，让我们先认为 define 存在并且 work。
实现加减乘除
让我们来实现那些基本的运算。注意，我们暂时只考虑自然数的情况。
- 加法
我们可以使用add1, sub1以及zero?来实现加法。对于n + m, 当m为0时，返回n，这是设置一个停止条件；然后让m往0逼近，递归调用加法函数即可。代码如下:
(define +
(lambda (n m)
(cond
((zero? m) n)
(else (add1 (+ n (sub1 m)))))))- 减法
(define -
(lambda (n m)
(cond
((zero? m) n)
(else (sub1 (- n (sub1 m)))))))- 乘法, 有了加法，乘法就自然有了
(define *
(lambda (n m)
(cond
((zero? m) 0)
(else (+ n (* n (sub1 m)))))))>,<, 还有数字的=, 因为eq?是一个更大的 scope
;; define >
(define >
(lambda (n m)
(cond
((zero? n) #f)
((zero? m) #t)
(else (> (sub1 n) (sub1 m))))))
;; define <
(define <
(lambda (n m)
(cond
((zero? m) #f)
((zero? n) #t)
(else (< (sub1 n) (sub1 m))))))
;; define =
(define =
(lambda (n m)
(cond
((> n m) #f)
((< n m) #f)
(else #t))))- 除法
(define /
(lambda (n m)
(cond
((< n m) 0)
(else (add1 (/ (- n m) m))))))- 求余
(define %
(lambda (n m)
(cond
((< n m) n)
((= n m) 0)
(else
(% (- n m) m)))))漂亮！可以看到，通过 lambda 和递归，我们只使用zero?, add1, sub1，便实现了加减乘除，求余，还有大于、小于、相等的判定功能。🙂
邱奇数
值得一题的是，The Little Schemer里还略微探讨了一下类似邱奇数的问题，当然不是真的邱奇数，而是类似邱奇数的简化版，且同样只考虑自然数。
简单的说，就是用()表示 0，(())表示 1，(()())表示 2，循环往复。
;; use '() to represent 0, '(()) represent 1
(define sero?
(lambda (n)
(null? n)))
(define edd1
(lambda (n)
(cons '() n)))
(define zub1
(lambda (n)
(cdr n)))以上是新版本的zero?, add1和sub1。有了这几个，根据上一节的 code，我们就可以抛开数字，玩转各种运算了!😏
常用数据结构和操作
Scheme 里只有链表，不过，其它数据结构都可以由链表来模拟或生成，比如 array, set, map(table)
当数组用：
;; (pick n lat), get the element of lat in position n
(define pick
(lambda (n lat)
(cond
((zero? (sub1 n)) (car lat))
(else (pick (sub1 n) (cdr lat))))))Set:
;; makeset, make a lat to a set
(define makeset
(lambda (lat)
(cond
((null? lat) '())
((member? (car lat) (cdr lat))
(makeset (cdr lat)))
(else (cons (car lat) (makeset (cdr lat)))))))这里member?的代码就不贴出了
关于 Table(map), 我们一般会构造Entry这样的结构，在 scheme 里可以表示为(keys values)这样的形式，而table(map)就是entry的 list。
至于一些相应的操作方法，由于本文并非流水帐(😅), 此处就不贴出了
continuation
跟着The Little Schemer的步伐，我们会一路 build 出越来越复杂的方法，也会开始学会abstract, 通过复用来简化 code。不过，这些其实也并没有太出彩的地方。
但到了第 8 章，我们将会碰到一个神奇的东西，continuation。
讲 continuation 之前，我先简单说一下continuation-passing style (CPS)。 在 JavaScript 程序里, 我们经常会用到回调函数，比如 ajax call：
$.getJSON("ajax/test.json", function (data) {
console.log(data);
});getJSON异步拿到数据后，便会执行 pass 进去的 function，而这个 funcion 就是 continuation 了。
有朋友可能会觉得，哎哟，不就是回调嘛，这有什么了不起的？
当然不只是回调。所谓 continuation，其实是对程序的控制流的抽象表示。上面的例子里，getJSON执行完后，控制流转到传入的匿名函数，在这里，实际上控制流是由我们所控制。 如果使用这种 style，我们甚至不再需要return。 比如将
function f(a) {
return a;
}改成：
function f(a, continuation) {
continuation(a);
}事实上很多编译器都会做这种事情。
而更重要的是，使用 Continuation 我们可以实现更复杂的控制流，比如Exception(try-catch block), coroutine(协程), generator
对于编译器来说，可以容易的把这些复杂的结构脱糖处理，变成简单的 CPS，这将极大的简化编译器的实现。
关于 continuation 的话题可以非常大，这里篇幅有限，暂不深入讨论。我将单独开一篇博文详谈。
回到The Little Schemer, 我不得不贴一下里面讲解 continuation 的 code, 非常之赞，因为真正的在解决问题，而不是如我这样空泛的举例:
(define multirember&co
;; param: atom, list, collector
(lambda (a l col)
(cond
((null? l)
(col '() '()))
((equal? a (car l))
(multirember&co a (cdr l)
;; 每次(cdr l), 都包一次col, seen经过(cons (car l))，收集了所有等于a的atom
(lambda (newlat seen)
(col newlat
(cons (car l) seen)))))
(else
(multirember&co a (cdr l)
(lambda (newlat seen)
(col (cons (car l) newlat) seen)))))))这里很重要的一点是，我们现在并没有提供局部变量的功能，但是通过 continuation 来巧妙的做 collect 工作。从这个角度来讲，局部变量也可以是语法糖!
为了便于不熟悉 scheme 的人理解，我用 javascript 翻译了一下，可在 chrome develop tool 或者 firebug 里 have a try。注意，里面的局部变量仅仅是为了写的方便，理解这个意思就行。
var multirember = function (a, arr, collector) {
var tmp;
if (arr.length === 0) {
return collector([], []);
} else {
tmp = arr.shift();
if (a === tmp) {
return multirember(a, arr, function (notseen, seen) {
seen = [a].concat(seen);
return collector(notseen, seen);
});
} else {
return multirember(a, arr, function (notseen, seen) {
notseen = [tmp].concat(notseen);
return collector(notseen, seen);
});
}
}
};
multirember(1, [1, 2, 3, 1, 4, 5, 1, 6], function (notseen, seen) {
console.log("notseen is: " + notseen);
return console.log("seen is: " + seen);
});
// result:
// notseen is: 2,3,4,5,6
// seen is: 1,1,1halting problem
经过 continuation 的一知半解和意犹未尽，让我们缓一缓，来看看停机问题。所谓停机问题，就是判断任意一个程序是否会在有限的时间之内结束运行的问题。
首先，我们写一个无限递归永不停机的函数：
(define eternity
(lambda (x)
(eternity x)))然后，我们假设存在一个函数will-stop?能判断一个函数是否会停机。然后我们再构建一个绝妙的矛盾的函数：
(define last-try
(lambda (x)
(and (will-stop? last-try)
(eternity x))))如果last-try会停机，即(will-stop? last-try)返回#t，将执行eternity，于是无限递归永不停机；如果last-try不会停机，即(will-stop? last-try)返回#f，last-try 停机并返回#f。 无论哪种情况，都是矛盾的，于是证明will-stop?不存在，停机问题得解。
这样看起来还是蛮简单的嘛，不过，没看过我肯定想不出来。。。啥也不说了，拜谢图灵!
Y Combinator
在The Little Schemer第九章里，还有一个大名鼎鼎的东西，Y combinator。我也曾看过一些关于它的文章，但大多都深奥晦涩，难以捉摸。而在The Little Schemer里，完全用 code 的方式来一步步引导出来，不过，为了接受度，且让我使用 js 来描述。
还记得我们之前提到define其实不是必需的么？想一想，如果我们只有 lambda，也就是只有匿名函数，可以实现递归么？
让我们试一试。
从一个简单的递归开始：
var f = function (n) {
if (n == 1) {
return 1;
} else {
return n * f(n - 1);
}
};由于只有匿名函数，所以f(n-1)是不存在的，那么这个写法就不正确了。
不过，如果我们能给出真正的递归函数f，那我们就可以写出以下的函数:
var F = function (f) {
return function (n) {
if (n == 1) {
return 1;
} else {
return n * f(n - 1);
}
};
};这个函数是可以给出的，因为f(n-1)里的f是外界传进来的，所以它是有意义的。而var F, 我们可以当做语法糖，因为函数定义里没有引用到它。不过，给出了F也不能解决问题，因为我们不知道如何给出f。
但是没关系，让我们一点点尝试，或许能慢慢逼近正确答案。
让我们看看F(f)的结果是什么?
// F(f)的展开
function(n){
if (n == 1){
return 1;
} else {
return n * f(n-1);
}
}这个f是我们传进去的真正的递归函数，而如果 f 是真正的递归函数，那么很明显，F(f)就是f本身。
也就是说，F(f) = f。很好，虽然我们还不能给出f，但我们能给出F，并找到了F和f的关系。让我们继续尝试，看能否通过F来最终找到f。
我们现在知道，F(f)就等于我们要找的递归函数。而 F 和 f 的定义看起来是很类似的，那我们来试试F(F)。F(F)展开的结果是:
// F(F)的展开
function(n){
if (n == 1){
return 1;
} else {
return n * F(n-1);
}
}你应该能注意到，F(n-1)不对，因为F接受一个函数作为参数。而如果从理论上递归函数的定义来看，应该是F(F)(n-1)才对。可以做到么？可以！我们再写一个函数 G:
var G = function (f) {
return function (n) {
if (n == 1) {
return 1;
} else {
return n * f(f)(n - 1); // 注意是f(f)
}
};
};这里G和F唯一的区别就是里面递归调用的是f(f)而不是f。现在G(G)的展开里会是这样：
// G(G)的展开
function(n){
if (n == 1){
return 1;
} else {
return n * G(G)(n-1);
}
}这不就是递归函数的定义么？看起来似乎没什么问题，G的定义里并没有引用G，那么理论上说G(G)就是我们的递归函数了。 让我们来测试一下，G(G)(5); // return 120，漂亮！我们成功了！原来只需要匿名函数，我们就可以实现递归！🍻
不过，稍等一下，还差一点点，这还不是 Y-combinator，因为还不够美。让我们更进一步，把f(f)再抽象一下:
var G = function (f) {
return (function (f) {
return function (n) {
if (n === 1) {
return 1;
} else {
return n * f(n - 1);
}
};
})(f(f));
};不难看出，这个定义等价于之前G的定义。 而根据之前的F的定义，这实际上就是:
var G = function (f) {
return F(f(f));
};由于G(G)是我们的递归函数，于是我们可以定义函数 Y，使得Y(F) == G(G):
var Y = function (F) {
var G = function (f) {
return F(f(f));
};
return G(G);
};这个Y就是我们的 Y-combinator 了，只要把一个形似F的函数丢给Y，就可以获得一个完美的递归函数了！ 我们已经测试过了G(G), 让我们再试试Y(F)。咦，不对啊，Maximum call stack size exceeded，难道我们推理有误？
好吧，这是最后一个坑了。问题出在F(f(f))，实际上我们需要在else分支执行f(f)(n-1)，而由于 JS 是没有Lazy Evaluation的，于是F(f(f))里的f(f)会直接执行。让我们来 fix 这个 bug:
var Y = function (F) {
var G = function (f) {
return F(function (x) {
return f(f)(x);
});
};
return G(G);
};最后，让我们把语法糖去掉，看看完全匿名函数写成的递归函数:
(function (F) {
return (function (G) {
return G(G);
})(function (f) {
return F(function (x) {
return f(f)(x);
});
});
})(function (f) {
return function (n) {
if (n == 1) {
return 1;
} else {
return n * f(n - 1);
}
};
})(5); // output 120😆
Interpreter
The Little Schemer的第十章，主要是讲如何用 scheme 实现一个简单的 scheme 解释器，虽然只支持 built-in 的方法和 lambda，但已然十分强大，其实现过程真正体现了数据即程序的特点。不过这个 code 就真是一大坨了，在此就不张贴了。要看 code 的戳这里
Commandments
最后，The Little Schemer里总结了十条诫律，非常有价值，在此罗列如下
- Always ask, null? for atom/lat, zero? for number; when S-expression, ask (null? l), (atom? (car l)) and else.
- cons => use to build list
- When build a list, describe the first typical element, and then cons it onto the natural recursion
- Always change at least one argument while recurring.(否则无法停止). It must be changed to be closer to termination. When lat, use (cdr lat); when number, use (sub1 n); when S-expression, use (car l) and (cdr l) if (null? l) is false and (atom? (car l)) is false
- 考虑终止条件，应选择不改变当前 value 的条件: when +, use 0; when *, use 1; when cons, use ()
- Simplify only after the function is correct, 当之前的函数是正确的时候，可以利用相互递归来简化它们。 如
eqlist?和equal?互相依赖 - Recur on the subparts that are of the same nature:
- On the sublists of a list
- On the sub expressions of an arithmetic expression
- Use help functions to abstract from representations
Abstractcommon patterns with a new function.- Build functions to collect more than one value at a time. 通过包装 function 产生新的 function, 让新的 function 来 collect 本次调用产生的数据
Code
所有 code 放在这里，如果真有人想看的话 :no_mouth: