怎样写一个解释器

写一个解释器，通常是设计和实现一个编程语言的第一步；亦或者我们想要一种自定义程度较高的 DSL ，通常也不得不自行去实现解释器。而如何实现一个解释器，网络上的资料其实也并不算多，所以我这里简单做个分享。

写在前面

写一个解释器，通常是设计和实现一个编程语言的第一步；亦或者如果我们想要一种自定义程度较高的 DSL，通常也不得不自行去实现解释器。而如何实现一个解释器，网络上的资料其实也并不算多，所以我这里简单做个分享。

要完整实现一个编译器/解释器，需要语法设计到编译前后端的完整实现，这涉及到巨大的工作量。但通常我们只需要能够实现 DSL，使得 DSL 能够依托于我们主语言环境运行即可，不需要考虑编译后端的问题。所以本文的解释器仅涉及到编译前端流程，后端执行细节交给宿主语言运行时。

此外，如果一开始就选择非常复杂的语言如 Python、Ruby或Haskell, 会让我们掉入词法/语法解析的深坑，但对学习书写解释器没什么帮助，所以我们选择了语法规则简单的 lisp 来实现一个解释器。

另外，主语言使用 Golang, 除了语言本身比较简单，也为了读者对照实验没有环境部署的焦虑。

If you don’t know how compilers work, then you don’t know how computers work.

http://norvig.com/lispy.html Steve Yegge.

Lisp 语法

考虑到很多国内的同学可能没有接触过 lisp，这里首先简单介绍下其语法。

  • golang
1
2
3

if x > 0 {
  return fn(arr[i] + 3 * i, []string{"a", "b"})
}
  • lisp
1
2
3

(if (> x 0)
  (fn (+ (array_get arr i) (* 3 i))
      (list "a" "b")))

如上例所示，尽管golang 相较于其他语言，其语法已经非常简单，但是它仍然有数十个关键字，若干中置操作符, 隐式操作优先级、逗号、各种括号等等，其语法规范仍然是比较多的；而相对来说，lisp 的语法规范就简单很多：

  • lisp 代码仅包含表达式，不包含语句，即，每一句lisp 必定都会返回值；
  • 数字、字符串、符号均称为「原子」，原子不可分解；
  • 除了原子外所有东西都是「列表」，列表以 (开头)结尾；列表的第一个元素要么是一个关键字，要么是一个函数调用；

lisp 的这种设计导致代码可读性略有下降，但是却带来易解析、表意性强、代码和数据统一等诸多优点，因此长期是国外 CS 教学的首选语言。

lis.go 计算器

我们本次的目标是基于 lisp 语法在 golang 是实现一个计算器。该计算器支持以下一些表达式:

Expression Syntax Semantics and Example
符号 symbol 一个符号通常引用了一个值，如 (define r 10) 表示符号 r 引用了值 10
字面量 number 比如数字 12
条件分支 (if test conseq alt) 如果 test 为 true，则返回 conseq，否则返回 alt
变量绑定 (define symbol expr) 定义一个符号 symbol,且将其值绑定为 expr
函数定义及调用 (proc arg …) 如果 proc 是关键字，如 if，则执行分支逻辑，否则寻找对应函数进行调用

解释器工作流程

解释器执行通常包含两步：

  • Parsing

解析代码生成抽象语法树,这一步通常叫 parse。

  • Execution

对 AST 求值，返回我们想要的结果,这一步通常叫 eval。

下图是解释器工作的简单示例:

parsing-execution

如下代码是是parse和eval工作的代码示例：

1
2
3
4
5
6
7

>> program := "(begin (define r 10) (* pi (* r r)))"

>> parse(program)
['begin', ['define', 'r', 10], ['*', 'pi', ['*', 'r', 'r']]]

>> eval(parse(program))
314.1592653589793

Get started

类型定义

首先，我们定义好 lis.go 需要的基本类型:

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

// 所有的表达式都需要实现 Expression 接口,该接口仅仅是一个标记接口
type Expression interface {
	Sexpr() string
}

// 符号类型
type Symbol string
// 列表类型,其实是一个单向链表,每个节点存储当前表达式和下一个节点指针
type List struct {
	Val  Expression
	Rest *List
}
// 函数类型
type Function func(*Env, []Expression) Expression
// 布尔类型
type Bool bool
// 整数
type Integer int64
// 浮点数
type Float float64

// 环境,包含父环境的引用及当前环境的符号表
type Env struct {
	parent *Env
	scope  map[string]Expression
}

我们定义了基本接口Expression，所有lis.go的类型都需要实现该接口，包括了：

  • Symbol 符号
  • Integer 整数
  • Float 浮点数
  • Bool 布尔值
  • List 列表
  • Function 函数

此外，我们还定义了环境 Env。或者叫作用域，程序运行时的符号查找都需要依赖于所处的环境，比如同一个符号 a，在不同的环境中，很可能引用了不同的值。

