sicp metacircular evaluator (6) - lexical closure

sicp metacircular evaluator 這系列的文章瀏覽率慘不忍睹 (當然平常的文章也不怎麼樣, 只是這系列真的太慘了, 可以寫個「慘」字, 有一篇當時在首頁的文章, 3 天只有 20 個點閱率), 不知道是我寫的太爛了還是這題目太冷門了, 但我從中學到很多, 也很快樂, 這是苦澀後的甘甜。

我有想過類似 Gigacircle 那種醒人的標題, 例如: 什麼, 你還不知道什麼是 closure 嗎? 她讓我高潮了。或是 ... 你還不知道的 closure 妙用, 我獲得的 10 種美妙經驗。

但我實在不想用這些讓人耳目一新的標題, 好像有點庸俗。

希望這篇可以破紀錄, 怎麼破, 很簡單, 3 天低於 20 就成了。

這篇是這系列的最後一篇了, 沒興趣的讀者們請忍耐一下, 接下來我就會寫不同的文章了。

這是 define + lambda 的組合。

exp1

1 (define (aa x) (lambda (y) (+ x y)))
2 (define aa (lambda (x) (lambda (y) (+ x y))))

exp1 L1, L2 是一樣的運算式, define 一個 function 只是 lambda 的語法糖衣。這會建立一個 procedure object, 然後把 aa 對應到這個 procedure object, 並加入 global environment, 而這個 procedure object 還有一個環境指標指到 global environment。

不過這個 procedure 是傳回一個 procedure, 語法不是很好看, 我可是花了不算短的時間才弄懂。也就是人家說的 function 傳回一個 function, 我還是不知道和 c 傳回 function pointer 有什麼不同??

下面是一個示意的結果:

aa =>
( ( x , () ) ( ( lambda , ( ( y , () ) ( ( + , ( x , ( y , () ) ) ) () ) ) ) () ) )
env name: global

procedure 的參數是 x, lambda ... 那一串就是 procedure body; 環境指標指向 global。

exp2

1 (define aax (aa 5))

exp2 L1 這個運算式稍微複雜一點, 這個時候 aa 會被執行起來 (因為 aa 是一個 procedure), 所以會開一個新環境 e0, 把 5 對應給 x, 然後 aa 會傳回一個 function: (y) (+ x y), 這是執行後的結果, 傳回一個 procedure, 而 e0 就和這個 function 綁在一起, 不是綁定到 global environment。而 e0 的上層環境是 global environment。

至於變數 aax 對應到這個 procedure object, 存在 global environment。

result:

( ( y ,  ()  ) ( ( + , ( x , ( y ,  ()  )  )  )  ()  )  )
env name: e0
  e0 outer env name: global

exp3

1 (aax 6)

exp3 L1 這個運算是在執行 aax 時, 會開一個新環境 e1 (其上層環境是 e0, 因為 e0 和 aax 綁在一起), 6 會對應到 y, 而在執行 aax 時, 就會到 e0 找到 x=5, 就這樣把 x, y 都找到所對應的值。

那 lexical closure 是什麼, 已經講完了, 這就是 lexical_closure。

aax 除了一個 procedure 還有一個環境 e0, e0 裡頭記載著 x=5, 要不然你以為 aax 是怎麼能正確找到 x 的值。

這有一個翻譯稱為「閉包」, 應該是個中國術語, 台灣不知道有沒相關翻譯的辭彙, 中國術語以後會入侵的更厲害了。

sicp metacircular evaluator (5) - define

終於要談 define 了。為什麼談 define 要先談 lambda? define 有兩種型式:

define-exp L2 很單純, 就是把 a=5 加入環境中就好。但是 L1 的型式會建議一個 function。這就是 lambda 要做的事情。我本來也以為 define 很簡單, 先看了 define, 結果還是要回頭看 lambda。

define-exp

1 (define (plus4 y) (+ y 4))
2 (define a 5)

define-exp L1 會建立一個 procedure object, 這是一個 pair, 一個代表 procedure 本身, 就是

(y) (+ y 4)

