PLAI前6章回顧

離上一章節翻譯已經過去三周，跨過了一個年。這篇文章大致回顧一下前幾章的內容並將相關代碼整理至此。

第一章（譯文，原文）簡單介紹了本書的結構以及書中使用的語言 plai-typed。可以參考 PLAI編程環境簡單介紹配置好編程環境，然後簡單過一下該章代碼熟悉一下 plai-typed 中 define-type 、 type-case 和 test 的使用。

#lang plai-typednn(define-type MisspelledAnimaln [caml (humps : number)]n [yacc (height : number)])nn(define ma1 (caml 2))n(define ma2 (yacc 1.9))nn(define (good? [ma : MisspelledAnimal]) : booleann (type-case MisspelledAnimal man [caml (humps) (>= humps 2)]n [yacc (height) (> height 2.1)]))nn(test (good? ma1) #t)n(test (good? ma2) #f)n

要實現一個編程語言的解釋器，第一步當然需要實現對輸入的解析，而本書的重點不在於此， 於是第二章（譯文，原文） 介紹了使用 plai-typed 語言內建函數 read 將輸入解析成 s-expression ， 後再解析成定義的語言的內部表示。

#lang plai-typednn(define-type ArithCn [numC (n : number)]n [plusC (l : ArithC) (r : ArithC)]n [multC (l : ArithC) (r : ArithC)])nn(define (parse [s : s-expression]) : ArithCn (condn [(s-exp-number? s) (numC (s-exp->number s))]n [(s-exp-list? s)n (let ([sl (s-exp->list s)])n (case (s-exp->symbol (first sl))n [(+) (plusC (parse (second sl)) (parse (third sl)))]n [(*) (multC (parse (second sl)) (parse (third sl)))]n [else (error parse "invalid list input")]))]n [else (error parse "invalid input")]))nn(parse (read))n;; (+ 2 (* 3 20))n;; ->n;; (plusC (numC 2) (multC (numC 3) (numC 20)))n

第二章（譯文，原文） 解析了一個簡單的算術語言（支持整數的加法和乘法），第三章（譯文，原文） 針對該語言的內部表示實現了一個解釋器。

#lang plai-typednn;; ArithC 代碼不變n;; parse 代碼不變nn(define (interp [a : ArithC]) : numbern (type-case ArithC an [numC (n) n]n [plusC (l r) (+ (interp l) (interp r))]n [multC (l r) (* (interp l) (interp r))]))n

第三章（譯文，原文） 實現的算術語言只支持加法和乘法，第四章（譯文，原文） 考慮在不改變語言核心（語言的內部表示）的情況下引入減法操作，於是引入了一個語法糖， 並且簡單討論了語法糖設計中的一些問題。最後通過讓讀者引入單目操作符「取負」引導讀者思考了更多有關語法糖的問題。

#lang plai-typednn;; ArithC 代碼不變n;; interp 代碼不變nn(define-type ArithSn [numS (n : number)]n [plusS (l : ArithS) (r : ArithS)]n [bminusS (l : ArithS) (r : ArithS)]n [multS (l : ArithS) (r : ArithS)])nn;; ArithS -> ArithCn(define (desugar [as : ArithS]) : ArithCn (type-case ArithS asn [numS (n) (numC n)]n [plusS (l r) (plusC (desugar l)n (desugar r))]n [multS (l r) (multC (desugar l)n (desugar r))]n [bminusS (l r) (plusC (desugar l)n (multC (numC -1) (desugar r)))]))nn;; 解析器現在輸出 ArithSn(define (parse [s : s-expression]) : ArithSn (condn [(s-exp-number? s) (numS (s-exp->number s))]n [(s-exp-list? s)n (let ([sl (s-exp->list s)])n (case (s-exp->symbol (first sl))n [(+) (plusS (parse (second sl)) (parse (third sl)))]n [(*) (multS (parse (second sl)) (parse (third sl)))]n [(-) (bminusS (parse (second sl)) (parse (third sl)))]n [else (error parse "invalid list input")]))]n [else (error parse "invalid input")]))nn;; 解釋代碼之前需要使用 desugar 剔除語法糖n(interp (desugar (parse (read))))n

在第五章（譯文，原文） 中首次引入了函數，注意這裡在語言中沒有引入函數值類型，函數都是預定義，函數列表作為參數傳遞給解釋器使用， 所有表達式的值還只是數。重點在於函數的求值過程的討論。

