仓库源文站点原文


key: 75 title: Scheme 语言 math: true

tags: [comupter-science, featured]

我最近在读 SICP (Structure and Interpretation of Computer Programs),中文译名是《计算机程序的构造与解释》,感觉受益匪浅。我打算开个坑,总结分享一些我学到的内容。SICP 综合性非常强,内容包括函数式编程、数据结构的分层与抽象、面向对象、无限流、元循环解释器、惰性求值、非确定性编程、逻辑编程、汇编语言与机器、编译原理等等。我只能选取一个主题抛砖引玉,这个系列文章的主题是 continuation,主要内容可能包括:

我最近已经在读最后一章了,待读完本书后再看情况更新一些内容。这些内容的基础是 Scheme 语言,我们从介绍 Scheme 语言开始。本文介绍的 Scheme 语言主要目的是让不了解 Scheme 的同学看完之后能看得懂后面几篇文章,因此不会涉及到一些很细节的内容。(特别细节的内容我也不懂,SICP 也没有很深入介绍)如果要深入了解,可以阅读相关的文档。

1 Scheme 的特性

Scheme 是一种 Lisp 的方言。而 Lisp 是世界上第二古老的语言(第一古老的是 Fortran),有着众多的方言。这些方言有着一个共同的特性——基于 S 表达式 (S-expressions)

S 表达式可以是原子表达式 (atom) 或者列表。原子表达式可以是数字,如 1, 42, 3.14;可以是字符串,如 "hello";可以是布尔值,如 #t, #f;也可以直接是符号,如 a, if, add。而列表则是将若干个 S 表达式放在一对括号里,用空格隔开:

(<s-exp1> <s-exp2> <s-exp3> ...)

下面给出了一些 S 表达式的例子:

100
100.13
"Hello world"
(add 1 2)
(display "Hello world")
(list (list 1 2) (list "a" "b"))

前三个 S 表达式都是原子表达式。(add 1 2) 是一个长度为 3 的列表,3 个元素分别是符号 add、数字 1 和数字 2。(display "Hello world") 是一个长度为 2 的列表,第一个元素是符号 display,第二个元素是字符串 "Hello world"(list (list 1 2) (list "a" "b")) 是一个长度为 3 的列表,三个元素分别是符号 list、列表 (list 1 2)、列表 (list "a" "b")

Scheme 全部是由 S 表达式组成的。在 Scheme 中,复合表达式的第一个元素作为表达式的类型,剩余的元素则作为表达式的参数。

s-exp

表达式类型决定这个表达式的语义和参数的含义。例如 if 表达式规定有三个参数,第一个参数为条件,第二个参数为条件为真时执行的表达式,第三个参数为条件为假时执行的表达式。由于 S 表达式可以任意嵌套,因此利用它就可以构造出任意复杂的代码。下面就是一段 Scheme 代码的例子:

