總結篇3 解釋器 —— Interpreter

02-12

0 解釋器概述
- 0-1 解釋器意義
- 0-2 解釋器結構
- 0-3 代碼說明
1 界面
- 1-1 界面啟動
- 1-2 輸入測試代碼
- 1-3 初始化符號表環境
- 1-4 驅動循環
2 結構
- 2-1 符號表環境
- 2-2 真假謂詞
- 2-3 原子過程
- 2-4 組合過程
3 表達式
- 3-1自求值表達式
- 3-2變數引號表達式
- 3-3定義賦值表達式
- 3-4條件表達式
- 3-5begin表達式
- 3-6自定義應用表達式
4 核心
- 4-1 eval表達式分類解析
- 4-2 apply過程求值
附:語法說明

0 解釋器概述

0-1 解釋器意義

在特定的符號表環境中求解表達式的過程組織
符號表環境包含基本原子符號和複雜符號
表達式在原子符號的基礎上以一定的規則構建複雜符號
求解表達式的過程就是將複雜符號根據規則分解為基本原子符號的遞歸過程

0-2 解釋器結構

界面：包括解釋器的輸入輸出部分實現

結構：包括基本符號與符號表的實現
表達式：包括基本符號到複雜符號的組織規則
核心：包括複雜符號到基本符號的求解過程

0-3 代碼說明

注釋SICP的第四章的元循環求值器
將代碼以可閱讀性目標進行組織

1 界面

1-1 界面啟動

(define the-global-environment (setup-environment))(driver-loop);;; M-Eval input:

界面啟動代碼
定義符號表
啟動循環
界面輸出提示語
等待輸入內容

1-2 輸入測試代碼

(define (append x y) (if (null? x) y (cons (car x) (append (cdr x) y) ) ))

輸入測試內容1

;;; M-Eval value:ok

輸出結果為ok，表示過程append定義成功

;;; M-Eval input:(append (a b c) (d e f))

輸入測試內容2

;;; M-Eval value:(a b c d e f)

輸出結果2，調用append過程結果

1-3 初始化符號表環境

(define (setup-environment) (let ;let的(<var><exp>) ( ( initial-env (extend-environment (primitive-procedure-names) (primitive-procedure-objects) the-empty-environment ) ) ) ;let的<body> (define-variable! true true initial-env) (define-variable! false false initial-env) ;let的<body>返回結果 initial-env ))

初始化運行環境(setup-environment)過程定義
let的var-exp語句部分，
擴展the-empty-environment為initial-env
let的body部分
註冊』true,』false到initial-env,並返回initial-env

1-4 驅動循環

(define (driver-loop) ;列印提示語 (prompt-for-input input-prompt) ;獲取輸入並運行 (let ( (input (read)) ) (let ( ( output (eval input the-global-environment) ) ) (announce-output output-prompt) (user-print output) ) ) ;遞歸驅動循環 (driver-loop))

驅動循環主體

列印輸入提示語
等待獲取輸入
處理輸入獲取結果
列印輸出提示語
輸出運行結果
再次進入驅動循環

(define input-prompt ";;;M-Eval input:")(define output-prompt ";;;M-Eval value:")(define (prompt-for-input string) (newline) (newline) (display string) (newline))(define (announce-output string) (newline) (display string) (newline))

輸入提示語input-prompt
輸出提示語output-prompt
input-prompt輸出
output-prompt輸出

(define (user-print object) (if (compound-procedure? object) (display (list compound-procedure (procedure-parameters object) (procedure-body object) <procedure-env> ) ) (display object) ))

結果輸出
結果為複合過程，輸出過程定義
其他結果，直接輸出

2 結構

2-1 符號表環境

(define the-empty-environment ())

空符號表環境

(define (make-frame variables values) (cons variables values))(define (frame-variables frame) (car frame))(define (frame-value 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) ) ))

使用vars vals對應列表擴展base-env
使用vars vals組織為鍵值對幀

將vars vals擴展的鍵值對幀註冊到base-env
env的結構為frame的列表組織

(define (first-frame env) (car env))(define (enclosing-environment env) (cdr env))

符號表環境當前鍵值對幀獲取
符號表環境擴展鍵值對環境獲取

(define (lookup-variable-value var env) ;環境中符號查找循環 (define (env loop env) ;frame中搜索var (define (scan vars vals) (cond ((null?vars) (env-loop (enclosing-environment env)) ) ((eq? var (car vars)) (car vals) ) (else (scan (cdr vars) (cdr vals)) ) ) ) ;env環境搜索 (if (eq? env the-empty-environment) (error "Unound variable" var) (let ( (frame (first-frame env)) ) (scan (frame-variables frame) (frame-values frams) ) ) ) ) ;返回env-loop作為符號查找過程 (env-loop env))

env中查找var變數
首先在當前環境搜索,查找成功，返回
查找失敗,查找外圍環境

(define (define-variables! 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 varl) ) (else (scan (cdr vars)(cdr vals)) ) ) ) (scan (frame-variables frame) (frame-values frame) ) ))(define (set-variable-value! var val env) (define (env-loop env) (define (scan vars vals) (cond ((null? var) (env-loop (enclosing-environment env)) ) ((eq? var (car vars)) set-car! vals val ) (else (scan (cdr vars) (cdr vals)) ) ) ) (if (eq? env the-empty-environment) (error "Unbound variable--SET1" var) (let ( (frame (first-frame env)) ) (scan (frame-variables frame) (frame-values frame) ) ) ) ) (env-loop env))

添加(var val)到env
修改env的var為val

