compiler [4] 環境與變數 => 環境變數

日拱一卒，功不唐捐

20161219 重要: 本篇文章有個錯誤, 感謝 fb Jensen Holder 指出, 我放在最後補充。

變數就是字面上的意思, 寫程式的都知道, 但知道 interpreter 怎麼把這功能做出來的程式員可能就不多了。

list 1

 1 x=1;
 2 x+5;

list 1 L2 怎麼把 x, 1 做個對應的呢? 就是靠《環境》, 他不是什麼神祕的東西, 用 c++ 來說明什麼是環境的話就是:

std::map<std::string, ASTNode *> env;

然後把 env["x"]=1 就完成 x=1 這個運算式。

不管你用什麼資料結構, 反正就是把 x 和 1 的關係存起來就對了。感覺很簡單, 但真實世界上可沒這麼簡單, 不過教學就是要化繁為簡, 先知道這樣就夠了。

再來的 list 1 L2 在 x+5 要做 eval 時, eval 5 就回傳 5 ASTNode 本身, x 就到 env 去把他對應的數字找出來, 也就是 1， 所以傳回 1 的 ASTNode, 然後 + 就可以把 1, 5 作相加的運算, 6 就這麼算出來了。

那《環境》困難在哪裡呢? 在 function call。

p1

 1 int x;
 2 int f1()
 3 {
 4   2*3;
 5   12+13;
 6 }
 7
 8 int f2(int i)
 9 {
 9.5 int cc;
10   5*i;
11 }
12 int main()
13 {
14   int z;
15   61+2;
16   z=5;
17   f1();
18   f2(z);
19 }

如果像 p1 這樣, 掃描到 L1 時, 把 x 加入 global_env (table 1), 在 call main 時, 要產生 main_env (table 2), main_env 的上層 up_env 要指到 global_env, 當掃描到 L 14 時, 把 x:0 加入到 main_env, 而掃描到 L 16 時, 把 5 的值至換到 z (table 3), 在 call f2(z) 時 (L 18), 又要產生 f2_env (table 4), 再把 up_env 指到 main_env, 並把 z/i 的對應存到 f2_env, cc 的對應也要存到 f2_env, 疑, cc 沒對應的值阿, 隨便塞一個就好了, 這不就是 c 語言 auto 變數的行為嗎? 而上層 env 要指到 main_env, 這樣層層下去, 讓整個環境建立起所有的變數名稱/變數值的對應關係。大概像 env class 那樣。

table 1. global_env

up_env	0
x	0

table 2. main_env

up_env	global_env
z	0

table 3 main_env

up_env	global_env
z	5

table 4. f2_env

up_env	main_env
i	z
cc	0

所以在 f2() 裡頭用到 cc, i 時, 就去查 f2_env, 把對應的值找出來, 就可以知道這個變數的值, 而在這層找不到, 就要去 up_env 找, 都找不到就發出錯誤訊息。

env class

14 class Environment
15 {
16   public:
17     Environment(Environment *outer=0, const char *name=0): outer_(outer)
18     {
21     }
22     Environment *outer_;
31     int free_frame_index_;
32   private:
33     std::map<std::string, ASTNode *> frame_;
34 };

觀念很簡單, 但實作還是會困難一點, 可參考以下範例程式碼。以下程式碼只有實作最簡單的環境, 我還沒完成 function call 那複雜的環境。目前的版本我已經完成了 function call 和 return, 真是有種覺得自己很不簡單的感覺呢! 你一定也很想要有這種成就感吧! 加油。

source code:
https://github.com/descent/simple_compiler
commit: 0452c23b770dad99b1d503e0f417cae45879ce72

除了加入變數, 函式的定義也一樣要加入環境, 當呼叫一個函式時, 就到環境來找這個函式, 找到後把 parameter, argument 配對後, 就去執行該函式了。

至於函式的傳回值, 那又是另外一件事情了。

因為使用了「環境」來處理「變數」, 這便是「環境變數」名稱的由來。

打通整個 interpreter 流程並不容易, 當我滿懷好奇心將所有疑問抽絲剝繭, 最後接觸到本質的那一刻, 我知道這些努力與堅持是值得的, 縱使我無法因為這樣而在工作上有立即的幫助, 但滿足自己的好奇心就是驅使我這麼做的最大動力。

html table from:
http://htmleditor.i2yes.com/

---

fb Jensen Holder

所以是 interpreter 還是 compiler 啊?
interpreter 的話通常是用 denoted value, 不是 AST Node
compiler 的話這應該是靜態決定的不是動態的東西吧
而常說的 symbol table 是另外一個東西

你的 env 處理有點奇怪, 這個行為看起來比較像 call stack

f2 查看 cc, i 的行為應該是在 f2_env 裡面查詢, 查不到去 global 找, 而不是從 call stack 找上去

fb Jensen Holder

這有點難避開數學或程式用純文字解釋, 但是大概有兩個部分 (1) 程式提到的變數到底是哪一個變數 (2) 程式提到的變數在 runtime 中到底放在記憶體的哪裡. (1) 的話, 若我們是 lexical scoping, 哪些 variable references 是指同一個 variable 是看他們寫在哪就知道, 這個不用執行程式也可以事先算出來. (2) 就是我們平常看到的即使同一個函式被呼叫兩次, 不同次的呼叫對應的是不同實體, 所以變數的值不會互相干涉

https://gist.github.com/shhyou/1b7afff0b8b470d9a531f56480165a51#file-variable-md

以這個程式為例, L06 跟 L13 的 x 指的是 L01 的 x, L05 L06 的 i 是 L03 的 i, 而 L10 L11 的 x 是 L09 的 x; L14 是錯誤的, scope 當中沒有 argc. 這是 "(1)" 的 "哪個變數到底是指哪個變數?".

執行時, 實作可以是這樣: 每次呼叫 f, 我們都會配個嶄新的記憶體給 i 跟 cc 跟 cc 跟 x. 而後面 reference 到 i, cc, x 時, 依照上一段所述已知哪個 variable reference 指哪個變數, 再去操作該變數對應的記憶體.

https://gist.github.com/shhyou/1b7afff0b8b470d9a531f56480165a51#file-intc-cpp

這是一個範例的轉換程式, 把 prog 轉成 prog2. prog2 當中, 變數都是 local_id 或 global_id, 執行時, 每次呼叫函數就直接建立新的 stack frame 就好, local 就存取該 stack frame, global 就存取 heap

事先計算哪個變數是哪個變數只是一種寫法, 直接邊跑邊更新 environment 也是可以, 不過比較複雜. 至於函數式語言直譯器範例的那種 environment 一個 linked-list 往上搜尋其實是另外一回事. 那是實作 lexical scoping 語意的一個方便寫法. 如果仔細觀察, 可以發現那種寫法在函數呼叫時, 實際上是 extend 函數建立時就保存起來的 environment (也就是 closure). 乍看之下雖然是一個鏈, 但實際上是一棵樹. 此外, 這種 environment 是不支援 mutation 的. 如果要 mutation 就是要有另外一個 global store, environment 中紀錄 address, 再到 store[address] 中去存取或修改值.