看完 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://webptt.com/cn.aspx?n=bbs/PLT/M.1422245376.A.274.html