2-2 真假謂詞

(define (true? x) (not (eq? ex false)))(define (false? x) (eq? ex false))

真假判斷

2-3 原子過程

(define (primitive-procedure? proc) (tagged-list? proc primitive))

1 判斷過程proc是否為原子過程

(define (primitive-implementation proc) (cadr proc))

2 獲取過程proc的實現部分

(define primitive-procedures (list (list car car) (list cdr cdr) (list cons cons) (list null? null?) <其他原子過程定義> ))

3 原子過程列表primitive-procedures

(define (primitive-procedures-name) (map car primitive-procedures ))

4 獲取原子過程列表的過程名』car

(define (primitive-procedure-objects) (map (lambda (proc) (list primitive (cadr proc)) ) primitive-procedures ))

5 構造原子過程(『primitive car)
原子過程組成鍵值對(『car (『primitive car))註冊到運行環境

2-4 組合過程

(define (make-procedure parameter 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))

組合過程構造
組合過程判斷
組合過程參數獲取
組合過程體獲取

組合過程環境參數獲取

3 表達式

3-1自求值表達式

(define (self-evaluating? exp) (cond ((number? exp) true) ((string exp) true) (else false) ))

判斷是否為自求值表達式

3-2變數引號表達式

(define (variable? exp) (symbol? exp))

判斷是否為變數表達式

(define (quoted? exp) (tagged-list? exp quote))(define (text-of-quotation exp) (cadr exp))(define (tagged-list? exp tag) (if (pair? exp) (eq? (car exp) tag) false ))

3-3定義賦值表達式

(define (definition? exp) (tagged-list? exp define))(define (definition-variable exp) (if (symbol? (cadr exp)) (cadr exp) (caadr exp) ))(define (definition-value exp) (if (symbol? (cadr exp)) (caddr exp) (make-lambda (cdadr exp) (caddr exp) ) ))

定義表達式判斷
定義表達式名稱獲取
定義表達式體獲取

(define (lambda? exp) (tagged-list? exp lambda))(define (lambda-paramters exp) (cadr exp))(define (lambda-body exp) (cddr exp))(define (make-lambda parameters body) (cons lambda (cons parameters body)))

lambda表達式判斷
lambda參數獲取
lambda體獲取
lambda構造

(define (assignment? exp) (tagged-list? exp set!))(define (assignment-variable exp) (cadr exp))(define (assignment-value exp) (caddr exp))

賦值表達式判斷
賦值表達式變數名
賦值表達式值

3-4條件表達式

(define (if? exp) (tagged-list exp if))(define (if-predicate exp) (cadr exp))(define (if-consequent exp) (caddr exp))(define (if-alternative exp) (if (not (null? (cdddr exp))) (cadddr exp) false ))(define (make-if predicate consequent alternative) (list if predicate consequent alternative))

if表達式判斷
if謂詞獲取
if真值表達式獲取
if假值表達式獲取
if表達式構造

3-5begin表達式

(define (begin? exp) (tagged-list? exp begin))(define (begin-actions exp) (cdr exp))(define (last-exp? seq) (null? (cdr seq)))(define (first-exp seq) (car seq))(define (rest-exps seq) (cdr seq))(define (sequence->exp seq) (cond ((null? seq) seq) ((last-exp? seq) (first-exp seq)) (else (make-begin seq)) ))(define (make-begin seq) (cons begin seq))

begin表達式判斷
begin表達式動作序列獲取

begin表達式最後一個表達式判斷
begin表達式第一個表達式獲取
begin表達式其餘表達式獲取
序列表達式合成begin表達式
begin表達式構造函數

3-6自定義應用表達式

(define (application? exp) (pair exp))(define (operator exp) (car exp))(define (operands exp) (cdr exp))(define (no-operands? ops)(null? ops))(define (first-operand ops)(car ops))(define (rest-operands ops)(cdr ops))

app表達式判斷
app表達式運算符獲取
app表達式運算對象獲取
app表達式無運算對象判斷
app表達式第一個運算對象
app表達式其餘運算對象

4 核心

4-1 eval表達式分類解析

(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表達式 ( (if? exp) (eval-if exp env) ) ;lambda表達式 ( (lambda? exp) (make-procedure (lambda-parameters exp) (lambda-body exp) env ) ) ;begin表達式 ( (begin? exp) (eval-sequence (begin-actions exp) env ) ) ;cond表達式 ( (cond? exp) (eval (cond->if exp) env) ) ;application表達式 ( (application? exp) (apply (eval (operator exp) env) (list-of-values (operands exp) env) ) ) ;錯誤表達式 (else (error "Unknown expression type --EVAL" exp) ) ));賦值表達式處理(define (eval-assignment exp env) (set-variable-value! (assignment-variable exp) (eval (assignment-value exp)) env ) ok);定義表達式處理(define (eval-definition exp env) (definition-variable! (definition-variable exp) (eval (definition-value exp) env) env ) ok);if表達式處理(define (eval-if exp env) (if ( true? (eval (if-predicate exp) env) ) (eval (if-consequent exp) env) (eval (if-alternative exp) env) ));序列表達式處理(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) ) ));過程參數求值(define (list-of-values exps env) (if (no-operands exps) () (cons (eval (first-operand exps) env) (list-of-values (rest-operands exps) env ) ) ))

分析exp表達式類型，並求值
各種不同表達式的處理流程

4-2 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 "Unkown procedure type -- Apply" procedure ) ) ))

附:語法說明

1 (let var-exp body)

(let ( (<var><exp>) ) <body>)