[一]Scheme Toy - 基础篇

最初写在自己的QQ空间(!)上，这是第一批内容的全部。
备份过来，未作修订，之后的内容依然要坑着一段时间。


* Scheme Toy #1 Prologue
ee.zsy 2010年12月08日 23:07

选择了一个话题，打算来一天一更新。
方向是内容浅显，丰富有趣，字数短小。
Ok，第一天就这么些内容，算个预告。
嘛...自己也想不出能写多少东西...就开篇了哦！

下节预告：Scheme Toy #2 Expression
 


* Scheme Toy #2 Expression
ee.zsy 2010年12月09日 22:59

那啥...昨天说有第二篇...今天就有第二篇了...来着...
虽然内容几乎于白话废话，不过当日历看也是可以的嘛...

首先来假设一个情景：篮子里有三个鸡蛋，一天吃掉一个，吃两天后还剩几个？
根据小学的知识我们会去求 3 - 1 * 2 的值，计算结果就是所需要的答案。
并且我们不会把结果计算为4，因为我们知道要先算乘法，而且知道鸡蛋不可能越吃越多。
现在，我们换种形式来表示这个算式，例如使用前缀表示法:
- 3 * 1 2，它的计算结果依然为1。
在操作符的操作数不固定时，我们可以添加括号消除歧义：
(- 3 (* 1 2))，它的计算结果依然等于1。
同时利用这种形式，我们也可以表达更多的运算如：
（+ (sqrt 4) 1），它是4开方后与1的和，计算结果为3。

现在，欢迎我们的主角Scheme登场，它可以用来帮我们求上述表达式的值。
本文附件提供一份编译好的TinyScheme系统，可以下载后使用。
它遵循REPL模型，也就是Read-Eval-Print-Loop模型的意思。
我们可以直接告诉Scheme要求值的表达式，然后输入回车。
系统会计算并返回结果，然后等待新的输入进行下一步操作。
Ok，本文读者可以随意尝试了，用Scheme来做计算器使用，算一些想算的东西。
例如输入(+ 1 1)然后回车，屏幕上会显示一个鲜明的结果 2 给我们。

那么，在本文结束前，再为了使用时概念更清晰一些，我们再接触两个新的名词。
首先是List，中文是列表的意思。在Scheme中List表现为括号包裹，元素用空格隔开的形式：
例如(+ 1 1)就是我们写下的一个有三个元素的List。
List可以嵌套，例如(+ 3 (* 5 6))也是有三个元素的List，其中的第三个元素也是一个List。
第二个要说的名词呢，叫S-expression，或者称之为符号表达式，它就是上述List所用的书写形式。
当需要执行S-expression时，Scheme可以对我们书写的表达式进行求值，它的求值规则是：
以S-expression第一个元素为operator运算符，其余元素为operand操作数，进行运算。

这个...就是Day 2的一篇了...虽然文字故意写得偏低龄化了...
内容虽然看起来说了不少...其实说白了...就是个计算器使用指南...
嘛...明天如果写的话...也还是会没什么特别的东西的...
并且...今天开始正文似乎有点话多了...就这样...
至于本文的意义呢...就是想说明...计算器还是个很有趣的东西的...
同样...Scheme也是...

下节预告：Scheme Toy #3 Lambda

附件：TScm.zip TinyScheme 一份编译好的不到40k的Scheme实现


* Scheme Toy #3 Lambda
ee.zsy 2010年12月10日 23:55

继续写日历...算是简短的科普性质文字...

昨天说到，S-expression可以用来被求值，比如做一些数学运算的。
当然不只二元四则运算，也可以是：
(> 0 (+ 3 4)) 得到 #f
(= (+ 1 1) 2) 得到 #t
(* 1 2 3 4 5) 得到 120
(max 2 5 7) 得到 7
它们的特点是子列表会先被求值，然后作为参数去求父列表的值。
而每个列表的第一个元素，如昨天所说，作为对所有参数的操作符。

上述的操作符被称为Procedure，中文是“过程”的意思，用来表示一种运算。
此外也若干有不符合上述求职规则的Special Form，例如这里要介绍的Lambda。
这里的Lambda源自λ演算，是一个和函数相关的形式系统，可以用来定义Procedure。
例如 (lambda (x) (* 2 x)) 就定义了一个过程，它接受一个参数，并返回参数值的两倍。
我们可以依照对一般proc的方式来使用它，完整的写下来就是：
((lambda (x) (* 2 x)) 6) 运算得12。
这里的Lambda运算符将以其第一个操作数为参数列表，对剩余操作数求值，并返回最后一个操作数的结果。
这看起来很简单，但是复杂与神奇的东西就将由这简单的规则组成，请发挥想象哦。
先简单的说比如这个((lambda (f) (f 1 1)) (lambda (x y) (+ x y)))的结果是 2 ，很明显吧^_^

下节预告：Scheme Toy #3 Binding
 


* Scheme Toy #4 Binding
ee.zsy 2010年12月11日 22:28

昨天已经把基本的背景知识介绍完了，下面的主要内容是用sexp和lambda玩Syntactic sugar。
语法糖衣虽然是建立在原有的概念之上，不过会方便我们的理解和复用，也可由去发现其妙的事情。
先接着昨天最后一个表达式 ((lambda (f) (f 1 1)) (lambda (x y) (+ x y))) 说：
该表达式列表由两个元素组成，这两个元素都是进行Lambda运算，求值后结果是两个不同的proc。
其中第二个lambda表达式是定义了一个二元运算，参数是x和y，调用结果是返回x与y的和。
其中第一个lambda表达式需要一个参数f，其返回值是用操作f对参数1和1求值。
同时根据我们sexp的规则，整个表达式的结果是把第二个lambda表达式作为参数去求第一个lambda表达式的值。
也就是把用第二个lambda代替第一个lambda表达式中的 f 对操作数 1 和 1 进行求值，那么结果就是 2 了.

以上的一段文字看起来像是解释，不过实际目的呢，是来介绍一下 binding，也就是绑定的意思。
在上述的求值过程中发生了两次绑定操作，这里只解释其中的一个，就是其中求子表达式（f 1 1）的时候。
其中的 f 已经被绑定到了 (lambda (x y) (+ x y)) 这个表达式所返回的proc上了。
我们可以称这个proc为一个值Value，或者称之为一个对象Object，它和数字都可以作为lambda运算求值时的参数使用。
我们也可以尝试另一种写法：
(let
  (
    (one 1)
    (add (lambda (x y) (+ x y)))
  )
  (add one one))
这里的新介绍的let看起来是个新的form，它的第一个操作符是一个绑定列表，每个绑定写为一个二元列表。
不过我想已经不需要解释let的存在，它只是lambda表达式的一个语法糖衣糖衣而已，两者是等价的。
虽然Scheme内建的macro系统可以自动把let用lambda表达式替换掉，不过用let可以使绑定显示得明显些。

最后留下一个小小的疑问，开头说使用sexp和lambda，那么这里不是出现了奇怪的东西了吗？
比如这个 1 ，比如这个 + ，虽然它们是源于生活中，可以为什么在可以在这里存在呢。
那么下面的例子里就定义我们用到的整数零，加一运算 以及 求和运算：
(let (
 (zero (lambda (f) (lambda (x) x)))
 (add-1 (lambda (n) (lambda (f) (lambda (x) (f ((n f) x))))))
 (add (lambda (x y) (lambda (f) (lambda (x) ((x f) ((y f) x))))))
)
 (add (add-1 zero) (add-1 zero))
)
这里的数字n is a function that takes a function f as argument and returns the n-th composition of f。
其运算和返回值也满足这样的约定，这便是lambda最神奇了的地方了。
虽然上面的表达式看起来有点晕，但依然只是用来最基本的规则，就这样。

不过为了方便，现实生活中的 1 和 + 都可以直接拿来使用的，它们已经有了最直观的定义。
例如(+ 1 1)的结果2，也和生活的数字 2 是表达了相同的含义，它们是被绑定好的。
我们称它们绑定的地方叫environment环境，环境是可以嵌套有内部环境和外部环境。
例如上面的lambda中的绑定便是一个内部绑定，它的存在意义仅存活于它这个表达式内。

今天的内容说完了 <- 从阅读统计上说估计没人看到这句的。

下节预告：Scheme Toy #3 Continuation


* Scheme Toy #5 Continuation
ee.zsy 2010年12月12日 23:06

继续写日历，虽然没什么内容，不过想把简单的事情表述清楚也不是件容易的事情。
现在回头看昨天写的东西，如果只是大略地一扫而过的话，自己也会头晕的。

如果先几天的文字让人不知所云呢，那么现在再把整个文本进行的思路简述一下：
首先是关于表达式，就是之前篇目里括号包裹的东西，可以计算并返回值。
这里我们使用的符号表达式是一种书写上的约定，它可以方便人之间的交流，也可以用工具来自动处理。
其次，在此之上，也就是说表达式的书写只是一种手段，我们所关注的是基本表达式的组合与抽象两个方面。
组合意味着以简单的元素去构建复杂的元素，抽象意味着以整体的单元代替实现的细节。
最后，通过对基本元素的抽象与组合，我们可以去解决一些与流程与数据有关的问题。
从实际的生活情境来写的话，本文的内容可以更清晰一些，给文本的展开提供一个清晰的目的。
不过为写着方便的话，这里还是依照某种逻辑关联来写了，即用前一篇的内容来推导后一篇的内容。
以上...这玩意儿...算写科普文吗...无语...

Ok，今天的正文开始。先看一个简单的表达式 (* (- 1) (+ -2 3)) 结果是 -1。
求值分两步进行，先求两个表达式的值，然后求积。然后我们换一种写法：
((lambda (x y) (* x y)) (- 1) (+ -2 3)) ，这样求值顺序可以更明显一些。
我们先求了(- 1)和(+ -2 3)的值，然后绑定到(x y)求(* x y)的值，然后返回结果。
用昨天的写法就是（为识别方便，同级表达式用同样的缩进）：
(let ((x (- 1))
      (y (+ -2 3)))
  (* x y))
这同样能看出明显的求值顺序，为了描述求值过程中的不同的状态，我介绍一个新的概念Continuation连续。
Continuation代表了一个子表达式返回结果后将要进行的计算，Continuation也是一种值，或称之对象。

暂且跳过怎么用call//cc来把continuation绑定到变量上，来说一个很有用的special form。它就是define，请看：
(define x 1)
(define f (lambda (x)(define n 1) (+ n x)))
(define (g x) (+ 1 x))
(+ (+ x 1) (f x) (g x))
返回的结果是 6。
define的作用是把表达式的值绑定到它所在环境的变量上，是不是新鲜的东西呢？
回答是否定的，绑定环境连续都是已经介绍过的概念，我们完全可以用let的嵌套来改写上面的define表达式。
不过为了帮助理解，这里再做一些说明：
1.第二行中变量x仅作用在lambda表达式中，与第一行的x无关。
2.第二行的n仅存在lambda中，如果第一行改为(define n 1)，那么与新写的n也无关。
3.第三行是define与lambda同时使用的缩写，写为把表达式绑定到一个列表上。
这样写的话，在形式上与使用上都可以按照定义函数来理解，我们可以把lambda看作一个匿名函数。

貌似..今天又写多了一点...内容继续简单化中...明天见哦...

下节预告：Scheme Toy #6 Closure


* Scheme Toy #6 Closure
ee.zsy 2010年12月13日 22:50

今天坑一回。
因为仅仅是为了存在而存在的一篇所以坑了。
发觉这部分没什么值得说的东西，就成了坑了。
面对坑，然后看见了一个坑了。
……

先看这个：
(define (n+ n) (lambda (x) (+ x n)))
(define n+1 (n+ 1))
(define n+2 (n+ 2))
(n+2 3)
结果是 5 。
这看起来是这样的：
第一行定义了函数 n+ ，它的执行结果是一个lambda创建的匿名函数。
第三行用参数 2 执行 n+ 函数，把返回的匿名函数绑定到 n+2 上。
第四行以 3 为参数使用 n+2 函数，并返回结果。
而实际呢，也确实就是这样的。不过还有一个要值得注意的是：
第一行中的匿名函数绑定了n+函数内部的变量 n。
这个变量 n 对全局环境不可见，但是在 n+ 函数内部是可见的。
于是ok，我们又有了一个新的概念叫Closure闭包，它是绑定了创建时局部环境的变量的匿名函数。
例如上面的第三行就是 执行(n+ 1)创建了一个闭包，并绑定到n+1上。
这个闭包在使用参数执行求值时可以使用它定义时的 n 的值。

然后在介绍一个操作符quote引用，它可以阻止表达式被求值：
(define a 1) => a
(+ 1 1) => 2
a =>1
(quote a) => a
(quote (+ 1 1)) => (+ 1 1)
为书写简单，我们使用一个单引号：
'a
'(+ 1 1)
并称第一行的为一个Symbol符号，第二行的为一个List列表。

