今晚想学习Scheme。
总算把Udi Manber 大师的《Introduction to Algorithms: A Creative Approach》的数学归纳法看完了，说来丢脸……，加起来看5个小时※如果归纳法在组合算法中真有如此神奇的话，那么Scheme所代表的函数式语言，把程序定义为都是一群只需要通过Evaluator就可以得到结果的list，那么算法就真的简单了。可惜，所谓递归不如非递归程序的观点在我的头脑中根深蒂固，唉，所谓的函数调用从来只是为了简化程序做模块而已。
言归正传。
Scheme的历史就省略了，反正它只认得一种数据结构：list。
关于数据结构：Scheme中的数据类型比较简单，写什么就是什么，字符变量都以#/形式做前缀。此外还有bool，number，character，string，vector，dotted-pair,，list，，procedure，form数据类型。Scheme默认的data是lexical常量，为了指定一个symbol变量的引用，需要使用' 做前缀或者使用带谓词的表(quote symbol-x)。
关于控制结构：Scheme提供类似C的if-（else），cond，case，when，unless的分支选择结构（没有循环结构？）。注意使用if时，else分支是隐含在if分支之后的，一般进行入口检查使用when就好了。
关于程序块：Scheme中的程序块称为form，也是一种可以evaluate的“数据”。过程procedure也是可以evaluate的，不同于pascal中无返回值的procedure。procedure使用lambda form来定义的。实际上，
The values bound to lexical variables can be procedures:
(let ((cons (lambda (x y) (+ x y))))
(cons 1 2))
=> 3
（用一个lambda form来给cons symbol赋值：（※＃◎～～）
关于程序结构与变量作用域：定义一个symbol变量使用谓词define定义global变量，使用谓词let定义local变量，可以嵌套定义（value-bind）。特别的是local变量，谓词let的对参数symbol的绑定作用域在let form程序快中，每次let只查询一次。
The local variable initializations -- x to 1; y to 2; z to 3 -- are not considered part of the let body. Therefore, a reference to x in the initialization will refer to the global, not the local x:
(let ((x 1)
(y x))
(+ x y))
=> 21
This is because x is bound to 1, and y is bound to the global x, which is 20.
The x in y's initialization refers to the x just above. The example is entirely equivalent to -- and is in fact intended to be a convenient abbreviation for -- the following program with nested lets:
(let ((x 1))
(let ((y x))
(+ x y)))
=> 2
Scheme本身是一个evaluator（评估器）（类似堆栈计算机？），递归程序设计是它的特长。变量的定义和作用域在scheme中的一个例子如下：
(letrec ((local-even? (lambda (n)
(if (= n 0) #t
(local-odd? (- n 1)))))
(local-odd? (lambda (n)
(if (= n 0) #f
(local-even? (- n 1))))))
(list (local-even? 23) (local-odd? 23)))
The lexical variables introduced by a letrec are visible not only in the letrec-body but also within all the initializations. letrec is thus tailor-made for defining recursive and mutually recursive local procedures.
（即letrec相当于static local，let while record ）
但letrec的用途远不在此，而是用于循环（注意到一般的控制结构谓词中没有while）：
recursive procedure defined using letrec can describe loops. Let's say we want to display a countdown from 10:
(letrec ((countdown (lambda (i)
(if (= i 0) 'liftoff
(begin
(display i)
(newline)
(countdown (- i 1)))))))
(countdown 10))
This outputs on the console the numbers 10 down to 1, and returns the result liftoff.
更方便的做法是命名这样一个循环，令人费解的是，此时let完全是一个macro（宏），而且在宏中的变量似乎能够递归替换，具有了letrec的功效。
Scheme allows a variant of let called named let to write this kind of loop more compactly:
(let countdown ((i 10))
(if (= i 0) 'liftoff
(begin
(display i)
(newline)
(countdown (- i 1)))))
Note the presence of a variable identifying the loop immediately after the let. This program is equivalent to the one written with letrec. You may consider the named let to be a macro (chap 8) expanding to the letrec form.
--------------------------------------------------下文中提到一个概念“(tail-recursive 尾递归”------------to be continued...
Udi Manber，国际算法大师，在线信息搜索引擎的先驱，现Amazon.com的副总裁兼首席算法师（CAO），“A Creative Approach”提出一种用数学归纳法来设计递归的组合算法程序的新方法。说到挖掘recurse 在程序设计中的潜力，其实，MIT早就用scheme讲授算法设计入门了……