實作麻雀雖小五臟俱全的程式語言

故事是這樣子的，很早以前曾經看過 understanding computation 這本書，這本書第二章的內容，是利用操作語義（operational semantic）的方式，自訂一款極簡程式語言，非常簡單但已經有 if 判斷式，while 迴圈等功能。
最近剛修完 coursera 上面的 programming language，其中有一個作業也是用 racket 的操作語義定義一款程式語言， 這個程式語言更複雜，在資料結構上支援 pair -> list，同時還支援函式，這是之前 Understanding Computation 沒有實做的部分。
花了幾天的時間，把過去的 code 擴展了一些，在那上面實作了函式，在這裡就簡單介紹一下相關的內容，還有一些個人的心得，心得內容可能有對有錯，如果有錯就請路過野生的大大們指教一下：
要看到原本的內容，可以參考之前發在這個 blog 的筆記，還有 Github 上面的原始碼。
https://yodalee.blogspot.com/2016/03/rust-recursive-structure.html
https://github.com/yodalee/computationbook-rust/tree/master/src/the_meaning_of_programs/simple
本次修改的程式碼則可見：
https://github.com/yodalee/simplelang

所謂操作語義，就是明白的定義程式的各指令實際執行起來是如何，實際執行的機器當然是一台虛擬機，模擬執行的過程。原本書裡面有兩種操作語義的方式，一種是小步 reduce，每次將程式的內容變小一些些；一種則是直接 evaluate，有什麼結果直接計算出來。
要實作函式的部分，我把 reduce 的實作刪掉了，因為我實在不知道要怎麼用 reduce 實作函式，reduce 每次只會拿一個指令，然後把它縮小一些些，但在處理 function 上，只要進到 function 內部就要代換成另一個環境給它，步步執行的 reduce 做不到這點。
因為我的程式是來自於 Understanding Computation，所以裡面有些 code 像 while, sequence 是來自書中，其實我們有了 function ，就可以用 recursive 的方式取代 while，sequence 也可以適度修改，例如把 assign 變成如 let var = val in expression 的形式，在環境裡將一個值賦值給變數之後，以這個環境執行第二個 expression，就不需要 sequence 這樣的語法了；這部分大家自己知道就好。

看一個最簡單的例子：加法。
首先我們定義我們程式的單位：Node，要實作加法需要實作兩種 Node，代表數字和代表加法運算的 Node，接著我們就可以用 Node::number(100) 代表數字，用 Node::add(Node::nubmer(3), Node::number(4)) 代表加法；另外要實做一個 evaluate 函式，讀入一個 Node 並做出對應的操作，例如加法是分別把兩個參數都 evaluate 過，用 value 取值，用我們熟悉的加法加起來；其他運算如乘法、判斷用的大於、小於，都是類似的實作。

再深入一點要實作變數，例如 x = 10，就會需要環境 (environment.rs)，它是 evaluate 需要的參數，實作是一個簡單的 HashMap，將變數名稱映射到相對應的 Node 上面，注意是 Node 不是實際地址，在我們的實作下輸入地址都是虛擬化為 Node；如此一來就能定義 Variable 跟 Assign 兩種 Node，分別會從環境中拿出值和將某段程式賦予給某個變數 。

再來就是複雜一些的 Pair, List，先定義 pair 以及兩個輔助用的 fst, snd Node，一個 pair 其實就是把兩個程式組合在一起，之後可以用 fst 跟 snd 取出第一個和第二個的值。
在這裡我們偷懶一下，重複使用 donothing 這個 Node 來表示 list 的結尾，一個 list 即是表示為許多 pair 的嵌套，最後一個 pair 的第二個 Node 必須是 donothing。
使用 iter 搭配 fold 就能輕易將 rust 的 integer vec 轉成我們這個程式語言中的 integer list，從最後一個元素開始，一個一個用 pair 與上一次的結果組合起來。

pub fn vec_to_list(v: Vec) -> Box {
  v.iter().rev()
   .fold(Node::donothing(), |cdr, car| Node::pair(Node::number(*car), cdr))
}

結果：

pair (1, pair (2, pair (3, pair (4, pair (5, do-nothing)))))

這裡有個小小的心得是，程式和資料其實是不可分開的，當我們在組合程式的過程，定義一些特定的組合方式就能將程式轉為資料，反之亦然；雖然這是我偷懶的關係，但 DoNothing 可以是程式，表示不做任何事情，也可以是資料，用來表示 pair 的結尾；程式和資料其實是一體兩面，端視我們執行的時候怎麼處理它。

我們來看一下函數，我們創了三個相關的 Node：

• Fun：參數是一個 string 作為函數名稱，一個 string 作為變數名稱，還有一個 Node 是函式內部的程式碼。
• Closure： 我一直很好奇 closure 到底有沒有標準中文翻譯，看到有些翻譯稱為閉包，Closure 是執行時遇到 Func 產生的東西，包含函式內的程式碼，以及 evaluate Fun 時的環境。
• Call：以給定的參數傳給一個 Closure 並執行。