#lang plai-typednn;; 函數類型n(define-type FunDefCn [fdC (name : symbol) (arg : symbol) (body : ExprC)])nn;; 語言的核心數據結構 ExprC 添加了標識符 (idC) 和函數調用 (appC) 函數類型n(define-type ExprCn [numC (n : number)]n [idC (s : symbol)]n [appC (fun : symbol) (arg : ExprC)]n [plusC (l : ExprC) (r : ExprC)]n [multC (l : ExprC) (r : ExprC)])nn;; 輔助函數:從函數列表 fds 取出名為 n 的函數定義n(define (get-fundef [n : symbol] [fds : (listof FunDefC)]) : FunDefCn (condn [(empty? fds) (error get-fundef "reference to undefined function")]n [(cons? fds) (condn [(equal? n (fdC-name (first fds))) (first fds)]n [else (get-fundef n (rest fds))])]))nn;; 輔助函數：將表達式 in 中所有標識符 for 替換為 whatn(define (subst [what : ExprC] [for : symbol] [in : ExprC]) : ExprCn (type-case ExprC inn [numC (n) in]n [idC (s) (condn [(symbol=? s for) what]n [else in])]n [appC (f a) (appC f (subst what for a))]n [plusC (l r) (plusC (subst what for l)n (subst what for r))]n [multC (l r) (multC (subst what for l)n (subst what for r))]))nn;; parsern(define (parse [s : s-expression]) : ExprCn (condn [(s-exp-number? s) (numC (s-exp->number s))]n [(s-exp-symbol? s) (idC (s-exp->symbol s))]n [(s-exp-list? s)n (let ([sl (s-exp->list s)])n (case (s-exp->symbol (first sl))n [(+) (plusC (parse (second sl)) (parse (third sl)))]n [(*) (multC (parse (second sl)) (parse (third sl)))]n [else (appC (s-exp->symbol (first sl))n (parse (second sl)))]))]))nn;; 解釋器多了一個參數，傳入預定義的函數列表n(define (interp [e : ExprC] [fds : (listof FunDefC)]) : numbern (type-case ExprC en [numC (n) n]n [idC (_) (error interp "shouldnt get here")]n [appC (f a) (let ([fd (get-fundef f fds)])n (interp (subst a (fdC-arg fd) (fdC-body fd))n fds))]n [plusC (l r) (+ (interp l fds) (interp r fds))]n [multC (l r) (* (interp l fds) (interp r fds))]))nn(interp (parse (read)) (listn (fdC plusOne x (plusC (idC x) (numC 1)))n (fdC square x (multC (idC x) (idC x)))))n;; (square (plusOne 10))n;; ->n;; 121n

第六章（譯文，原文）首先說明了一些上一章實現的函數替換模型的問題，以該章解釋器為參考實現，將替換模型更換成環境模型重新實現了一個行為一致的解釋器。 並在實現過程討論了關於動態作用域的問題。

#lang plai-typednn;; 函數類型n(define-type FunDefCn [fdC (name : symbol) (arg : symbol) (body : ExprC)])nn;; 語言的核心數據結構 ExprC 添加了標識符 (idC) 和函數調用 (appC) 函數類型n(define-type ExprCn [numC (n : number)]n [idC (s : symbol)]n [appC (fun : symbol) (arg : ExprC)]n [plusC (l : ExprC) (r : ExprC)]n [multC (l : ExprC) (r : ExprC)])nn;; 輔助函數:從函數列表 fds 取出名為 n 的函數定義n(define (get-fundef [n : symbol] [fds : (listof FunDefC)]) : FunDefCn (condn [(empty? fds) (error get-fundef "reference to undefined function")]n [(cons? fds) (condn [(equal? n (fdC-name (first fds))) (first fds)]n [else (get-fundef n (rest fds))])]))nn;; 定義環境相關數據結構與操作n(define-type Bindingn [bind (name : symbol) (val : number)])n(define-type-alias Env (listof Binding))n(define mt-env empty)n(define extend-env cons)nn;; 在環境 env 中查找標識符 n 綁定的值n(define (lookup [n : symbol] [env : Env]) : numbern (condn [(= 0 (length env)) (error lookup "Cant find binding")]n [else (let [(b (first env))]n (if (symbol=? n (bind-name b))n (bind-val b)n (lookup n (rest env))))]))nn;; parsern(define (parse [s : s-expression]) : ExprCn (condn [(s-exp-number? s) (numC (s-exp->number s))]n [(s-exp-symbol? s) (idC (s-exp->symbol s))]n [(s-exp-list? s)n (let ([sl (s-exp->list s)])n (case (s-exp->symbol (first sl))n [(+) (plusC (parse (second sl)) (parse (third sl)))]n [(*) (multC (parse (second sl)) (parse (third sl)))]n [else (appC (s-exp->symbol (first sl))n (parse (second sl)))]))]))nn;; 解釋器多了一個參數,傳入預定義的函數列表n(define (interp [a : ExprC] [env : Env] [fds : (listof FunDefC)]) : numbern (type-case ExprC an [numC (n) n]n [idC (n) (lookup n env)]n [appC (f arg) (let ([fd (get-fundef f fds)])n (interp (fdC-body fd)n (extend-env (bind (fdC-arg fd)n (interp arg env fds))n mt-env) ;; 這個地方 mt-env 改成 env 此解釋器將變成動態綁定的n fds))]n [plusC (l r) (+ (interp l env fds) (interp r env fds))]n [multC (l r) (* (interp l env fds) (interp r env fds))]))nn(interp (parse (read))n mt-envn (listn (fdC plusOne x (plusC (idC x) (numC 1)))n (fdC square x (multC (idC x) (idC x)))))n;; (square (plusOne 10))n;; ->n;; 121nn;; 可以通過計算n;; (interp (appC f1 (numC 3))n;; mt-envn;; (list (fdC f1 x (appC f2 (numC 4)))n;; (fdC f2 y (plusC (idC x) (idC y)))))n;; 來了解動態綁定的求解過程n

後面一章將把函數作為值引入解釋器，我們將能夠進行高階函數的解釋，敬請期待， 或直接去往原文。