一种难以编译的语言


我最近又开始研究Seph了。我去年夏天就提前宣布了(here),然后promply工作变得异常忙碌。太忙了,我真的有一段时间没有精力做这个项目了。可悲的是,我仍然很忙,但是我仍然设法找到一些小的时间来开始实现的编译器部分的工作。自从JSR292接近完成以来,这变得更加容易和有趣,并且有了一个ASM 4分支,它使得编译支持调用动态内置的Java字节码变得更加容易。

这意味着存储库中的当前代码实际上已经达到了我想要的程度。具体来说,除了创建抽象的抽象和接受关键字参数的调用之外,编译器编译大多数代码。目前也不支持分配。我不认为这些特性中的任何一个会很难实现,所以我在等待,并致力于其他更复杂的事情。

这篇博文有两个目的。第一个是告诉世界,Seph作为一个想法和项目,实际上是有生命的,正在努力的,并且已经取得了什么进展。这篇文章的另一个方面是谈论一些使Seph成为一种非常棘手的编译语言的事情。我还将包括一些我对如何解决这些问题的想法——如果你知道一个更好的方法,建议是非常受欢迎的。

概括地说,Seph工作的约束是它必须在Java 7上运行。它必须被完全编译(事实上,在编译器工作之后,我还没有决定是否保留解释器)。而且必须要快。差不多。我的目标至少是Ruby 1.8速度。我不认为这是不合理的,考虑到Seph必须允许的灵活性。

让我们开始吧。这些是目前的主要难点——在某些情况下,它们是相互关联的……

尾部递归

所有Seph代码都必须是尾部递归的,这意味着尾部调用永远不会增加堆栈。为了在JVM上实现这一点,您需要将信息保存在某个地方,以便继续调用。然后,任何使用值的人都必须检查尾部标记令牌,如果找到了,调用方将不得不对当前尾部重复调用,直到产生一个真正的值。尾巴所需的所有信息也必须保存在某个地方。

我目前采用的方法与埃尔詹格斯相当相似。我有一个SThread对象,所有Seph调用都必须传递这个对象——一旦我给Seph添加了轻量级线程,它就会作为一个线程上下文。但是这个地方也是保存下一步去哪里的信息的好地方。我目前对尾部的编码只是一个没有参数的方法句柄。因此,您需要做的唯一一件事就是反复检查标记并调用尾部方法句柄。尽管如此,在所有地方都这样做可能没那么好。目前,代码不是在热路径中从头开始查找方法句柄,而是必须绑定几个参数来创建尾部方法句柄。我不确定这会对性能产生什么影响。

被调用方的参数计算

Seph的一个与Ioke相同的方面是方法调用永远不会评估参数。评估参数的责任在于接收代码,而不是调用代码。因为我们不知道某个东西是会做常规评估还是做类似宏的事情,所以实际上不可能预先评估这些参数并把它们推上堆栈。

Ioke和Seph解释器采用的方法是只发送消息对象,并允许被调用方对其进行评估。但这正是我想用Seph避免的——所有的东西都应该可以编译,如果可能的话,运行得很热。因此,四处发送信息违背了初衷。

我发现了一种编译方法,它实际上非常有效。在大多数情况下,它也减少了代码膨胀。基本上,作为消息发送一部分的每一段代码都将被编译成一个单独的方法。所以如果你有类似foo(bar baz,qux)的东西,它将编译成主激活方法和两个参数方法。当然,这种方法是递归的。这给了我一个协议,在这个协议中,我可以对参数方法使用方法句柄,将它们推送到堆栈上,然后允许被调用方以他们想要的方式对它们进行评估。我可以提供一个标准的评估路径,它只是依次调用每个方法句柄来生成值。但是,对我来说,把它们以未估价的方式寄出也变得非常容易。作为一个例子,这几乎就是内置“if”方法的当前实现的样子。(由于过渡解释器的细节,现在不完全是这样的)。

public final static SephObject _if(SThread thread, LexicalScope scope,
MethodHandle condition, MethodHandle then, MethodHandle _else) {
SephObject result = (SephObject)condition.invokeExact(thread, scope,
true, true);

if(result.isTrue()) {
if(null != then) {
return (SephObject)then.invokeExact(thread, scope,
true, true);
} else {
return Runtime.NIL;
}
} else {
if(null != _else) {
return (SephObject)_else.invokeExact(thread, scope,
true, true);
} else {
return Runtime.NIL;
}
}
}

 