最后再来说些新的形式：
(begin <expression1> <expression2> ...)
依次求值并返回最后一个表达式的值，是Lambda的一个语法糖衣。
可以结合 (display var) (display "hello") 使用，在表达式求值中显示一些东西。

看来还是得换一个更简略的文字风格为好...今天坑完了...

下节预告：Scheme Toy #6 Condition
 


* Scheme Toy #7 Condition
ee.zsy 2010年12月15日 21:01

Lambda演算除了可用来表示数量运算，也可以表示逻辑运算，例如：
TRUE := λxy.x
FALSE := λxy.y
IFTHENELSE := λpab.p a b
ISZERO := λn.n (λx.FALSE) TRUE
更多的就不做列举了，下面说用Scheme的表示方式：
1.逻辑值的写法 真#t ，假#f。判断时#f外都为真。
2.(if exp0 exp1 exp2) 根据exp0的值真假去求exp1或exp2的值。
3.if是special form不是procedure，因为不会先求全部参数的值。
3.(zero? 1) => #f 我们称返回逻辑值的过程为一个谓词，命名通常以?结尾。

ok，下面是一个例子，定义一个求绝对值运算abs函数。
它有一个参数，计算结果是其参数值的绝对值。
这个运算可以先用一个分段函数来定义它为：
abs(x)={x for x>=0,-x for x<0}
然后用Scheme的符号表达式重写得到：
(define (abs x) (if (>= x 0) x (- x)))
于是事情解决了，可以尝试 (abs -6) => 6。

以上让一个简单的数学公式变成了可执行的表达式。
当然，这也是做了一件很简单的事情，不过基于它我们可以实现很多有趣的东西哦。

下节预告：Scheme Toy #8 State
 


* Scheme Toy #8 State
ee.zsy 2010年12月15日 21:32

首先来看一个名词Pure Function纯函数，它要求一个函数：
1.对同样的参数总返回一致的结果，
2.求值过程中不产生副作用
常见的数学函数sin cos就属于纯函数，而random()这样返回随机结果的就不是纯函数。
上面还说到一个名词Side effect副作用，它的意思是值函数运行会改变函数所处环境的状态。
于是，我们可以说，一个纯函数是不受它环境状态的影响，也不会影响它所处环境的状态。
这里的环境，前面说过，是定义为层次状的，可以使用私有环境而不去影响全局环境。

在Scheme中我们可以用 set! 来改变一个对象的绑定，名称中的 ! 提醒我们这是一个会改变环境状态的操作。
我们可以有这样的写法：(set! x (f x))
这里的f是一个纯函数，在这条表达式中我们根据f有x的状态产生一个新的状态，并把这个状态绑定回x。
当然我们也可以把set!定义在f当中，然后执行 (f! x) ，这样的 f! 会产生副作用，便不是一个纯函数了。
一般而言，要尽量不要让函数有副作用，这会增加一些不必要的复杂性，并且不方便实行并行计算。

下面给一个例子，定义一个计数器counter过程，每次执行的结果+1。
(define (make-counter)
 (let ((n 0))(lambda () (set! n (+ n 1)) n)))
(define counter (make-counter))
(counter) ;=>1
(counter) ;=>2
(counter) ;=>3
以上n由于闭包的关系，只能在counter内使用，不过我们可以再 (define counter2 (make-counter))。
display会显示数据，也是一种副作用。对于分段函数用cond会比用if更直观一些 <- 这个是上一篇的补充。

副作用仅仅在需要改变环境状态的时候使用，而通常会去倾向使用基于参数得到结果这种状态的映射关系。

下节预告：Scheme Toy #9 Recursion
 


* Scheme Toy #9 Recursion
ee.zsy 2010年12月15日 22:00

这篇来思考一个简单的问题，如何求1到100的和，下面是一个类似问题的演示：

数学中有n!表示求1到自然数n的积，我们称这个为Factorial阶乘。
对于求n!，我们可以计算1*2*3...*n，特别的0!=1。
这样我们也可以定义一个函数fact，表示对于自然数n有：
fact(n)={1 for x=0,n*fact(n-1) for x>0}
然后再用Scheme中的符号表达式重写一遍：
(define (fact n) (cond ((zero? n) 1) (else (* n (fact (- n 1))))))
执行 (fact 4) =>24 ，1*2*3*4=24符合预期。
于是事情完成了，十分直观的样子。

这里可以看到，fact函数是递归定义的，它在求值过程中又以不同的参数使用了fact函数自身。
此外在实现fact函数的时候，我们只需要给出递归的定义，而不需要要去考虑计算中的重复过程。
于是我们的意识里有这样一些概念：
1.递归是可以用来优雅地表示重复的
2.去发现并声明问题本身，而抽象掉问题解决的过程。

下节预告：Scheme Toy #10 Iteration
 


* Scheme Toy #10 Iteration
ee.zsy 2010年12月17日 14:28

用前一篇递归的方式求阶乘，对于自然数n，当：
n=0 时，执行函数次数 1 ，执行乘法计算 0；
n=1 时，执行函数次数 2 ，执行乘法计算 1；
n=2 时，执行函数次数 3 ，执行乘法计算 2；
n=k-1 时，执行函数次数 k ，执行乘法计算 k-1；
n=k 时，执行函数次数 k+1 ，执行乘法计算 k。
因为每次执行函数需要保存先前执行函数的状态，再用返回值执行乘法。
所以对于计算n的阶乘而言，有n+1个临时状态的产生。

于是我们可以用尾递归修改先前写的表达式，以减少空间开销：
(define (fact n)
 (define (fact-iter n result)
  (if (zero? n) result (fact-iter (- n 1) (* result n))))
 (fact-iter n 1)
)
尾递归的意思是以函数调用作为返回结果，例如这里的fact-iter，其结果或者返回 result，或者直接调用fact-iter自身。
因为是返回了一个而函数调用，而不再对这个结果进行计算，所以在这个表达式的求值过程中，不再需要临时状态的保存。
不同于递归让一个问题的解通过另一个问题的解来表达，以上是通过一个状态到另一个新的状态的映射来表示重复的。
我们称上面的这种方式为迭代，其中n和result是参与迭代的变量，在Scheme中迭代用尾递归表示。

此外，以上的迭代过程可以看作{n -> n-1,result -> result*n for n>0} ，初始状态{n=k,result=1}，当n=0时result便是结果。
而为方便使用呢，有Named let做语法糖衣使用，上面的iterator也可以用let绑定来fact-iter的。

下节预告：Scheme Toy #11 Pair
 


* Scheme Toy #11 Pair
ee.zsy 2010年12月17日 15:24

这篇来说如何抽象的表示数据，在r5rs的可选特性中，执行(+ -2/3 1/3)会返回-1/3。
这就是说分数也是可以参与到表达式的求值当中的，下面就来演示一下如何实现复数运算。

演示之前先介绍一个新的数据类型，叫dotted pair点对，例如 '(1 . 2)。
一个pair有两个字段组成，书写时用. 点号分隔，这里用quote防止被求值。
空字段写作 '() empty list，如果第二个元素为空则写作 '(1 . ())了，两个元素都为空表并不等于一个空表
pair可作为我们用来构建复杂数据类型的基础，因为pair中的一个元素也可以是一个pair。

为了使用pair，我们有了如下新的概念：
predicate 谓词，用来对数据进行判断。
例如(pair? 1) => #f 判断是否为点对，(null? '()) => #t判断是否为空表。
constructor 构造器，用来构造数据。
例如 (cons 1 2) =>'(1 . 2) 用两个参数构造了一个点对。
selector 选择器，用来获取数据。
例如当x为'(2 . 1)时，(car x) =>2获取可一个元素，(cdr x) =>1 获取第二个元素。
对于immutable不可变的数据而言，对已有数据使用selector后可以再constructor建立新的数据。
对mutable可变的数据而言，可以定义mutator，也就是俗称setter的东西来改变数据。
从简化和安全的角度说，下面就只会用带不可变的数据来表现抽象的数据。
通过以上的方式我们就可以基于它们定义新的方法了。

有了pair，我们就可以用它来实现我们的复数类型了：
首先定义是constructor和selector
(define (make-rectangular real imag) (cons real imag))
(define (real-part complex) (car complex))
(define (imag-part complex) (cdr complex))
接下来定义若干运算符，例如加法运算：
(define (complex-add c1 c2)
 (make-rectangular
  ((+ (read-part c1)) (+ (real-part c2)))
  ((+ (imag-part c1)) (+ (imag-part c2)))))
这里是分别把实部和虚部相加，然后构造一个新的复数。
进而我们可以用更多数学类型实现numerical tower的Hierarchies of types和generic method。

以上只是一个基本的表示数据抽象的演示，其要点是：
我们基于数据提供的方法函数来使用数据，而抽象掉了数据实现的细节。

下节预告：Scheme Toy #11 List
 


* Scheme Toy #9.5 Hanoi
ee.zsy 2010年12月17日 16:47

