open-courses
Search…

### 解释器的基本构造

![](/assets/Screen Shot 2018-04-07 at 4.23.21 PM.jpg)

• Lexical Analyzer: 将字符串转化成有意义的单词，称作 token
• Parser：将各单词组合成便于推导转化的树状结构 （tree structure）
• Evaluator & Environment：结合环境中的其它变量，将输入的树状结构推导转化成最终的结果值
• Printer：将结果值转化成字符串输出到屏幕上

### 构造 Scheme* 解释器

Arithmetic calculator

(plus* 24 (plus* 5 6))

(define (tag-check e sym)
(and (pair? e) (eq? (car e) sym)))
(define (sum? e) (tag-check e 'plus*))
(define (eval exp)
(cond
((number? exp) exp)
((sum? exp) (eval-sum exp))
(else
(error "unknown expression" exp))))
(define (eval-sum exp)
(eval '(plus* 24 (plus* 5 6)))

![](/assets/Screen Shot 2018-04-07 at 4.23.54 PM.jpg)
eval 过程通过判断表达式的第一个 token 的类型，来决定要对其进行什么样的操作 --- 如果是 number，就直接返回对应数值，如果是 plus*，则将表达式交给 eval-sum 去递归推导转化成最终结果。

Names

(define* x* (plus* 4 5))
(plus* x* 2)

; make-table void -> table
; table-get table, symbol -> (binding | null)
; table-put! table, symbol, anytype -> undef
; binding-value binding -> anytype

(define (define? exp) (tag-check exp 'define*))
(define (eval exp)
(cond
((number? exp) exp)
((sum? exp) (eval-sum exp))
((symbol? exp) (lookup exp))
((define? exp) (eval-define exp))
(else
(error "unknown expression" exp))))
(define environment (make-table))
(define (lookup name)
(let ((binding (table-get environment name)))
(if (null? binding)
(error "unbound variable: " name)
(binding-value binding))))
(define (eval-define exp)
(table-put! environment name (eval define-to-be)) 'undefined))
define* 表达式与之前的 plus* 表达式不同。plus* 表达式会 evaluate 它的两个参数，我们称这种表达式为一般表达式；define* 表达式只会 evaluate 第二个参数，把第一个参数当作 symbol，我们称不 evaluate 所有输入参数的表达式为特殊表达式 (special forms)。
Conditionals and If
scheme* 少不了 predicates 和条件语句 if
(define (greater? exp) (tag-check exp 'greater*))
(define (if? exp) (tag-check exp 'if*))
(define (eval exp)
(cond
((number? exp) exp)
((sum? exp) (eval-sum exp))
((symbol? exp) (lookup exp))
((define? exp) (eval-define exp))
(else
(error "unknown expression" exp))))
(define (eval-greater exp)
(define (eval-if exp)
(let ((test (eval predicate)))
(cond
((eq? test #t) (eval consequent))
((eq? test #f) (eval alternative))
(else (error "predicate not a conditional: " predicate))))))
Store operators in the environment

(define scheme-apply apply) ; 保存 scheme 内置的 apply
(define (apply operator operands)
(if (primitive? operator)
(scheme-apply (get-scheme-procedure operator) operands)
(error "operator not a procedure: " operator)))
(define prim-tag 'primitive)
(define (make-primitive scheme-proc) (list prim-tag scheme-proc))
(define (primitive? e) (tag-check e prim-tag))
(define environment (make-table))
(table-put! environment 'plus* (make-primitive +))
(table-put! environment 'greater* (make-primitive >))
(table-put! environment 'true* #t)

(define (eval exp)
(cond
((number? exp) exp)
((symbol? exp) (lookup exp))
((define? exp) (eval-define exp))
((if? exp) (eval-if exp))
((application? exp) (apply (eval (car exp))
(map eval (cdr exp))))
(else
(error "unknown expression " exp))))

Environment as explicit parameter

(define (eval exp env)
(cond
((number? exp) exp)
((symbol? exp) (lookup exp env))
((define? exp) (eval-define exp env))
((if? exp) (eval-if exp env))
((application? exp) (apply (eval (car exp) env)
(map (lambda (e) (eval e env))
(cdr exp))))
(else
(error "unknown expression " exp))))
(define (lookup name env)
(let ((binding (table-get env name)))
(if (null? binding)
(error "unbound variable: " name)
(binding-value binding))))
(define (eval-define exp env)
(table-put! env name (eval defined-to-be env))
'undefined))
(define (eval-if exp env)
(table-put! env name (eval defined-to-be env))
'undefined))

lambda* 表达式有三个重要成部分，参数、函数体以及环境，因此在 eval lambda* 的时候，需要在返回的数据结构中保存这三部分信息。在这里我们称这个数据结构为 compound，也就是上文到的 double bubble 或 compound procedure：
(define (lambda? e) (tag-check e 'lambda*))
(define (eval exp env)
(cond
((number? exp) exp)
((symbol? exp) (lookup exp env))
((define? exp) (eval-define exp env))
((if? exp) (eval-if exp env))
((lambda? exp) (eval-lambda exp env))
((application? exp) (apply (eval (car exp) env)
(map (lambda (e) (eval e env))
(cdr exp))))
(else
(error "unknown expression " exp))))
(define (eval-lambda exp env)
(make-compound args body env)))
;; ADT that implements the "double bubble"
;; 这里 compound 由 parameters、body、env 三部分构成，ADT 同时提供三者的 selectors
(define compound-tag 'compound)
(define (make-compound parameters body env)
(list compound-tag parameters body env))
(define (compound? exp) (tag-check exp compound-tag))

1. 1.
创建一个新的 Frame，设为 A
2. 2.
将 A 的外环境指针指向 P 的外环境指针所指的环境，此时 A 及其外环境一起构成新的环境，设为 E
3. 3.
在 A 中，将 P 的参数与它的值绑定起来
4. 4.
在 E 中执行 P 的程序体
(define (apply operator operands)
(cond ((primitive? operator)
(scheme-apply (get-scheme-procedure operator)
operands))
((compound? operator)
(eval (body operator)
(extend-env-with-new-frame
(parameters operator)
operands
(env operator))))
(else
(error "operator not a procedure: " operator))))
(define (extend-env-with-new-frame names values env)
(let ((new-frame (make-table)))
(make-bindings! names values new-frame)
(cons new-frame env))) ; 注意：这里 new-frame 在 env 之前，体现 lookup 顺序
(define (make-bindings names values table)
(for-each
(lambda (name value) (table-put! table name value))
names values))
; the initial global environment
(define GE
(extend-env-with-new-frame
(list 'true* 'plus* 'greater*)
(list #t (make-primitive +) (make-primitive >))
nil))
; lookup searches the list of frames for the first match
(define (lookup name env)
(if (null? env)
(error "unbound variable: " name)
(let ((binding (table-get (car env) name)))
(if (null? binding)
(lookup name (cdr env))
(binding-value binding)))))
; define changes the first frame in the environment
(define (eval-define exp env)
(table-put! (car env) name (eval defined-to-be env))
'undefined)

(eval '(define* twice*
(lambda* (x*) (plus* x* x*))) GE)

![](/assets/Screen Shot 2018-04-07 at 4.24.05 PM.jpg)

(eval '(twice* 4) GE)

(apply (eval 'twice* GE)
(map (lambda (e) (eval e GE)) '(4)))
map 表达式在 GE 中 evaluate twice* 的参数 --- 4：
(apply (eval 'twice* GE) '(4))
GE 中可以找 'twice*
(apply (list 'compound '(x*) '(plus* x* x*) GE) '(4))
apply 发现后面的表达式是 compound procedure
(eval '(plus* x* x*)
(extend-env-with-new-frame '(x*) '(4) GE))

(eval '(plus* x* x*)
((list 'table 'new-frame) (list 'table 'GE)))
> 8

(eval '(twice* 4) AE) ; another environment
(apply (eval 'twice* AE)
(map (lambda (e) (eval e AE)) '(4)))
(apply (eval 'twice* GE) '(4))
(apply (list 'compound '(x*) '(plus* x* x*) GE) '(4))
(eval '(plus* x* x*)
(extend-env-with-new-frame '(x*) '(4) GE))
(eval '(plus* x* x*)
((list 'table 'new-frame) (list 'table 'GE)))
> 8

function printWindow () {
console.log(this.window);
}
printWindow.apply(null, null);
> Window {postMessage: f, blur: f, focus: f, ... }
printWindow.apply({ window: "hello world" }, null)
> "hello world"