sicp metacircular evaluator (2) - 四則運算

metacircular evaluator 要處理 10 種 expression, 先來看看怎麼處理四則運算, 這會用到 10 個當中的 3 個 expression。

準備好被小括弧折磨了嗎? 我: 「準備好了!」

eval function 相關部份程式碼

 78((application? exp)
 79 (define (eval exp env)
 83   (cond ((self-evaluating? exp) exp)
 84         ((variable? exp) (lookup-variable-value exp env))
 85         ((application? exp)
 86          (apply (eval (operator exp) env)
 87                 (list-of-values (operands exp) env)))
 88         (else (error "Unknows expression type -- EVAL" exp))))
 89

只要
((self-evaluating? exp) exp)
((variable? exp)
((application? exp)
就可以完成四則運算式。ex: (+ 1 2), (+ (* 2 3) 5) 之類的運算。騙你的, 哪這麼容易, 不過重點是在這邊沒錯。

這個 list-of-values 可把我的腦袋轉了好幾轉, list-of-values 除了是呼叫自己的 recursive function 還呼叫了 eval, 而這個 eval 也是個 recursive function, 這兩個勾結在一起, 用掉我不少 A4 紙, 不知打了多少 ... 不是, 是畫了不少呼叫流程圖才搞懂。據說這個叫 mutual recursion。

list-of-values, eval, apply 要一起談。

下面是一個大概的解釋 (好像沒解釋, 那就自己看吧), list-of-values 是怎麼運作, 可以觀察 L2 ~ L11 的輸出。

list-of-values

 59 (define (list-of-values exps env)
 60   (if (no-operands? exps)
 61       '()
 62       (cons (eval (first-operand exps) env)
 63             (list-of-values (rest-operands exps) env))))
 64 

 70 (display (list-of-values '(1 (* 2 3)) the-global-environment))

 1 ;Loading "me.scm"...@(1 (* 2 3))@
 2 @((* 2 3))@
 3 @()@
 4 #(* 2 3)#
 5 
 6 ^^(* 2 3)^^
 7 @(2 3)@
 8 @(3)@
 9 @()@
10 #3#
11 #2#
12 
13 $$(* 2 3)$$
14 #*#
15 ppp---(primitive #[arity-dispatched-procedure 11])
16 (2 3)---ppp---
17 #1#
18 (1 6)
19 ;... done
20 ;Unspecified return value

先來看看要 evaluate (+ 1 2), 程式會怎麼跑? 總共會執行三個 function: eval, apply, list-of-values

eval

 79 (define (eval exp env)
 80   (display "#")
 81   (display exp)
 82   (display "#\n")
 83   (cond ((self-evaluating? exp) exp)
 84         ((variable? exp) (lookup-variable-value exp env))
 85         ((application? exp)
 86          (apply (eval (operator exp) env)
 87                 (list-of-values (operands exp) env)))
 88         (else (error "Unknows expression type -- EVAL" exp))))

如果你跳過上面的上面 list-of-values 程式碼, 沒關係, 那也不重要, 下面的圖比較清楚, 這是手工打造的, 歡迎投稿給我一個精緻的版本。

那你說看了上面的上面 list-of-values 程式碼的傢伙是不是浪費時間, 有點像蠢蛋呢? 怎麼可能, 那把這段寫出來的我, 不就是蠢蛋之王了。

eval L85 ~ L87 就是 (+ 1 2) 會被執行的部份, 我都不知道該怎麼說了, 看完 fig 1 後整個是一目了然, 不用再打字囉!

(飛踢) ... 呃 ... 還是說明一下好了。(+ 1 2) 會被拆成兩部份, '+, '(1 2), '+ 傳給 eval, '(1 2) 傳給 list-of-values, 再 recursive 下去。

fig 1

最後 eval 2 的時候會傳回數字 2, list-of-values '() 回傳 '(), 而 list-of-values 會用 cons 接起這兩個值, 就像這樣 (cons 2 '()) 會得到 '(2); eval 1 會傳回數字 1, (cons 1 (2)) 會得到 (1 2)。

而 symbol + 會被 eval 傳回一個 primitive add procedure, apply 會接收這個 primitive add procedure, 和 (1 2), 再來你也想像得到, apply 呼叫 add procedure 以 (1 2) 為參數, 把 1+2 算出來的 3 傳回。3 就這樣被算出來了。

---

再來看看複雜一點的 expression: (* (+ 1 2) 3), 看 fig 2 還是一目了然, 這個 expression 被分解成那樣, 沒什麼好說明的。evaluate (+ 1 2) 看起來好像很面熟, 就是上面 fig 1 的流程, 我應該不用把整段 copy/paste, 這樣就把所有 expression 處理完了, 最後得到 3, 在把 3 和最後一個 3 cons 起來得到 '(3 3) 傳給乘法函式, 9 就這麼被算出來了。

recursive 的想法實在厲害, 不過我的腦袋真的打太多結, 看懂這程式碼不厲害, 寫出這樣的程式碼才厲害。mit (請別誤會為台灣製造) 出品的程式碼果然不同。

fig 2

這個看來不怎麼厲害的東西也不過就是常見的計算機程式, 而且還是奇怪的變形, prefix 的語法, 但要理解她, 還是花上我不少的腦力。

mit metacircular evaluator source code: http://mitpress.mit.edu/sicp/code/ch4-mceval.scm

https://github.com/descent/sicp_prog/tree/master/4.1
git tag basic_exp 有這個範例, mit 網站的範例需要一點修改才能正常執行, 這是我縮小的版本, 已經修正到只能處理四則運算。只能用 mit-scheme 執行。