Pyrolog 作者回顾项目诞生20年
来源标题:20 Years of Pyrolog
RPython 实现的 Prolog 项目 Pyrolog 于 2006 年 11 月 12 日完成首次提交,如今已满 20 年。作者发文回顾称,Pyrolog 从未拥有真实用户,但推动了相关研究,并影响了多个 RPython 项目,包括 2008 至 2009 年的 JIT 开发以及 2022 至 2024 年的 Effekt RPython 实现。
以下正文由 AI 翻译自 Hacker News 最新(原文版权归原站所有),可能存在偏差,重要内容请以原文为准。
2006年11月12日,我将自己基于RPython的Prolog实现Pyrolog的第一次留存至今的提交记录放进了PyPy仓库。其实从2006年春天起我就已经在做这个项目了。那一年我们正在收尾第一个PyPy欧盟研究项目,而我也在杜塞尔多夫大学完成本科学业。如今20年过去了,我想写一篇关于这个项目的个人回顾。Pyrolog从未有过真正的用户,但它仍然催生了一些有趣的研究,并影响了不少其他RPython项目。
2008/2009年 PyPy一侧的JIT开发 2009-2010年 Pyrolog新架构:更多续延 2022-2024年 Effekt的RPython实现
作为欧盟项目的一部分,我们承诺了很多事情,包括在PyPy中实现某种约束编程。为了这条工作线,我通过阅读Clocksin和Mellish的《Programming Prolog》[CM2003],以及后来的《The Art of Prolog》[SS1994]来学习Prolog。
2006年3月,PyPy项目合作伙伴Logilab在比利时新鲁汶的UCLouvain组织了一次sprint,Peter van Roy和一些研究Gecode的研究人员也参加了。计划是给PyPy加上某种合一(unification)和约束求解能力。Logilab的人深受Van Roy/Haridi那本书[VH2004]的启发,我后来也研究了他的Prolog实现综述论文[VanRoy1994]。
2006年我还旁听了导师Michael Leuschel在杜塞尔多夫开设的Prolog课程。在此期间,我开始用RPython编写一个Prolog解释器,后来它被称为Pyrolog。遗憾的是,早期提交历史大部分已经丢失——它没能正确地随Subversion到Mercurial的迁移保留下来,我也不知道codespeak的存档现在在哪里。
Pyrolog的第一个版本用面向对象的RPython代码相当直接地实现了合一。逻辑变量存储一个索引,其绑定则存放在该索引对应的全局数组中。
那个版本在解释器层面通过异常处理器来表示选择点,回溯则通过抛出异常、在上层捕获来实现。它采用基于续延的架构来存储剩余待执行的调用。这些成功续延存放在堆上,不断被分配和消耗。这种做法取自Paul Tarau的BinProlog([TB1990]、[Tarau1992]),也基于其他一些Prolog论文[Lindgren1994] [Neumerkel1995]。
为了应对Prolog程序典型的深递归,那个版本的Pyrolog依赖RPython的stackless变换[BR2007D071]:当宿主栈(即C栈)即将溢出时,它会展开宿主栈,把信息存到宿主堆上。以这种方式把C栈帧存到堆上时,我们还做了一定程度的尾调用优化。当时我们对这个想法极其热衷。然而事实证明它不太实用,会让二进制文件大一倍、速度变慢,所以最终我们又把它移除了。
我还在那个版本的Pyrolog上试验了第一个RPython JIT。那个JIT是基于部分求值的方法JIT,成功加速了一些小型Python程序。不过我觉得它对Pyrolog帮助不大。
那个版本Pyrolog的性能相当令人失望。在我的本科论文[Bolz2007]中,我与SWI和Sicstus Prolog做了一些对比测量。此时Sicstus常常比Pyrolog快一个数量级。在论文中我还实现了一种从Python代码调用Prolog的方式,并做了一个案例研究:用Python实现井字棋GUI,游戏逻辑则用Prolog实现。
完成论文后不久,我改变了变量的表示方式:不再索引到全局绑定数组,而是让每个变量对象存储自己的绑定。基于异常的回溯架构又保留了两年。
欧盟项目结束后,我们开始为RPython元JIT探索各种新的架构想法。Armin Rigo、我以及其他一些人写了两个新原型。我们对它们不满意,于是2008年Armin和我开始试验一个用Prolog编写的新trace-based JIT原型。我们用Prolog,是因为它的模式匹配和元编程的便利性让我们更容易试验不同的设计。
2008年底到整个2009年,Armin、Maciej Fijałkowski、我以及其他一些人开始把该设计移植回RPython,并称之为pyjitpl5(名字中的“pl”代表“Prolog”)。这仍然是当前PyPy元JIT编译器的基础,并成为Eurostars计划中第二个(较小的)PyPy欧盟项目的主题。
我们最终在LOPSTR 2009上发表了关于JIT的Prolog版本的论文[BLR2010]。
2008和2009年主要忙于PyPy和新JIT之后,我在2009年圣诞假期期间重新开始做Pyrolog。由于stackless变换与新JIT不兼容,我不得不切换到另一种架构,这种架构至今仍在使用。Pyrolog架构的第一个版本已经把成功续延存放在堆上。这次重构的目标是把失败续延也具体化为RPython对象。
简化后的主解释器循环
def interpret(sc, fc, trail): while not sc.is_done(): try: sc, fc, trail = sc.activate(fc, trail) except UnificationFailed: sc, fc, trail = fc.fail(trail)
这样做的效果是:解释Prolog调用时,宿主栈的使用完全是平的。继续执行Prolog所需的状态始终存储在堆上的续延对象中。因此解释器要处理两个续延:一个在成功时激活,一个在失败时激活。此外还有一个(分段的)trail对象,存储回溯时需要撤销的变量绑定。失败续延在被激活时,会持有对它需要回溯到的trail部分的引用。
这种方法的缺点在于,解释器必须持续地
(原文较长,此处译出前 6000 字,完整内容请点「打开原文」。)
正文由 探How 从来源站点 RSS 同步,内容未经改写;遇到排版缺失或需要图片、视频时请以原文为准。