当然,这种方法并不完美。这仍然是一个很大的代码膨胀,我不能使用堆栈将东西传递给参数评估,并且绑定参数方法句柄的代码占用了当前生成的大部分代码。尽管如此,它看起来还是有效的,并且有很大的灵活性。并且编译常规的方法评估将使得直接将这些参数方法句柄绑定到一个调用动态调用站点成为可能,这可以在评估参数时大大提高性能(这在现实世界的代码中很可能经常发生……=)。

本质只是普通的信息

其他语言中的许多语法元素只是Seph中的消息。像“无”、“真”、“假”、“如果”这样的东西和许多其他东西的工作方式完全一样,就像一条普通的信息发送给你自己定义的东西一样。但是在许多情况下,这是完全不必要的——而且在大多数情况下,了解调用站点的实现允许您在许多情况下实质性地改进事情。我认为覆盖任何一个标准的名字都是非常不寻常的。但是我还是想让它成为可能。我对这样做的程序很满意,并从中获得了性能上的成功。所以我想出的方法(但还没有实现)是这样的——我将把每个与一个内部函数同名的地方的编译作为特例。这个特殊的外壳将绑定到一个不同于常规Seph方法的引导方法。作为一个连续的例子,让我们考虑编译一段带有“真”的代码。这将生成一个消息发送,该消息发送将由一个sephTrueBootstrapMethod处理。但是,我们仍然需要发送所有常规的方法激活参数。这个引导方法将做的是建立一个指向一个非常特殊的方法句柄的调用站点。这个方法句柄将是一个guardWithTest,它是通过一个特定于真实值的开关点创建的。GWT测试的第一条路径将直接返回真实值,不需要任何检查。GWT的else路径将回退到一个常规的Seph回退方法,该方法进行内联缓存和常规查找。开关点的神奇之处在于——创建新绑定的地方会检查这些固有名称,如果其中一个名称在客户端代码中的任何地方使用,开关点将被切换到慢速路径。

总的来说,我认为对于大多数程序来说,这些事情中的许多都可能有一条快速的路径。当您覆盖“if”时的行为应该仍然像预期的那样工作,但是会使该程序的全局性能在其余的执行中变慢。

词汇范围什么时候逃脱?

Seph有可变的词法范围。但是不可能知道哪些名字会转义,哪些不会——所以就我所见,我不能用Java栈来表示变量,除非是在一些非常退化的情况下。我不确定拥有这样的代码路径是否值得,所以我没有考虑太多。

基于类的图片不太合适

面向对象语言使用的标准优化之一是所谓的多态内联缓存。基本思想是查找方法是非常缓慢的操作。因此,如果你可以通过一个非常便宜的测试来避免这样做的结果,那么你就可以简化最常见的情况。现在,最便宜的测试通常是对班级的检查。只要您发送一个具有相同类的实例,那么就不必进行新的方法查找。做一个getClass然后在上面做一个身份相等通常是相当快的(在大多数架构上是一个指针比较)——所以你可以构建实际上不花太多时间在守卫上的图片。

但是Seph是一种基于原型的语言。因此,系统中的任何对象都可以有不同的方法或值与一个名称相关联,并且对于其中具有新名称和值的对象没有明确的描述。特别是,由于Seph对象是不可变的,每个新对象很可能都有一组新的值。保存一种方式的对象并在其上调度会变得不那么有效,因为调用站点基本上不会在同一个对象上工作。现在,对此有一些解决方案——但是大多数都是为那些通常使用基于类的模式的语言量身定制的。V8使用一种叫做隐藏类的方法来解决类似的问题。我正在考虑实现类似的东西,但是我有点担心Seph的使用模式会离基于类的世界太远,以至于它可能不能很好地工作。

摘要

所以,Seph不是非常容易编译的,我也不知道它实际上能做得多快。我想我们只能拭目以待了。但提出这些问题的解决方案也是一个有趣的挑战。我想我可能还得继续新的研究热潮,调查赛尔夫和牛顿脚本是如何做事情的。