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。