V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
爱意满满的作品展示区。
geelaw
V2EX  ›  分享创造

做了个极简的 λ 演算(lambda calculus)的解释器

  •  1
     
  •   geelaw ·
    GeeLaw · 2018-02-18 16:06:27 +08:00 · 2727 次点击
    这是一个创建于 2231 天前的主题,其中的信息可能已经有所发展或是发生改变。

    前情提要:/t/430679

    自从上次以来,修复了一些 bug 并重构了代码,为实现 规范顺序归约、记忆化懒惰求值 做准备。实现了 η-变换和 β-归约,并完成了一个简单的 interactive interpreter。实现这个版本的 β-规约的方法论是三步,每一步都很自然:

    1. 在做 β-归约时,把所有要替换的绑定变量替换为被替换的东西,并且共享对象引用(这样下次 β-归约这个被替换对象的时候,就可以一下子归约很多地方,提高效率);
    2. 在 β-归约 (λx. M) N 的时候,语法树里面的 M 需要被 深复制 才能替换 x 为 N,这是因为前面一个方法导致的(或是因为一些子项来自常数表导致的)共享对象会导致 M 可能和 N 共享一些引用,如果不深复制(比如,原地修改),可能会意外改变 N 里面的东西,更惨的是可能改变这个子项之外的东西;
    3. 要确保一次 β-归约被最佳利用,需要在 (λx. M) N 被归约后把所有 (λx. M) N 的引用都替换为归约结果。

    你可以查看我的 blog 原文

    还可以从这个 GitHub 仓库 访问代码,现已按 MIT License 提供授权。


    效果图

    2 条回复    2018-02-19 03:20:10 +08:00
    cholerae
        1
    cholerae  
       2018-02-18 22:12:52 +08:00 via iPad
    呃,没必要更新一次发个帖子吧
    geelaw
        2
    geelaw  
    OP
       2018-02-19 03:20:10 +08:00
    @cholerae 并不是更新一次发一个帖子 - - 这是一篇新的 blog entry 了。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   5376 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 32ms · UTC 08:31 · PVG 16:31 · LAX 01:31 · JFK 04:31
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.