每个符号的解释，都需要优先查找当前环境，如果找不到则向上到父环境查找，直至根环境。

Parsing: parse, tokenize and read_from_tokens

解析的过程通常分为两步：

  • 词法解析，逐个字符读取代码文件，将字符串流解析为「词」的流，也叫 tokenize
  • 语法解析，对 token 流进行语义分析，生成 AST

词法分析有很多现成的工具，这里我们使用最简单的一种: golang的 strings.Split

1
2
3
4
5

func tokenize(s string) *TokenStream {
	s = strings.ReplaceAll(s, "(", " ( ")
	s = strings.ReplaceAll(s, ")", " ) ")
	return &TokenStream{tokens: strings.Split(s, " ")}
}

parse 函数接受代码字符串作为输入,调用tokenize 得到 token 流, 然后调用 read_from_tokens 将词流组织成抽象语法树。

read_from_tokens 遇到 ( 则开始一个列表的解析,直至遇到列表结束符); 如果其他 case 则作为原子解析。

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

// Read an expression from a sequence of tokens.
func read_from_tokens(tokens *TokenStream) Expression {
	if tokens.Empty() {
		panic("unexpected EOF while reading")
	}
	token := tokens.Pop()
	if "(" == token {
		l := &List{}
		for tokens.Peek() != ")" {
			l.Append(read_from_tokens(tokens))
		}
		tokens.Pop() // drop ')'
		return l
	} else if ")" == token {
		panic("unexpected )")
	} else {
		return atom(token)
	}
}

// Numbers become numbers; Booleans become booleans; any other token is a symbol.
func atom(token string) Expression {
	if val, err := strconv.ParseInt(token, 10, 64); err == nil && !strings.Contains(token, ".") {
		return Integer(val)
	} else if fval, err := strconv.ParseFloat(token, 64); err == nil {
		return Float(fval)
	} else if token == `true` || token == `false` {
		return Bool(token == `true`)
	} else {
		return Symbol(token)
	}
}

OK, 我们的 parse 函数已经可以运行了:

1
2
3
4

>>> program = "(define r 10) (* pi (* r r))"

>>> parse(program)
['define', 'r', 10], ['*', 'pi', ['*', 'r', 'r']]

基础环境

在进入下一步之前，我们需要为代码准备好执行环境。

1
2
3
4
5
6
7
8
9
10
11

func baseEnv() *Env {
	env := NewEnv(nil)
	env.scope["+"] = Function(plus)
	env.scope["-"] = Function(minus)
	env.scope["*"] = Function(multiple)
	env.scope["/"] = Function(divide)
	env.scope[">"] = Function(gt)
	env.scope["<"] = Function(lt)
	env.scope["=="] = Function(eq)
	return env
}

如前文所述，环境是符号解释的核心组件。在我们的基础环境里，已经定义好了加减乘除等几个基本操作函数，当然，你也可以提前定义好一些全局变量，任何 lis.go 支持的表达式都可以根据需求预置到环境中。

函数的实现也非常简单，以加法为例，其实就是调用了 golang 自己的加法操作符进行计算而已。

1
2
3
4
5
6

func plus(env *Env, exprs []Expression) Expression {
	if isFloat(exprs[0]) || isFloat(exprs[1]) {
		return Float(toFloat(exprs[0]) + toFloat(exprs[1]))
	}
	return Integer(toInt(exprs[0]) + toInt(exprs[1]))
}

Evaluation: eval

我们将根据之前的需求，实现该表中的能力:

Expression Syntax Semantics and Example
符号 symbol 一个符号通常引用了一个值，如 (define r 10) 表示符号 r 引用了值 10
字面量 number 比如数字 12
条件分支 (if test conseq alt) 如果 test 为 true，则返回 conseq，否则返回 alt
变量绑定 (define symbol expr) 定义一个符号 symbol,且将其值绑定为 expr
函数定义及调用 (proc arg …) 如果 proc 是关键字，如 if，则执行分支逻辑，否则寻找对应函数进行调用

下面的代码即 eval 的实现:

1
2
3
4
5
6
7
8
9
10
11
12

func eval(x Expression, env *Env) Expression {
	switch val := x.(type) {
	case Symbol:
		// variable reference
		return env.Find(val)[val.Sexpr()]
	case *List:
		return evalList(val, env)
	default:
		// constant literal
		return x
	}
}

如果是符号，则从环境中查找其引用的值，如果是列表则调用evalList对列表求值，如果是其他字面量，则直接返回字面量本身。

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

