了解STG

问题描述 投票:40回答:4

GHC的设计基于一种名为STG的东西,它代表“无骨架,无标签G机”。

现在G-machine显然是“图形缩减机”的缩写,它定义了如何实现懒惰。未评估的thunk被存储为表达式树,并且执行该程序涉及将这些减少到正常形式。 (树是非循环图,但Haskell的普遍递归意味着Haskell表达式形成一般图,因此图减少而不是树减少。)

不太清楚的是术语“无骨”和“无标记”。

  1. 我认为“无脊椎”指的是功能应用程序没有功能应用程序节点的“脊椎”这一事实。相反,您有一个对象,该对象命名所调用的函数并指向其所有参数。那是对的吗?
  2. 我认为“无标签”指的是构造函数节点没有用构造函数ID“标记”,而是使用跳转指令解析case-expression。但现在我不确定这是否正确。相反,它似乎指的是节点没有用其评估状态标记的事实。谁能澄清这些解释中哪些(如果有的话)是正确的?
haskell compilation ghc bytecode intermediate-language
4个回答

15
投票

如果我是正确的话,你是正确的“无脊椎”,就是这样。它基本上由Burn,Peyton-Jones和Robson在1988年发表的文章“The Spineless G-Machine”中描述。我已经读过了,但在我看来并不是那么新鲜。基本上,在G-Machine上,所有堆栈条目都指向一个应用程序节点,除了顶部的应用程序节点,它指向表达式的头部。这些应用程序节点间接访问参数,并且在某些G-Machine描述中,在应用函数之前,重新排列堆栈,以使堆栈中的最后n个节点指向参数而不是应用程序节点。如果我没有弄错的话,“Spineless”部分就是避免在堆栈上完全避免使用这些应用程序节点(它们被称为图形的主干),从而避免在每次减少之前进行重新排列。

至于“无标签”部分,你现在比以前更正确,但是...在节点上使用标签是一件非常非常古老的事情。你能想到如何实现LISP这样的动态类型语言吗?每个单元格都必须具有其值和标记类型。如果你想要一些东西,你必须检查标签并采取相应的行动。在Haskell的情况下,评估状态比类型更重要,Haskell是静态类型的。

在STG机器中,不使用标签。通过一组函数指针,可以通过OO语言的灵感来替换标签。当您想要一个尚未计算的节点的值时,该函数将计算它。当它已经被计算时,函数返回它。这使得该功能可以在不使客户端代码变得更复杂的情况下获得很多创造力。

这个“无标签”部分是,在SPJ的“库存硬件上的函数语言实现”一文中有所描述。

也有人反对这种“无标记”的东西。基本上,这涉及函数指针,这是计算机体系结构术语的间接跳跃。而间接跳跃是分支预测的障碍,因此也是流水线的一般障碍。因为架构认为跳转参数存在数据依赖性,暂停管道,或者架构假定它不知道目标并停止管道。



3
投票

migle的答案正是STGM的无空转和无标记意味着什么。今天,不值得尝试理解这两个特征的名称,因为这些名称源于图形缩减技术的历史:从G-machine,Spineless G-machine,以及Spineless和Tagless G-machine。

G机器使用脊柱和标签。 spine是从函数应用程序的根节点到函数节点的边的列表。例如,“f e1 e2 ... en”的函数应用表示为

root = AP left_n en
left_n = AP left_n-1 en-1 ...
left_2 = AP left_1 e1
left_1 = FUN f

在G-machine中,脊柱是由left_n - > left_n-1 - > ... - > left_2 - > left_1组成的边列表。它实际上是函数应用程序的一个主题!

在同一个功能应用程序中,有标签AP和FUN。

在下一个称为Spineless G-machine的高级G机器中,通过在连续块中表示这样的功能应用程序没有这样的脊柱,其第一个插槽指向f,第二个插槽指向e1,...,和n + 1个插槽指向en。在此表示中,我们不需要脊柱。但是块会启动一个指定插槽数量的特殊标签,依此类推。

在最先进的G机器,即所谓的Spineless无标签G机器中,这样的标签被替换为功能指针。评估函数应用程序是通过函数指针跳转到代码。

很遗憾,Simone Peyton Jones的STGM论文没有在某些抽象层面上给出编译/评估规则,因此人们不容易理解STGM的本质是很自然的。

© www.soinside.com 2019 - 2024. All rights reserved.