Fork me on GitHub

在这个系列里面,我会用scheme语言来实现一个scheme语言的解析器。 我们会在实现中学习到很多程序语言相关的概念和相关的实现, 这对于我们理解我们常用的语言也有很大的帮助。

Scheme: A little bit history

Scheme语言是lisp语言的其中一个变种。Lisp语言可以说是计算机历史上第二长寿的语言了, 第一是Fortran。Lisp语言早期主要是应用在人工智能方面, 70年代至80年代由于人工智能的大繁荣,Lisp得到了很大的发展,但是后来由于人工智能的冬天, Lisp的应用也随之进入了冬天。而就在这段冬天里,Scheme就在MIT诞生了。

Scheme作为Lisp最大的两个变种之一(另外一个是Common Lisp),在最近得到了很多的关注, 因为最近Scheme的其中一个JVM方言Clojure在业界得到了比较多的 应用。Scheme在诞生之初就有很多的创新,而其中最大的特征的就是Scheme是一门以minimalist 为设计思想的语言,也就是说Scheme的核心非常的小,但是里面却包含了许多强大的语言思想。

简单来说,Scheme包含了以下的特性:

  1. 鼓励函数式编程。与传统的Imperative Programming不同, 函数式编程鼓励无副作用的编程方式,整个计算的过程可以用数学函数来描述, 从而达到简介表达高级程序逻辑的目的。(关于FP我也还在学习中)
  2. 使用Lexical scoping。由于使用了Lexical scoping,所以实现闭包是非常简单的一件事。
  3. 函数的尾递归(Tail recursion)优化。在函数式编程里面, 循环是比较不鼓励的一种编程style, 取而代之的是递归调用。而递归调用在平常的语言里面的开销比循环要大,但是有了尾递归之后, 循环和递归某种程度上是等价的。
  4. 函数是first class object。这个在目前的很多语言中也都已经实现了。

除了上面的特性之外,Scheme还有延续(continuation)等其他的高级特性,在这里就不多说了。 如果感兴趣的话,可以移步维基百科看详细的介绍。

我们要实现的语言——Scheme的定义

讲了那么多,那么我们要实现的语言到底是怎么样的一个语言呢?

接下来我会讲述我们实现的Scheme包含的特性。而实现这个解析器的语言同时也可以用它来描述。

语法:S表达式

一个具有下面性质的表达式,可以称之为S表达式:

  1. 一个不包含括号的原子表达式,比如1、”hello”、true、false等。
  2. 一个用括号”()”括住的表达式,其中括号之间包含0个或以上的S表达式。

可以看到S表达式是一个递归的定义,所以下面的几个表达式都是S表达式:

1 "hello" () (1 2) (("hello") 2) (+ 1 2)

而在Scheme里面,所有的表达式都是S表达式。其中第一种形式的S表达式称为atom, 而有括号的S表达式称为列表(list)。其中当表达式是列表形式的时候, 这个列表表示函数调用,其中第一个元素是函数的名字,后面的就是这个函数调用的实参。 也就是说(+ 1 2)表示的是1 + 2的意思。这种表示形式称为前缀表达式。

作为函数调用的另一个例子,假设mod是一个取模函数,就是第一个参数除于第二个参数的余数。 那么这个函数调用在Scheme里面就是写作(mod 4 3)就是在C里面的对应写法就是mod(4, 3)

基本类型

我们编写的基本类型一共有以下几种:

  1. Number,包括interger、floating point number。例如2,2.1。
  2. String,和C里面的string是一样的,如”hello”。
  3. Symbol,这个类型在Lisp里面比较常见,如abc。在Scheme里面, 要得到abc这个symbol,就用(quote abc)表示。
  4. Boolean, 包括两个值,true和false。
  5. List,这个和Python里面的List是类似的,不过写法是(1 2 a)。 并且Scheme里面的List不是数组,是单链表。而构造list的写法有几种:
    1. (quote (1 2 a))。注意到空的list表示为(quote ())
    2. (cons 1 (cons 2 (cons a (quote ()))))。注意到, 元素的添加是通过cons来构造的。(cons a b)表示构造一个2个元素的list, 其中第一个元素是a,余下的元素是b。
    3. 元素的取出是两个操作:car和cdr。假设a的值是(cons 1 2), 那么(car a)的值是1,(cdr a)的值是2。所以那上面的例子来说, (car (quote (1 2 a)))的值是1,(cdr (quote (1 2 a)))的值是 (quote (2 a))

其中Number、String和Boolean称为Atom

lambda

