看完 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