func evalList(x *List, env *Env) Expression {
	name := string(x.Val.(Symbol))
	switch name {
	case "if":
		// (if test conseq alt)
		test, conseq, alt := x.Rest.Val, x.Rest.Rest.Val, x.Rest.Rest.Rest.Val
		if res := eval(test, env); res.(Bool) {
			return eval(conseq, env)
		} else {
			return eval(alt, env)
		}
	case "define":
		// (define var exp)
		vvar, expr := x.Rest.Val, x.Rest.Rest.Val
		env.scope[vvar.Sexpr()] = eval(expr, env)
		return env.scope[vvar.Sexpr()]
	case "set!":
		// (set! var exp)
		vvar, expr := x.Rest.Val, x.Rest.Rest.Val
		env.Find(vvar.(Symbol))[vvar.Sexpr()] = expr
		return expr
	default:
		// (function arg...)
		proc := eval(x.Val, env)
		var args []Expression
		for ptr := x.Rest; ptr.Val != nil; {
			args = append(args, eval(ptr.Val, env))
			ptr = ptr.Rest
		}
		return proc.(Function)(NewEnv(env), args)
	}
}

evalList 如果发现第一个符号是 if 等关键字，则执行对应逻辑，如果是函数调用，则调用对应的函数即可。

Interaction: A REPL

为了使用我们的计算器，我们实现了一个简单的 REPL.

REPL: Read Eval Print Loop

逐行读入代码字符串，然后计算结果并打印到标准输出。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

func repl() {
	line := liner.NewLiner()
	defer line.Close()

	line.SetCtrlCAborts(true)

	env := baseEnv()
	for {
		if sentence, err := line.Prompt("lis.go> "); err == nil {
			val := eval(parse(sentence), env)
			fmt.Println(val.Sexpr())
		} else {
			return
		}
	}
}

自定义函数

到目前为止，我们的计算器已经能使用内置函数进行基本的四则运算；但是，其能力也就仅此而已，如果现在需要一个计算一个数的平方的函数，就只能在每个计算的地方写上：

1

(* a a)

所以，我们需要自定义函数的能力。

我们希望使用关键字 define-func 来定义函数，比如平方函数可以这样定义。

1
2

(define-func ** (a)
    (* a a))

定义自定义函数类型:

1
2
3
4
5
6

type UserFunction struct {
       Name string
       Args []string
       Body []Expression
}
func (s UserFunction) Sexpr() string { return "user-function:" + s.Name }

在 evalList 中添加对函数定义的解释：

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

func evalList(x *List, env *Env) Expression {
.......
       case "define-func":
               var userf UserFunction
               // (define-func name (arg1 arg2) body)
			   // 解析参数列表
               var args []string
               argsExpr := x.Rest.Rest.Val.(*List)
               for argsExpr.Val != nil {
                       args = append(args, string(argsExpr.Val.(Symbol)))
                       argsExpr = argsExpr.Rest
               }
			   // 解析函数名
               name := string(x.Rest.Val.(Symbol))
               userf.Name = name
               userf.Args = args
			   // 解析函数体
               expr := x.Rest.Rest.Rest
               for expr.Val != nil {
                       userf.Body = append(userf.Body, expr.Val)
                       expr = expr.Rest
               }
			   // 安装函数
               env.scope[name] = userf
               return userf
.......

实现对自定义函数的调用:

1
2
3
4
5
6
7
8
9
10
11

func callUserFunction(env *Env, f UserFunction, args []Expression) Expression {
       env = NewEnv(env)
       for i, arg := range f.Args {
               env.scope[arg] = args[i]
       }
       var ret Expression
       for _, expr := range f.Body {
               ret = eval(expr, env)
       }
       return ret
}

callUserFunction主要完成两件事:

  • 创建新的执行环境，并将参数绑定到当前环境；
  • 在当前环境对函数体表达式求值；

重新编译启动 REPL，可以定义并试用新的求平方函数了:

1
2
3

(define a 100)
(define-func ** (a) (* a a))
(** 2) ;; 返回 4

这里特意定义同名的全局变量 a 和函数入参局部变量 a，由于平方函数在独立的环境中绑定求值，所以二者互不影响。

完整代码

完整的代码可以参考: lis.go

应用到生产环境?

lis.go 只是帮助学习实现解释器的简单玩具，要作为生成环境的嵌入式语言，还缺乏很多关键性质:

  • Tail Call Optimization, 对于不支持循环的函数式语言，没有 TCO 支撑的递归很可能栈溢出;
  • VM, 目前 lis.go 其实是依赖 go 语言默认的调用栈来实现函数调用，没有自己设计虚拟机，性能有待提高；同时，无法通过编译提前感知指令流，就难以控制程序运行时状态，更无法做指令优化；
  • 调用环境没有隔离完全，下层函数可以”看到”上层环境;
  • 常用语法 feature 如闭包、宏等能力缺失，无法提供足够生产力；
  • 文档，注释 etc.

如果想要应用于生产环境，可以使用 glisp，其完整文档参考 glisp-wiki.

programming
Comments

Comments