大二时学习Scheme过程中的一些简单总结

目录

  1. 使用Edwin
    1. Edwin介绍
    2. 两种模式
    3. 主要快捷键
    4. 装载文件
    5. 退出及缓冲区
    6. 文件开关
    7. 缩进
    8. 复制粘贴
    9. 求值S-表达式
  2. 算数运算
    1. quotient、remainder、modulo和sqrt
    2. sin、cos、tan、asin、acos和atan
    3. 指数和对数
    4. 数值变换
  3. 比较do, let, loop
    1. 对象的比较
      1. eq?
      2. eqv?
      3. equal?
    2. 其它用于比较的函数
    3. 递归与尾递归
      1. 递归版
      2. 尾递归版
    4. named let
    5. letrec
    6. do
    7. 总结
  4. 高阶函数
    1. 高阶函数的介绍
    2. 映射
    3. for-each
    4. 过滤
    5. 归档
  5. 排序
    1. apply函数
  6. 数据结构
    1. Scheme的数据结构
    2. 字符
    3. 字符串
    4. 符号
    5. 向量
    6. 结构体
  7. 赋值
    1. 赋值
    2. 赋值和内部状态
    3. 副作用
    4. 队列
    5. 定义语法,宏
  8. 常用关键字
    1. display
    2. newline
    3. trace
    4. runtime

使用Edwin

Edwin介绍

Edwin是MIT Scheme系统的一个窗口式的编辑使用前端。启动Edwin实际是先启动Scheme系统,再启动也给Edwin前端。Edwin是一个使用Scheme写的交互式编辑器,其特点是支持Scheme表达式的编辑和求职。

两种模式

Edwin模式:
编辑Scheme文件的模式,如果装入一个.scm文件,相应的Edwin的这个编辑区处于Edwin模式。这种模式下可以编写Scheme程序,也可以对表达式求值。正常求出的值显示在最下面交互行,但不会显示出错信息,也不能进入调试系统。

REPL模式:
REPL也就是Read-Evaluation-Print-Loop,读入-求值-打印-循环。在该模式下,你可以看到状态条显示”REPL:lsten“。这时系统处于正常的Scheme交互模式,所有输出都显示在编辑器的窗口中,只不过是在Edwin中执行。这种情况下可以输出所有信息,包括进入debug模式。

主要快捷键

对于多行输入的表达四,换行后按C-i,系统能够将光标自动对齐到合适位置。
C-v:向下翻一屏   M-v:向上翻一屏
C-a:移动到行首   C-e:移动到行尾
C-b:往左移一位 C-f:往右移一位
C-p:往上移一位 C-n:往下移一位
C-xC-e则会对左边(光标位于表达式后但在同一行)或上一个(光标位于表达式后但位于下一个表达式前且不在同一行)表达式求值。
对区域内所有代码求值可以用C-M-z,若在Windows下使用Edwin,必须得前清理掉最上方的版权信息等。

装载文件

装载文件可以采用

1
2
(cd"d:\\lisp\\scheme")
(load"scheme1.scm")

然后按下C-x C-e之后会显示
;Loading “scheme1.scm”…done
当有大量的函数等需要写入的时候,建议用另外的记事本等来保存。

退出及缓冲区

一旦进入了Edwin,可以通过如下的方式退出:

C-x z
停止Edwin并返回到Scheme(suspend-edwin)。进入Edwin的editor过程调用正常返回。接下来若调用edit则会从上次停止的地方重启Edwin。

C-x c
保存任何修改过的缓冲区,关闭Edwin并返回到Scheme(save-buffers-kill-edwin)。这个与suspend-edwin命令类似,不过下次调用edit会重新初始化编辑器。

C-x C-z
停止Edwin并挂起Scheme,把控制权交给操作系统的命令解释器(suspend-scheme)。当Scheme被重新启用(使用命令解释器的作业控制(job-control)命令),Edwin会自动从它停止的地方重启。这个命令与Emacs的C-x C-z命令是一样的。

C-x C-c
保存任何修改的缓冲区,然后关闭Edwin和Scheme(save-buffers-kill-scheme)。把控制权交给操作系统的命令解释器,Scheme进程也被终止。此命令与Emacs的C-x C-c命令相同。

全局变量的补全功能:键入变量的前面几个字符,然后键入C-M-i,Edwin就会尝试去补全变量的名称,根据当前界限内的变量集。若给出了一个参数前缀,C-M-i会补全这个名称,根据当前的限制的(interned)符号集合(包括了边界变量作为一个子集)。

文件开关

文件的打开与关闭,编辑器的关闭。按下Ctrl-XCtrl-F来打开一个文件。如果你指定的文件并不存在,则会创建一个新文件。初始路径被设置为了‘C:\’,你在打开文件前应该修改这个路径。按下C-XC-S来保存文件,而按下C-x C-w则是文件另存为。退出编辑器请按下C-x C-c。

缩进

按下C-i或者TAB可以缩进。

复制粘贴

剪切,复制和粘贴。我们无法使用鼠标,因此复制(剪切)、粘贴起来就会显得不太方便。但你可以像下面这样做:
首先,通过方向键将光标移动至待选区域的开头,然后按下C-SPACE。
然后移动至结束位置按下C-w来剪切区域,按下M-w来复制区域。
最后,移动至你想要复制的区域,按下C-y。

求值S-表达式

