[心得] scheme interpreter by c++

看板PLT (程式語言與理論)作者descent (「雄辯是銀，沉默是金」)時間9年前 (2015/01/26 12:09)推噓2(2推 0噓 2→)

留言4則, 4人參與討論串1/1

看完 sicp 4.1 時, 真是興奮, 原來 scheme interpreter 就是這樣完成的, 我辛苦搞懂了 scheme 的程式碼, 想用 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 car + * 2 3 1 要得到 * 2 3 這樣的資料結構。 (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++ ( http://goo.gl/ZMxcE6 ) 這篇文章的 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 ( http://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/ZMxcE6 ) 的程式碼 , 我只需要 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 )。這是其他人開發的 c++ 版本: http://www.open-open.com/lib/view/open1352593340668.html ( http://goo.gl/MsrYVC ) 其 soure code: https://github.com/zoowii/SchemeRuntime ( http://goo.gl/NQE6G3 ) 我的版本: https://github.com/descent/simple_scheme ( http://goo.gl/tiMXwi ) 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 網址: http://descent-incoming.blogspot.tw/2014/10/scheme-interpreter-by-c.html -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 36.236.199.19 ※ 文章網址: https://www.ptt.cc/bbs/PLT/M.1422245376.A.274.html