V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
kcworms
V2EX  ›  Lisp

又一个玩具 Scheme 解释器,使用 Python 编写

  •  
  •   kcworms · 2015-03-14 21:49:40 +08:00 · 5830 次点击
    这是一个创建于 3301 天前的主题,其中的信息可能已经有所发展或是发生改变。

    其实在本站搜索可以找到已经有人写过了(顺便里面提到的lispy非常值得参考),这个的功能绝对没有希望……不过这个应该有一些特别的地方:

    • 与SICP第四章4.1.5节之前做的元循环求值器对应,但是使用了OO风格(基本就是照着书抄代码,又轻松又快乐……使用了OO,有点类似前几章提到的消息传递风格)
    • 暂时不到500行(不包括空行,注释,测试)
    • 这种玩法真的比做无聊的习题好玩得多

    现在的状况是可以运行练习2.42(八皇后谜题的那个)的代码,但是参数设成5就会突破Py递归深度上限。除法和浮点数都不能用!

    这个项目应该可以完成第四章的使命,等做到4.1.7节分离语法分析与求值过程之后顺便加一下尾递归优化应该可以把上面的问题解决……

    Repo

    第 1 条附言  ·  2015-03-16 19:51:41 +08:00
    4.1.7节的优化已经弄好了。令人感动的是原来能解(queen-louis 5),现在只能解4了。虽然速度是快了很多,果然eval本身还要改成迭代
    第 2 条附言  ·  2015-03-21 23:07:35 +08:00
    在寻找修改eval的方法中偶然发现伯克利的SICP课程也用这种玩法……
    https://inst.eecs.berkeley.edu/~cs61a/fa12/
    第 3 条附言  ·  2015-03-24 20:18:16 +08:00
    加上了两个对于玩具来说比较强大的功能:
    尾递归优化(只消除尾递归,而不是所有tail-call)
    递归无上限,直到用完内存
    假冒的traceback

    不科学的性能比较:
    八皇后习题中queens过程,用时是Racket的100倍
    递归定义的阶乘过程,用时是Racket的2倍(真不科学)
    第 4 条附言  ·  2015-07-02 10:51:04 +08:00
    应该是最后一次更新了:
    加入call/cc
    去掉了假冒的traceback,并优化所有tail-call
    继续补充基本过程

    结果是可以运行原来书上的那个元循环解释器了。对于call/cc至少维基百科页面里的generator例子是可以运行的。

    最后是令人悲伤的性能:
    对于(queen 8),Racket用了0.6秒。TSI在加上PyPy魔法之后用的时间居然是前者的30倍
    目前尚无回复
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   5476 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 33ms · UTC 08:54 · PVG 16:54 · LAX 01:54 · JFK 04:54
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.