由於 scheme 語法很簡單 (對比 c 語法之流), 給了我信心, 我深信我一定做的出來, 但這只是錯覺, 寫 compiler/interpreter 真的比較難, 是有他的道理的。
c++ 的版本比我想得還難, 我一下子就遇到 scanner 的困難, 沒想到我特地找了 s-expression 來練習, 還是無法實作 scanner, s-expression 已經算是很簡單的了。
把 (+ 1 2) 變成
( + 1 2 )
產生這樣的 token list 不難, 難的是怎麼把它變成 scheme 的 list 資料結構。
ex: (+ ( * 2 3) 1) => + * 2 3 1
而 car + * 2 3 1
得到 +
(car (cdr + * 2 3 1) )
要得到 * 2 3
這樣的資料結構。
ref:
https://github.com/descent/simple_scheme/blob/master/s_eval.cpp
Cell *read(TC &tokens)
這裡需要用到 recursive 的觀念, 並不是很好想。
sicp 4.1 的實作並沒有以 BNF 的形式來處理, 似乎不需要用 BNF 的方式, 直接就可以寫出整個 parser, 沒有符號表, 沒有 AST, 當然那個 recursive 一樣很複雜。
(How to Write a (Lisp) Interpreter (in Python)) 內文給我了一些提示, 真難得有繁體中文翻譯: http://reborn2266.blogspot.tw/2011/11/how-to-write-lisp-interpreter-in-python.html
可惜的是我還不夠聰明到可以用 python code 推出 c++ 的版本, 直到 Lisp interpreter in 90 lines of C++ 這篇文章的 source code 一舉為我解除疑惑。
除了幫我解決 scanner 的疑惑外, 還幫我解決了 Cell 這個資料結構的問題, 我想了好幾天, 總是卡在某個地方無法突破。不過最後我重新改寫成較類似 scheme cons 的 pair, 不需要使用 std::list, c++ 標準程式庫的東西我得慢慢移掉才行, 這次的改寫讓我一次完成兩個功能; std::map 則是我下階段要移掉的東西。
完成一個 interpreter 並沒有想像中的容易, 光是最簡單的計算機, 就得使用上編譯器教科書上的理論, 否則應該是很難寫出來, 如果你靠自己克服了這難題, 想必你一定是個聰明的傢伙。
UNIX 编程环境 (Brian W.Kernighan, Rob Pike) 第八章在談一個計算機怎麼寫, 其中使用了 lex, yacc。
Stroustrup Programming: Principles and Practice using C++ (這本有 Second Edition, 談及 c++11, c++14) 6, 7 章也在談怎麼寫一個計算機, 沒有使用 lex/yacc。C++ 程序设计原理与实践 (Programming: Principles and Practice using C++ 的簡體中文版本 - 第一版) p 109 提到: 「這是 50 年來的經驗, 想要一夜打破 50 年來的經驗不是個好主意。」
1+2*3 也許很難處理, 我本來以為 (+ 1 (* 2 3)) 會好一點, 是好一點, 不過依然不是件簡單的事情。
一開始的目的就只打算完成四則運算, (+ 1 2 3), (+ (* 2 3) 6) 之類的, 沒想到也花了好大一番功夫才搞定。
這是兩階段的學習, 我先把 scheme 的實作版搞懂, 才來實作 c++ 版本的四則運算。
https://github.com/descent/simple_scheme
tag three_op
在 branch origin/new_cell 我重新實作了 Cell, 使用 Cell *get_cell(const char *val, ProcType proc) 來從 array 得到一個 Cell, 而不是用 malloc/new 來得到一個 Cell, 這是為什麼呢? 容我賣個關子, 若你大概看了這個版本, 應該會覺得這是個很像 c 的 c++ 程式, 事實上, 這是刻意的, 因為我不想使用太多 c++ 的特性, 怕到時候會有問題。
在這個版本之後, 我有了 cdr, car, cons 可以用, 後來的程式碼幾乎就是把 sicp 的 code 抄過來。為什麼要改寫 struct Cell? 因為我被 car, cdr 整個搞亂了, 套用原來的 Cell 結構, 我很難做到 car, cdr 的功能, 老是把 car, cdr 的結果搞錯, 我並沒有完全使用 Lisp interpreter in 90 lines of C++ 的程式碼, 我只需要 scanner 和 Cell 這部份, 打通之後就可以繼續下去; 新的 Cell 幾乎大量使用指標操作, 沒有 std::list, 整個速度應該提升不少。
再來的困難是環境, 有點複雜, 和 sicp metacircular evaluator 的實作不同, 我有 std::map 可以用, 實作環境輕鬆多了。
lambda 的實作我認為最困難, 只要過了這關, 後面的 define, if, cond, set!, begin 根本就是照抄 sicp 的 code。
我就是照著 sicp metacircular evaluator 這系列, 一步步完成 c++ 版本。其中花了不少精神, 總算小有所成。
這個程式在 linux 平台開發/測試, 再來的版本就有點挑戰性, 我滿懷能量, 準備完成它, 這是個集我所學大成的計劃, 取名為作業系統之前的 scheme。
後來在開發了《simple c++ 標準程式庫》後, 我總共有了
- linux
- bare-metal rpi2
- bare-metal stm32f407
- bare-metal p103 模擬器
- x86 16bit mode bare-metal
- x86 16bit mode ms dos
- uefi
 |
| uefi scheme |
這是其他人開發的 c++ 版本:
http://www.open-open.com/lib/view/open1352593340668.html
其 soure code:
https://github.com/zoowii/SchemeRuntime
我的版本:
https://github.com/descent/simple_scheme
ref:
沒有留言:
張貼留言
使用 google 的 reCAPTCHA 驗證碼, 總算可以輕鬆留言了。
我實在受不了 spam 了, 又不想讓大家的眼睛花掉, 只好放棄匿名留言。這是沒辦法中的辦法了。留言的朋友需要有 google 帳號。