写一个解释器
Table of Contents
1. 什么是解释器
1.1. 解释器
同声传译- 一段能够理解并执行
你的程序的程序- 理解你的代码所表示的意图
- 执行你的意图
1.2. 代码的意图
赋值/定义
(setf a 1) (defun plus (a b) (+ a b))
取值
a执行
(plus 1 2)
2. 如何下手
2.1. 步骤 B_frame
Dragon book, 中文名 编译原理
Tiger book, 中文名 现代编译原理-C 语言描述
Whale book, 中文名 高级编译器设计与实现
2.2. 结束
- <+-> 好，分享结束，大家可以回去看书了.
- <2-> 预计一年后，应该可以成功写出来了。
- <3> 开个玩笑，我们继续. 看一个 半小时就能写出来的版本 。
3. 半小时版本
3.2. 解析(1 min)
这里我们就偷个懒，利用 lisp 的 read-from-string / read 方法
(read-from-string "(1 2 3)") ;;; => (1 2 3) (read-from-string "1") ;;; => 1 (read-from-string "nil") ;;; => NIL (read-from-string "(defun plus (a b ) (+ a b))") ;;; => (DEFUN PLUS (A B) (+ A B)) (read-from-string "(defun plus (a b)") ;;; Exception
3.3. 表达式类型
- 原子
- 常量 1, "abc"
- 变量 a, test
- 列表
- quote (quote (a b c))
- if (if t 1 2)
- lambda (lambda (a) (+ 1 a))
- define (define a 1)
- assign (set! a 2)
- begin (begin (define b 1) (set! b 2))
- apply procedure (plus 1 2)
3.4. 原子表达式
3.5. 特殊形式 if
(if predicate consuquence alternative)
先求值
predicate, 如果符合，则求值consquence, 反之，则求值alternative
特殊在于, 控制表内的求值顺序 。
并不会将表内表达式均求值，而是根据第一个元素的值，来决定后续如何进行求值。
3.6. 特殊形式 define 以及 set!
(define variable value) (set! variable value)
只求值
value, 并将求值后的结果赋值给variable3
特殊在于, 控制表内的求值顺序 以及 修改上下文
不对 variable 求值，仅求值 value, 而后修改上下文。
3.7. 特殊形式 quote
(quote (a b c))
返回其引用的表达式
syntactic sugar: '(a b c)
特殊在于, 控制表内的求值顺序 。
不对表达式内求值，仅返回其引用的表达式。
3.8. 特殊形式 lambda
(lambda (a) (+ 1 a))
生成一个
procedure, 包含 形式参数 列表，以及 待执行的表达式 列表。
特殊同样在于, 控制表内的求值顺序 。
只将待执行的表达式记录下来，留待需要时使用。
3.9. 特殊形式 begin
(begin (define a 3) (set! a 1) (+ a 2))
依次执行表达式序列
特殊在于, 控制表内的求值顺序
3.10. 函数调用
(define plus (lambda (a) (+ 1 a))) (plus 2) ;;; 3
- 求值操作符
- 求值操作数
- 系统方法，则直接调用下层的 apply
- 自定义的方法
- 把形参对应的值添加到上下文中, 生成新的上下文
- 在新的上下文中，求值表达式列表
函数定义
;;; env => ((+) (<primitive +>)) (define plus1 (lambda (a) (+ 1 a))) ;;; env => ;;; ( (+ plus1) ;;; (<primitive +> <procedure object>) ) (plus1 2)
执行过程
(eval 'plus1 env) ;;; <procedure object> (eval 2) ;;; 2 (extend (a) (2) env) ;;; env' => ( (+ plus1 a) ;;; (<primitive +> <procedure object> 2)) (eval '(+ 1 a) env') (eval a env') ;;; 2 (apply-primitive '+ (1 2)) ;;; 3
3.11. 求值环境/上下文
4. 实现一个解释器
4.1. 声明
源代码来自 SICP 第 4 章，链接见附录。
4.2. eval (dispatch)
(define (eval exp env)
(cond ((self-evaluating? exp) exp)
((variable? exp) (lookup-variable-value exp env))
((quoted? exp) (text-of-quotation exp))
((assignment? exp) (eval-assignment exp env))
((definition? exp) (eval-definition exp env))
((if? exp) (eval-if exp env))
((lambda? exp)
(make-procedure (lambda-parameters exp)
(lambda-body exp)
env))
((begin? exp)
(eval-sequence (begin-actions exp) env))
((application? exp)
(apply (eval (operator exp) env)
(list-of-values (operands exp) env)))
(else
(error "Unknown expression type -- EVAL" exp))))
4.3. apply
(define (apply procedure arguments)
(cond ((primitive-procedure? procedure)
(apply-primitive-procedure procedure arguments))
((compound-procedure? procedure)
(eval-sequence
(procedure-body procedure)
(extend-environment
(procedure-parameters procedure)
arguments
(procedure-environment procedure))))
(else
(error
"Unknown procedure type -- APPLY" procedure))))
4.4. env 求值上下文
(define (enclosing-environment env) (cdr env)) (define (first-frame env) (car env)) (define the-empty-environment '()) (define (make-frame variables values) (cons variables values)) (define (frame-variables frame) (car frame)) (define (frame-values frame) (cdr frame)) (define (add-binding-to-frame! var val frame) (set-car! frame (cons var (car frame))) (set-cdr! frame (cons val (cdr frame))))
(define (extend-environment vars vals base-env)
(if (= (length vars) (length vals))
(cons (make-frame vars vals) base-env)
(if (< (length vars) (length vals))
(error "Too many arguments supplied" vars vals)
(error "Too few arguments supplied" vars vals))))
4.5. eval-atom
(define (self-evaluating? exp)
(cond ((number? exp) true)
((string? exp) true)
(else false)))
(define (variable? exp) (symbol? exp))
(define (lookup-variable-value var env)
(define (env-loop env)
(define (scan vars vals)
(cond ((null? vars)
(env-loop (enclosing-environment env)))
((eq? var (car vars))
(car vals))
(else (scan (cdr vars) (cdr vals)))))
(if (eq? env the-empty-environment)
(error "Unbound variable" var)
(let ((frame (first-frame env)))
(scan (frame-variables frame)
(frame-values frame)))))
(env-loop env))
4.6. eval-define & eval-assign
(define (eval-assignment exp env)
(set-variable-value!
(assignment-variable exp)
(eval (assignment-value exp) env)
env)
'ok)
(define (eval-definition exp env)
(define-variable!
(definition-variable exp)
(eval (definition-value exp) env)
env)
'ok)
(define (define-variable! var val env)
(let ((frame (first-frame env)))
(define (scan vars vals)
(cond ((null? vars)
(add-binding-to-frame! var val frame))
((eq? var (car vars))
(set-car! vals val))
(else (scan (cdr vars) (cdr vals)))))
(scan (frame-variables frame)
(frame-values frame))))
4.7. eval-if
(define (eval-if exp env)
(if (true? (eval (if-predicate exp) env))
(eval (if-consequent exp) env)
(eval (if-alternative exp) env)))
4.8. eval-quote
(define (quoted? exp) (tagged-list? exp 'quote)) (define (text-of-quotation exp) (cadr exp))
4.9. eval-lambda
(define (make-procedure parameters body env) (list 'procedure parameters body env)) (define (compound-procedure? p) (tagged-list? p 'procedure)) (define (procedure-parameters p) (cadr p)) (define (procedure-body p) (caddr p)) (define (procedure-environment p) (cadddr p))
4.10. eval-begin
(define (eval-sequence exps env)
(cond ((last-exp? exps) (eval (first-exp exps) env))
(else (eval (first-exp exps) env)
(eval-sequence (rest-exps exps) env))))
5. 最后
5.1. 几个题外话
- 如果没有 assign, 会不会简单很多
- 如果使用 lazy 的求值, 而不是应用时求值，是否很多特殊形式就没有必要了
- 如果增加一个
case的关键字 - 如果做语法分析
- 如果要编译成 c