(define (queens board-size)
  (define (queen-cols k)
    (if (= k 0)
      (list '())
      (filter
        (lambda (positions) (safe? positions))
        (flatmap
          (lambda (rest-of-queens)
            (map (lambda (new-row)
                   (adjoin-position new-row k rest-of-queens))
                 (enumerate-interval 1 board-size)))
          (queen-cols (- k 1))))))
  (queen-cols board-size))

可以看到 S 表达式层层嵌套,形成了一个树状结构,这其实就是语法树。也就是说这个语言实际是把语法树明确的写出来。后面我们能看到这种做法的好处:代码可以直接表示为数据结构,代码极其容易解析、编译。

2 编程环境

Scheme 作为 Lisp 的一种方言,它本身又有很多方言,例如 Chez Scheme, MIT Scheme, Racket 等。我们使用的环境是 Racket,它功能强大,易于使用。我们可以到它的官网下载最新版本。Racket 自带一个 IDE,叫 DrRacket,我们可以使用它学习编写 Scheme。

打开 DrRacket,就可以开始 Scheme 编程了。程序的第一行需要声明所使用的语言 #lang racket。编辑好了后点击 "Run" 便可执行代码。

s-exp

有些同学可能不习惯这种全是括号的语言,阅读代码需要数括号,十分麻烦。但如果代码做好缩进与对齐,之间的嵌套关系是一目了然的。我们可以让参数另起一行,相对类型缩进两个空格:

(type
  arg1
  arg2
  ...)

或者第一个参数与类型同行,后续参数与第一个参数对齐:

(type arg1
      arg2
      ...)

如果第一个参数比较特殊,也可以让第一个参数与类型同行,剩余的参数另起一行,并缩进两个空格

(type special-arg1
  arg2
  arg3
  ...)

基本上就这三种缩进风格。使用 DrRacket 可以自动缩进;阅读代码时一般不需要关心括号,直接看代码缩进即可,就像 Python 一样。

3 基础表达式

一个高级语言一定具备这三个要素:

  1. 原子表达式 (primitive expressions):语言提供的最简单、最基础的元素。
  2. 组合方法 (means of combination):将原子表达式组合成复合元素的方法。
  3. 抽象方法 (means of abstraction):给复合元素命名,从而将其作为一个整体操作。

我们说汇编语言不是高级语言,因为它有非常弱的组合能力和抽象能力。例如 add $42 %eax 可以表示 eax + 42,但是要想表示 (eax + 42) * 3 就得写两条指令了,因为这个语言根本没有嵌套组合的能力。至于抽象能力,汇编中的函数(准确来说应该是 subroutine)更像是个 goto。而 Scheme 是非常高级的语言,因为它有非常强的组合能力和抽象能力,稍后我们可以看到。

3.1 原子表达式

原子表达式有这么几种:

3.2 复合表达式

Scheme 中的复合表达式有两种,特殊形 (special form) 和函数调用。Scheme 函数调用的语法是 (function arg1 arg2 ...),让 S 表达式的第一个元素为函数,剩余元素为函数参数。例如下面的几个表达式都是函数调用:

(sqrt 2)
(+ 1 2)
(* (+ 1 2) (+ 3 4))

这里的 sqrt+* 都是函数名,分别执行平方根、加法和乘法操作。与其他大部分语言不同,Scheme 没有运算符,加减乘除运算、比较运算等都是函数。

对于初学者来说可能有些奇怪,但这种语法有很大的好处。首先表达式关系明确无歧义,程序员不需要记忆运算符优先级、是左结合还是右结合,且程序容易解析编译。使用方式统一,不会像 C 语言一样,乘法运算是 a * b,指数运算却是 pow(a, b)。不需要 C++ 那样复杂的运算符重载规则,直接定义一个名为 +* 的函数即可。

下面给出了一些常用函数和调用方式:

(+ 1 1) ;; 加法
(- 1 1) ;; 减法
(* 2 3) ;; 乘法
(/ 3 2) ;; 除法。整数触发会返回有理数,这个例子返回 3/2
(= 2 2) ;; 判断两个数字是否相等
(< 2 3) ;; 第一个参数是否小于第二个参数。类似的还有 >, <= >=
(eq? a b) ;; 判断两个对象是否相同,可以理解成比较地址
(remainder 3 2) ;; 求余数。这个例子返回 1
(sqrt 2) ;; 开根号
(display "Hello world") ;; 打印到标准输出
(newline) ;; 打印换行符

分号 ; 在 Scheme 中用作单行注释。

看到这里,你可能会以为表达式 (if (> a b) a b) 也是调用了一个 if 函数。但,实际上不是。对函数求值时,会先依次对各个参数求值,然后再调用函数。而对于 if 来说,当 (> a b) 为真时,只应该对 a 求值,不应该对 b 求值。反之,只应该对 b 求值。因此 if 不能是函数,应该是一个特殊形。

S 表达式就像是语法树的表示,而特殊形就是一种特定的语法,它定义这个语法有哪些子节点,含义分别是什么。下面给出了一些常用的特殊形和使用方式。

(if predicate consequence alternative) ;; 如果 predicate 为真返回 consequence, 否则返回 alternative

;; 方括号 [] 与圆括号 () 等价,可交错使用方括号和圆括号提升可读性。
(cond [predicate1 consequence1] ;; 依次判断: 如果 predicate1 为真返回 consequence1
      [predicate2 consequence2] ;; 如果 predicate2 为真返回 consequence2
      ...
      [else alternative]) ;; 如果所有的条件都不成立,则返回 alternative

(define var val) ;; 定义变量 var 的值为 val

(and exp1 exp2 ...) ;; 逻辑与,遵循短路原则(所以必须是特殊形)
(or exp1 exp2 ...) ;; 逻辑或,遵循短路原则
;; 逻辑非是一个函数 (not exp)

(begin exp1 exp2 ...) ;; 按顺序依次对 exp1, exp2, ... 求值,整个表达式的值为最后一个表达式的值。类似于 C 中的逗号运算符。

(lambda (arg1 arg2 ...) body ...) ;; 构造一个函数,第 4 节详细介绍

4 定义函数

lambda 特殊形创建一个函数,形式为 (lambda (arg1 arg2 ...) body ...)。其中 (arg1 arg2 ...) 为参数列表,剩下的 body ... 为函数体,可由多个表达式组成,函数的返回值为最后一个表达式的值。我们通常结合 define 定义函数,下面给出了一个例子

(define gcd
  (lambda (a b)
    (if (= b 0)
        a
        (gcd b (remainder a b)))))

这个函数实现欧几里得算法,求两个整数 ab 的最大公约数。函数参数列表是 (a b),函数体只有一个 if 表达式。if 表达式检查 b 是否为 0,如果 b 为 0 则返回 a,否则递归调用自身 (gcd b (remainder a b))。现在我们就可以调用 gcd 了:

(gcd 10 12) ;; 2
(gcd 7 11) ;; 1

由于我们经常使用 definelambda 定义函数,我们有一种简便的写法 (define (fname args ...) body ...) 等价于 (define fname (lambda (args ...) body ...))。因此 gcd 还可写成这样

(define (gcd a b)
  (if (= b 0)
      a
      (gcd b (remainder a b)))))

