看完 sicp 4.1 時, 真是興奮, 原來 scheme interpreter 就是這樣完成的, 我辛苦搞懂
了 scheme 的程式碼 (我整理了一系列看懂 sicp 4.1 的
《心得 ( http://goo.gl/X1btQ4 )》), 想用 c/c++ 實作一個簡單版本,
畢竟 c++ 一直以來是我很喜歡的語言。
由於 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 (
https://goo.gl/tiMXwi/blob/master/s_eval.cpp )
Cell *read(TC &tokens)
這裡需要用到 recursive 的觀念, 並不是很好想。
sicp 4.1 的實作並沒有以 BNF 的形式來處理, 似乎不需要用 BNF 的方式, 直接就可以
寫出整個 parser, 沒有符號表, 沒有 AST, 當然那個 recursive 一樣很複雜。
http://reborn2266.blogspot.tw/2011/11/how-to-write-lisp-interpreter-in-python.html
( http://goo.gl/vDz2Y7 )
可惜的是我還不夠聰明到可以用 python code 推出 c++ 的版本, 直到 Lisp
interpreter in 90 lines of C++ ( http://goo.gl/3RCUi4 ) 這篇文章的
source code 一舉為我解除疑惑。
除了幫我解決 scanner 的疑惑外, 還幫我解決了 Cell 這個資料結構的問題, 我想了好
幾天, 總是卡在某個地方無法突破。不過最後我重新改寫成較類似 scheme cons 的
pair, 不需要使用 std::list, c++ 標準程式庫的東西我得慢慢移掉才行, 這次的改寫讓
我一次完成兩個功能; std::map 則是我下階段要移掉的東西。
完成一個 interpreter 並沒有想像中的容易, 光是最簡單的計算機, 就得使用上編譯器
教科書上的理論, 否則應該是很難寫出來, 如果你靠自己克服了這難題, 想必你一定是個
聰明的傢伙。
UNIX 程境 (Brian W.Kernighan, Rob Pike) ( http://goo.gl/1SYqG0 ) 第八章在談一
個計算機怎麼寫, 其中使用了 lex, yacc。
Stroustrup Programming: Principles and Practice using C++ (
http://goo.gl/qlSwj ) (這本有 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 ( https://goo.gl/tiMXwi )
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++ ( http://goo.gl/3RCUi4 ) 的程式碼
, 我只需要 scanner 和 Cell 這部份, 打通之後就可以繼續下去; 新的 Cell 幾乎大量
使用指標操作, 沒有 std::list, 整個速度應該提升不少。
再來的困難是環境, 有點複雜, 和 sicp metacircular evaluator 的實作不同, 我有
std::map 可以用, 實作環境輕鬆多了。
lambda 的實作我認為最困難, 只要過了這關, 後面的 define, if, cond, set!, begin
根本就是照抄 sicp 的 code。
我就是照著 sicp metacircular evaluator ( http://goo.gl/X1btQ4 ) 這系列, 一步步
完成 c++ 版本。其中花了不少精神, 總算小有所成。
這個程式在 linux 平台開發/測試, 再來的版本就有點挑戰性, 我滿懷能量, 準備完成它
, 這是個集我所學大成的計劃, 取名為作業系統之前的
scheme ( http://goo.gl/UcDFYz )。
後來在開發了《simple c++ 標準程式庫 ( http://goo.gl/xKIag7 )》後,
我總共有了:
linux
bare-metal rpi2
bare-metal stm32f407
bare-metal p103 模擬器
x86 16bit mode bare-metal ( http://goo.gl/ldsvE2 )
x86 16bit mode ms dos
uefi
這麼多的實作版本。
( https://goo.gl/01E06B )
uefi scheme
這是其他人開發的 c++ 版本:
http://www.open-open.com/lib/view/open1352593340668.html
( http://goo.gl/MsrYVC )
其 soure code:
https://github.com/zoowii/SchemeRuntime ( https://goo.gl/NQE6G3 )
我的版本:
https://github.com/descent/simple_scheme
這應該是地表最慢的 scheme 實作了, 沾了地表的光, 真不好意思。
ref:
Scheme from Scratch - Introduction ( http://goo.gl/fWbq3y )
Write a Scheme Interpreter in Ruby(2): THE Interpreter ( http://goo.gl/rX19PB
)
// 本文使用 Blog2BBS 自動將Blog文章轉成縮址的BBS純文字 http://goo.gl/TZ4E17 //
blog version:
http://descent-incoming.blogspot.tw/2014/10/scheme-interpreter-by-c.html