例外一個就是一個環境指標, 指到哪個環境呢? 因為是在 global environment 執行 (define (plus4 y) (+ y 4)), 所以這個環境指標指到 global environment。

在 simple scheme (by c++) 的實作中, 我把這個環境指標存到 (y) (+ y 4) 這個 lambda procedure 中。

再來就是把 plus4 和 procedure 本身做個對應, 加到 global environment。這樣 plus4 就可以在 global environment 找到。繞如下面表格紅色部份。

new frame

((plus4 false true car cdr cons null? + *) (procedure (y) ((+ y 4))) #f #t (primitive #[compiled-procedure 2 (list #x1) #x3 #x4d655]) (primitive #[compiled-procedure 3 (list #x2) #x3 #x4d64e]) (primitive #[compiled-procedure 4 (list #x3) #x3 #x4d648]) (primitive #[compiled-procedure 5 (list #x5) #x3 #x4d639]) (primitive #[arity-dispatched-procedure 6]) (primitive #[arity-dispatched-procedure 7]))

new frame 的結果是從這段程式碼當中印出來的。

(define (add-binding-to-frame! var val frame)
(set-car! frame (cons var (car frame)))
(set-cdr! frame (cons val (cdr frame)))
(display "\nnew frame:\n")
(display frame)
(newline))

define-exp L2 很簡單, 把 a 和 5 找出來, 加入到目前的環境就好了, 一樣, 目前的環境是 global environment, 所以用 c++ std::map, map["a"] = 5 這樣就解決了。

在 sicp metacircular 的實作中, 類似 new frame plus4 的作法。

sicp metacircular evaluator (4) - lambda

這次要實作的部份是 lambda, 在 functional programming 熱潮來息時, 最常出現的名詞是 lexical closure 和 lambda, 很多相關主題的聚會也會看到 λ 標誌。讓我想到 2000 年的顯學 - OO , 其三大特性也是讓人朗朗上口, 封裝、繼承、多型, OO 流派是否有時不我予之感。

喔! 還有那個 first-class function。

流行十多年了換人當主角也無不可, 不過 lambda 在 1958 年的 lisp 就已經出現, 經過這麼多年總算熬出頭。

其實我不知道 lambda 到底有多威, 現在的語言似乎一窩蜂要加入這個特性, c++11 也來湊熱鬧了, 用一般 function 遜, 來跑個 lambda 潮。不過在 scheme 裡頭, lambda 是唯一可以建立 function 的方法, 所以沒有 lambda, scheme 就沒有 function call 可以用了。所以得把 lambda 實作出來, 才會有 function call 可以用。

來看看 sicp 4.1.1 怎麼用 scheme 實作 lambda。

當 scheme evaluate 下面的 lambda 運算式時, 會發生什麼事情?

(lambda (x) (+ x 4))

lambda-res1

1 xx output: (procedure (x) ((+ x 4)) (((false true car cdr cons null? + *) #f #t (primitive #[compiled-procedure 2 (list #x1) #x3 #x4d655]) (primitive #[compiled-procedure 3 (list #x2) #x3 #x4d64e]) (primitive #[compiled-procedure 4 (list #x3) #x3 #x4d648]) (primitive #[compiled-procedure 5 (list #x5) #x3 #x4d639]) (primitive #[arity-dispatched-procedure 6]) (primitive #[arity-dispatched-procedure 7]))))

沒幹什麼事情, 很單純的把這個 procedure 加入到目前的環境中 (紅色部份是原本環境的內容)。會 append procedure 這個 symbol, 用來區別 lambda function 還是 primitive function。

這個運算式會建立一個 procedure object, 這是一個 pair, 一個代表 procedure 本身:

(x) (+ x 4)

另外一個東西就是環境指標, 上表的紅色部份就是它的環境指標, 指向 global environment。

handle lambda

143 (define (make-procedure parameters body env)
144 (list 'procedure parameters body env))

156 ((lambda? exp)
157 (make-procedure (lambda-parameters exp)
158 (lambda-body exp)
159 env))

lambda-parameters, lambda-body 兩個就是把 (x), (+ x 4) 分別抓出來, 傳給 make-procedure, 很容易理解。

下面的是 function call (會建立新環境), 以 lambda-exp L1 來說, 就是把 5 傳給 x, 然後計算 (+ x 4)。我知道語法很怪, lambda 就是這麼潮, 我也沒辦法。這就不是單純加入這個 procedure 就好, 還要能執行 + 的那個動作, 並把 x 換成 5, 這樣就能得到 9。

lambda-exp

1 ((lambda (x) (+ x 4)) 5)
2 ((lambda (x) (+ (* x 2) (* 3 x)))5)

lambda-exp L1 那個 expression 在 interpreter 會被怎麼處理? 直譯器會先處理這個 (lambda (x) (+ x 4)) expression, 知道要產生一個 function, 然後要把 5 當成變數 x 的值, 送進去給 (+ x 4), 透過 + 計算得到 9。說完了, 真簡單。

程式流程當然沒這麼簡單, 由於 (lambda (x) (+ x 4)) 是一個 function, 所以在呼叫 apply 時要執行一個 function 時, 會開一個新環境, 稱為 e0 好了, e0 的上層環境是 global 環境, 再把 x = 5 加入這個 e0 這個環境。當 eval x 的時候, 就會在 e0 這個新環境找到 x=5, 然後就是之前的故事了 - 四則運算。

那 lambda-exp L2 呢? 一樣阿! 在新環境找到 x=6 之後, 不就是 (+ (* 5 2) (* 3 5)), 四則運算式就提過了。

apply

  1 ; metacircular evaluator
 49 (define (apply procedure arguments)
 56   (cond ((primitive-procedure? procedure)
 57          (apply-primitive-procedure procedure arguments))
 58         ((compound-procedure? procedure)
 59          (eval-sequence
 60            (procedure-body procedure)
 61            (extend-environment
 62              (procedure-parameters procedure)
 63              arguments
 64              (procedure-environment procedure))))
 65         (else
 66          (error
 67           "Unknown procedure type -- APPLY" procedure))))

apply L58 ~ 64 是處理 lambda function, L61 的 extend-environment 就是用來開一個新環境, 將新的變數名稱變數值存入到那個新環境, 那個新環境會接在上層環境裡頭。

如下表的 L6 紅字部份。

test lambda

1 ((lambda (x) (+ x 4)) 5)
2
3 (procedure (x) ((+ x 4)) (((false true car cdr cons null? + *) #f #t (primitive #[compiled-procedure 11 (list #x1) #xf #x3218d3]) (primitive #[compiled-procedure 12 (list #x2) #xf #x321917]) (primitive #[compiled-procedure 13 (list #x3) #xc #x32195c]) (primitive #[compiled-procedure 14 (list #x5) #xc #x3219b8]) (primitive #[arity-dispatched-procedure 15]) (primitive #[arity-dispatched-procedure 16]))))
4
5
6 (((x) 5) ((false true car cdr cons null? + *) #f #t (primitive #[compiled-procedure 11 (list #x1) #xf #x3218d3]) (primitive #[compiled-procedure 12 (list #x2) #xf #x321917]) (primitive #[compiled-procedure 13 (list #x3) #xc #x32195c]) (primitive #[compiled-procedure 14 (list #x5) #xc #x3219b8]) (primitive #[arity-dispatched-procedure 15]) (primitive #[arity-dispatched-procedure 16])))

sicp metacircular evaluator (3) - environment

這裡談的是 sicp metacircular evaluator 的 environment, 什麼是 environment?

ref: http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-26.html#%_sec_4.1.3

Operations on Environments

The evaluator needs operations for manipulating environments. As explained in section 3.2, an environment is a sequence of frames, where each frame is a table of bindings that associate variables with their corresponding values. We use the following operations for manipulating environments:

下面是個簡單的示意圖, 我不確定一個 environment 只有一個 frame, 還是可以有多個 frame, 我的 c++ 版本的 scheme interpreter 一個 environment 只有一個 frame。如有有新環境的話, 會有一個指標對應到上層環境, 當然不一定要指標, scheme 就沒有指標可以這樣做, 它是用 list 來做類似的事情。當目前環境找不到變數定義時, 就到上層環境找, 都找不到才可宣稱此變數無定義。

environment (frame sequence)

frame 1 => table [variables = values; ex: a = 5, b=6] frame 2 => table [variables = values; ex: + = add_proc, b="iamstring"] frame 3 => table [variables = values; ex: - = sub_proc, b=1.2.3]

以下的程式碼便是建立 global environment。

env.scm

  1 ;;;;METACIRCULAR EVALUATOR FROM CHAPTER 4 (SECTIONS 4.1.1-4.1.4) of
295 (define (setup-environment)
296   (let ((initial-env
297          (extend-environment (primitive-procedure-names)
298                              (primitive-procedure-objects)
299                              the-empty-environment)))
300     (define-variable! 'true true initial-env)
301     (define-variable! 'false false initial-env)
302     initial-env))
303 
304 ;[do later] (define the-global-environment (setup-environment))

環境就是建立一個變數和變數值的對應, 幹什麼用呢？

(+ 1 2)

當要處理這個 expression 時, expression 我看過一些翻譯: 表達式、算式, 不過這裡我把他翻譯作 "運算式", 再回到我們那個運算式, 1, 2 是數字沒問題, 那 + 這個符號是什麼呢?

你說它是什麼就是什麼, 不過一個正常人都會把 + 解釋成加號 (如果你看到 + 會想到減法, 那說明你的品味很獨特), 所以這個運算式就是把 1, 2 加起來。那怎麼讓 + 對應到加法呢? 把 + 當成變數, 加法當成變數值對應起來就好。

所以 frame 裡頭有一個 (+, 做加法的函式) 這樣一個對應。在 c++ 裡頭, 用 std::map 就可以搞定這件事情。

不過 scheme 沒有 map, 只有 pair, 所這個程式用了另一種辦法。

e1

 1 (display (extend-environment (primitive-procedure-names)
 2                              (primitive-procedure-objects)
 3                              the-empty-environment) )
 4 
 5 ((
 6   (car cdr cons null? +) 
 7   (primitive #[compiled-procedure 11 (list #x1) #xf #x3218d3]) 
 8   (primitive #[compiled-procedure 12 (list #x2) #xf #x321917]) 
 9   (primitive #[compiled-procedure 13 (list #x3) #xc #x32195c]) 
10   (primitive #[compiled-procedure 14 (list #x5) #xc #x3219b8]) 
11   (primitive #[arity-dispatched-procedure 15])
12 ))

e1 L6 是變數 (variables), L7 ~ 11 是這些變數的值 (values)。這個程式碼把變數保存在一個 list, 變數值保存在另外幾個 list, 如果是 primitive procedure 就加入 primitive 來識別他是一個 primitive procedure。

env.scm L300, L301 則把 true, false 加入這個環境的第一個 frame。

所以裡頭有: false, true ... 這些 name, 還有 primitive procedure, 下面框框的紅色部份, 以 primitive symbol 開頭, 後面奇怪的東西就是 primitive procedure。
(ex:#[compiled-procedure 12 (list #x2) #xf #x321917])

env

1 (((false true car cdr cons null? +) #f #t (primitive #[compiled-procedure 11 (list #x1) #xf #x3218d3]) (primitive #[compiled-procedure 12 (list #x2) #xf #x321917]) (primitive #[compiled-procedure 13 (list #x3) #xc #x32195c]) (primitive #[compiled-procedure 14 (list #x5) #xc #x3219b8]) (primitive #[arity-dispatched-procedure 15])))

(setup-environment) 回傳的 environment

 1 (
 2   (
 3     (false true car cdr cons null? +) 
 4     #f 
 5     #t 
 6     (primitive #[compiled-procedure 11 (list #x1) #xf #x3218d3]) 
 7     (primitive #[compiled-procedure 12 (list #x2) #xf #x321917]) 
 8     (primitive #[compiled-procedure 13 (list #x3) #xc #x32195c]) 
 9     (primitive #[compiled-procedure 14 (list #x5) #xc #x3219b8]) 
10     (primitive #[arity-dispatched-procedure 15])
11   )
12 )

這個就是 global environment, 一開始就會有的環境, 也是所有子環境的父環境。今天不談子環境, 單純談 global environment。

有了 environment 之後, 遇到 symbol (variable?) 時, 就可以來查這個 environment 有無對應的值。下面的  lookup-variable-value 就是在做這件事情。從 L260 開始執行起。可參照 sicp 中文版 p261 對環境的操作一節

ch4-mceval.scm

230 (define the-empty-environment '())

249 (define (lookup-variable-value var env)
253   (define (env-loop env)
254     (define (scan vars vals)
255       (cond ((null? vars)
256              (env-loop (enclosing-environment env)))
257             ((eq? var (car vars))
258              (car vals))
259             (else (scan (cdr vars) (cdr vals)))))
260     (if (eq? env the-empty-environment)
261         (error "Unbound variable" var)
262         (let ((frame (first-frame env)))
263           (scan (frame-variables frame)
264                 (frame-values frame)))))
265   (env-loop env))
266 
267 (define (set-variable-value! var val env)

(display (lookup-variable-value '+ the-global-environment)
會回傳
(primitive #[arity-dispatched-procedure 15])
這個 list。
'primitive 和 + 這個 procedure。

把回傳的 + procedure 和 (1 2) 作為 apply 的參數 (這個 apply 是 scheme 的 primitive procedure, 不是 metacircular evaluator 程式碼裡頭那個 apply), 就可以計算出 3 來。用 c++ 實作的話, + procedure 會是一個 function, 把 1, 2 作為參數傳給這個 function 即可。

你如果想要惡搞 +, 把 + 對應到 - procedure, 就可以得到 (+ 1 2) = -1 的奇怪結果。

(define aa 5) 會把變數 aa 對應到 5, 因為這個 define 是在 global environment, 所以 aa 會被加入到 global enviroment。有了環境之後, 應該也可以實作 define 了, 不過 define 比你想像得還要複雜。

下次再談 define, 不過要談 define 得先談 lambda。

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 執行。

sicp metacircular evaluator (1) - read procedure

有些朋友說我的 blog 都是滿滿的組合語言, 那不是刻意為之的, 組合語言之前沒有秘密, 得把這樣的程式碼挖出來才能理解一些東西。

不過我這陣子換口味了, 滿滿的小括號應該會充斥版面一段時間。

sicp 4.1 要寫一個 Metacircular Evaluator, 簡單說就是用 lisp 來寫一個 lisp, 用到一個 read primitive procedure, 可以當成是內建的 procedure, 這是用來讀取鍵盤輸入的資料。我花了一陣子才搞懂。

r_t.scm

 1 (define (handle_read exp)
 2   (display (car exp))
 3   (newline)
 4   (display (cdr exp))
 5   (newline)
 6   )
 7 
 8 (define (aa)
 9   (newline)
10   (display "aaa")
11   (newline)
12   (handle_read (read))
13   (newline)
14   (display "bbb")
15   (newline)
16   'ok)
17 
18 (aa)

read 回傳的值就當成 handle_read 的 exp 參數內容。

執行結果:

result

 1 
 2 ad "r_t.scm")
 3 
 4 ;Loading "r_t.scm"...
 5 aaa
 6 ('a)
 7 (quote a)
 8 ()
 9 
10 bbb
11 ;... done
12 ;Value: ok
13 
14 1 ]=> (load "r_t.scm")
15 
16 ;Loading "r_t.scm"...
17 aaa
18 'z
19 quote
20 (z)
21 
22 bbb
23 ;... done
24 ;Value: ok
25 
26 1 ]=> 
27 
28 
29 (load "r_t.scm")
30 
31 ;Loading "r_t.scm"...
32 aaa
33 (+ 1 2 3)
34 +
35 (1 2 3)
36 
37 bbb
38 ;... done
39 ;Value: ok
40 
41 1 ]=> 

L6 輸入 ('a), read 回傳一個 list 包含 'a 和 ()。 
L18 輸入 'Z, read 回傳一個 list 包含 quote 和 Z。
L33, 輸入 (+ 1 2 3) read 會傳回一個 list 包含了 + 這個 symbol, 還有 1, 2, 3。

sicp metacircular evaluator (0) - map/car/cdr

sicp 4.1 要寫一個 Metacircular Evaluator, 有個部份在處理 environment。把 car, cdr, +, - 這些 primitive procedure 定義在這環境裡, 是很重要的一步。不過 scheme cons pair 資料結構實在難倒我, 把這些部份獨立出來測試。

t1.scm

 1 (define primitive-procedures
 2   (list (list '- -)
 3         (list '+ +)
 4         (list 'car car)
 5         (list 'cdr cdr)
 6         (list 'cons cons)
 7         (list 'null? null?) 
 8         ))
 9 (display primitive-procedures)
10 (newline)
11 (display (car primitive-procedures))
12 (newline)
13 (display (map car primitive-procedures))
14 (newline)

t1.scm L13 是最主要的部份, 結果是 res L5, 把 symbol -, + , car, cdr, cons, null? 集合成一個 list。

res

1 1 ]=> (load "t1.scm")
2 
3 ;Loading "t1.scm"...((- #[arity-dispatched-procedure 11]) (+ #[arity-dispatched-procedure 12]) (car #[compiled-procedure 19 (list #x1) #xf #x3218d3]) (cdr #[compiled-procedure 14 (list #x2) #xf #x321917]) (cons #[compiled-procedure 16 (list #x3) #xc #x32195c]) (null? #[compiled-procedure 18 (list #x5) #xc #x3219b8]))
4 (- #[arity-dispatched-procedure 11])
5 (- + car cdr cons null?)
6 ;... done
7 ;Unspecified return value
8 
9 1 ]=> 

t2.scm 這個複雜一點, res2 L23 是要達成的效果。

t2.scm

 1 (define primitive-procedures
 2   (list (list '- -)
 3         (list '+ +)
 4         (list 'car car)
 5         ))
 6 
 7 
 8 (define (primitive-procedure-objects)
 9   (map (lambda (proc) (newline) (display proc) (newline) (newline) (display (cdr proc)) (newline)  (newline) (display (cadr proc)) (newline) (list 'primitive (cadr proc)))
10        primitive-procedures))
11 
12 (newline)
13 (display primitive-procedures)
14 (newline)
15 (display (primitive-procedure-objects))
16 (newline)

res2 L4 的 list 由 t2.scm L1~5 構成。L9 的 map 難倒我, proc 可以想成 res2 L4 的 list 裡頭的 list, 就是 L6, L12, L18, 把他們 cdr 後, 就變成 L8, L14, L20, 再 car 後, 就是 L10, L16, L22, 因為 (a) 其實是用 'a, nil 構成的 pair, car 取前面 ('a), cdr 取後面 (nil)。

res2

 1 1 ]=> (load "t2.scm")
 2 
 3 ;Loading "t2.scm"...
 4 ((- #[arity-dispatched-procedure 11]) (+ #[arity-dispatched-procedure 12]) (car #[compiled-procedure 13 (list #x1) #xf #x3218d3]))
 5 
 6 (- #[arity-dispatched-procedure 11])
 7 
 8 (#[arity-dispatched-procedure 11])
 9 
10 #[arity-dispatched-procedure 11]
11 
12 (+ #[arity-dispatched-procedure 12])
13 
14 (#[arity-dispatched-procedure 12])
15 
16 #[arity-dispatched-procedure 12]
17 
18 (car #[compiled-procedure 13 (list #x1) #xf #x3218d3])
19 
20 (#[compiled-procedure 13 (list #x1) #xf #x3218d3])
21 
22 #[compiled-procedure 13 (list #x1) #xf #x3218d3]
23 ((primitive #[arity-dispatched-procedure 11]) (primitive #[arity-dispatched-procedure 12]) (primitive #[compiled-procedure 13 (list #x1) #xf #x3218d3]))
24 ;... done
25 ;Unspecified return value
26 
27 1 ]=>