4.1 环境

函数可以嵌套定义。例如定义函数 prime? 判断一个数是否是质数,我们寻找能整除它的大于 1 的整数。如果找不到能整除它的整数,则它是一个质数

(define (prime? n)
  (define (iter i)
    (cond [(> (* i i) n) #t]
          [(= (remainder n i) 0) #f]
          [else (iter (+ i 1))]))
  (iter 2))

prime? 所在的环境称为全局环境,iter 所在的环境为 prime? 的内部环境。define 执行的时候,会在它所处的环境中增加一个变量。当函数被调用时,会创建一个新环境,这个新环境继承函数定义时所在的环境;而函数的参数就在新环境中实例化。对表达式求值,会先在当前环境寻找变量的值,如果找不到则在上层环境寻找,依次类推。因此要考察一个函数的行为,必须考虑两个要素:这个函数的代码,和这个函数所在的环境。这两要素有时合在一起称为“闭包”。

env

当我们在全局环境中执行 (prime? 11) 时,会有这么几步:

这便是 Scheme 环境的运作机制。下一篇文章我们会实现这个机制,从而实现一个 Scheme 解释器。

Scheme 的函数是一等公民,我们可以将函数当作参数传递,也可以当成返回值返回。当函数被传递时,它所在的环境也将被传递。例如

(define (f x)
  (lambda () x))

(define n (f 10))
(n) ;; 10

函数 f 返回一个函数,这个函数便保存了调用 f 时创建的环境。因此我们可以通过这个函数获取到调用 f 时传的值。后面我们可以看到这个机制有趣的应用。

4.2 letlet*

当我们需要中间变量时,例如计算 $5(3x^2+1)^2 + 4(3x^2+1)$,为了避免重复计算,我们需要一个中间变量 $t=3x^2+1$。这个使用我们会使用 let 特殊形。

(let ([t (+ (* 3 x x) 1)])
  (+ (* 5 t t) (* 4 t)))

let 的语法格式如下:

(let ([var1 val1] ;; 定义若干个变量
      [var2 val2]
      ...)
  body            ;; 可在 body 中使用这些变量
  ...)
;; let 外不能使用这些变量

它其实是个语法糖,等价于使用 lambda 创建一个函数,然后立刻调用它:

((lambda (var1 var2 ...)
    body
    ...)
  val1 val2 ...)

let 有一个缺陷,就是定义后面的变量的值时不能引用前面的变量,也就是说 (let ([a 1] [b (+ a 1)]) b) 是非法的。于是我们有 let*

(let* ([var1 val1]
       [var2 val2] ;; val2 可以引用 var1
       ...)
  body
  ...)

它也是一个语法糖,等价于

(let ([var1 val1])
  (let ([var2 val2])
    (let ...
      body
      ...))

let* 通过嵌套 let 实现,因此允许引用前面的变量。

5 数据结构

前面介绍了代码的组合和抽象,这一节介绍数据结构。这一系列文章只会用到非常简单的数据结构。

5.1 有序对和列表

为了构造复合结构,我们用 cons 构造有序对 (pair)car 获取有序对的第一个元素,cdr 获取有序对的第二个元素。

(define p (cons 1 2))
(car p) ;; 1
(cdr p) ;; 2

有序对可以任意嵌套,如 (cons (cons 1 2) (cons 3 4))。因为可以任意嵌套,所以理论上仅靠有序对就可以构造出任意复杂的数据结构。如果将有序对依次连接,就得到了一个链式列表:

(cons 1 (cons 2 (cons 3 (cons 4 '()))))

每个有序对的第一个元素 (car) 存储当前节点的值,第二个元素 (cdr) 指向下一个节点。最后一个元素的 cdr 为 '(),表示 NIL,链表的结尾。使用 list 函数可以快速创建一个列表:

(list 1 2 3 4) ;; 等价于 (cons 1 (cons 2 (cons 3 (cons 4 '()))))

这样对于列表来说,car 用于获取列表的第一个元素,cdr 用于获取列表剩余的元素,而 cons 在列表头部插入一个元素。

(define items (list 1 2 3 4))

(car items) ;; 1
(cdr items) ;; '(2 3 4)
(cons 0 items) ;; '(0 1 2 3 4)

(car (cdr items)) ;; 2
(car (cdr (cdr items))) ;; 3
(cdr (cdr (cdr items))) ;; '(4)
(cdr (cdr (cdr (cdr items)))) ;; '()

5.2 Quote

你可能会好奇 '()'(2 3 4) 中的单引号 ' 是什么意思。回想一下第 1 节,S 表达式可以是原子表达式或列表。是的,这里的说的列表list 函数创建的列表是一个东西。也就是说,S 表达式

(1 2 3 4)

本身就是一个列表。但是这个表达式会被 Scheme 解释成调用函数 1,传入参数 2, 3, 4。为了表示列表本身,我们用 quote 特殊形。quote 接受一个 S 表达式作为参数,不对这个表达式求值,而是直接返回它。下面是一些使用例子。

(quote (1 2 3 4)) ;; 等价于 (list 1 2 3 4)
(quote a) ;; 不认为 a 是一个变量,而是直接返回符号 a 本身
(quote (+ a b)) ;; 返回一个长度为 3 的列表,三个元素分别是符号 +, 符号 a, 符号 b
(quote (lambda (x) (* x x))) ;; 任何代码都可以放到 quote 里

由于 quote 十分常用,因此我们有一种简化形式。在任意 S 表达式前加上单引号 ' 表示对这个 S 表达式 quote。

'a ;; 等价于 (quote a)
'() ;; 等价于 (quote ()),表示一个空列表,也称为 NIL
'(1 2 3 4) ;; 等价于 (list 1 2 3 4)
'(lambda (x) (* x x)) ;; 任何代码前面都可以加上单引号,表示代码本身

这有这非常重要的意义——意味着代码可以当作数据解析。这是其它非 Lisp 系语言不具备的能力。我们会在下一篇文章中大量使用它,这里我们先看一些简单的例子:

(define code '(lambda (x) (* x x)))

(car code) ;; 'lambda
(cadr code) ;; '(x)
(caddr code) ;; '(* x x)

这里的 cadrcaddr 是快捷函数。(cadr x) 等价于 (car (cdr x))(caddr x) 等价于 (car (cdr (cdr x)))。这种命名也很容易记忆:中间的 ad 分布表示依次调用 carcdr

我们知道列表由有序对构成。S 表达式使用括号表示列表,那么对于有序对这种更基础的元素,它如何表示呢?我们可以试验下:

(cons 1 2) ;; '(1 . 2)

如果括号里的两个元素用 . 隔开,则表示这是一个有序对。但如果有序对的第二个元素被括号包裹,则会省略掉 . 和第二个元素的括号:

'(1 . (2 . 3)) ;; '(1 2 . 3)
'((1 . 2) . (3 . 4)) ;; '((1 . 2) 3 . 4)
'(1 . (2 . (3 . (4 . ())))) ;; '(1 2 3 4)

因此 (cons 1 (cons 2 (cons 3 (cons 4 '())))) 的结果是 '(1 2 3 4),看上去像是个列表了。这种语法的好处是,既能体现列表是由有序对构成的(可以显式写成 (+ . (2 . (3 . ())))),又能让列表看上去很舒服(一般写作 (+ 2 3))。

5.3 Quasiquote 与 unquote

Scheme 还提供了一对方便我们构造特定列表的特殊形:quasiquoteunquote。它们同样接受一个 S 表达式作为参数。(quasiquote exp) 可简写为 `exp(unquote exp) 可简写为 ,exp。与 quote 类似,quasiquote 也原样返回 S 表达式,但会对其中 unquote 的部分求值。

(define a 10)
(define b 20)
(define c '(x y))

`(1 2 ,a ,b) ;; '(1 2 10 20)
`(,a . ,b) ;; '(10 . 20)
`(1 ,c 2 3) ;; '(1 (x y) 2 3)
`(1 ,(* a b) 2) ;; '(1 200 2)

还有一个类似的语法是 unquote-splicing,接受一个列表作为参数,(unquote-splicing list) 简写为 ,@list。它会对列表求值并展开:

(define items (list 10 20 30))

`(1 2 ,@items 3) ;; '(1 2 10 20 30 3)
`(,@(list 1 2) 3 4) ;; '(1 2 3 4)
`(,@'(1) 2 3) ;; '(1 2 3)

5.4 常用函数

这里介绍一些操作列表的常用函数。

pair? 判断是否是有序对

(pair? 1) ;; #f
(pair? '()) ;; #f,NIL 不是有序对
(pair? (cons 1 2)) ;; #t
(pair? (list 1 2 3)) ;; #t,列表也是有序对组成的

list? 判断是否是列表

(list? '(1 2 3)) ;; #t
(list? '()) ;; #t,NIL 就是空列表
(list? '(1 2 . 3)) ;; #f,不以 NIL 结尾,不是列表

symbol? 判断是否是符号

(symbol? 12) ;; #f,数字不是符号
(symbol? 'abc) ;; #t
(symbol? (quote abc)) ;; #t
(symbol? pi) ;; #f,pi 的值是 3.14159,不是符号
(symbol? 'pi) ;; #t
(symbol? '(1 2 3)) ;; #f,列表不是符号

null? 判断列表是否为空。

(null? '()) ;; #t
(null? (list)) ;; #t
(null? (list 1 2)) ;; #f
(null? (cddr '(1 2))) ;; #t

memq 在列表中找到 car 等于给定值的有序对

(memq 2 '(1 2 3)) ;; '(2 3)
(memq 3 '(1 2 3)) ;; '(3)
(memq 4 '(1 2 3)) ;; #f,返回 false 表示不存在

assoc 假设列表的元素都是有序对,找到有序对的 car 等于给定值的元素

(assoc 2 '((1 a) (2 b) (3 c))) ;; '(2 b)
(assoc 3 '((1 . a) (2 . b) (3 . c))) ;; '(3 . c)
(assoc 4 '((1 a) (2 b) (3 c))) ;; #f

append 连接两个列表

(append '(1 2 3) '(4 5)) ;; '(1 2 3 4 5)
(append '(1 2 3) '()) ;; '(1 2 3)

6 函数式编程

Scheme 倡导函数式编程,除了函数是一等公民外,还有一点就是“非必要不赋值”。到现在为止,我们还没有介绍赋值语句。对于命令式编程来说,不使用赋值语句连个有限 while 循环都写不出来。但是在函数式编程中,我们会熟练使用各种递归。

(define (sum items)
  (if (null? items)
      0
      (+ (car items)
         (sum (cdr items)))))

(sum '(1 2 3 4)) ;; 10

虽然无法通过赋值改变变量,但是我们在可以调用函数时改变参数的值。有人可能会说递归性能差,因为需要消耗栈空间。确实,上面的代码在调用 (sum (cdr items)) 之前需要将 (car items) 的值压栈,以便 sum 返回后计算两者之和。但是我们只需要稍微修改一下写法:

(define (sum items)
  (define (iter i s)
    (if (null? i)
        s
        (iter (cdr i) (+ s (car i)))))
  (iter items 0))

我们发现递归调用 (iter (cdr i) (+ s (car i))) 的返回值直接作为原函数 (iter i s) 的返回值,因此调用之前不需要压栈。这被称为尾递归。尾递归本质就是迭代,因为递归调用 iter 的过程就是不断迭代更新变量 is 的过程。

6.1 Accumulate

刚才我们定义了一个函数求所有元素之和。那么如果要求所有元素之积呢?我们可以定义一个 product 函数

(define (product items)
  (define (iter i p)
    (if (null? i)
        p
        (iter (cdr i) (* p (car i)))))
  (iter items 1))

我们发现这个函数跟 sum 几乎一样。这两个函数都是给定一个初始值,依次与列表中的元素执行某个操作,然后依次迭代;只是初始值(一个是 0 另一个是 1)和操作(一个是 + 另一个是 *)不同。在 Scheme 中,函数可以当作值传递,而 +* 都是函数。因此我们可以定义一个通用的函数,将初始值和操作作为参数传递进去:

(define (accumulate op init items)
  (define (iter i res)
    (if (null? i)
        res
        (iter (cdr i) (op res (car i)))))
  (iter items init))

(accumulate + 0 '(1 2 3 4)) ;; 10
(accumulate * 1 '(1 2 3 4)) ;; 24
(accumulate append '() '((1 2) (3 4 5) (a b c d))) ;; '(1 2 3 4 5 a b c d)

6.2 Map

与之类似的函数是 mapmap 将列表中的每个元素通过一个给定的函数映射成新值

(map - '(1 2 3 4 5)) ;; '(-1 -2 -3 -4 -5)
(map (lambda (x) (* x x)) '(1 2 3 4 5)) ;; '(1 4 9 16 25)

map 还支持传多个列表,如 (map proc list1 list2 ...)。这些列表的长度要相等,并且列表的数量等于传入函数的参数数量。list1 的元素作为第一个参数传给 proclist2 的元素作为第二个元素传给 proc,以此类推。

(map + '(1 2 3) '(10 20 30)) ;; '(11 22 33)
(map list '(1 2 3) '(a b c) '(x y z)) ;; '((1 a x) (2 b y) (3 c z))

如何实现 map 呢?Scheme 支持定义可变参数的函数。我们可以定义 (define (map proc . lists)),这种情况下 lists 便是一个包含剩余参数的列表。因为 (map proc list1 list2) 也可以写作 (map proc . (list1 list2))(见 5.2 节),因此不难理解这种写法。

反过来如果有 n 个参数存储在一个列表中,可以用 apply 将它们传给一个指定函数:

(apply + '(1 2)) ;; 3
(apply * '(2 3 4)) ;; 24

这样我们可以实现 map 函数:

(define (map proc . lists)
  (if (null? (car lists))
      '()
      (cons (apply proc (map car lists))
            (apply map (cons proc (map cdr lists))))))

Filter

从列表中过滤出符合要求的函数,可以用 filter。它接受一个返回布尔值的函数和一个列表作为参数,例如

(filter odd? '(1 2 3 4 5 6)) ;; '(1 3 5)
(filter even? '(1 2 3 4 5 6)) ;; '(2 4 6)

我们同样可以实现 filter

(define (filter proc items)
  (cond [(null? items) '()]
        [(proc (car items))
         (cons (car items) (filter proc (cdr items)))]
        [else
         (filter proc (cdr items))]))

思考题:你能把 mapfilter 改成迭代(尾递归)的形式吗?

7 赋值

虽然函数式编程不鼓励使用赋值,但是很多场景完全不使用赋值会非常不方便,并且有些场景适当地使用赋值可以提升代码性能,简化一些实现。Scheme 使用 set! 特殊形执行赋值,使用格式是 (set! var val)set! 先对 val 表达式求值,然后将值赋值给 var。例如:

(define a 1)
(set! a (+ a 1)) ;; a = 2
(set! a (* a 2)) ;; a = 4
(set! a (cons a (+ a 1))) ;; a = '(4 . 5)

引入赋值会给系统增加很多不确定性。对于不使用赋值的函数,传入确定的参数必然得到确定的值,就像数学函数一样。而一旦引入赋值,就不一定了。可以看下面的例子:

(define (make-account n)
  (lambda (d)
    (set! n (+ n d))
    n))

(define account (make-account 0))

(account 10) ;; 10
(account 10) ;; 20
(account -5) ;; 15

这里 (account 10) 调用了两次,传入相同的参数但是返回不同的值。4.1 节提到,当我们把函数当作值传递时,它所在的环境也会随之传递。因此我们可以把函数当作数据结构使用。上面的 account 是一个函数,也可以认为是一个数据。

Racket 中的有序对一旦构造好就不能修改。我们可以利用函数实现一个可修改的有序对:

(define (mcons 1st 2nd)
  (let ([set-mcar! (lambda (v) (set! 1st v))]
        [set-mcdr! (lambda (v) (set! 2nd v))])
    (lambda (m)
      (cond [(eq? m 'mcar) 1st]
            [(eq? m 'mcdr) 2nd]
            [(eq? m 'set-mcar!) set-mcar!]
            [(eq? m 'set-mcdr!) set-mcdr!]))))

(define (mcar mpair) (mpair 'mcar))
(define (mcdr mpair) (mpair 'mcdr))
(define (set-mcar! mpair val) ((mpair 'set-mcar!) val))
(define (set-mcdr! mpair val) ((mpair 'set-mcdr!) val))

上面的例子可以认为是 Scheme 中的“面向对象编程”。mcons 返回的函数可视为对象,它通过传入的参数决定执行的操作,因此这种写法又被称为消息传递模式 (massage passing style)。mcons 可以称为构造器 (constructor),调用构造器的返回值获取“成员”,(mpair 'mcar) 这样的表达式就类似于 Java 中的 mpair.mcar。下面的代码展示了 mcons 的一些用法。

(define p (mcons 1 2))
(mcar p) ;; 1
(mcdr p) ;; 2
(set-mcar! p 10)
(set-mcdr! p 20)
(mcar p) ;; 10
(mcdr p) ;; 20

8 总结

这篇文章介绍 Scheme 的一些基础内容,包括 S 表达式的构造、常用特殊形的用法、函数的调用与定义、对环境的理解、有序对与列表、常用函数的使用、赋值操作等内容。这些内容足以写出很多 Scheme 程序了。下一篇文章我们将用 Scheme 实现一个 Scheme 的解释器,实现本文介绍的绝大部分语言特性。


参考资料: