Friedman 啊,把这样一个问题作为“智力题”,真有你的!我开玩笑地对他说:“我保证,我不会把这个程序开源,不然以后你的 C311 学生们就可以拿来作弊了。”回到家,我开始看那篇 Danvy 和 Filinski 的论文。这篇 1991 年的论文的想法,是从 1975 年一篇 Gordon Plotkin 的论文的基础上经过一系列繁琐的推导得出来的,而它最后的结果几乎跟我的程序一模一样,只不过我的程序可以处理更加复杂的 Scheme,而不只是 lambda calculus。我之前完全不知道 Plotkin 的做法,从而完全没有收到他的思想的影响,直接就得到了最好的结果。这是我第一次认识到自己头脑的威力。
第二个学期,当我去上 Friedman 的进阶课程 B621 的时候,他给我们出了同样的题目。两个星期下来,没有其它人真正的做对了。最后他对全班同学说:“现在请王垠给大家讲一下他的做法。你们要听仔细了哦。这个程序价值100美元!”
下面就是我的程序对于 lambda calculus 的缩减版本。我怎么也没想到,这短短 30 行代码耗费了很多人 10 年的时间才琢磨出来。
(define cps (lambda (exp) (letrec ([trivs '(zero? add1 sub1)] [id (lambda (v) v)] [C~ (lambda (v) `(k ,v))] [fv (let ((n -1)) (lambda () (set! n (+ 1 n)) (string->symbol (string-append "v" (number->string n)))))] [cps1 (lambda (exp C) (pmatch exp [,x (guard (not (pair? x))) (C x)] [(lambda (,x) ,body) (C `(lambda (,x k) ,(cps1 body C~)))] [(,rator ,rand) (cps1 rator (lambda (r) (cps1 rand (lambda (d) (cond [(memq r trivs) (C `(,r ,d))] [(eq? C C~) ; tail call `(,r ,d k)] [else (let ([v* (fv)]) `(,r ,d (lambda (,v*) ,(C v*))))])))))]))]) (cps1 exp id)))) 而这还不是 B621 的全部,每一个星期 Friedman 会在黑板上写下一道很难的题目。他不让你看书或者看论文。他有时甚至不告诉你题目里相关概念的名字,或者故意给它们起个新名字,让你想查都查不到。他要求你完全靠自己把这些难题解出来,下一个星期的时候在黑板上给其它同学讲解。他没有明确的评分标准,让你感觉完全没有成绩的压力。
这些题目包括一些很难的问题, 比如 church numeral 的前驱 (predecessor)。这个问题,当年是 Stephen Kleene (图灵的学长) 花了三个月冥思苦想才做出来的。不幸的是我在 Cornell 就学到了 Kleene 的做法,造成了思维的定势,所以这个训练当时对我来说失去了意义。而我们班上却有一个数学系的同学,出人意料的在一个星期之内做出了一个比 Kleene 还要简单的方法。他的完整的代码(用传统的 lambda calculus 语法表示)如下:
λn w z. ((n λl h. h (l w)) (λd.z)) (λx.x) 其它的问题包括从 lambda calculus 到 SKI combinator 的编译器,逻辑式(可逆)CPS 变换,实现 Hindley-Milner 类型系统,等等。我发现,就算自认为明白了的东西,经过一番思索,认识居然还可以更进一步。
当然,重新发明东西并不会给我带来论文发表,但是它却给我带来了更重要的东西,这就是独立的思考能力。一旦一个东西被你“想”出来,而不是从别人那里 “学”过来,那么你就知道这个想法是如何产生的。这比起直接学会这个想法要有用很多,因为你知道这里面所有的细节和犯过的错误。而最重要的,其实是由此得到的直觉。如果直接去看别人的书或者论文,你就很难得到这种直觉,因为一般人写论文都会把直觉埋藏在一堆符号公式之下,让你看不到背后的真实想法。如果得到了直觉,下一次遇到类似的问题,你就有可能很快的利用已有的直觉来解决新的问题。
而这一切都已经发生在我身上。比如在听说 ANF 之后,我没有看 Amr Sabry 的论文,只把我原来的 CPSer 程序改了一点点,就得到了 ANF 变换,整个过程只花了十几分钟。而在 R. Kent Dybvig 的编译器课程上,我利用 CPS 变换里面的直觉,改造和合并了 Dybvig 提供的编译器框架的好几个 pass,使得它们变得比原来短小好几倍,却生成更好的代码。
第二个学期,当我去上 Friedman 的进阶课程 B621 的时候,他给我们出了同样的题目。两个星期下来,没有其它人真正的做对了。最后他对全班同学说:“现在请王垠给大家讲一下他的做法。你们要听仔细了哦。这个程序价值100美元!”
下面就是我的程序对于 lambda calculus 的缩减版本。我怎么也没想到,这短短 30 行代码耗费了很多人 10 年的时间才琢磨出来。
(define cps (lambda (exp) (letrec ([trivs '(zero? add1 sub1)] [id (lambda (v) v)] [C~ (lambda (v) `(k ,v))] [fv (let ((n -1)) (lambda () (set! n (+ 1 n)) (string->symbol (string-append "v" (number->string n)))))] [cps1 (lambda (exp C) (pmatch exp [,x (guard (not (pair? x))) (C x)] [(lambda (,x) ,body) (C `(lambda (,x k) ,(cps1 body C~)))] [(,rator ,rand) (cps1 rator (lambda (r) (cps1 rand (lambda (d) (cond [(memq r trivs) (C `(,r ,d))] [(eq? C C~) ; tail call `(,r ,d k)] [else (let ([v* (fv)]) `(,r ,d (lambda (,v*) ,(C v*))))])))))]))]) (cps1 exp id)))) 而这还不是 B621 的全部,每一个星期 Friedman 会在黑板上写下一道很难的题目。他不让你看书或者看论文。他有时甚至不告诉你题目里相关概念的名字,或者故意给它们起个新名字,让你想查都查不到。他要求你完全靠自己把这些难题解出来,下一个星期的时候在黑板上给其它同学讲解。他没有明确的评分标准,让你感觉完全没有成绩的压力。
这些题目包括一些很难的问题, 比如 church numeral 的前驱 (predecessor)。这个问题,当年是 Stephen Kleene (图灵的学长) 花了三个月冥思苦想才做出来的。不幸的是我在 Cornell 就学到了 Kleene 的做法,造成了思维的定势,所以这个训练当时对我来说失去了意义。而我们班上却有一个数学系的同学,出人意料的在一个星期之内做出了一个比 Kleene 还要简单的方法。他的完整的代码(用传统的 lambda calculus 语法表示)如下:
λn w z. ((n λl h. h (l w)) (λd.z)) (λx.x) 其它的问题包括从 lambda calculus 到 SKI combinator 的编译器,逻辑式(可逆)CPS 变换,实现 Hindley-Milner 类型系统,等等。我发现,就算自认为明白了的东西,经过一番思索,认识居然还可以更进一步。
当然,重新发明东西并不会给我带来论文发表,但是它却给我带来了更重要的东西,这就是独立的思考能力。一旦一个东西被你“想”出来,而不是从别人那里 “学”过来,那么你就知道这个想法是如何产生的。这比起直接学会这个想法要有用很多,因为你知道这里面所有的细节和犯过的错误。而最重要的,其实是由此得到的直觉。如果直接去看别人的书或者论文,你就很难得到这种直觉,因为一般人写论文都会把直觉埋藏在一堆符号公式之下,让你看不到背后的真实想法。如果得到了直觉,下一次遇到类似的问题,你就有可能很快的利用已有的直觉来解决新的问题。
而这一切都已经发生在我身上。比如在听说 ANF 之后,我没有看 Amr Sabry 的论文,只把我原来的 CPSer 程序改了一点点,就得到了 ANF 变换,整个过程只花了十几分钟。而在 R. Kent Dybvig 的编译器课程上,我利用 CPS 变换里面的直觉,改造和合并了 Dybvig 提供的编译器框架的好几个 pass,使得它们变得比原来短小好几倍,却生成更好的代码。