按键M-z用于求值以define开头的S-表达式。
按键M-:用于在一个小型的缓冲区中求值S-表达式。这个通常用在测试用M-z求值的函数。
按键C-x C-e用于求值整个scheme缓冲区中的S-表达式。

算数运算

quotient、remainder、modulo和sqrt

函数quotient用于求商数(quotient)。
函数remainder和modulo用于求余数(remainder)。
函数sqrt用于求参数的平方根(square root)。
以下是一些示例:

1
2
3
4
5
6
(quotient73)
;Value:2
(modulo73)
;Value:1
(sqrt 10)
;Value:3.1622776601683795

sin、cos、tan、asin、acos和atan

atan接受1个或2个参数。如果期望atan的结果是1/2π,就使用第二个参数指明使用弧度制。
以下依旧是一些示例:

1
2
3
4
5
6
(atan1)
;Value:0.7853981633974483
(atan 1 0)
;Value:1.5707963267948966
(*4 (atan 1.0))
;Value:3.141592653589793

指数和对数

指数通过exp函数运算,对数通过log函数运算。a的b次幂可以通过(expt a b)来计算。

1
2
3
4
5
6
(exp2/3)
;Value:1.9477340410546757
(expt3 4)
;Value:81
(log1000)
;Value:6.907755278982137

数值变换

函数exact->inexact用于把分数转换为浮点数。

1
2
(exact->inexact(/2937))
;Value:1.380952380952381

比较do, let, loop

对象的比较

eq?

这个函数用来比较2个对象的地址,如果相同的话就返回#t。在Scheme中真用#t表示,假则用#f。
例如,(eq? str str)返回#t,因为str本身的地址的是一样的,但是”scheme”和”scheme”则被存储在不同的地址中,因此函数返回#f。注意,不要用eq?来比较数字,因为在R5RS和MIT-Scheme中均没有被指定返回值,建议使用eqv?或者=代替。以下是一些示例:

1
2
3
4
5
6
(define str "scheme")
;Value: str
(eq? str str)
;Value: #t
(eq? "scheme" "scheme")
;Value:()

eqv?

该函数比较2个储存在内存中的对象的类型和值,如果类型和值都一致则返回#t。对于过程(lambda表达式)的比较依赖于具体的实现。这个函数不能用于类似于表和字符串一类的序列比较,因为尽管这些序列看起来是一致的,但它们存储在不同的地址中。以下同样是一些示例:

1
2
3
4
5
6
7
8
(eqv? 1.0 1.0)
;Value: #t
(eqv? 1 1.0)
;Value: ()
(eqv? (list 1 2 3) (list 1 23)) 不要去比较序列
;Value: ()
(eqv? "scheme" "scheme")
;Value: ()

equal?

比较序列就应该这个函数了。

1
2
3
4
(equal? (list 1 2 3) (list 1 2 3))
;Value: #t
(equal? "hello" "hello")
;Value #t

其它用于比较的函数

pair?如果对象为序对则返回#t;

list?如果对象是一个表则返回#t。要小心的是空表’()是一个表但是不是一个序对。

null?如果对象是空表’()的话就返回#t。

symbol?如果对象是一个符号则返回#t。

char?如果对象是一个字符则返回#t。

string?如果对象是一个字符串则返回#t。

number?如果对象是一个数字则返回#t。

complex?如果对象是一个复数则返回#t。

real?如果对象是一个实数则返回#t。

rational?如果对象是一个有理数则返回#t。

integer?如果对象是一个整数则返回#t。

exact?如果对象不是一个浮点数的话则返回#t。

inexact?如果对象是一个浮点数的话则返回#t。

odd?如果对象是一个奇数的话则返回#t。

even?如果对象是一个偶数的话则返回#t。

postitive?如果对象是一个正数的话则返回#t。

negative?如果对象是一个负数的话则返回#t。

zero?如果对象是零的话则返回#t。

类似于用<=等比较数字,在比较字符的时候可以使用char=?、char<?、char>?、
char<=?以及char>=?函数。

比较字符串时,可以使用string=?和string-ci=?等函数。

递归与尾递归

在自己的定义中调用自己的函数叫做递归函数(Recursive Function)。想必大家都知道这些。
计算阶乘则是演示递归的典型示例。

1
2
3
4
(define (fact n)
(if (= n 1)
1
(* n(fact (- n 1)))))

因此(fact 5)的计算过程用以下方式可以说明得很明显。

1
2
3
4
5
6
7
8
9
10
(fact 5)
=> 5 * (fact 4)
=> 5 * 4 * (fact 3)
=> 5 * 4 * 3 * (fact 2)
=> 5 * 4 * 3 * 2 * (fact 1)
=> 5 * 4 * 3 * 2 * 1
=> 5 * 4 * 3 * 2
=> 5 * 4 * 6
=> 5 * 24
=> 120

但由于(fact 5),(fact 4)…(fact 1)都被分配了不同的存储空间,直到(fact(- i 1))返回一个值前,(fact i)都会被保存在内存中,由于存在函数调用的开销,这也就意味着会占用更多的内存空间和计算时间。

这种时候,使用尾递归则包含了计算结果,当计算结束时直接将其返回。尤其是Scheme规范要求尾递归调用转化为循环,因此尾递归调用就不存在函数调用开销。以下就是fact函数的尾递归版本。

1
2
3
4
5
6
7
(define (fact-tail n)
(fact-rec n n))
(define (fact-rec n p)
(if (= n 1)
p
(let ((m (- n 1)))
(fact-rec m (* p m)))))