用过Python的人都知道Python里面有个keyword叫做lambda。但是Python里面的lambda功能很弱, 只能写一行的匿名函数。而Scheme里面的lambda就要强大多了,是一个功能完备的函数。

Scheme里面的lambda定义语法如下:

1
2
(lambda (args)
  (body))

比如说下面的都是lambda

1
2
3
4
5
6
7
8
(lambda (x y)
  (+ x y))

(lambda (x)
  x)

(lambda (p)
  (p p))

定义

定义包括变量定义和函数定义。其中变量定义是的语法如下:

1
(define a 1)

上面的表达式是定义了一个名为a的变量,他的值是1。

而函数定义的语法如下:

1
2
(define (add x y)
  (+ x y))

其中add是函数名,而x、y是这个函数的参数,而这个函数体是(+ x y), 也就是求两个参数的和。

而实际上,函数定义和变量定义是一样的,也就是函数定义等价于下面的语句:

1
2
3
(define add
  (lambda (x y)
    (+ x y)))

也就是函数实际上是一个值为lambda的变量。

还有一点值得说明的是,在函数的定义里面可以有嵌套的定义,例如:

1
2
3
4
5
6
(define (fact-iter n)
  (define (iter x result)
    (if (= x 1)
	result
	(iter (- x 1) (* x result))))
  (iter n 1))

上面例子中的iter函数就是定义在fact-iter里面的。他的scope就是在fact-iter里面。 如果fact-iter外面有定义iter的话,那么外面的iter就会被里面的这个iter覆盖掉。 注意到例子中的程序是用来“循环”计算factorial的。

闭包与Lexical scoping

闭包的准确定义是包含了其环境的函数,但是但从这句话里面我们很难明白到底什么是闭包。 用例子来解释应该是最简单的了。

比如说下面的Scheme代码:

1
2
3
(lambda (x)
  (lambda (y)
    (+ x y)))

上面的例子里,lambda里面的函数体是另外一个lambda,而这个里面的lambda使用了x, 这个x的定义并不在里面的lambda里面,而在外面的lambda,这个外面的lambda就是里面的 lambda的一个lexical的环境。那么我们就称里面这个lambda是一个闭包。

这里还涉及了一个叫做lexical scope的概念,它是和dynamic scope相对应的一个概念。 lexical scope的意思是,闭包里面的变量的取值是根据其定义的地方的环境来进行取值。

比如说例子里面的x取值就是外面的lambda的参数x的值。

而dynamic scope的意思就是说,闭包里面的变量值是根据调用的时候的环境来进行取值。 比如说下面的例子里面,

1
2
3
4
5
6
7
8
(define (inc x)
  (lambda (y)
    (+ x y)))

(define (test x)
  ((inc 3) 4))

(test 2)

对于dynamic scope的语言来说,上面的(test 2)的值是6, 但是对于lexical scope的语言来说,他的值是7。

if条件语句

最基本的if条件语句是下面这样的

1
2
3
(if (= x 1)
    (+ x 1)
    x)

上面的语句和下面的C语句是等价的。

x == 1 ? x + 1 : x

Example

OK,说了上面那么多,接下来我用上面的语法说明写一个例子程序,并说明预期的输出。 接下来的几章,我们就会用这个例子程序来验证我们的解析器的正确性。

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
;;;; 测试递归
(define (fact n)
  (if (< n 2)
      n
      (* n (fact (- n 1)))))

(fact 3)  ; 6
(fact 4)  ; 24
(fact 5)  ; 120

;;;; 测试嵌套定义
(define (fact-iter n)
  (define (iter x result)
    (if (= x 1)
	result
	(iter (- x 1) (* x result))))
  (iter n 1))

(fact-iter 3)
(fact-iter 4)

;;;; 测试闭包
(define (get-number-closure n)
  (lambda () n))

(define get-1 (get-number-closure 1))
(get-1) ; 1

(define get-100 (get-number-closure 100))
(get-100) ; 100

编程环境

OK,有了前面的基础,我们就剩下编程的环境了。 这里就以我自己用的环境为准。 我自己使用的Scheme是mit-scheme, 因为它是《SICP》里面使用的 教学版本。而mit-scheme和Emacs配合的也比较好,利用mit-scheme源码包里面的xscheme.el 来替换掉Emacs自身的scheme-mode可以很高效的进行Scheme的编程。所以我用的环境就是 mit-scheme + Emacs + xscheme.el。

我会在下一节讲解释器的基本结构。


知识共享许可协议
作品airekans创作,采用知识共享署名-相同方式共享 4.0 国际许可协议进行许可。


Published

18 November 2012

Tags

Share To