Lisp语言的后代，Scheme语言深入浅出

　　一、关于符号类型
　　符号类型又称引用类型，在概要一文中本人介绍得非常的模糊，使很多初学者不理解。符号类型在Scheme语言中是最基础也是最重要的一种类型，这是因为Scheme语言的祖先Lisp语言的最初目的就是符号处理，在Scheme语言中几乎所有的东西都可以看做是符号或做为符号列表来处理，这也是我们把符号类型做为第一个问题研究的原因。
　　
　　与符号类型相关的关键字有四个，分别是：quote, quasiquote, unquote和unquote-splicing，如下所示：
　　
　　规范用法：(quote obj)
　　简化用法：'obj (注意，'为右单引号，"双引号下面的那个符号。)
　　意义：符号类型的定义，(quote obj)本身就是一个值，虽然它不如数字123这样直观。
　　
　　规范用法：(quasiquote obj)
　　简化用法：`obj (注意，`为左单引号，~波浪号下面的那个符号。)
　　意义："类似符号"类型的定义，最好称之为逆符号类型，它可以将符号类型转换为具有实际意义的东西。
　　
　　规范用法：(unquote obj)
　　简化用法：,obj (注意，,逗号，<小于号下面的那个符号。)
　　意义："非符号"类型的定义，非符号类型出现在符号类型或逆符号类型定义中间，它不直接做为符号类型使用，而是将运算结果做为符号类型的一部分。
　　
　　规范用法：(unquote-splicing obj)
　　简化用法：,@obj
　　意义：非符号类型的拼接，注意：,@ 两个符号做为一个操作符来使用)。当非符号类型是一些复杂算法时，需要用它来做一下拼接，以达到符号类型的目的。
　　上面所说的所有规范用法和简化用法的功能都是相同的。
　　
　　符号类型的意义在于，一个说明，英文单词zebra指的是活生生的斑马，而'zebra或(quote zebra)指的是由字母z、e、b、r、a构成的这串符号(不是字符串)，就象我们定义变量(define x 100)，这时x指的就是100这个数值，而'x或(quote x)则代表字母x构成的这个符号。
　　
　　首先看一段代码：
　　
　　guile> (define s '(good morning))
　　guile> s
　　(good morning)
　　guile> (symbol? s)
　　#f
　　guile> (list? s)
　　#t
　　guile> (symbol? (list-ref s 1))
　　#t
　　
　　从此示例中可以看出，用quote定义的列表的类型仍是列表，而列表中的某一值的类型则是符号类型。还可以看出有点类似于如下：
　　
　　(+ 1 (+ 2 (+ 3 (+ 4 5))))　==>　(+ 1 2 3 4 5)
　　(list 'a 'b 'c 'd 'e)　　　==>　'(a b c d e)
　　
　　两者有异曲同工之妙，减少了多余的操作符，使表达式更直观，更容易理解。
　　
　　从 '(1 2 3 4 5) ==> (1 2 3 4 5) 可以看出，由符号类型的定义来形成列表，这是Scheme语言继承自LISP语言的传统。
　　
　　下面是在guile中的用法示例：
　　
　　guile> `(1 ,(+ 1 1) 3)
　　(1 2 3)
　　guile> (quasiquote (1 (unquote (+ 1 1)) 3))
　　(1 2 3)
　　;;;第一个是简化用法，第二个是标准用法。
　　
　　guile> `(1 ,@(map + '(1 3) '(2 4)) 9)
　　(1 3 7 9)
　　guile> (quasiquote (1 (unquote-splicing (map + (quote (1 3)) (quote (2 4)))) 9))
　　(1 3 7 9)
　　;;;第一个是简化用法，第二个是标准用法(注意：,@ 两个符号做为一个操作符来使用)。
　　
　　从示例中我们可以看出，这些应用多数与列表有关，而处理列表是Scheme语言的关键所在。符号类型的用法对深入理解Scheme语言也非常关键，因为Scheme语言本身就可以理解为是这种符号类型的列表，处理符号类型就是处理Scheme语言本身。
　　
　　二、关于尾递归
　　数列问题是研究递归的非常好的范例，在王垠的主页中有关于用菲波那契数列来说明非尾递归与尾递归之间区别和尾递归的好处的一个例子，见 http://learn.tsinghua.edu.cn/homepage/2001315450/wiki/TailRecursion.html 。我们这里用更简单一点的问题，求累计的问题来说明，即求自然数1+2+3+4+ ... +n的和。事实上就是设计一个过程，给它一个参数n，求1+2+3+ ... +n的和，我们首设计一个suma过程，代码如下：
　　
　　#! /usr/local/bin/guile -s
　　!#
　　
　　(define suma
　　(lambda (n)
　　(if (= n 1)
　　1
　　(+ n (suma (- n 1))))))
　　
　　(display "(suma 100)　==>　")
　　(display (suma 100)) (newline)
　　
　　(display "(suma 818)　==>　")
　　(display (suma 818)) (newline)
　　运行这段代码，会出现如下结果：
　　(suma 100)　==>　5050
　　(suma 818)　==>　334971
　　
　　说明：
　　以(suma 5)为例，表达式展开后：
　　
　　(suma 5)
　　(+ 5 (suma 4))
　　(+ 5 4 (suma 3))
　　(+ 5 4 3 (suma 2))
　　(+ 5 4 3 2 (suma 1))
　　(+ 5 4 3 2 1)　==>　15
　　
　　如果n为1000的话则会最终形成(+ 1000 999 ... 3 2 1)这样长度惊人的表达式，结果直接导致guile的崩溃。
　　
　　为什么会是818呢？因为819是会溢出的，出错，得不到结果，这可能大出乎我们意料之外，因为如果用C来写这样功能的程序代码，可能会求到6位数而不出问题。这一过程是用非尾递归来完成的，它的扩张呈指数级增长。代码的迅速膨胀，使guile没有处理到1000就崩溃了。
　　
　　我们再来看看采用尾递归的情况，代码如下：
　　
　　#! /usr/local/bin/guile -s
　　!#
　　
　　(define sumb
　　(lambda (n)
　　(let f ((i n) (a 1))
　　(if (= i 1)
　　a
　　(f (- i 1) (+ a i))))))
　　
　　(display "(sumb 100)　==>　")
　　(display (sumb 100)) (newline)
　　
　　(display "(sumb 1000)　==>　")
　　(display (sumb 1000)) (newline)
　　
　　运行结果如下：
　　
　　(sumb 100)　==>　5050
　　(sumb 1000)　==>　500500
　　还是以n为5的情况来说明：
　　(sumb 5)
　　(f 5 1)
　　(f 4 6)
　　(f 3 10)
　　(f 2 13)
　　(f 1 15) ==> 15
　　
　　这样的话，始终是依次计算，不会出现列表膨胀，所以n为1000时也不会出错，计算速度也很快。
　　
　　此结果大超出了非尾递归的818限制，参数是10000也没问题，因它采用尾递归，代码根本没有膨胀，而是依次计算。首先是在过程内部绑定了一个过程f，它有两个参数，一个i的值来自sum过程的参数n，另一个参数a定义值为1，当i值不等于时，仍调用f，第一个参数(也就是i)减1，第二个参数(也就是a)的值在原来的基础上加上i，当i的值为1是返回a，也就此sum过程的结果。理解这些后，你会发现事实上尾递归是在过程的绑定和过程的参数上做文章，用参数来保存运算结果，递归调用绑定的过程，最终达到运算目的。
　　
　　三、关于过程参数的问题
　　过程的多参数问题对初学者不太好理解，一般情况下我们处理过程时，过程参数的数量是固定的，当过程的参数数量不固定时怎么办呢？对了，时刻记住列表，把过程的参数做为一个列表来处理，如求和过程：(sum arg1 arg2 ...)，(初学者可能对如何实现定义这样的过程无从下手不知所措)，我们如何来求这些参数的和呢？看下面的代码：
　　
　　guile> (define sum (lambda args (apply + args)))
　　guile> sum
　　#
　　guile> (sum 1 2 3 4 5)
　　15
　　
　　从中可以看出，lambda的格式有所变化，由原来的((lambda arg1 arg2 ...) body ...)变成了(lambda args body ...)，也就是将原来的多个项组成的列表，改成了用一个名称args来标识的列表，其本质并没有变，变的是我们的方法，由原来的单项处理变成了统一处理的列表。
　　
　　这里还用到了for-each过程，通过下面代码来看一下for-each过程的一般用法：
　　
　　guile> (define newdisplay (lambda (x) (begin (display x)(newline))))
　　guile> newdisplay
　　#
　　guile> (define tt (lambda args (for-each newdisplay args)))
　　guile> tt
　　#
　　guile> (tt 'abc 'efg 'tomson)
　　abc
　　efg
　　tomson
　　
　　for-each过程的一般用法是(for-each 过程 列表)，此中的过程可以是我们自定义的，也可以是系统提供的，还可以是lambda 表达式。
　　
　　栈结构是一种简单而又有意义的数据结构，我们可以用列表来模拟一个简单的栈，下面是代码：
　　
　　#! /usr/local/bin/guile -s
　　!#
　　
　　(define stack '())
　　
　　(define push!
　　(lambda (x)
　　(set! stack (cons x stack))))
　　
　　(define pop!
　　(lambda ()
　　(let ((temp (car stack)))
　　(set! stack (cdr stack))
　　temp)))
　　
　　(push! 9)
　　(push! 8)
　　(push! 7)
　　(display stack) (newline)
　　(display (pop!)) (newline)
　　(display stack) (newline)
　　
　　结果如下：
　　
　　(7 8 9)
　　7
　　(8 9)
　　
　　这里面我们定义了一个变量stack来表示栈，定义一个过程push!向栈内压数据，同时还定义了一个过程pop!来从栈内弹出数据，完成了基本的栈功能。这段代码的缺点是要定义一个外部的变量来表示栈，同时还有两个过程，如果创建多个栈的话就需要更多的过程和变量了，这在某些情况下是不可想象的，如果程序中要用100个栈，我们就不得不100次复制和更改上面的代码。如何解决这一问题呢？看下面的代码：
　　
　　#! /usr/local/b