同时,计算过程如下。

1
2
3
4
5
6
7
(fact-tail 5)
⇒(fact-rec 5 5)
⇒(fact-rec 4 20)
⇒(fact-rec 3 60)
⇒(fact-rec 2 120)
⇒(fact-rec 1 120)
120

就是因为使用fact-rec并不用等待其它函数的计算结果,因此当它计算结束时即从内存中释放。fact-rec的参数不断在变化,这实际上就相当于是一种循环。就如同上文说到的,Scheme将尾递归转化为循环。

我们先来看看2个递归的例子。

1
2
3
4
5
6
7
8
9
10
11
12
(define (my-length ls)
(if (null? ls)
0
(+ 1 (my-length(cdr ls)))))
(define (remove x ls)
(if (null? ls)
'()
(let ((h (car ls)))
((if (eqv? x h)
(lambda (y) y)
(lambda (y) (cons h y)))
(remove x (cdr ls))))))

这2个例子的一个很明显的区别在于它们各自最后让递归过程停止的对象不同,前者是0,后者是’()。对于前者,我们要算出的是ls中元素的个数,后者则是将ls中的x元素去掉。前者最后返回的是数,后者则是表。

下面我们通过具体的示例来深入了解这两者之间的关系。

求和由数构成的表中的元素

递归版

1
2
3
4
(define (my-sum ls)
(if (null? ls)
0
(+ (car ls) (my-sum (cdr ls)))))

尾递归版

1
2
3
4
5
6
7
(define (my-sum-tail ls)
(my-sum-rec ls 0))
(define (my-sum-rec ls n)
(if (null? ls)
n
(my-sum-rec (cdr ls) (+ n (car ls)))))

前者最后当ls为空是,返回0给+这个操作;后者的+操作则在my-sum-rec这个函数的参数位置,因此最后返回的是整个运算的结果n。前者通过不断地加上(car ls)来达到最终的目的;后者则通过不断的循环,将+操作的最终结果赋值给n。

named let

named let也可以用来表示循环,以下这个fact-let函数使用了一个loop,这和上文中的fact-rec函数是有很大区别的。在代码的第二行,代码将参数n1和p都初始化为n。当每次循环后,参数都在最后一行进行更新,此处的更新为:将n1减1,而将p乘以(n1-1)。

1
2
3
4
5
6
(define (fact-let n)
(let loop ((n1 n)(p n))
(if(= n1 1)
p
(let ((m (- n1 1)))
(loop m (* p m))))))

当然了,如果觉得有了一个let在这里比较难以理解,下面这样也是可以的,不过上面这张方式更加简洁明了罢了。