把 Fun 丟進 evaluate 會把當下的環境打包起來，生成一個 Closure；如果是 Closure 的話就不會特別做什麼。
Call 是最複雜的，它有下列幾個步驟：

1. 把 closure 跟參數 evaluate 過，如果拿到的不是closure 就會發生錯誤。
2. 將 closure 儲存的環境跟函式取出來。
3. 在這個環境中加上兩個新的變數：一個是函數名稱指向自己這個 closure，這樣在函式內 Call 自己的名字就能做到遞迴呼叫的效果； Fun 的參數名稱指向傳進來的變數值。
4. 用新的環境去 evaluate Fun 所帶的程式。

其實如果寫過 closure ，了解相關的概念之後，再去看下面這個 functionalC 的 repository 就滿好懂的了，如果要實作 Functional Programming 裡面的概念，函式都要自帶一個執行的環境，才能把函式像 first class member 一樣丟來丟去，由於 C 的函式並沒有強制要求這點，所以這一個 repository 裡面才會自己定義 closure 這個 struct ，基本上和我的定義一樣，都包含一個真正要執行的函式，還有執行的環境。

struct closure {
  void *(*fn)(list *);
  list *env;
};

再深入一點，假設程式一開始先設定 1000 個變數，然後再定義一個函式，這個函式要包含的環境是否需要這 1000 個變數？如果完整複製所有環境，太浪費空間了，實際上我們只需要記下函式中真正需要的變數即可，以下面這個函數為例子：

let x_add_y = Node::fun(
  "add1", "y",
  Node::add(Node::variable("x"), Node::variable("y")));

它接受一個參數 y 並將它和變數 x 相加 ，這時只要記錄 x ，其他變數都不需要保存，連變數 y 也不需要，因為 y 一定會在呼叫函式的時候被參數 y 給蓋掉（Shadow）。
變數 x 我們稱之為 free variable ，沒有被程式中的 assign 賦值或是以參數的方式掩蓋掉，它在執行時可視我們的環境設定自由變動。

我在 evaluate.rs 另外寫了一個 cal_free_vars 的函式來計算一段程式內的自由變數，它會生成兩個 HashSet 記錄出現過的變數跟自由變數，然後丟給 helper 函式處理。
大部分的處理方式都差不多，就是一路遞迴往下呼叫，像加法就是分別對兩個 Node 計算內部的自由變數；比較不一樣的是 Variable, Assign, Fun；在 Assign 跟 Fun 的地方，分別要把變數名稱、函數名稱跟參數名稱加到變數名單中，如果 Variable 取用的變數還沒在變數名單內，這個變數就是自由變數。
最後修改 evaluate Fun 的地方：

let free_vars = get_free_vars(self);
let mut new_env = Environment::new();
for var in free_vars {
  new_env.add(&var, env.get(&var));
}

用 get_free_vars 得到函式內的自由變數，生成一個新的環境，從現在的環境取得自由變數的值，用新的環境產生 closure；如果環境中沒有自由變數的值，環境的實作會直接崩潰，強制在執行函式的時候，環境中必須要有它的記錄。
以上大概就是一個有函式的程式語言會需要的實作，基本上這個語言能做到一些相當複雜的事，例如遞迴跟 currying 等，在 evaluate.rs 裡有一些相關的測試，例如階乘的遞迴實作：

fn test_simple_big_function_recursive() {
    let factor = Node::fun("factor", "x", Node::if_cond_else(
            Node::gt(Node::variable("x"), Node::number(1)),
            Node::multiply(Node::variable("x"),
              Node::call(Node::variable("factor"), 
              Node::subtract(Node::variable("x"), Node::number(1)))),
            Node::number(1)));
    let statement = Node::sequence(
        Node::assign("entry", factor),
        Node::assign("result", Node::call(Node::variable("entry"), Node::number(10)))
    );
    let mut env = Environment::new();
    println!("{}", statement.evaluate(&mut env));
    assert_eq!(3628800, env.get("result").value());
}

寫完這款程式語言，我開始覺得其實我是在寫個虛擬機，或者說有點像在實作一台電腦。
我們先把所有的資料：數值、真假值虛擬化為 Node 這個單位，一切的操作都是在 Node 上進行；就像真實的 CPU，也是將數字轉化為記憶體內部的 0, 1，在加法這個指令被執行的時候，會拿出記憶體的內容，通過一連串的邏輯閘變成輸出，再存回記憶體。 記憶體就好比我們的 Node，邏輯閘實作則是 evaluate，CPU 執行 x86 指令這款「語言」對應我們自訂的程式語言，只是CPU是真實的機器，我的程式是一台虛擬機 。
程式其實根基於數學，加法是一個概念，我們只是透過 CPU/電腦的實作，亦或是這篇文的操作語義，用虛擬機模擬出加法這個概念，所謂「程式語言」應是數學之神座下超凡的存在。 我們用上人類智慧的極致，打造 CPU，打造電腦，試著去追趕的這神聖的目標，追之求之，卻稱這款模倣的玩意兒為「程式語言」，何等自傲？想想不禁啞然失笑。