创建一个快速解释型语言

6

我正在创建一个使用Nim编写的编程语言。

编译器的前端已经完成,我现在正坐在一个良好构建的抽象语法树(AST)面前,并尝试实现一个简单的解释器,在每个树节点上调用evaluate()方法。这起初效果不错,我甚至为函数等创建了环境。但是,结果显示它比Python慢了大约15-20倍。Python运行在虚拟机上,并将源程序转换为字节码。其他语言使用JIT编译。这两种东西都不容易实现,但对我来说真正令人沮丧的是找不到任何一本书来教你如何将这两个世界合并在一起,要么是构建一个有用的单独VM,要么是构建一个编译语言。

像LLVM和GraalVM这样的工具可以帮助,但我仍然看不出如何将我的AST与这些工具链接起来。

我的下一步应该是什么?JIT / VM?

如果是VM:有没有推荐的方法将AST转换为字节码并为其创建VM?

如果是JIT:如何在动态语言中编译代码。例如

fun add(a, b) {
    return a + b;
}

解释器只有在运行时才知道a和b的类型,因此在找到它之前无法编译它。但是,如果将其编译为机器代码,则必须知道参数是什么,那么如果下一次调用使用不同的参数类型会发生什么?需要重新编译吗?
我对这个问题有点困惑,希望能得到解决。
提前感谢!

1
如果你的目标是与Python相媲美,那么在15-20%的范围内就足够接近了。在你决定转向更复杂的模型之前,你应该对解释器进行性能分析,并寻找一些简单的优化方法。 - 500 - Internal Server Error
我犯了一个错误。我的意思是慢15-20倍...我的错! - Erik Campobadal
哦,好的,那就不一样了 :) - 500 - Internal Server Error
3个回答

5
你希望能有一本书来描述如何构建超高性能的解释器。为了做到这一点,你需要将“解释器”和“编译器”混合使用以提高效率。为了做到这一点,简单的答案是,在书中使用所有编译器技巧(显然有很多书)。你需要大量阅读。
然而,你想要了解的核心内容可以在 SELF 的论文中找到,它是一个快速运行时“解释器”,在面对动态类型时定义了 JIT 编译器应该如何工作的规范:
《An efficient implementation of SELF a dynamically-typed object-oriented language based on prototypes》 (Chambers/Ungar),ACM Sigplan Notices。PDF 版本可以在此处找到: https://www.researchgate.net/profile/David_Ungar2/publication/234781317_An_Efficient_Implementation_of_Self_a_Dynamically-Typed_Object-Oriented_Language_Based_on_Prototypes/links/540f8fbe0cf2f2b29a3de0a6.pdf 通过访问 scholar.google.com 并搜索“JIT Compilers”和“Craig Chambers”的任何文章,可以找到更多有关此主题的技术论文。

0

如果您有兴趣在GraalVM上构建自己的语言解释器,请查看simple language,这是一个为了演示如何实现而构建的GraalVM样例编程语言。

简而言之,您需要使用Truffle来描述程序的AST,它是一个用于实现GraalVM编程语言的框架。它提供了一个API来描述AST中的节点及其所需执行的操作。

您可以在此处找到更多基于Truffle实现的编程语言示例。如果您对此有更详细的问题,也许gitter chat是最容易提问的地方。


你只能使用Java,无法编译本地实现,那怎么办? :C - Erik Campobadal
抱歉,我不明白你的意思,请详细说明一下。但是,以防万一,你完全可以在不依赖JVM的情况下运行你的语言实现。例如,TruffleRuby就是这样做的,你可以从https://github.com/oracle/truffleruby/releases下载“truffleruby-1.0.0-rc3-linux-amd64.tar.gz”版本。它可以正常运行带有JIT编译器的TruffleRuby,但不依赖于JVM。 - Oleg Šelajev
那我会去看一下的。我只是以为你只能使用GraalVM,而这个版本只有在Linux上才能免费使用。 - Erik Campobadal
Windows支持正在开发中(在JVM模式下可以工作,但本地镜像编译还没有),GraalVM CE版本的macOS构建尚未推出,因为缺乏我们可以使用的带有JVMCI的开源JDK8,至少应该在基于JDK11的构建版本中提供。 - Oleg Šelajev

0

虽然与直接相关性不大,但您可能会对研究RPython(“缩减”的Python)如何处理初始代码分析感兴趣。在生成流程图后,它严格验证变量的单一类型(尽管CPython是一种完全动态的语言,Pypy是用RPython编写的Python解释器,通过装箱支持完全动态性)。RPython还自然地集成了一个流程图级别的JIT(利用“ guard”指令,在违反期望时允许专门代码安全回退),没有太多的显式注释,“赋予”这个特性给任何使用它编写的语言解释器。此外,它提供了多种内存管理方案(例如多代标记/清除)。

总之:虽然变量是“动态的”,但代码通常不是,因此静态分析可以提供有关每个变量类型的答案。


RPython的问题在于文档太少了。我感到很迷茫,我读到他们会为你的解释器“免费”提供JIT编译器。但我不知道这是否值得... - Erik Campobadal
@ErikCampobadal 这取决于您的解决方案的性能特征,但请注意,即使在Pypy本身下运行普通的Python代码,您也会从中受益。例如,我的模板引擎在CPython 2.7上每秒生成38,775次,在Pypy下则为45,680次。当然,现代的CPython越来越好,例如在CPython 3.7下进行相同的测试可达到47,938次/秒。(重要且相关的说明:这不是用于模板代码的解析器/解释器;它是一个在导入时进行文本转换的流水线。) - amcgregor

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接