汉诺塔问题，有三个柱子，n个从大到小的盘子在第一个柱子上：
当n=1时，1 -> C 移动一次；
当n=2时，1 -> B , 1 -> C ,2 -> C 移动三次；
当n=3时，1..2 -> B , 3 -> C,1..2 -> C 移动2*2+1；
当n=k时，1..(n-1) -> B, n -> C,1..(n-1) -> C 移动次数2*f(n-1)+1。
可以看出，每次移动分三步进行，其中的第二步是实际的移动操作。
于是得表达式：
(define (hanoi n)
 (define (move n from to helper)
  (if (> n 0)
      (begin (move (- n 1) from helper to) ;把1..(n-1)从目标from移到目标to上
             (display "move disk from ") (display from) ;执行
             (display " to ") (display to) (newline) ;移动
             (move (- n 1) helper to from)))) ;把1..(n-1)从目标helper移到目标to上
 (move n 'a 'c 'b)) ;把n个盘子从目标from 'a移到目标to 'c上
执行(hanoi 4)得到：
move disk from a to b
move disk from a to c
move disk from b to c
move disk from a to b
move disk from c to a
move disk from c to b
move disk from a to b
move disk from a to c
move disk from b to c
move disk from b to a
move disk from c to a
move disk from b to c
move disk from a to b
move disk from a to c
move disk from b to c
其中的移动次数建议用数学方法求一个O(1)的表达式，而不需要用到递归。

然后，顺便写个 prime? 用来判断素数：
素数的常用判断方法是对于大于1的自然数n，n不能被[2,n]中的整数整除。
也就是说素数n的最小因子是n本身：
(define (prime? n) (= n (smallest-divisor n)))
此外通过remainder运算符，可以判断是否能整除。
然后通过递归或者迭代的方式从2开始递增测试的方式来实现这里的smallest-divisor即可。
不过，以上实现细节略，因为还有种更直观的写法：
(define (prime? n) (not (any divides? (number-from-to 2 (- n 1)))))
而其中的实现细节，会在后面的篇目中涉及到。

此为分支路线，不影响主线流程。
 


* Scheme Toy #11.5 Message-passing
ee.zsy 2010年12月18日 16:08

关于generic operations再补充一篇，其要点是一个操作符作用在不同的数据类型上，会产生该数据对应的效果。
比如加法运算，在仅有整数的时候就仅仅是指整数的加法。而当数的定义扩充到实数复数上时，加法就有了不同的执行方式。
如果我们直接用系统提供了+操作符到我们自定义的数据上时，结果会是难以预料的。

一种可以的实现方式是，每个操作符，也就是函数，可以指定参数的类型，并定义多重的版本。
在使用这样的函数时，可以根据参数的数据类型去寻找适合的版本，然后调用。
每个数据类型可以指定唯一的数据名称，并提供谓词来方便判断。
特别的，为减少为每个新增类型都要和他需要关联的类型都定义一个操作符，我们可以引入类型的层次机制。
让类型间呈现父子关系，使用谓词时子类型也满足父类型，当子类型没有定义专门的操作符时，父类型的操作符可以使用。
接口上可以设计为(define (get-generic-operation-and-apply . objects) ...)来针对参数类型选择和应用操作符。
而操作符可以通过(define (define-generic-operation typenames procedure) ...)的形式来定义。

以上废话玩了，下面演示一个实现简单的方式，即消息传递机制：
例子仍然为定义一个复数类型。
(define (make-rectangular real imag)
 (define (dispatch op)
  (cond ((eq? op 'real-part) real)
        ((eq? op 'imag-part) imag)
        (else (display "unknown op"))))
dispatch)
(define (real-part complex) (complex 'real-part))
(define (imag-part complex) (complex 'imag-part))
测试(real-part (make-rectangular 2 5)) =>5 结果如期。

此外，我们先前写的那个counter也可以用这样的形式改写。
不过这都是用闭包实现对象，消息传递是从接口的风格来说的。
闭包的使用方式是函数调用，闭包可以保存它的私有状态。

系列号有点乱了，不过本来就不是内容严肃的东西
 


* Scheme Toy #12 List
ee.zsy 2010年12月18日 17:28

因为pair的两个元素也可以是pair，这样就可以实现许多更丰富的类型。
今天先说最常见的一种，即前面说过的List列表。
List是一个pair链，每个pair的第一元素，也就是car是用来存放我们的数据，而第二个元素cdr是指向另一个List或者Empty List。
上面是一个List的循环定义，下面也可以换一种方式，以pair实现list的视角来说明。
即pair的cdr指向另一个pair，作为List的下一个元素，也可以cdr为空什么都不指向，那么这就是List的最后一项。
直观一些说'(1 2 3 )和'(1 . (2 . (3 . ())))是等价的，ok闲话说完了。

于是下面来以对待Pair的方式使用List了：
(define myList '(a b c)) ;构造List
(car myList) => a 取第一个元素
(cadr myList) => b 取第二个元素
(caddr myList) => c 取第三个元素
(pair? mylist) =>#t 判断List也是Pair
(null? (cdddr myList)) =>#t 最后空表结尾
因为car/cdr常一起使用，随意可用以上用到的缩写形式。

接下来我们可以使用对pair的操作符定义一些对list的操作符：
比如 构造list，长度length，连接append，倒置reverse，还有 截取list-tail，下标list-ref什么的。
实现方式上依然使用我们熟悉的分段函数形式的递归，多自变量的情况可以一个做迭代一个作结果一个作参照。
(define (list . s) (cons (car s) (if (null? (cdr s)) '() (apply list (cdr s)))))
(define (length list) (if (null? list) 0 (+ 1 (length (cdr list)))))
(define (append list1 list2) (if (null? list1) list2 (cons (car list1) (append (cdr list1) list2))))
(define (reverse list1) (append (if (null? (cdr list1)) (list) (reverse (cdr list1))) (list (car list1))))
(define (list-tail list k) (if (zero? k) list (list-tail (cdr list) (- k 1))))
(define (list-ref list k) (car (list-tail list k)))
然后，再引入一个自变量表示结果，通常就可以将迭代改写为递归的形式了。

下节预告：Scheme Toy #12 Sequence
 


* Scheme Toy #13 Sequence
ee.zsy 2010年12月19日 13:36

昨天是从List的实现上来说的，今天是将从List的用法上来说，即基于List来表示使用上抽象。
而且一旦这种使用的接口建立的话，我们可以根据需要去选择List之外更适合的实现。
于是就可以来说标题里的那个名词，也就是序列的意思，线性的存放或使用一组元素。
例如对于某个list名为x而言可定义：
(define (thisItem x) (car x)) ;获取当前元素
(define (nextSequ x) (cdr x)) ;获取后续的序列
(define (hasNext? x) (not (null? (cdr x)))) ;判断是否有后续序列
然后我们可以基于此来定义一个迭代函数：
(define (for-each x do)
 (do (thisItem x))
 (if (hasNext? x)
  (for-each (nextSequ x) do)))
测试 (for-each '(1 2 3 4) display) =>1234 符合预期，虽然改用hasItem会性能上更好一些。
此外可以发现，在定义以上的函数时，虽然多定义了几个方法，但是表达可读性有大的提升。
这便是基于序列的一个抽象，List是我们所使用的实现，暂且能满足目前的使用。
而且根据之前所说的泛型方法，我们可以为同一个函数使用不同的实现，之后会演示到。

下面再以类似阶乘函数为例子，不过这次就换求和函数吧：
(define (sum x) (apply + x))
(define (range l h) (if (<= l h) (cons l (range (+ l 1) h)) '()))
这里的range是包括l也包括h的，于是 (sum (range 1 100)) =>5050 符合预期。

不过上面这个例子只是能够工作而已，并没有很明显的抽象掉迭代，只是求和是没有迭代而已。
那么下面来演示如何以链的方式来使用序列，即由序列产生序列，或者产生结果。
(define (map do items) (if (null? items) '() (cons (do (car items)) (map do (cdr items)))))
(define (filter need items) (cond ((null? items) '()) ((need (car items)) (cons (car items) (filter need (cdr items)))) (else (filter need (cdr items)))))
(define (reduce do items)
 (if (null? items)
     (do)
     (let loop ((i (cdr items)) (r (car items)))
          (if (null? i) r (loop (cdr i) (do r (car i)))))))
    
这样写1到100中所有质数的和就可以写为 (reduce + (filter prime? (range 1 100))) 了。
也可以再定义一个(define (copy list) (append list '()))用以防止数据被其他地方修改。

下节预告：Scheme Toy #14 Stream
 


* Scheme Toy #14 Stream
ee.zsy 2010年12月19日 16:31

如果求1到100的和就把展开一个有一百个元素的列表，未免是种不必要的损耗。
根据前一篇的描述，我们只需要car/cdr/null?就可以来使用可以序列了，而序列的实现完全可以用更实惠的方式。
例如用一个有局部状态的闭包来实现：
(define (xrange low high)
 (lambda ()
  (define item '())
  (cond ((<= low high)
         (set! item low)
         (set! low (+ low 1))
         item)
        (else '()))))
出于接口的一致，我们可以用消息传递机制写为：
(define (make-generator gene-proc)
 (lambda (op)
  (cond ((eq? op 'car) (gene-proc))
        ((eq? op 'cdr) (make-generator gene-proc)))))
(define (stream-car generator) (generator 'car))
(define (stream-cdr generator) (generator 'cdr))
这样我们原先那些针对序列使用了car/cdr函数都可以改写出stream的版本。
例如(define generator (make-generator (xrange 1 5)))后使用stream-car/cdr。
这里仅仅是肮脏的wrapper，这个make-generator依赖于gene-proc的局部状态。
出于安全考虑可把函数定义为(make-generator proc . args)的形式，
然后添加(define gene-proc (apply proc x))把gene-proc定义在局部。
而且要让序列链可以工作的话，我们还缺少一个 stream-cons 函数。

于是下面采用Lazy Evaluation的实现方式，使用了Promise类型。
语法接口是delay一个表达式和force执行，而在实现上和Lambda+缓存是等价的。
也就相当于用delay创建一个闭包对象(lambda () <exp>)，然后用force获得结果(<promise>)。
所以一切依然是美好的语法糖衣，实现在r5rs里有提供，不依赖运行环境，此略。
然后我们就可以用(cons <a> (delay <b>))的形式来定义点对了：
(define (stream-car stream) (car stream))
(define (stream-cdr stream) (force (cdr stream)))
我们前一篇的range函数只要简单的改写一下：
(define (stream-range l h) (if (<= l h) (cons l (delay (range (+ l 1) h))) '()))
原本的range会展开列表的全部元素，而现在将只是第一个元素，以及用以获得余下序列的闭包，而这里的闭包是用一个Promise类型。
接下来可以改写出我们的stream-filter，stream-map，stream-reduce，stream-append，stream-ref以及等等很多东西。

对于 (define (ones) (lambda () 1)) ，它返回的闭包调用结果总是1。
对于stream我们也可以定义一个总是返回1的序列：
(define (ones) (cons 1 (delay ones)))
或者令(cons-stream <a> <b>)等价于(cons <a> (delay <b>))写为：
(define ones (cons-stream 1 ones))
于是可再写出如下表达式：
(define (add-streams s1 s2) (stream-map + s1 s2))
(define integers (cons-stream 1 (add-streams ones integers)))
这里的integers便是一个正整数无序列了，这样我们就可以是使用序列链来代替可见的迭代。
同时，用delay来改写迭代的话，可以让状态的映射仅仅在有需要的是有进行，节约了无用的时间空间开销。

下节预告：Scheme Toy #15 Coroutine
 


* Scheme Toy #15 Coroutine
ee.zsy 2010年12月21日 16:01

名词Coroutine可写作co-routine中文译为协程，意思是Subroutine子程序之间执行权力的转移，可以用在实现合作式多任务。
下面为了说明简单，将仅讨论两个过程之间的协程，并使用continuation连续来实现简单协程。
Producer生产者与Consumer消费者之间的协同，前者产生数据而后者使用数据。
当Producer产生数据后将暂定执行，而让Consumer执行，之后Consumer暂定而等待Producer继续。
这样，Producer和Consumer两个过程轮流进行计算，协作之下产生最后的结果。
此外的例子中，iterator迭代器和pipe管道也都是都是这样的模型，实现方式也是类似的。

于是我们要实现问题可以进一步简化，或者说是特例化，就是来继续讨论generator生成器函数。
前一篇的前一篇里，我们的generator是展开一个列表，然后又消费过程对其迭代。
而为了减小空间损耗，前一篇里运用了：1.生成器的局部状态，2.生成器的惰性计算。
然后，在此篇里用continuation来继续讨论这一话题，来换种方式改写之前的range函数。
我们所期望的结果是make-generator产生一个闭包，闭包在产生一个数据后暂停，然后可以用函数调用或其他方式让它继续。
而实现的思路是Producer每次暂停会保存当前的连续，然后在继续运行时使用这个连续。
不过说明一下，一些简单的Scheme实现对continuation支持未完全支持，以下表达式会无法运行。
Ok，直接上表达式：
(define call/cc call-with-current-continuation)
(define (make-generator-xrange low high)
  (define produce '())
  (define continue '())
  (define (yield x) (call/cc (lambda (here) (set! continue here) (produce x))))
  (define (range-iter i) (if (<= i high) (begin (yield i) (range-iter (+ i 1))) '()))
  (set! continue (lambda () (range-iter low)))
  (lambda () (call/cc (lambda (here) (set! produce here) (continue))))
)
(define g (make-generator-xrange 1 3))
(g) ;=>1
(g) ;=>2
(g) ;=>3
(g) ;=>'()
(g) ;=>'()
其中要注意的是call/cc函数，它会把自己的连续作为参数调用它的参数。
我们可以把这个连续保存起来，之后以函数的形式加一个参数使用这个连续（就是上面的here）。
使用的结果就等价于让提供这个连续的call/cc返回这个参数的值继续运算。
也就是说我们可以用call/cc把它返回值继续执行的状态保存下来多次使用。
以上的实例中保存了两个连续，其用法都是在一个表达式保存当前连续。
然后调用另个过程，在那个过程中使用这个连续来让之前的表达式返回值。
同时在被调用的过程中，也把自己的运行状态以连续的形式保存了下来。
当它以调用其它的连续交出执行权后，再之后使用这个被保存的连续就让其继续执行。

对于迭代器而言，上面的内容已经足够了，对于多任务协同而言，还需要一些更直观的接口。
比如用fork/yield+queue，或者用多线程模拟，或者支持resume/pause消息什么的，以后再说。
此外上面有大段说明如何用连续实现协程，不过连续只是一种控制流程的机制和方式。
连续本身可以用来实现break或者throw之类的控制的转移，当然协程也一种控制的转移而已。
而作为此篇而言，目的是关于协程的，上面的演示虽然简单，不过已经展示协程的基本面貌。

下节预告：Scheme Toy #16 Nest
 


* Scheme Toy #16 Nest
ee.zsy 2010年12月22日 22:27

这么些篇目下来，发觉之后的思路要有点乱了。虽然如此，还是有内容可以继续说下去的。
前面说过递归，这回来说嵌套。递归可以用来表示重复，而一个重复单元里，可以有另一个重复单元。
这样的解释听起来有些含糊，不过嵌套这么名词本身就是很直观的嘛，于是下面也没什么内容可以说的了。

先一个简单的演示，使用了两层的循环：
(define (main)
 (define (show i j) (display i) (display j) (display " "))
 (define (loop1 i j) (if (<= j 2) (begin (show i j)(loop1 i (+ j 1)))))
 (define (loop2 i) (if (<= i 3) (begin (loop1 i 0) (loop2 (+ i 1)))))
 (loop2 1))
(main)
输出为10 11 12 20 21 22 30 31 32 ()，该用let来写在一句内也是可以的。

然后按照之前内容的思路，以基于序列的函数重写一遍：
(define (main)
(define (range l h) (if (<= l h) (cons l (range (+ l 1) h)) '()))
(define (show i j) (display i) (display j) (display " "))
(define (in-map1 x)
 (define (in-map2 y) (show x y))
 (map in-map2 (range 0 2)))
(map in-map1 (range 1 3))
'())
(main)
输出结果和上面是一致的，而循环是以map函数为主体来表达的。
此外一个要注意的修改是，内部循坏可以通过嵌套作用域使用外部循环的迭代变量。
而最上面那个是把外部的迭代变量作为参数了，使得两个函数较独立，嵌套的意味就显得不明显了。

于是，下面可以来做两个小小的演示：1.求两个集合的笛卡尔乘积，2.列出一个集合的全排列。
笛卡儿积的数学定义是对于集合A和B得到{(x,y)|x<=A,y<=B}，利用map写为：
(define (flat x) (apply append x)）
(define (product x y) (flat (map (lambda (j) (map (lambda (i) (cons i j)) x)) y)))
测试(product '(1 2) '(9 5 7))后输出((1 . 9) (2 . 9) (1 . 5) (2 . 5) (1 . 7) (2 . 7))。
如果不使用flat则输出是(((1 . 9) (2 . 9)) ((1 . 5) (2 . 5)) ((1 . 7) (2 . 7)))有两层了。
然后说全排列，对于n个元素的集合来说，它的全排列有n!个，从下面第三行看起：
(define (filter need items) (cond ((null? items) '()) ((need (car items)) (cons (car items) (filter need (cdr items)))) (else (filter need (cdr items)))))
(define (exclude i list) (filter (lambda (x) (not (= i x))) list))
(define (permutation x)
(if (null? (cdr x)) (list x) (begin
 (define (proc item)
  (define (in-proc list)
   (cons item list))
  (map in-proc (permutation (exclude item x))))
(apply append (map proc x)))))
(ap '(1 2 3 4))
输出结果是一个有24个元素的列表，且验证是集合'(1 2 3 4)的全排列。
这里使用同时使用了map和递归，写为一个集合的全排列是集合里的每个元素和除它外所有元素集合的全排列的笛卡尔积。
虽然此话并不严密，但也算是方便对这段表达式理解的一个说明，之后会再改用Backtracking再演示一遍的。

下节预告：Scheme Toy #17 Member
 


* Scheme Toy #16.5 24-Game
ee.zsy 2010年12月23日 09:59

今天有分支达成，有了笛卡尔积和全排列之后，可以来解决一个有趣的问题——算24点。
规则很简单，在一副扑克中抽四张牌，其数字属于[1,13]，然后运用加减乘数来寻找到结果为24的求法。
因为数字和运算的排列是有限的，我们可以枚举出全部的组合来进行尝试。

首先，改进一下前一篇的函数，来计算多元的笛卡儿积：
(define (mix x y) (define (tolist i) (if (pair? i) i (list i))) (append (tolist x) (tolist y)))
(define (product x y) (apply append (map (lambda (j) (map (lambda (i) (mix i j)) x)) y)))
(product '(1 2) '(2 3))
 ;=>((1 2) (2 2) (1 3) (2 3))
(product '(1 2) (product '(1 2) '(2 3)))
 ;=>((1 1 2) (2 1 2) (1 2 2) (2 2 2) (1 1 3) (2 1 3) (1 2 3) (2 2 3))
然后，还需要我们的permutations用来求全排列。
接下来的思路很简单：
集合A={first,second,thrid,forth}
集合B={+ - * /}
集合C是集合A的全排列有，4!个元素
集合D是B^3,即B与B与B的笛卡尔积，有4^3个元素
对于四个叶和四个节点的与顺序无关的树，有两种结构，记为集合D。
接下来用乘法原理，或者也可以说求B*C*D这个笛卡尔积。
这样就枚举了所有的计算可能，验证其中的元素计算结果是否为24。
这次换用Python2.6演示，算分支篇目的福利，表明同样的用法是不限于语言的。
不过依然是函数的风格，思路是一样的，写为Scheme表达式也差不多的样子。
代码：
from itertools import *
from operator import *
def math24(a,b,c,d):
    nums,ops_func=(a,b,c,d),(add,sub,mul,truediv)
    ops=dict(zip(ops_func,("+","-","*","/")))
    for j,i,k,l in permutations(nums):
        for o,p,q in product(ops_func,repeat=3):
            if o(p(i,j),q(k,l))==24:
                yield "(%s%s%s)%s(%s%s%s)"%(i,ops[p],j,ops[o],k,ops[q],l)
            if o(p(q(i,j),k),l)==24:
                yield "(((%s%s%s)%s%s)%s%s)"%(i,ops[q],j,ops[p],k,ops[o],l)
for i in math24(1,2,3,4):
    print i
 
输出：
(((2+1)+3)*4)
(2*1)*(3*4)
(((2*1)*3)*4)
(((2/1)*3)*4)
(2/1)*(3*4)
(2*1)*(4*3)
(((2*1)*4)*3)
(((2/1)*4)*3)
(2/1)*(4*3)
(3+1)*(2+4)
(((3+1)+2)*4)
(3*1)*(2*4)
(((3*1)*2)*4)
(((3/1)*2)*4)
(3/1)*(2*4)
(3+1)*(4+2)
(3*1)*(4*2)
(((3*1)*4)*2)
(((3/1)*4)*2)
(3/1)*(4*2)
(4*1)*(2*3)
(((4*1)*2)*3)
(((4/1)*2)*3)
(4/1)*(2*3)
(4*1)*(3*2)
(((4*1)*3)*2)
(((4/1)*3)*2)
(4/1)*(3*2)
(((1+2)+3)*4)
(1*2)*(3*4)
(((1*2)*3)*4)
(1*2)*(4*3)
(((1*2)*4)*3)
(((3+2)+1)*4)
(3*2)*(1*4)
(((3*2)*1)*4)
(((3*2)/1)*4)
(3*2)/(1/4)
(3*2)*(4*1)
(((3*2)*4)*1)
(3*2)*(4/1)
(((3*2)*4)/1)
(4+2)*(1+3)
(4*2)*(1*3)
(((4*2)*1)*3)
(((4*2)/1)*3)
(4*2)/(1/3)
(4+2)*(3+1)
(4*2)*(3*1)
(((4*2)*3)*1)
(4*2)*(3/1)
(((4*2)*3)/1)
(1+3)*(2+4)
(((1+3)+2)*4)
(1*3)*(2*4)
(((1*3)*2)*4)
(1+3)*(4+2)
(1*3)*(4*2)
(((1*3)*4)*2)
(((2+3)+1)*4)
(2*3)*(1*4)
(((2*3)*1)*4)
(((2*3)/1)*4)
(2*3)/(1/4)
(2*3)*(4*1)
(((2*3)*4)*1)
(2*3)*(4/1)
(((2*3)*4)/1)
(4*3)*(1*2)
(((4*3)*1)*2)
(((4*3)/1)*2)
(4*3)/(1/2)
(4*3)*(2*1)
(((4*3)*2)*1)
(4*3)*(2/1)
(((4*3)*2)/1)
(1*4)*(2*3)
(((1*4)*2)*3)
(1*4)*(3*2)
(((1*4)*3)*2)
(2+4)*(1+3)
(2*4)*(1*3)
(((2*4)*1)*3)
(((2*4)/1)*3)
(2*4)/(1/3)
(2+4)*(3+1)
(2*4)*(3*1)
(((2*4)*3)*1)
(2*4)*(3/1)
(((2*4)*3)/1)
(3*4)*(1*2)
(((3*4)*1)*2)
(((3*4)/1)*2)
(3*4)/(1/2)
(3*4)*(2*1)
(((3*4)*2)*1)
(3*4)*(2/1)
(((3*4)*2)/1)
 


* Scheme Toy #17 Member
ee.zsy 2010年12月25日 15:19

继续说List，之前是在说以序列的方式使用List，这篇补充一下以List作为容器的内容。
比如说有一个篮子，可以看看篮子里有什么东西。或者是有一个字典，由条目查到对应的解释。

首先定义如下两个函数，用途下面会解释到：
(define (member item x)(cond ((null? x) #f)((equal? item (car x)) x)(else (member item (cdr x)))))
(define (assoc item x)(cond ((null? x) #f)((equal? item (caar x)) (car x))(else (assoc item (cdr x)))))

使用member会返回列表x中由item开始的部分列表，并由此可以判断元素是否在列表中：
(member 1 '(3 4 2 1 4 5)) ;=> (1 4 5)
(define (in-list? item x) (pair? (member item x)))
(in-list? 7 '(3 4 2 1 4 5)) ;=> #f

使用assoc会返回关联列表x中满足是item开始的列表的子列表元素，并由此可以进行查找：
(assoc 1 '((0 'a) (1 'b) (2 'c))) ;=> (1 'b)
(define (lookup item x) (let ((res (assoc item x))) (if (pair? res)(cadr res) #f)))
(lookup 'apple '((apple red) (banana yellow))) ;=> red
(lookup 'pear '((apple red) (banana yellow))) ;=> #f

不过在下标是连续自然数的情况下，不使用关联列表而使用list-ref结果可以可行的。
且在Scheme中还有一个vector类型，其长度不可变，数据是连续的，vector-ref只需要O(1)的时间:
(vector-ref #(a b c) 1) ;=>b
(vector-set! (vector 'a 'b 'c) 1 'o) ;=>#(a o c)
在数据满足一定性质的的时候或有某方面使用需要的时候，可以代替List或相互转换着使用。
还可以使用make-vector创建，vector-length长度，vector-fill!填充，vector->list以及list->vector转换。

如果用List表示集合的话，在合并两个集合的时候需要排除重复元素：
(define (union-set x y)
 (cond
 ( (null? x) y)
 ( (member (car x) y) (union-set (cdr x) y) )
 ( else (cons (car x) (union-set (cdr x) y)) )
 ))
(union-set '(3 5 1) '(2 1 6)) ;=> (3 5 2 1 6)
也可使用基于序列的方法更为直观地写为：
(define (union-set x y) (append (filter (lambda (i) (not (member i y))) x) y))
(union-set '(3 5 1) '(2 1 6)) ;=> (3 5 2 1 6)

最后，如果用一个有序列向量来表示集合的话，那么判断是否属于集合还可以有性能上的改进：
(define (make-tree vector begin end) (list vector begin end));tree[begin,end)
(define (tree-vector tree) (car tree))
(define (tree-begin tree) (cadr tree))
(define (tree-end tree) (caddr tree))
(define (tree-null? tree) (>= (tree-begin tree) (tree-end tree)))
(define (tree-mid tree) (floor (/ (+ (tree-begin tree) (tree-end tree)) 2)))
(define (tree-entry tree) (vector-ref (tree-vector tree) (tree-mid tree)))
(define (tree-left tree)
 (make-tree (tree-vector tree) (tree-begin tree) (tree-mid tree)))
(define (tree-right tree)
 (make-tree (tree-vector tree) (+ 1 (tree-mid tree)) (tree-end tree)))
(define (in-ordered-vector? item vector)
 (bin-searched? item (make-tree vector 0 (vector-length vector))))
(define (bin-searched? item tree) (if (tree-null? tree) #f (let ((e (tree-entry tree)))
(cond
 ( (= item e) #t )
 ( (< item e) (bin-searched? item (tree-left tree)) )
 ( (> item e) (bin-searched? item (tree-right tree)) )
))))
(in-ordered-vector? 1 #(1)) ;=>#t
(in-ordered-vector? 4 #(1 2 3 4 5 6 7)) ;=>#t
(in-ordered-vector? 5 #(1 4 6 8 10)) ;=>#f
这里使用的搜索策略称为折半搜索算法，其实现方式是构建二叉搜索树。
这样平均时间复杂度由O(N)降到了O(logN)，当数据量N很大时，将有性能上的好处。
这里使用了一些额外的写法，使得搜索树的使用看起来明显一些。
此外，以上表达式从上往下写叫bottom-up，从下往上写叫top-down，先写自动测试的话叫test-driven。

对于字典类型，还可以使用用Hash函数的方式，时间复杂度是O(1)：
(define (make-hash-table alist) ...)
(define (lookup hash-table key) ...)
具体实现略，其中要注意的是：
1.在创建时table的大小，在查找是使用取模运算，当数据在添加时，可能需要改变大小重新hash。
2.hash函数的碰撞，通常是由key映射到一个关联列表再查找，也有直接往后放或再次hash的方法。

下节预告：Scheme Toy #18 Mutable-Model
 


* Scheme Toy #18 Mutable-Model
ee.zsy 2010年12月25日 17:44

前一篇说到用列表作为容器，其元素之间通过指针相连，使用下标访问的复杂度是O(N)。
此外还有一种容器是向量，其运算之间按顺序存放，使用下标访问的复杂度是O(1)。
他们迭代过程的时间复杂度是相同的，而列表是可以方便的添加元素，向量类型则是定长的。
列表和向量都可以和自身或者互相的嵌套，及即列表的元素可以是另一个列表。

以下的内容依然以介绍列表为主，开始之前先明确一下指针的概念。或者称为Reference引用，仅仅知道一下就可以：
(define x (list 1 2))
(define y (list x x))
(set-car! x 3)
x ;=>(3 2)
y ;=>((3 2) (3 2))
因为y的两个元素都是引用了同一个列表x，所以在x被修改时，y中会有两处发生了变化。

这节是说可变容器来着，那么首先就是往列表中添加删除元素的操作：
(define x '(1 2 3))
(set! x (append x '(4)))
x ;=>(1 2 3 4)
(set! x (cons 0 x))
x ;=>(0 1 2 3 4)
(set! x (filter (lambda (i) (> i 1)) x))
x ;=>(2 3 4)
(define (del-nth x n) (if (= n 0) (cdr x) (cons (car x) (del-nth (cdr x) (- n 1)))))
(set! x (del-nth x 1))
x ;=>(2 4)
上面分别进行了尾部添加、头部添加、以条件删除、以下标删除，当然可以有别的更多的方式。

使用set!的好处是表现出了状态的转移，不过以上出了cons函数，都为为使用的元素额外的创建一个副本。
(define x (list 1 2 3))
(define (append! x y) (set-cdr! (let last ((i x)) (if (null? (cdr i)) i (last (cdr i)))) y))
(append! x '(4 5 6))
x;=>(1 2 3 4 5 6)
这样便直接在原数据上修改了，不过因为查找最后一个元素还有O(N)的复杂度，所以还可以进一步优化。

接下来便采用之前使用的过的抽象方法，来定义一种新的类型Queue列队，让使用首尾元素的复杂度为O(1)：
(define (make-queue) (cons '*queue* (cons '() '())))
(define (queue? x) (eq? (car x) '*queue*))
(define (queue->list queue) (cadr queue))
(define (front-ptr queue) (cadr queue))
(define (rear-ptr queue) (cddr queue))
(define (set-front-ptr! queue item) (set-car! (cdr queue) item))
(define (set-rear-ptr! queue item) (set-cdr! (cdr queue) item))
(define (empty-queue? queue) (null? (front-ptr queue)))
(define (insert-queue! queue item)
 (define new-pair (cons item '()))
 (cond ((empty-queue? queue) (set-front-ptr! queue new-pair) (set-rear-ptr! queue new-pair))
       (else (set-cdr! (rear-ptr queue) new-pair) (set-rear-ptr! queue new-pair)))
 queue)
(define x (make-queue))
(insert-queue! x 2) ;=>(*queue* (2) 2)
(insert-queue! x 5) ;=>(*queue* (2 5) 5)
(insert-queue! x 8) ;=>(*queue* (2 5 8) 8)
(queue->list x) ;=>(2 5 8)
(define (delete-queue! queue)
 (cond ((empty-queue? queue)(display "<error>empty queue"))
       (else (set-front-ptr! queue (cdr (front-ptr queue)))
 queue)))
(delete-queue! x)
(queue->list x) ;=>(5 8)
这里所实现的queue类型中定义了指向列表首尾的指针，这样在尾部插入元素或者删除首部元素时，都有O(1)的复杂度。
列队是一种FIFO((first-in first-out))结构，插入和删除在列表的两端进行，先插入的数据会被先删除，就像先排队的任务会先做一样。
其需要提供的方法有empty？判断空、front获取、pop弹出、push添加，命名不一定相同，但作用是类似的。
而且在实现上会针对这些方法进行优化，如安排额外的指针，以降低操作的时间复杂度。

那么使用同样的方法，可以在实现更多简单的抽象结构：
Stack堆栈，LIFO(last-in first-out)后进先出结构，提供方法push/pop，
Deque双端队列，Double-ended queue，可以在两端同时访问添加删除，
Priority queue优先列队，可以获取其中优先权最高的元素，通常基于heap堆这种树结构。
前一篇的内容实现修改方法后，就获得了：
Set集合，元素不能重复，可以添加删除，以及求并集交集，
Map关联类型，用以储存映射关系，可以添加或查询映射。
外加最基本的List和Vector两种，都是可修改的类型，他们都是建立进一步抽象的接口。
我们称这些抽象的结构为Container容器，或者写为Collection，建立了固定的界面，并可采取合适的实现以满足需要。
在这里建立这些常用的复合类型之后，接下来的内容中便可以把它们作为思考的平台，去实现一些更丰富的东西。
关于还有两种常见的抽象类型tree树和graph图，会在之后的篇目中再具体提及。

下节预告：Scheme Toy #19 Sort
 


* Scheme Toy #19 Sorting
ee.zsy 2010年12月28日 15:03

按照顺序写，这篇该说到Sorting排序了，其作用是让序列以特定的顺序呈现。
关于各种排序算法，各种相关教材或书籍都会有所讲解，以下内容将仅是初步的介绍。

首先是简单的用于排序的Scheme表达式：
(define (quicksort x)
 (if (null? x)
  '()
  (let ((t (partition x)))
   (append (quicksort (part<= t)) (list (pivot t)) (quicksort (part> t))))))
(define (partition x)
 (let p ((tosort (cdr x)) (less (list)) (pivot (car x)) (great (list)))
  (cond ((null? tosort) (list less pivot great))
        ((<= (car tosort) pivot) (p (cdr tosort) (cons (car tosort) less) pivot great))
        ((> (car tosort) pivot) (p (cdr tosort) less pivot (cons (car tosort) great))))))
(define (part<= x) (car x))
(define (pivot x) (cadr x))
(define (part> x) (caddr x))
(quicksort '(5 1 9 2 7 3 4 7)) ;=> (1 2 3 4 5 7 7 9)
其中partition分组函数从列表抽取一个元素，并通过比较把余下的元素分为两组。
这种排序方式被称为quicksort快速排序，其原理是递归地对所分的两组进行快速排序直到待排序列表为空。

对于有N个元素列表x而言，如果x是已排序的，那么按照以上方式选择的元素会是一个极值，使得有一个分组为空。
其所执行的qsort函数就需要对N-1个元素的列表再排序，最终执行的次数将是O(N)，也就是与N呈线性增长关系。
每次Partition函数对于有N个元素的列表，将抽取pivot并让每个余下元素与之比较，将比较O(N)次。
那么在这种情况下，整个对N个元素的排序中的比较次数是一个等差数列的和，其结果执行了是O(N^2)次的比较。
当然，这是执行次数最坏的情况，在改进pivot的抽取方式后，不一定每次都能抽取到列表中的极值的。
另一种情况，也就是最理想的状况是每次分组都尽可能把元素分为相等的两份，然后再分别进行qsort的执行。
也就是说执行一个对N个元素的qsort函数，将会接着执行2次对N/2个元素的求值，即写为C(N)=1+2C(N/2)的递推关系。
该数列的展开形式C(N)=1+2{1+2[1+2(C(N/8))]}增长呈对数级别，即N每增一倍时C的值将加2（或者2的倍数）。
在这种情况下，执行qsort的次数总计为O(logN)，比较次数则相应为O(NlogN)次。
一般而言，也就是说再非最坏或最好的情况下，假设每次划分的两组元素个数比为k，k<-(1/2,1)。
运用同样的方法建立并展开递推公式，可以发现qsort的执行次数也可写为O(logN)。
现在进一步假设pivot的选择是完全随机的，那么N个元素被分为 i<-[0,N-1] 和 (N-i-1) 两组共N种分法。
对着N种求平均可以得到平均的复杂度，结果是对于有N个元素的列表而言，qsort执行O(logN)次，比较O(NlogN)次。
此外每次qsort函数将调用一次上面的partition函数，该函数创建的返回结果和它输入的元素个数相等。
平均情况下，整个qsort的执行过程中所分配的元素为O(N)，这是从空间的角度描述了这个过程。
此外还需要维护递归所用的空间O(LogN)，所用空间合计为O(N)。

接下来，来定义一个函数判断列表是否已经递增排列：
(define (ordered? x) (if (null? (cdr x)) #t (and (< (car x) (cadr x)) (ordered? x))))
这里的special形式and在第一个参数为#f时，将不会对余下参数求值，这可以避免多余的比较。
这个函数可以用作对上面的排序函数的测试代码，不过最好还是用数学归纳法对整个表达式进行证明。
用另一种可能直观些的形式来重写上面的快速排序为：
(define (qsort x)
 (if (null? x)
  '()
   (append (qsort (filter (lambda (i) (<= i (car x))) (cdr x)))
           (list (car x))
           (qsort (filter (lambda (i) (> i (car x))) (cdr x))))))
可以看出整个qsort是一个对list进行filter和append的过程。
再接下来，仿照之前写过的那个二叉搜索树，将qsort改为vector的实现，并使用vector直接对原数据进行排序：
(define (make-slice vector begin end) (list vector begin end))
(define (qsort! vector begin end)(if (< begin end)
 (let ((pivot (partition! slice)))
  (qsort! vector begin (- pivot 1)) (qsort! vector (+ pivot 1) end))))
为了书写简单，这里把qsort!的参数写为展开的形式，而没有去构建一个临时对象了。
为了让这段表达式工作，下面还需要实现其中的partition!函数，只需要遍历列表执行一些swap交换操作即可。
把比pivot小的值依次交换往向量的前方位置，并最终确定了pivot元素自身的位置，从而实现in-place原地分组操作。
整个过程进行递归情况和比较次数和最上面的那个实现情况相同，交换次数会小于比较次数，且每次递归中不再需要创建额外的空间了。
具体实现略。

对于大多数情况来说，快速排序是一个时间和空间上都十分划算的排序算法，不过对于特别的输入也需要专门的选择。
下面顺便展示两种特别的情况，将元素插入已排序列表，以及合并两个已排序列表。
插入可以看作合并的一种特例，在实现上可仿照之前的partition函数和union-set函数。
先是插入：
(define (insert-ordered item x)
 (if (null? x) (list item)
  (if (< item (car x)) (cons item x) (cons (car x) (insert-ordered item (cdr x))))))
(insert-ordered 5 '(1 2 5 8 10)) ;=>(1 2 5 5 8 10)
然后可再改写为序列，尾递归，或者向量的形式。
然后是合并：
(define (merge-ordered x y)
 (cond ((null? x) y)
  ((null? y) x)
  (else (let ((a (car x)) (b (car y)))
   (if (<= a b) (cons a (merge-ordered (cdr x) y)) (cons b (merge-ordered x (cdr y))))))))
(merge-ordered '(1 3 5 7) '(2 5 8 9)) ;=>(1 2 3 5 5 7 8 9)
这里的插入和合并函数对任意列表以一定方式递归或迭代，也可以实现排序的作用，优先列队也是如此。
而且通常的快速排序实现是不稳定的，即不能保证相同元素在排序后有一致的数据。
不稳定排序可以通过在交换元素时增加对原顺序的比较，而变成一种稳定排序。
在排序函数中可增加一个less或cmp参数接受一个lambda表达式，用作排序序列的依据。
对于(4 . 5)和(4 . 7)两个点对，它们的car是比较后相同，而明显是不同的值。
如果需要对一组点对按照car排序，并car相同的cdr排序，则可依次针对cdr和car进行稳定排序。

说明一下，这篇内容有点杂乱，有些地方准确性貌似有些问题。

 
下节预告：Scheme Toy #20 Tree
 


* Scheme Toy #16.7 DP
ee.zsy 2010年12月30日 12:27

感觉从#17篇开始话题有所转移，所以虽然这篇分支是现在写的，给个小的标号能方便内容上作参考。
不过，这篇的内容仅仅是算是对整体的一个补充，话题会略显松散并且重复。
同时呢，也可以看作对之后篇目的牵引，一些细节问题会再之后再做一些说明。

在前面很早的一篇说过用递归算阶乘，在递推式中计算数列的后项值会需要对前一项进行求值。
运用同样的方法，可以来求Fibonacci数列的第N项值：
(define (fib n) (cond ((= n 0) 0) ((= n 1) 1) (else (+ (fib (- n 1))(fib (- n 2))))))
(fib 10) ;=> 55
在计算第N项时，会去分别计算第N-1和N-2项的值，而在计算N-1项时，又会分别计算第N-2和N-3的值。
在这个过程中，重复进行了对第N-1项的值。所以，接下来改写为尾递归的形式。
(define (fib n) (let f ((a 0) (b 1) (i n)) (if (= 0 i) a (f b (+ a b) (- i 1))) ))
(fib 10) ;=> 55
在这个迭代过程中使用了三个迭代变量，i用于计数项数，a和b同时维护状态并用于产生下一项。
这样使用递推关系不断地推出下一项，直到求到所需要的项，就不用维护一层层的递归过程。
此外，可以明显的以上迭代过程中计算下一项(+ a b)是多余的，如果i非0则可在i为1时直接停止并返回(+ a b)。
不过这样的形式可以很明显再转写为另一种形式：
(define (fibgen a b) (cons a (delay (fibgen b (+ a b)))))
(define fibs (fibgen 0 1))
接下来可以去获取fibs数列的某一项了，并且计算过程只在该项需要的时候才进行。
再接下来可再以stream的形式改写，因为delay函数是具有记忆功能的，对获取已计算项是不需要再次计算的。
同样的，也可以让最前面的递归fib函数有记忆功能，例如使用一个向量或hash表保存映射。
让这个函数在被计算前先去查找是否已被计算过，如果有保存的结果则直接返回而不再去计算。

下面继续说的内容和上面很接近，首先有：
(max 1 3 4 5 6) ;=> 6
(min 1 3 4 5 6) ;=> 6
那么就可以顺带来说了，如果地图上有若干点，有相邻点之间相连，用T(a,b)表示两点间转移所花费的时间。
所要解答的问题是，如何去求任意两点之间转移所需的最小时间，同样可以扩展到有限花费最大收益的问题上。
假如地图上点的个数是有限的，并且路径是单向的，那么可以去列出所有可能的路径，然后再做比较。
不过这个方法在这里不合适，所以通常的做法是：
从某点出发，而当另一点可以由若干它所相邻的点到达时，该点与其点的最小时间是起点他每个相邻点所用的最小时间与转移到该的时间之和中的最小时间。
直接地翻译为Scheme的表达式可得到：
(define (min-time from to)
 (cond ((connect? from to) (cost-time from to))
 (else (apply min (map (lambda (i) (+ (cost-time i to) (min-time from i))) (connected-point to))))))
为了让这段表达式能够执行，需要选择适当的方式选择地图数据的呈现，例如提供map-data变量。
并实现其中的connect?、cost-time、connected-point以让min-time函数可以如期地工作。
然后运用前面对Fibonacci数列的优化方法，避免其中重复的求值过程。
实现细节之后再说明，并且可以把图的模型呢也可以看作是一种对状态转移的描述。
不过上面的min-time的求值是一个基本的树的深度优先搜索过程，只对特定的图的类型可用。
而且这个过程也可以由起点开始，一步步往下推，并保存会需要的中间状态，或者使用更丰富的搜索策略。

最后，来找一个简单的例子方便说明，比如和基础的背包问题类似的什么：
有若干项不同的任务，每个任务有不同的花费和不同的收益，那么如何在有限花费里获得最多的收益呢？
这个问题看起很有现实感，同时在实际问题中还有任务可否重复进行的差异，或者其他方面的约束。
解决的思路是把这个问题转化为熟悉的模型，这里就是上面的那个地图模型：
地图上的点是可能的分配方案，约束条件下允许再做一项选择后到达改点的各种选择方案作为相邻点，于是求路径上的最大值。
或者用迭代过程说明为：起点的任务集合为空，其相邻的点是所有的选择了一项任务但没有溢出的状态，并在这个过程中更新相邻点的状态为可能的最值。
而通常的做法是以花费的数值为图上的点，任务的选择就作为点的转移，转移到一个新的花费数值上。
把收益标记为点的值，而结果是其中的最值，也就是让花费相同时可以取得最大的收益。
先来凭直觉把上面的状态转移过程用Python来写：
class Task:
    def __init__(self,cost,income):
        self.cost=cost
        self.income=income
def maxIncome(tasks,costLimit):
    incomeOfCost=defaultdict(int)
    for cost in range(0,costLimit+1):
        for task in tasks:
            nextCost=cost+task.cost
            if nextCost>costLimit:
                continue
            nextIncome=incomeOfCost[cost]+task.income
            if nextIncome>incomeOfCost[nextCost]:
                incomeOfCost[nextCost]=nextIncome
            #incomeOfCost[nextCost]=max(incomeOfCost[nextCost],nextIncome)
    return incomeOfCost
tasks=(Task(1,4),Task(2,7),Task(3,1),)
costLimit=6
print maxIncome(tasks,costLimit)
得到：
{0: 0, 1: 4, 2: 8, 3: 12, 4: 16, 5: 20, 6: 24}
如果限定每个任务做多只能做一次，往cost篮子中依次添加每个task，并更新最值。
递减迭代的目的是防止任务自身覆盖了前一个任务转移后的状态，因为这个值用到。则有：
def maxIncome2(tasks,costLimit):
    incomeOfCost=defaultdict(int)
    for task in tasks:
        for cost in range(costLimit,-1,-1):
            nextCost=cost+task.cost
            if nextCost>costLimit:
                continue
            nextIncome=incomeOfCost[cost]+task.income
            if nextIncome>incomeOfCost[nextCost]:
                incomeOfCost[nextCost]=nextIncome
    return incomeOfCost
print maxIncome2(tasks,costLimit)
得到：
{0: 0, 1: 4, 2: 7, 3: 11, 4: 11, 5: 11, 6: 12}
在其中添加一些"print incomeOfCost"可以用来观察整个迭代过程。
然后就是个别地方还可以优化一下，复杂性分析略过。
那么最后来想象这里用到的视觉形象，这可是这里所用到的模型：
有若干不同容量篮子点从左到右递增排列，两个篮子间可能有从左到右的箭头，箭头指向往篮子里放物品后所用的更大的篮子。所放置的物体有不同的体积和价值，目的则是让每个篮子（容积固定）里放置的价值尽可能大。

这篇内容很是含糊，就这样，算个过度吧。
 


* Scheme Toy #20 Tree
ee.zsy 2010年12月30日 22:29

前面说过List可以嵌套，Map可以嵌套，于是这篇的话题来接这个。
为了感觉上直观一点，这里使用Tree树这个模型来表达。
这是一种父子节点呈一对多关系的模型。

例如这里使用列表的car放置节点的值，而cdr放所有的子节点：
(define (value x) (car x))
(define (children x) (cdr x))
(define (leaf? x) (null? (children x)))
(define tree '(3 (1 3 5) (5 (4 8) 6)))
(value tree) ;=> 3
(map value (children tree)) ;=> (1 5)
(map leaf? (children tree)) ;=> (#f #f)
最后三行的输出表示树tree的根节点为2，根有两个子节点，值为1和5，且都不是叶节点。

然后来实现一个可以对嵌套列表使用的Map函数：
(define (tree-map proc x) (map (lambda (i) (if (pair? i) (tree-map proc i) (proc i))) x))
(tree-map (lambda (i) (+ 1 i)) '((1 2) 3)) ;=> ((2 3) 4)
也可不用map而直接用cons+cdr来写：
(define (tree-map proc tree)
 (cond ((null? tree) '())
       ((not (pair? tree)) (proc tree))
    (else (cons (tree-map proc (car tree))(tree-map proc (cdr tree))))))
(tree-map (lambda (i) (- i 1)) '((1 2) 3)) ;=> ((0 1) 2)
对于上面用car存放节点数据的树的实现，仅再小小的修改即可。

接下来，来以一定的顺序打印节点：
(define (display-tree tree) (tree-map display tree))
(display-tree '(((0 (1 2 3)) (4 5)) 6)) ;=> 0123456
这样以同样的方式让嵌套列表变为序列：
(define (flatten tree)
 (apply append (map (lambda (i) (if (pair? i) (flatten i) (list i))) tree)))
(flatten '(((0 (1 (a b) 3)) (j q)) 6)) ;=> (0 1 a b 3 j q 6)
或者改为不使用map来写：
(define (flatten tree)
 (cond ((null? tree) '())
       ((not (pair? tree)) (list tree))
       (else (append (flatten (car tree)) (flatten (cdr tree))))))
(flatten '(((0 (1 (a b) 3)) (j q)) 6)) ;=> (0 1 a b 3 j q 6)
这里使用的顺序是树的深度优先遍历中先序遍历，即先父节点再子节点的处理顺序。

通常的，还有一种常见的顺序称为广度优先遍历，它是以子节点到根节点的距离为顺序。
实现方法可以是使用一个列队，把待处理的嵌套列表进行多趟的展开：
(define (flatten2 tree)
 (let flat-iter ((result '()) (nest-list tree))
  (if (null? nest-list) result
   (if (pair? (car nest-list))
    (flat-iter result (append (cdr nest-list) (car nest-list)))
    (flat-iter (append result (list (car nest-list))) (cdr nest-list))))))
(flatten2 '(((0 (1 (a b) 3)) (j q)) 6 3)) ;=>(6 3 0 j q 1 3 a b)
出于性能考录，可以再把这里的迭代变量nest-list改为可变类型的列队。
其原理是当nest-list中出现叶节点时就添加到result中，不然就展开节点扔会nest-list尾部。
或者再拆开一些来按下面的方式说明一下：
(define (leaf x)
 (let leaf-iter ((leaf '()) (pair '()) (tree x))
  (if (null? tree) (cons leaf pair)
   (if (pair? (car tree))
    (leaf-iter leaf (append pair (list (car tree))) (cdr tree))
    (leaf-iter (append leaf (list (car tree))) pair (cdr tree))))))
(leaf '(((0 (1 (a b) 3)) (j q)) 6 2)) ;=>(((6 2) ((0 (1 (a b) 3)) (j q)))
返回列表的car为leaf节点的列表，而cdr的值需要再次遍历直到为空。
这便是广度优先遍历的顺序，对于一个使用接口的无限树而言，可以在发现所需要的节点时就返回结果。
对于一些求最少步骤解决某问题的情况，可以以这个遍历顺序为基础来进行。

BFT过程中所使用的数据结构是Queue，这样来说DFT的递归过程中就是用到了Stack结构。
于是可以人肉把这个Stack结构给写出来，提取一个节点，然后压会它的子节点。
也就是说BFT是处理列表头部元素并把子节点展开在列表尾，而DFT对节点的处理是在列表的一端进行的。
同样的，优先列队可以作为遍历或搜索过程中使用的结构，来实现一种更有针对性的搜索策略。
如果节点表示从根到这个节点所用的距离，那么一个节点的权有两部分的和s，即已用的距离加上离目标的估计值。
每次迭代从列队中选择这个s最小的元素，计算实际距离并展开子节点并计算子节点的权s插入到列队中。
一个使用PQ优先列队进行树的搜索的实例是A*地图寻径问题：
(define (path map home target)
 (define (next-point-s x)
  (map (lambda (i) (point i x (+ (g x) (h* i)))) (point-s-not-reached-and-from x)))
 (let path-iter ((pq (list here)))
  (let ((now (smallest-in pq)))
   (cond ((is? here target) here)
    ((not-has-next? here) "not-found")
    (else (path-iter (pq-add-and-update pq (next-point-s here) now (g now))))))))
这个里面还需要补充一些东西，而且貌似不大对，之后再补充吧。
图的搜索和树的搜索是相似，不过其中也有些差异，如回路。
此外，前面所说到的bin-search是个以树的方式处理向量的例子。

下节预告：Scheme Toy #21 Search
 


* Scheme Toy #21 Search
ee.zsy 2011年01月01日 22:35

第一期内容准备结束了，就先来写这么些篇。
最后伧俗一下也算让内容完整，就简单口水几下。
这篇继续说简单的树结构，不过会和上一篇有些区别。

之前是把完整的树放在嵌套列表中，而这篇使用函数来使用树。
不过从前一篇里可以看到，我们是可以可以给调套列表定义接口的。
这样的好处是可以改变树的实现方式，如增加节点的信息，而不影响树的遍历过程。
同时，这样也获得了另一种好处，可以提高同样的接口让树边生成边使用。
也就是说，对树的遍历过程，可以转化为树的搜索过程。
当一对多的选择过程存在的时候，可以把这一过程转化为树的模型来操作。

对于8皇后问题，在8*8棋盘上放置8个互不能相吃的皇后，就是一个深度优先搜索过程。
而另一类问题，试图寻找最少的行动序列达成特定条件，可看作是一个广度优先搜索过程。
当有办法衡量所做行动到达的状态距离目前程度，则可运用A*算法优化搜索的过程。
简单地来说就是这样，当被搜索路径存在回路时，依然需要让搜索过程呈树的结构。
写出来的内容根据昨天的遍历过程的来改，相当于伪代码：
(define (DFS root)
 (map (lambda (step)
   (if (need-search-next? step) (DFS step) (result-this step)))
  (next-steps root)))
  
对于8皇后问题可写：
(define step (make-vector (* 8 8 ) '()))
(define (need-search-next? step)
 (and (deep<=8? step) (not-crash? step)))
这里的step是作为不可变类型使用的，也可以把搜索到的列数存放进去作为（缓存一样的）性能优化。
这样每搜索一步就会创建新的step状态，为减少空间需要，可以把step改为可变类型，并在回溯时恢复状态。
也就是说当某一搜索到的节点是不需要的时候，也就是result-this返回空结果或正确结果，并将step变为前一步骤的状态。
对于其他搜索过程，因为不能进行这样的回溯，所有保存状态的开销是无法避免的。

下面来说另一种问题，即遍历过程是使用子节点的值去推导父节点的值的情况。
(define (price node)
 (give-value! node (minimax-value (apply price next-steps))))
节点将被赋予它子节点的最值，取值根据行动方的不同按照最大最小值交替来取。
在计算一个节点a的子节点集合B的最小值时，子节点b<-B将取其自身子子节点集合C的最大值。
如果在集合C中发现任何一个点的值大于集合B中的已知点，那么b点肯定不是B中的最小值。
在这种情况下对集合C中其余点的搜索已经不再必要了，集合C的父节点已经从搜索支中剪去。
在这个搜索过程中存在已知的最小值和最大值最为上下界，并在搜索下一个子节点时于之比较。
实现时可以把子节点最值的相反数赋予父节点，这样可以在推导父节点是取同一方向的最值。
而搜索值的值可以是实际的值也可以是估计的值，因为在限定搜索的距离时不一定能到达叶节点。
这种这里所说的搜索是一种双人博弈树的情况，自己尽可能让节点的值更大，而对方会让节点更小。
节点可以用1代表己方胜利用0代表自己失败，或者用一个值代表对获胜的可能性的评估。
让轮到自己行动时，自己将选择平值最高的节点进行，而这个节点值即源自上述的一个过程。
即节点到即子节点是自己行动时，该节点是子节点的最大值，因为到时自己自己可以选择抉择。
当到子节点是对方行动时，父节点的取值将是子节点的最小值，假设对手会在这一支做最有利他的选择。
说明部分就这样了，实际的过程将以树的深度优先DFS为基础，递归用子节点给当前节点赋值。
在使用递归函数时以上下界为参数用于比较，当发现不需要再搜索时，可以直接返回无用的部分元素最值。
略作修改就是：
def price(node,bound):
    min=-inf
    for n in node.children:
        if n.value>bound:
            return n.value
    if n.value>min:
        min=n.value
    return min
在Scheme可以设置条件判断迭代时候要继续，或者用连续在实现执行位置的转移。

不过这里好多具体的地方都没有说到来着。。。

下节预告：Scheme Toy #22 Graph
 


* Scheme Toy #23 DSL
ee.zsy 2011年01月02日 20:53

这是这一阶段的最后一篇了，这个科普文系列到此告一段落。
如果再找话题来随意说说，主线就不会显得足够完整了。
于是这篇里，关注点又回到对求值过程本身的说明。

列表是用来表示数据的，也可以数据在表示执行的方式，例如：
(define (debug-print . x)
 (define (display . x)'())
 (map (lambda (i) (display i) (display " ") ) x) (display "\n"))
(define (op exp) (cadr exp))
(define ops `((+ -) (* /)))
(define (op-proc x) (let ((r (assq x `((+ ,+) (- ,-) (* ,*) (/ ,/))))) (if r (cadr r) #f)))
(define (calc-iter exp ops)
 (debug-print "calc-iter>" exp "\n" ops)
 (cond
  ((number? exp) exp)
  ((null? (cdr exp)) (calc (car exp)))
  ((null? ops) exp)
  ((memq (cadr exp) (car ops)) =>
   (lambda (i) (let((op (op-proc (car i))) (rest (calc-iter (cddr exp) (cdr ops))))
    (if (pair? rest) (calc (cons (op (calc (car exp)) (caddr exp)) (cdr rest)))
     (op (calc (car exp)) rest)))))
  (else (calc-iter exp (cdr ops)))))
(define (calc exp) (calc-iter exp ops))
(calc '(1 + (4 / 2) * 3)) ;=> 7
(calc '(3 * (1 + (5 / 2) * 4 / 3 + 1))) ;=> 16
这是一个不安全不过能用的对四则运算表达式的计算过程。
其中calc函数接受表示表达式的列表，并根据二元操作符的优先级计算并返回结果。
例如可以用数据来定义规则，然后编写过程让规则可以运作。

同时在Scheme中提供eval函数可以处理列表形式的Scheme表达式：
(eval '(+ 1 (* 2 4))) ;=>9
为了书写列表方便，有对应quote'的quasiquote`，按键在键盘数字1的左边。
上面的代码中op-proc一行便有用到，其中unquote,表示求值unquote-splicing,@表示求值展开列表，例如：
(define a 1)
`(a ,a ,@(list a 'a) ,(+ 1 1)) ;=> (a 1 1 a 2)
Scheme代码是可编译执行可解释执行，eval的存在使得Analysis与Execution的界限变得模糊。
并且允许在编译好的代码中执行未知的表达式也是一种不安全和不健壮的操作。
于是就有了macro的存在，它用来将表达式在执行前展开，可以在执行前进行。
macro与procedure在使用形式上是一致的，不过macro不会收到求值后的参数。
源自common lisp的defmacro是这样的，返回一个可eval的list作为替换代码：
(defmacro (when c . e) `(if ,c (begin ,@e)))
(when #t (display 1) 2) ;=> 2
像when这样的form是无法通过define来定义的。

不过出于洁癖，对这种把这种把列表当作代码执行还是有点什么，算是不放心吧。
因为事实是上例中begin如果在代码展开的环境里有了其他的语义，结果就是错误的。
也就是这种宏不够安全，或者说不够卫生，虽然说是可以再做展开时的替换。
另一方面还是希望宏里是可执行的代码，于是就有了Scheme中满足词法作用域的hygienic-macro。
在r5rs中是define-syntax、let-syntax、letrec-syntax并有对应lambda的syntax-rules。
syntax-rules的第一个参数是保留字列表，接下来是一组模式匹配有点像cond的结构：
(define-syntax gen
 (syntax-rules (for in if)
 ((_ exp ... for i in seq if cond ) (map (lambda (i) exp ...) (filter (lambda (i) cond) seq)))
 ((_ exp ... for i in seq ) (gen exp ... for i in seq if #t))))
(gen (+ 1 i) for i in '(1 2 3 4)) ;=> (2 3 4 5)
(gen (+ 1 i) for i in '(1 2 3 4) if (> i 2)) ;=>(4 5)
定义中允许递归或使用别的定义，以上是一个仿Python中列表生成器的例子。
不过在Python3中生成器是惰性的，那么接下来可以改为用delay来实现，略。
此外其中模式部分的...规则有点丰富，使用时得额外注意一下。

通常的，定义过程是为了抽象与组合，而这里则增强了其中的表述能力。
在r5rs中就给出了众多Scheme语句的定义宏，不过宏虽然强大但不可滥用。

这次，这次暂时没有下节预告了。
 


* Scheme Toy #22 Graph
ee.zsy 2011年01月03日 23:05

树的模型是一种很有用的抽象工具，不过这个还是显得有点特殊，比如根节点什么的。
于是为了能够描述生活中更多的问题，就需要模型更多抽象，限制也更少。
那么下面介绍的是存在回路的情况，让任意节点之间都可以有若干条边相连。

如果直接按照树的遍历方式对一般的图进行遍历的话，可能会因为回路的存在陷入循环。
通常的解决办法是不再走到已近过的点上，可以给走过的点做标记，或者加入一个集合中。
这样这样略作修改，深度和广度优先搜索的过程对带回路的路就也适用了。
并且图中的边可以增加一些条件，如方向或其他限制，在遍历时依照进行即可。
这样的搜索结果对图的遍历结果依然是以树的形式存在，不过可以有不同的树或路劲存在。

相比可以直接用嵌套列表表示树，下面需要寻找某种形式来表示图（包括树）的结构。
首先是用关系矩阵来表达：
(define (make-graph node-num) (make-vector node-num (make-vector node-num 0)))
(define (edge x y) (vector-ref (vector-ref x ) y))
(define (edge-set! x y value) (vector-set! (vector-ref x ) value))
(define (edge-set-nodirect! x y value) (edge-set! x y value) (edge-set! y x value))
从点x到点y在矩阵中对应一个值，可用1表示连通0表示不通，而对于无向图，x到y和y到x的值是相等的。
同时这个值对应图中的一条边，可以给这个边赋予一个或多个值表示边的权，其作用下面会说到。
对于有大量0点的情况关系矩阵可以使用散列来表示，或者来继续使用最熟悉的列表。
符号和序号来标记点：
(define (make-graph node-num) (make-vector node-num (list)))
边作为一个对象放在节点对应的列表中，边对象可以自带数据供查询。
其放置的位置就是边的出发点，指向的地方可以用符号序号或者指针来表达。

这里将不具体地涉及图算法的原理，而仅仅是来说说图这个模型的用法。
首先是Graph Search，用来在图中查找需要的节点，可以看作是带回路的树。
实例是带回路的决策树，最基本的做法依然是BFS和DFS广度和深度优先搜索算法。
Minimum Spanning Tree最小生成树，是带权无向连通图权总和最小的展开树。
实例是若干城市之间假设最短距离的电话线，常用Prim算法和Kruskal算法。
Shortest-Paths最短路径问题，两寻找节点之间权之和最小的路径。
实例是最小转车成本的问题，确定起点时常用Dijkstra算法，可以用A*优化。
对于权有负数的情况，有Bellman-Ford算法，不会陷入趋向无穷小的负环路中。
而有Floyd-Warshall算法用于解决全局最短路径问题，推出全部任意两点之间的值。
Network Flow网络流是每条边有容量的有向图，在流的工作中边的流量不可超过其容量。
可以用来计算其中的maximum flow最大流，即总流量最大的情况，使用的是Ford-Fulkerson算法。
如果给每条边不同的成本，那么又引申出了Minimum Cost Flow最少费用流问题。
网络流模型是线性规划的一个特例，实例是交通运输和管道运输，同时又可引申出匹配相关问题。
例如在流量容来那个为一时就可以转入一些很现实的问题：
不同人做不同事的成本不同如何分配成本最小，
不同的人能胜任不同的工作如何分配使得匹配最多，
若干产量固定工厂往不同市场运输成本不同如何分配成本最小，
同上问题不过增加了中转站的存在，
包括上面说过了MF和MCF的例子。
这些情况的线性规划问题都能使用网络流的模型来求解，通过增加起末两个节点的方式。

此外，除了图的模型，现实还有若干问题可以以其他的方式抽象，如几何知识：
寻找空间中距离最近和最远的点对，
寻找最小的可以包裹所有点的多边形/圆形，
判断区域内若干直线的相交情况，
……

一方面是解决问题，一方面是减少算法的复杂度。

具体点的东西等之后能补则补吧，暂时就这样了。
正篇的内容就安排至此，这篇留个不完整吧。

下节预告：Scheme Toy #23 DSL
 


* Scheme Toy #20.5 BT
ee.zsy 2011年01月05日 18:20

这篇再补充或更正一些内容，是要是关于backtarcting的。

来说backtarcting回溯，指在尝试问题失败时可以恢复一步或几步再做尝试。
树的深度优先搜索过程就是一个一个使用回溯过程来寻找节点的。
作为示例的是前面提到过的八皇后问题，这次稍微说详细一些。
首先是函数递归加嵌套map的风格，第k个棋子的存放是基于第k-1个棋子：
def solve_eight_queens():
    size=8
    def can_add(l,y):
        x = len(l)
        crash_any = any(y==q or x-p==y-q or x-p==q-y for p,q in enumerate(l))
        return not crash_any
    def q(x):
        if x==0:
            return [[]]
        else:
            return (j+[i] for j in q(x-1) for i in xrange(size) if can_add(j,i))
    return q(size)
for k,v in enumerate(solve_eight_queens()):
    print k,v
这里已经用到了惰性求值，所以在map时不要额外的空间。
递归得写在range的里面，这个的list是先展开前面的for。
一般的append操作相比cons有点损耗，不过不明显。
然后写得像深度优先搜索一些，用递归来展示回溯：
def seq_dfs():
    def s(p):
        size=8
        if len(p)<size:
            for i in xrange(size):
                if can_add(p,i):
                    s(p+[i])
        else:
            print p
    s([])
不过Python限制了生成器中递归的存在，所以不能yield了。
此外，因为这个深度搜索的顺序是固定的，为每次的函数调用所创建的列表是可以优化的。
于是可以写一个风格较常见的版本出来：
def seq_dfs():
    l=[0]*8
    def can_put(x,y):
        #return not any(y==q or x-p==y-q or x-p==q-y
        # for p,q in enumerate(l[:x]))
        for i in xrange(x):
            p,q=i,l[i]
            if y==q or x-p==y-q or x-p==q-y:
                return False
        return True
    def s(p):
        size=8
        if p<size:
            for i in xrange(size):
                if can_put(p,i):
                    l[p]=i
                    s(p+1)
        else:
            print l
    s(0)
seq_dfs()
再此外，前面提过DFS的递归是等价于一个Stack结构的，于是还可以明显迭代形式:
def stack_dfs(size=4):
    l=[]
    class End(Exception):
        pass
    def bt():
        if len(l)==0:
            raise End()
        r=l.pop()
        if r<size:
            try_next(r+1)
        else:
            bt()
    def try_next(x):
        if len(l)==size:
            print l
            bt()
        elif x==size:
            bt()
        elif can_add(l,x):
            l.append(x)
            try_next(0)
        else:
            try_next(x+1)
    try:
        try_next(0)
    except End:
        print "End"
stack_dfs()
尾递归和迭代是等价的，这段代码可以改用While来写，这样就不存在递归的函数调用了。
不过Python中不支持尾递归优化，所以在size=8时会溢出，用while写的话需要多层break。

然后，前面的广度优先搜索这次要修改一下：
(define tree '(((0 (1 (a b) 3)) (j q)) 6 3))
(define (bft tree)
 (cond
  ((null? tree) '())
  ((pair? (car tree)) (bft (append (cdr tree) (car tree))))
  (else (cons (car tree) (bft (cdr tree))))))
(bft tree) ;=>
其中append操作会复制整个列表，而原列表又随即被垃圾收集了。
于是这里的append和cons可以改为lazy的实现方式：
(define (stream-append s1 s2)
 (if (null? s1) s2
  (cons (car s1) (stream-append (force (cdr s1)) s2))))
(define-syntax cons (syntax-rules ()
 ((cons car cdr) (cons car (delay cdr)))))
在把所有内置函数都替换为Lazy的Scheme中可以写出：
(define fibs (cons 0 (cons 1 (map + (cdr fibs) fibs))))
这样的循环定义是可以的，而不会陷入一个死循环。

此外string字符串可以看作是字符类型组成的向量，字符用#\前缀书写：
(string-ci=? "Abc" (string-copy(string-append (substring "aBD" 0 2) (make-string 1 #\c))))
这里例子没实际用途意义，也没用最基本的和vector类似的那一组函数，结果为#t。
还有一个语法糖衣式的do循环，之前一直没机会演示到：
(do ((i 4 (- i 1))(x '() (cons i x))) ((< i 1) x)) =>(1 2 3 4)
do的参数迭代变量，返回条件，若干迭代中的命令（此例为空）。
这种情况一般用named let来写会也很简单。
关于r5rs之前还没说到的有：
多返回值values相关的一组函数，输入输出port相关的一组。
还有load用于载入脚本，使用时要很小心，有点eval的邪恶感觉。
补充，对于n皇后问题n为1时有一个解，当n=4之后，解的个数是：
2 10 4 40 92 352 724 2680
这个可以当测试数据使用。
 

[序]Scheme 与 Algorithm

这篇本来计划些内容的，不过后来有变动。
因为和另一篇“Scheme Toy”是同时开篇的，后来写着那篇，结果这篇就给废弃了。
两篇计划的内容有些重复，而且本来是把那篇作为这篇的简化版和详细版的。
既然那篇已经写完了，虽然写着不注意使得内容上已经和这篇有所偏离，这里也无心再重复。
最后把这篇的框架整理完，算一个索引吧，质量什么也是无力的事情了（摊手。
在那里写每行间有空行的，结果这里也开始乱断行了。

创建日期：2010年12月13日


* 序言

此篇是随意的笔记，仅尽力为一些可述的内容建立关联，算是导读性质。
另外，虽然文字设法去接触一些理论化的东西，不过关注点会放在使用。
也就是说从概念和接口的角度来发现应用，对实现的细节暂时不去暴露。
所以，一个不幸的后果是，以下内容无任何技术含量，留下的仅仅是文字的堆砌而已。
如果确实要使用到下面涉及的一些内容，还是要有相关教材的阅读经验，而不仅仅接触一下的罗列。
注意：以下各部分未按一定次序排列，而是又若干话题引开。


* SICP

历史上传奇的MIT6.001课程教材，受很大的推崇。原因略。
有提供在线版本获得：http://mitpress.mit.edu/sicp/

大致内容可以参考目录，也章节相联系，不过话题还是算比较分散的。
本来是说这里再简单整理一个索引的，不过有在另一篇里写了一些。


* Scheme Toy

这个算自己断断续续写了近一个月的科普文。

首先补遗一下：
关于数值计算，符号计算，矩阵模型，并行模型这些话题结果那里漏写了。
于是就写在这里吧，Scheme有对于这些应用还是可以胜任的。
在Scheme有Number Tower，数字分精确和非精确两种。
高精度数和分数都是精确类型中很有用的东西，特别在一些数学问题上。
比如某些的数列增长很快，很容易就计算到比较大的整数上面。
复合类型可以用列表来表示，这样很容易对符号进行计算。
例如求导数，可以用数值方法进行大量的运算，求更精确的近似解。
或者可以直接对表达式求导，判断运算类型，然后选择适用的规则。
矩阵的话，本身是一个符号，可以表达点的关联，以及向量的变换。
矩阵可以按照符号的方式进行计算，并用来抽象现实中的情景。
并行模型的话，一种是说多任务，一种是说传统的并发。
协同式多任务是对连续的一种有趣的应用，强调的是配合。
并发的话则是注意同步锁的问题，要避免其中的冲突。
这些内容是计算写到的，不过后来给忽略掉了，因为主线往后推了。
还有GCD和奇偶上的话题，可以涉及一些基础的数论知识。

说到主线，最初的动机是从SICP跳跃的发现一些有趣的东西来作些说明。
所以最初的内容还是从该书的前三章来挑选的，并寻找一些生活中的例子。
这个算是出发点，就是Scheme中机制可以让问题的描述变得简单。
这种简单是语言对功能的抽象，以及编码对思维的抽象。
因为Lambda是Church数方面的理论，所以这次的问题也主要侧重数学方面。
当然，是生活中的数学了，比如第一节就是说关于表达式与计算器什么的。
关于语言呢，是一中用来表达思维的方式，因为Scheme语言有层次状的结构。
也就是说一种应用可以基于更基础的运用，这样在使用的时候会更专注到抽象过程中。
也就是说，去运用数学知识去讨论问题的本身，把问题能够描述清楚了。
这样解决过程就显得很直接，作为对思维的表达，而不是反过来专注表述本身的意义。
关于副作用，为视为函数式语言的特征，使得状态的改变变得复杂。
不过同时，状态在迭代与递归过程中的变化，又是可以利用的东西。
Scheme在这些方面没有什么限制，而且让仍一种范式都很方便。
而且因为是考虑思维上面的东西，用C/C++/Java来重写并是困难的事情。
使用Scheme只是让人的关注点牵引到某些容易忽视的本质，
而对于这种本质的表达却是可以使用更具体的更方便目的的工具上的。

关于Scheme的资料，还可以参考一下内容：
Scheme - Wikipedia
[[http://en.wikipedia.org/wiki/Scheme_(programming_language)]]
Yet Another Scheme Tutorial
[[http://www.shido.info/lisp/idx_scm_e.html]]
Teach Yourself Scheme in Fixnum Days
[[http://www.ccs.neu.edu/home/dorai/t-y-scheme/t-y-scheme.html]]
schemers.org
[[http://www.schemers.org/]]
CLiki
[[http://www.cliki.net/]]
CMU Artificial Intelligence Repository
[[http://www.cs.cmu.edu/Groups/AI/0.html]]
The SLIB Portable Scheme Library
[[http://people.csail.mit.edu/jaffer/SLIB.html]]
这上面有一些是教程，一些是索引，一些是代码。
这些可以作为查阅的参考，或者寻找参考的出发点。
实体书方面的学校里有一些老的书籍，比较偏实例，不多。

下面来说实现方面的，说些自己在意到的实现：
TinyScheme可作用于嵌入式，一点完整的语言子集，Gimp就在用它。
Scm这是和Slib结合最好的一个实现，优点是Slib是纯Scheme代码的
Kawa是一个Java环境下的Scheme嵌入工具。
MIT Scheme这是Sicp的书配环境，某种意义上是很重要的参考。
Plt-scheme教学为目的的，很集成，实用的文档和功能组件丰富。
Sisc一个很完整的Java实现，实现了很多的东西
Gambit可以编译执行，性能有优势，可加入C语句一起编译。
还有个浏览器js的在bluishcoder.co.nz/jsscheme/
这里无法多列举以及适用的场合，以及如何用自己的小实现。
现在Plt-scheme改名Racket了，适合学习，不过可变类型和R5RS不一致。
关于标准方面有R5RS，和R4RS兼容，虽然各实现有区别，但不会和它冲突。
还有R6RS提出了很多有用的想法，这些想法在各实现中均有表达。
比如错误处理，包管理，结构什么的，还有未涉及网络和线程方面的特性。
SRFIs是作为一个可参考的标准或者作为库存在的，也可以用。
个人一般在意各实现在数学类型和对连续的支持上的程度，以及用途。
不过其实自己其实也很偏向Python实现，因为库多。

关于Scheme的编辑器，自己的要求是有有括号匹配就行。
通常出于演示目的所写出的代码不会组合层次太复杂。
要严格注意要缩进，左括号对应好右括号，这个可以通过缩进和断行的帮助。
右括号数量够后写一行就行，行尾一串右括号不必多少顾虑。

接下来一个写编写实现以及99个小问题。


* 数学方面

在话题中Scheme是工具，是关注的出发点，但是也需要其他方面的东西。
所以在Scheme Toy的后半部就开始想从SICP说到以外的内容了。
关于各实现的网络或线程或一定会用到的扩展库什么的是不一定非要说的了。
因为这些内容在用别的语言时，是也会接触到的一些东西，不作为重点。
于是下面的内容还是以一些手头的书籍为参考了，这里参考到的有：
离散数学 Discreted Mathematics @ Richard Johnsonbaugh
算法算法手册Algorithms in a nutshell @ George T. Heineman
数学建模与数学实验 @ 赵静, 但琦
《------------------------------附一下目录会比较好------------
这里仅仅是可以参照，所以在此文之外有很多有价值的东西可读的。


是想说数学方面的，所以话题会不仅限于这几本书涉及的方面，
不过有个内容的出发点还是有必要的，虽然说查阅的让人很难受。
总的来说，查阅的方式，对于基础知识来说，不是很适合的了解方式。
还是来列举一些这里涉及的话题吧，都是自己还不够深入的东西：
离散数学、数据结构、算法分析、数值计算、数学建模、线性规划
暂时就仅仅了列了下关键字，因为内容说起来很缺少自信的感觉
还有算法导论和计算机艺术都还怀有敬畏之心，不做说明。
不过这里总在所数学模型，在作为思路展现，没有细入。

这里真的有很多值得写的东西，真的，这行是占位用的。

看起来这篇是说Scheme，其实这里才是重点的。


* 算法复用

这里的复用有三个方面，一是思维的复用，二是模型的复用，三是库的复用。
按照重要定排列，思维的复用是最重要，它是对模型模型运用的根本。
模型也很重要，它是对思维的表达和运用，同时也是对现实的抽象。
然后来说库的复用，它不是作为这里的重点，不过是很实用的东西。

模型的话，算是很有用的东西，这里是指的一些数学模型。
比如说在上一节里用的很简单的例子就是集合论以及图论方面的一些模型。
这一节的下面来说库的复用方面的东西，文档形式也算。

Dictionary of Algorithms and Data Structures
http://www.nist.gov/dads/
算法与数据结构词典

Data Structures and Algorithms with Object-Oriented Design Patterns
http://www.brpreiss.com/
一个五种语言来写同样问题的书籍系列

C++中的算法复用主要体现在模板与泛型方面的部分
首先是STL，属于C++标准
http://www.sgi.com/tech/stl/
http://www.cplusplus.com/reference/stl/
包含各种Containers容器Algorithms算法，以及一些使用函数。
此外Boost中还有一些，比如
http://www.boost.org/doc/libs/release/libs/graph/doc/table_of_contents.html
就是Boost Graph Library描述了一些图方面的哦算法

Java的情况和C++有点类似，作为语言机制上来说算法复用是有必要的。
PHP也有类似的库存在，还有其他一些语言平台的情况也差不多。

Python是个发展活跃的语言，虽然库设计不如Java精致，但很易用。
其自带的List/Dict类型可以做很多用途，外加for的语句和生成器。
在文档的Data Types和Numeric and Mathematical Modules两节是相关的库。
第三方库的话Graph方面参考
http://wiki.python.org/moin/PythonGraphApi
并有NetworkX这样抽象为库的存在http://networkx.lanl.gov/

在Haskell的Wiki上有关于纯函数语言的资料，而ML/Ocaml也和Scheme更像一点。
Common Lisp晚于Scheme，标准化了很多必要的部件。
CLOS是个很特别的设计，也有很多其他的亮点的东西存在。
Emacs Lisp用于嵌入，居然没词法定界用不了词法闭包，但执行命令是够了。
不过三者表达循环的方式都不相同，相同有不同的东西有点让人困惑。
而算上Maxima就又创在了一种特别的东西了，再算Dylan呢。
还是暂且把它们当作长得有点像的不同的东西看待吧，但都值得参考。
再说就是Lisp本身，除了S表达式，还有M表达式和I表达式可用。

最后来说Scheme，自身可以直观的表达算法，一般基于代码复用。
有Maxima包含了很多东西，是Common Lisp之上的东西，可参考。
线性规划和图论方面的东西都有，最为一个DSL的库存在。
[[http://www.cs.cmu.edu/afs/cs/project/ai-repository/ai/lang/scheme/edu/tut/0.html]]

怎么觉得还有很多不重要的闲散的存在可以滥说说呢。
比如说关于FP有很多Paper来着。


* 代码展示

这篇没有这部分了


* 补充说明

这次换行太多，自己已经不习惯。
而且所写缺乏内容，对此深表歉意。
东西要写给别人看，这我还没有做到。


* 总结

关于Lambda和Scheme可看
http://en.wikipedia.org/wiki/Lambda_calculus
http://library.readscheme.org/page1.html