1
2
3
4
5
(define (fact-let n)
(let loop ((n1 n) (p n))
(if (= n1 1)
p
(loop (- n1 1) (* p (- n1 1)))))

同样,我们通过对比递归来理解named let。
我们要做的是通过函数求出x元素在ls中的位置,索引从0开始,如果不在ls中则返回#f。

递归版:

1
2
3
4
5
6
7
8
(define (position x ls)
(position-aux x ls 0))
(define (position-aux x ls i)
(cond
((null? ls) #f)
((eqv? x (car ls)) i)
(else (position-aux x (cdr ls) (1+ i)))))

named let版:

1
2
3
4
5
6
(define (position x ls)
(let loop((ls0 ls) (i 0))
(cond
((null? ls0)#f)
((eqv? x (car ls0)) i)
(else (loop (cdr ls0)(1+ i))))))

后者就像嵌套一般,进入了递归版的第二行代码。前者的else后面,通过函数调用返回自身;后者则很直接地通过更新参数来达到和递归同样的目的。后者我们先将ls赋值给ls0,通过不断的(cdrls0)来更新,先将0赋值给i,通过不断的(1+ i)来更新,这和递归中最后一行有着异曲同工之妙。

下面我们再通过尾递归来理解named let,多角度的对比,能够使我们更清晰的理解和加深印象。

这些的示例都很简单,基本上各大书籍文档中都大同小异,下面我们通过一个函数来反转ls中的所有元素。

尾递归版:

1
2
3
4
5
6
7
(define (my-reverse ls)
(my-reverse-rec ls ()))
(define (my-reverse-rec ls0 ls1)
(if (null? ls0)
ls1
(my-reverse-rec (cdr ls0) (cons (car ls0) ls1))))

named let版:

1
2
3
4
5
(define (my-reverse-letls)
(let loop ((ls0 ls) (ls1 ()))
(if (null? ls0)
ls1
(loop (cdr ls0)(cons (car ls0) ls1)))))

我们很容易的看到两个版本的最后一行几乎一模一样;后者的第二行也相当于将前者的第二行代码并到第三行代码一样。由此可见,named let也不过是个皮囊而已,正在的动力依旧来源于不断的更新。

如果对named let感兴趣的话,可以看看这道题:【SICP练习】152 练习4.8

letrec

letrec类似于let,不过它允许让一个名字递归地调用它自身。通常letrec都用于定义复杂的递归函数。
依旧是这个经典的示例:

1
2
3
4
5
6
7
(define (fact-letrec n)
(letrec ((iter (lambda (n1 p)
(if (= n1 1)
p
(let ((m (- n1 1)))
(iterm (* p m)))))))
(iter n n)))

倒数第二行的代码中,局部变量iter可以在它的定义里面引用它自己。而语法letrec是定义局部变量约定俗成的方式。

还是老规矩,对比出真知,我们先来看看上面第二大节中用来对比过的求和的例子。

我还在再次将它们贴出来好了。

尾递归版:

1
2
3
4
5
6
7
(define (my-sum-tail ls)
(my-sum-rec ls0))
(define (my-sum-rec ls n)
(if (null? ls)
n
(my-sum-rec (cdr ls) (+ n (car ls)))))

letrec版:

1
2
3
4
5
6
(define (my-sum-letrec ls)
(letrec((iter(lambda(ls0 n)
(if(null? ls0)
n
(iter (cdr ls0) (+ (car ls0) n))))))
(iter ls0)))

我们可以看出后者的最后一行的ls和0被赋值到第二行的ls0和n中,然后再倒数第二行中得到更新。下面我们再来看一个示例,这是将一个代表正整数的字符串转化为对应整数。例如“ 3389”会被转化为3389。不过只是个示例而已,不需要去检查那些不合法的输入。符到整数的转化是通过将字符#\0……#\9的ASCII减去48,可以使用函数char->integer来获得字符的ASCII码。函数string->list可以将字符串转化为由字符构成的表。

尾递归版本:

1
2
3
4
5
6
7
8
(define (my-string->integer str)
(char2int (string->list str) 0))
(define (char2int ls n)
(if (null? ls)
n
(char2int (cdr ls)
(+ (- (char->integer (car ls)) 48)
(* n 10))))

named let版本:

1
2
3
4
5
6
7
(define (my-string->integer-letstr)
(let loop ((ls0 (string->list str)) (n0))
(if (null? ls0)
n
(loop (cdr ls0)
(+ (- (char->integer (car ls0)) 48)
(* n 10))))))

letrec版本:

1
2
3
4
5
6
7
8
(define (my-string->integer-letrec str)
(letrec ((iter (lambda (ls0 n)
(if (null? ls0)
n
(iter (cdr ls0)
(+ (- (char->integer (car ls0)) 48)
(* n 10)))))))
(iter (string->list str) 0)))

将尾递归中的第二行并到第三行就相当于named let版本的第二行了,更新的过程也大同小异。letrec版本的也和这个类似,将最后一行并到第二行也是一样的,第五行到第七行均为参数的更新,更新的过程也就是求解的过程。

do

就像在C系列语言中我们通常用while比较多而do比较少一样,在scheme中do也并不常见,但语法do也可以用于表达重复。它的格式如下:

1
2
3
(do binds
(predicate value)
body)

变量在binds部分被绑定,而如果predicate被求值为真,则函数从循环中逃逸(escape)出来,并返回值value,否则循环继续进行。binds部分的格式如下所示:

1
[binds] - ((p1 i1 u1) (p2 i2u2)...)

变量p1,p2,…被分别初始化为i1,i2,…并在循环后分别被更新为u1,u2,…。

最后一次fact函数的do表达式版本。

1
2
3
(define (fact-do n)
(do ((n1 n (- n1 1)) (p n (* p (- n1 1))))
((= n1 1) p)))

变量n1和p分别被初始化为n和n,在每次循环后分别被减去1和乘以(n1-1)。当n1变为1时,函数返回p。此处的n1和p分别相当于上文中的p1和p2,n1后面的n和p后面的n分别相当于上文中的i1和i2,(- n1 1)和(* p (-n1 1))分别相当于上文中的u1和u2。

do也挺难的,不过我觉得letrec更加难以灵活运用。
下面我们换一种方式,通过各个示例的do版本之间的联系来对比加深对这些语法的理解。

1
2
3
4
5
6
7
8
9
10
11
12
13
(define (my-reverse-do ls)
(do ((ls0 ls (cdr ls0)) (ls1() (cons (car ls0) ls1)))
((null? ls0) ls1)))
(define (my-sum-do ls)
(do ((ls0 ls (cdr ls0))(n0 (+ n (car ls0))))
((null? ls0) n)))
(define (my-string->integer-do str)
(do ((ls0 (string->list str)(cdr ls0))
(n0 (+ (- (char->integer (car ls0)) 48)
(* n1 0))))
((null? ls0) n)))

加色部分通过上文的讲解相信很容易理解了,最后一行都是do的终止的判断,为真的时候则求值并返回最后一个ls1(或n)。

总结

通过这一节的学习,相信大家都对讲过的语法有了一定的理解,大家可以利用这些函数来编写自己的程序了。简单的循环用let就够了,至于复杂的局部递归函数则可以使用letrec。至于do,如果能够灵活运用,相信也是威力无穷的。那么,我们下节见咯。

高阶函数

高阶函数的介绍

高阶函数的英文名称是Higher Order Function,它们是以函数为参数的函数。主要用于映射(mapping)、过滤(filtering)、归档(folding)和排序(sorting)表。高阶函数让程序更具模块性,让函数更加通用。

函数sort具有2个参数,一个是需要排序的表,另一个是定序(Ordering)函数。下面展示了按照大小将一个整数表正序排序。而<函数就是本例中函数的定序函数。

1
2
(sort‘(420 -130 138 983 0298 783 -783) <)
;Value:(-783 -130 0 138 298 420 783 983)

通过灵活使用定序函数,我们可以写出更强大的函数。

1
2
3
(sort‘(783 298 -289 429 892479 -197)
(lambda(x y) (< (modulo x 100)(modulo y 100))))
;Value:(-197 -289 429 479 783 492 892 298)

我们之前讲过,modulo函数用来求余。

Scheme并不区别过程和其他的数据结构,因此你可以通过将函数当作参数传递轻松的定义自己的高阶函数。而且Scheme并没有定义块结构的语法,因此使用lambda表达式作为一个块。

映射

映射是将同样的行为应用于表所有元素的过程。R5RS定义了两个映射过程:其一为返回转化后的表的map过程,另一为注重副作用的for-each过程。

map过程的格式如下:

1
(map procedurelist1 list2…)

procedure是个与某个过程或lambda表达式相绑定的符号。作为参数的表的个数视procedure需要的参数而定。

1
2
3
4
(map+‘(1 3 5)‘(2 4 6))
;Value:(3 7 11)
(map(lambda (x) (* x x))‘(1 2 3))
;Value:(1 4 9)

通过类比可以发现后者的lambda表达式相当于前者的+函数。只不过后者只有一个list,而前者有2个。如果想要像前者一样,让两个list中的元素一次相乘,除了用*外,也可以用lambda表达式。

1
2
(map(lambda (x y) (* x y))‘(1 2 3)‘(2 4 6))
;Value:(2 8 18)

但是如果我们这样写:

1
(map (lambda (x) (* x x))‘(1 2 3)‘(1 3 5))

它并不会得出(1 4 9) (1 9 25)。

如果我们这样写:

1
(map (lambda (x y) (* x x) (* y y))‘(1 2 3)‘(1 3 5))

它得出的结果是(1 9 25),这是因为其只有一个返回值。但是(* x x)这一部分确实计算了。通过下面的例子我们可以确信这一点。

1
2
3
4
5
6
(map(lambda (x y) (let ((list1 (* x x)) (list2(* y y)))
list1))‘(1 2 3)‘(1 3 5))
;Value:(1 4 9)
(map(lambda (x y) (let ((list1 (* xx)) (list2(* y y)))
list1 list2))‘(1 2 3)‘(1 3 5))
;Value:(1 925) 这里同样是因为其只能有一个返回值。

而map函数最终的返回值以运算结果来判断。

1
2
3
4
(map - '(3 2 0) '(3 1 1 3))
;Value:(0 1 -1)
(map – '(3 2 0) '(3 1))
;Value:(0 1)

因为前者中list1中没有和list2中最后一个元素相对应的元素了,而后者中list2中没有和list1中最后一个元素相对应的元素。

1
2
(map(lambda (x y z) (* x x) (* y y) (* z z))‘(1 2)‘(3 4 5) ‘(6 78 9))
;Value:(36 49)

而在这里例子中为什么最后的返回值不是(36 49 64 81),博主也不知道了,还请知道的网友留个回复。

for-each

for-each的格式与map一致,但是for-each并不返回一个具体的值,只是用于副作用。(副作用的解释)我们同样通过一个示例来展示。

1
2
3
4
5
6
(definesum 0)
;Value:sum
(for-each(lambda (x) (set! sum (+ sum x)))‘(1 2 3 4))
;Unspecifiedreturn value
sum
;Value:10

如前所述,for-each并没有返回值。

过滤

尽管过滤函数并没有在R5RS中定义,但MIT-Scheme实现提供了keep-matching-items和delete-matching-item两个函数。注意item后加和不加s。

1
2
(keep-matching-items‘(1 -2 3 -4 5)even?)
;Value: (-2 -4)

其中even?我们可以认为对应于上前文中sort函数的定序函数,当然,我们也可以用lambda来作为这个参数。

1
2
(keep-matching-items‘(10 39 0 -100 76)(lambda (x) (<= 10 x 100)))
;Value: (10 39 76)

归档

同样在R5RS中没有定义归档函数,但MIT-Scheme提供了reduce等函数。

1
2
3
4
5
6
7
8
(reduce + 0 '(1 2 34)) ;⇒ 10
(reduce + 0 '(12)) ;⇒ 3
(reduce + 0'(1)) ;⇒ 1
(reduce + 0'()) ;⇒ 0
(reduce + 0'(foo)) ;⇒ foo
(reduce list '() '(1 2 34)) ;⇒ (((1 2) 3) 4)
(define (sqrt-sum-sq ls)
(sqrt (reduce + 0(map (lambda (x) (* xx)) ls))))

排序

同样在R5RS中没有定义排序函数,而在MIT-Scheme中提供了sort(实为merge-sort实现)和quick-sort函数。这个函数我们在前面展示过,下面我们用sort函数,lambda,tan函数和<来写一个以tan(x)的大小升序排列的函数。

1
2
3
4
5
(define(sort-tan ls)
(sort ls(lambda (x y) (< (sin x) (siny)))))
;Value:sort-tan
(sort-tan‘(1 2 3 4 5 6))
;Value:(5 4 6 3 1 2)

apply函数

apply函数将一个过程应用于一个表,也就是将表展开作为过程的参数。该函数具有任意多个参数,但首末参数必须分别是一个过程和一个表。

1
2
3
4
(applymax‘(-1 2 -3))
;Value:2
(apply* 1 2‘(3 4 5))
;Value:120

数据结构

Scheme的数据结构

在前面的博文中我们使用了list等等,像其他的编程语言一样,Scheme也有字符(Character),字符串(String),符号(Symbol),向量(Vector)等数据结构。下面我们来一一介绍。

字符

在某个字符前添加#\来表面该物是一个字符。例如,#\a表示字符a。

\Space,#\Tab,#\Linefeed,#\Return分别代表空格(Space),制表符(Tab),换行(linefeed)和返回(Return)。

1
2
3
4
5
6
(char-whitespace?#\ )
;Value:#t
(char-whitespace?#\)
;Value:#\)
(char-whitespace?#\a)
;Value:#f

(char? obj) 如果obj是一个字符则返回#t。
(char=? c1 c3) 如果c1和c2是同一个字符的话则返回#t。
(char->integer c) 将c转化为对应的整数(字符代码,character code)。示例:(char->integer #\a) => 97
(integer->char n) 该函数将一个整数转化为对应的字符。

1
2
3
4
(char<? c1 c2)
(char<= c1 c2)
(char> c1 c2)
(char>= c1 c2)

这些函数用于比较字符。
实际上,这些函数比较的是字符代码的大小。
例如,(char<?c1 c2)等同于(< (char->integer c1) (char->integerc2))

1
2
3
4
5
(char-ci=? c1 c2)
(char-ci<? c1 c2)
(char-ci<=? c1 c2)
(char-ci>? c1 c2)
(char-ci>=? c1 c2)

这些比较函数对大小写不敏感。

1
2
3
4
5
(char-alphabetic? c)
(char-numeric? c)
(char-whitespace? c)
(char-upper-case? c)
(char-lower-case? c)

这些函数分别用于检测字符c是否为字母、数字、空白符、大写字母或小写字母。

1
2
(char-upcase c)
(char-downcase c)

这些函数分别返回字符C对应的大写或小写。

字符串

字符串通过两个闭合的双引号表示。例如,”abc“表示字符串abc。

1
2
3
4
5
6
7
8
9
(string? s) 如果s是一个字符则返回#t。
(make-string n c) 返回由n个字符c组成的字符串。参数c可选。
(string-length s) 返回字符串s的长度。
(string=? s1 s2) 如果字符串s1和s2相同的话则返回#t。
(string=?“a” “A”)
;Value:#f
(string-ref s idx) 返回字符串s中索引为idx的字符(索引从0开始计数)。
(string-ref“abc” a)
;Value:#\c (index form 0)
1
2
3
4
5
6
(string-set! s idx c) 将字符串s中索引为idx的字符设置为c。
(substring s start end) 返回字符串s从start开始到end-1处的子串。
(string-append s1 s2 ...) 连接两个字符串s1s2
(string->list s) 将字符串s转换为由字符构成的表。
(string->list“abABcD”)
;Value:(#\a #\b #\A #\B #\c #\D)
1
2
(list->string ls) 将一个由字符构成的表转换为字符串。
(string-copy s) 复制字符串s。

符号

1
2
3
4
5
6
7
8
9
10
(symbol? x)
如果x是一个符号则返回#t
(string->symbol str)
将str转换成符号。str应该都是小写,否则地址系统可能无法正常工作。
(eq?(string->symbol “hello”) ‘hello)
:Value:#t
(eq?(string-symbol “hello”) “hello”)
;Value:#f
(symbol->string(string->symbol “hello”))
;Value:“hello”
1
2
(symbol->string sym)
将sym转换为字符。

向量

与C语言中的数组不同,一个向量可以存储不同类型的数据。与表相比,向量更加紧凑并且存取时间更短。但从另外一个方面来说,向量是通过副作用来操作的,这样会造成负担。Scheme中的结构体与C语言中的结构体类似。但Scheme中的结构体比C语言中的更容易使用,这是因为Scheme为结构体自动创建了读取函数和写入函数,这收益于Lisp/Scheme程序设计语言中的宏。

向量通过闭合的#表示,例如#(12 3)。但作为字面值时,它们应该被引用,例如:

1
2
#(1 2 3 4)
#(a 0 #\a)
1
2
3
4
5
(vector? obj) 如果obj是一个向量则返回#t。
(make-vector k fill) 放回一个有k个元素的向量,如果指定了第二个参数fill,那么所有的元素都会被初始化为fill。
(vector obj …) 返回由参数列表构成的向量。
(vector“a” ‘a ‘())
;Value:#(“a” a ())
1
2
3
4
5
6
(vector-length vector) 返回向量vector的长度。
(vector-ref vector k) 返回向量vector的索引为k的元素。(索引从0开始)
(vector-set! vector k obj) 将向量vector的索引为k的元素修改为obj。
(vector->list vector) 将vector转换为表。
(list->vectorlist) 将list转换为向量。
(vector-fill!vector fill) 将向量vector的所有元素设置为fill。(备注,还未弄清楚fill到底上要填什么)
1
2
3
4
5
6
7
8
9
10
11
12
一个对向量中元素求和的函数。
(define (vector-add v1 v
(let((lenv1 (vector-length v1))
(lenv2 (vector-length v2)))
(if (= lenv1 lenv2)
(let ((v (make-vector lenv1)))
(letloop ((i 0))
(if (= i lenv1)
v
(begin
(vector-set!v i (+ (vector-ref v1 i) (vector-ref v2 i))) (loop (1+ i))))))
(error "differentdimensions."))))

结构体

结构体本质上来说豆色向量,每一个槽都通过使用一个宏来命名。结构体通过不同的属性清楚地表示数据。定义结构体的宏自动为结构体创建读取(accessor)函数和设置(setter)函数。你可以通过“程序“来写程序,这被认为是Lisp/Scheme最好的好处之一。

在MIT-Scheme中,结构体通过函数define-structure来定义。为了使你更加容易理解,我会用一个实例来讲清楚。
请考虑书籍。书籍都有下列属性:
标题
作者
出版商
出版年份
ISBN号
因此结构体book就可以像下面这样定义:

1
(define-structure book title authors publisheryear isbn)

下面演示了如何注册《大教堂与市集(The Cathedral and Bazaar)》。

1
2
3
4
5
6
7
(define bazaar
(make-book
"The Cathedral and the Bazaar"
"Eric S. Raymond"
"O'Reilly"
1999
0596001088))

然而,这样做多多少少有点不便,因为属性与值的关联并不清楚。参量keyword-constructor可以用于解决这个问题。下面的代码就是使用这个参量的重写版,这个版本中,属性与值的关联就非常清楚了。更进一步来说,制定这个参量后,参数的顺序就不重要了。
参量copier可用于为结构体创建一个拷贝(copier)函数。

1
2
3
4
5
6
7
8
9
10
(define-structure (book keyword-constructorcopier)
titleauthors publisher year isbn)
(define bazaar
(make-book
'title "The Cathedral and the Bazaar"
'authors "Eric S. Raymond"
'publisher "O'Reilly"
'year1999
'isbn0596001088))

一个名字形如[结构体名称]?的函数用于检查某对象是否为特定结构体。例如,可使用函数book?来检查bazaar是否为book结构体的一个实例。

1
2
(book? bazaar)
;Value: #t

一个名字形如copy-[结构体名称]的函数用于拷贝结构体。例如,下面的代码演示了将bazaar拷贝到cathedral。

1
(define cathedral (copy-book bazaar))

一个名字形如[结构体名称]-[属性名称]的函数用于读取结构体某属性的值。例如,下面的代码演示了如何读取bazaar的title属性。

1
2
(book-title bazaar)
;Value 18: "The Cathedral and theBazaar"

一个名字形如set-[结构体名称]-[属性名称]!用于将某属性设定为特定值。下

面的代码演示了如何将bazaar的year字段更新到2001(《大教堂与市集》2001年再版)。

1
2
3
4
5
(set-book-year! bazaar 2001)
;Unspecified return value
(book-year bazaar)
;Value: 2001

赋值

赋值

因为Scheme是函数式语言,通常来说,你可以编写不使用赋值的语句。然后如果使用赋值的话,有些算法就可以轻易实现了。尤其是内部状态和继续(continuations)需要赋值。

R5RS中规定的用于赋值的特殊形式是set!,set-car!,set-cdr!,string-set!,vector-set!等。

因为赋值改变了参数的值,因此它具有破坏性(destructive)。
在Scheme中,具有破坏性的方法都以!结尾,以警示程序员。

set!可以为一个参数赋值。与Common Lisp不同,set!无法给一个S-表达式赋值。另外,在赋值前参数应该被定义。例如:

1
(define num 10) ;Value: num (set! num (* num num)) ;Value: 100 (let ((n 0)) (set!n (+ n 3)) n) ;Value: 3

赋值和内部状态

Scheme中变量的作用被限定在了源码中定义其的那个括号里。作用域与源代码书写方式一致的作用域称为“词法闭包(Lexical closure)”或“静态作用域(Static scope)”。

另一方面,还有一种被称为“动态作用域(Dynamic scope)”的作用域。这种作用域仅在程序运行时确定。但由于会在调试时带来种种问题,这种作用域现在已经不再使用。

特殊形式let,lambda,letrec生成闭包。lambda表达式的参数仅在函数定义内部有效。let只是lambda的语法糖,因此二者无异。

你可以使用词法闭包来实现带有内部状态的过程。我们通过一个简单的银行账户的例子来展示。

1
2
3
4
5
(define bank-account
(let ((balance 100))
(lambda (n)
(set!balance (+ balance n))
balance)))

该过程将存款赋值为(+ balance n),下面是调用这个过程的结果。

1
2
3
4
(bank-account 100)
;Value: 200
(bank-account -50)
;Value: 150

因为在Scheme中,你可以编写返回过程的过程,因此你可以编写一个创建银行账号的函数。这个例子预示着使用函数式程序设计语言可以很容易实现面向对象程序设计语言。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
(define (make-bank-account balance)
(lambda(n)
(set!balance (+ balance n))
balance))
(define bill-bank-account (make-account 100))
;Value: bill-bank-account
(bill-bank-account 50)
;Value: 150
(bill-bank-account -100
;Value: 50
(define nomasp-bank-account (make-bank-account200))
;Value: nomasp-bank-account
(nomasp-bank-account -50)
;Value: 150
(nomasp-bank-account 250)
;Value: 400

副作用

Scheme过程的主要目的是返回一个值,而另一个目的则称为副作用(Side Effect)。赋值和IO操作就是副作用。

表的破坏性操作(set-car!,set-cdr!)
函数set-car!和set-cdr!分别为一个cons单元的car部分和cdr部分赋新值。和set!不同,这两个操作都可以为S-表达式赋值。

1
2
3
4
5
6
(define list1 ‘((1 2) (3 4 5) (6 7 8 9)))
;Value: list1
(set-cdr! (third list1) ‘(a b c))
;Unspecified return value
list1
;Value: ((1 2) (3 4 5) (6 a b c))

队列

队列可以用set-car!和set-cdr!实现。队列是一种先进先出(First in first out, FIFO)的数据结构,表则是先进后出(Firstin last out, FILO)。
队列的Scheme实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
(define (make-queue)
(cons'() '()))
(define (enqueue! queue obj)
(let((lobj (cons obj '())))
(if(null? (car queue))
(begin
(set-car! queue lobj)
(set-cdr! queue lobj))
(begin
(set-cdr! (cdr queue) lobj)
(set-cdr! queue lobj)))
(carqueue)))
(define (dequeue! queue)
(let((obj (car (car queue))))
(set-car! queue (cdr (car queue)))
obj))
(define q (make-queue))
;Value: q
(enqueue! q 'a)
;Value 12: (a)
(enqueue! q 'b)
;Value 12: (a b)
(enqueue! q 'c)
;Value 12: (a b c)
(dequeue! q)
;Value: a
q
;Value 13: ((b c) c)

定义语法,宏

用户定义语法称作宏(Macro)。Lisp/Scheme中的宏比C语言中的宏更加强大。宏可以使你的程序优美而紧凑。

宏是代码的变换。代码在被求值或编译前进行变换,and the procedure continues as if the transformed codes are writtenfrom the beginning.

你可以在Scheme中通过用符合R5RS规范的syntax-rules轻易地定义简单宏,相比之下,在Common Lisp中自定义语法就复杂多了。使用syntax-rules可以直接定义宏而不用担心变量的捕获(Variable Capture)。On the other hand,defining complicated macros that cannot be defined using the syntax-rules ismore difficult than that of the Common Lisp.

我将以一个简单的宏作为例子。
[代码片段 1]一个将变量赋值为’()的宏

1
2
3
4
(define-syntax nil!
(syntax-rules ()
((_x)
(set! x '()))))

syntax-reuls的第二个参数由是变换前表达式构成的表。_代表宏的名字。简言之,代码片段1表示表达式(nil! x)会变换为(set!x ‘()).

这类过程不能通过函数来实现,这是因为函数的闭包性质限制它不能影响外部变量。让我们来用函数实现代码片段1,并观察效果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
(define (f-nil! x)
(set!x '()))
(define a 1)
;Value: a
(f-nil! a)
;Value: 1
a
;Value: 1 ; the value of a dose not change
(nil! a)
;Value: 1
a
;Value: () ; a becomes '()

我会演示另外一个例子。我们编写宏when,其语义为:当谓词求值为真时,求值相应语句。

1
2
3
4
(define-syntax when
(syntax-rules ()
((_pred b1 ...)
(ifpred (begin b1 ...)))))

代码片段2中的…代表了任意多个数的表达式(包括0个表达式)。代码片段2揭示了诸如表达式(whenpred b1 …)会变换为(if pred (begin b1 …))。
由于这个宏是将表达式变换为if特殊形式,因此它不能使用函数来实现。下面的例子演示了如何使用when。

1
2
3
4
5
6
(let ((i 0))
(when(= i 0)
(display "i == 0")
(newline)))
i == 0
;Unspecified return value

我会演示两个实宏:while和for。只要谓词部分求值为真,while就会对语句体求值。而数字在指定的范围中,for就会对语句体求值。

1
2
3
4
5
6
7
8
9
10
11
12
13
(define-syntax while
(syntax-rules ()
((_pred b1 ...)
(let loop () (when pred b1 ... (loop))))))
(define-syntax for
(syntax-rules ()
((_(i from to) b1 ...)
(let loop((i from))
(when (< i to)
b1 ...
(loop (1+ i)))))))

下面演示了如何实用它们:

1
2
3
4
5
6
7
8
9
10
11
12
13
(define-syntax while
(syntax-rules ()
((_pred b1 ...)
(let loop () (when pred b1 ... (loop))))))
(define-syntax for
(syntax-rules ()
((_(i from to) b1 ...)
(let loop((i from))
(when (< i to)
b1 ...
(loop (1+ i)))))))

常用关键字

display

在common lisp中有format,在scheme中则有display,轻松应对各种输出。

1
2
3
4
5
6
(display(+ 1 2 3 4))
10
;Unspecifiedreturn value
(display‘(1 2 3 4))
(12 3 4)
;Unspecifiedreturn value

newline

换行符一枚

trace

trace可以用来跟踪函数的调用。我们用一个简单的例子来展示:

1
2
3
4
5
6
(define(cube x)
(* x x x))
(define(sum-cube-x x)
(if (= x 1)
x
(+ (cube x) (sum-cube-x (- x 1)))))

然后就可以开始跟踪了:

1
2
3
4
5
6
7
8
(trace-entrycube)
;Unspecifiedreturn value
(sum-cube-x3)
[Entering#[compound-procedure 12 cube]
Args: 2]
[Entering#[compound-procedure 12 cube]
Args: 3]
;Value:36

返回值之前的就是跟踪的结果了,跟踪结果除了告诉我们(sum-cube-x 3)共调用了2次cube外,还列出了每次调用的参数。

runtime

在新版本的MIT-Scheme中,runtime按秒来计算,如要用微秒可采用real-time-clock函数。不过这两者的用法是一样的。

1
2
3
4
(runtime)
;Value:79.163
(real-time-clock)
;Value:6922453

如果要测试一个表达式等的运行时间,在Scheme也同样是完全可以做到的:在表达式之前和之后分别添加一个real-time-clock即可,两个real-time-clock之间的数值差就是运行该表达式等的所需时间。具体代码如下:

1
2
3
4
(define(get-time)
(let ((start-time (real-time-clock)))
(get-time-2)
(- (real-time-clock) start-time)))

这个get-time函数返回的就是运行get-time-2函数所需的时间了。