50

GHC 的设计基于一种叫做 STG 的东西，它代表“spineless, tagless G-machine”。

现在 G-machine 显然是“graph reduction machine”的缩写，它定义了如何实现惰性。未求值的 thunk 存储为表达式树，执行程序需要将它们缩减为正常形式。（树是无环图，但 Haskell 的普遍递归意味着 Haskell 表达式形成一般图，因此是图归约而不是树归约。）

不太清楚的是术语“spineless”和“tagless”。

  1. 我认为“spineless”是指功能应用程序没有功能应用程序节点的“spine”。相反，您有一个对象来命名被调用的函数并指向其所有参数。那是对的吗？

  2. 我认为“无标记”指的是没有用构造函数 ID“标记”的构造函数节点，而是使用跳转指令解析大小写表达式。但现在我不确定这是否正确。相反，它似乎指的是节点没有用它们的评估状态标记的事实。谁能澄清这些解释中哪一个（如果有的话）是正确的？

4

4 回答 4

30

GHC wiki 包含一篇由 Max Bolingbroke 撰写的关于 STG 的介绍性文章：

STG 机器是世界领先的 Haskell 编译器 GHC 的重要组成部分。它定义了如何在标准硬件上有效地实现 Haskell 评估模型。尽管有这个关键作用，但 GHC 用户通常对它知之甚少。本文档旨在通过一系列显示 Haskell 源代码如何编译的简单示例，概述 STG 机器的现代、基于 eval/apply、指针标记的化身。

于 2012-08-25T02:01:24.970 回答
16

如果我是对的，您对“Spineless”的看法是正确的。Burn、Peyton-Jones 和 Robson 在 1988 年的文章“The Spineless G-Machine”中基本上描述了它。我读过它，但它在我的脑海中并不新鲜。基本上，在 G-Machine 上，所有堆栈条目都指向一个应用程序节点，除了顶部的那个指向表达式的头部。这些应用程序节点间接访问参数，并且在某些 G-Machine 描述中，在应用函数之前重新排列堆栈，以便堆栈上的最后 n 个节点指向参数而不是应用程序节点。如果我没记错的话，“Spineless”部分是关于避免将这些应用程序节点（称为图形的脊椎）完全放在堆栈上，

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

在 STG 机器中，不使用标签。标签被一组函数指针取代，可能是受到 OO 语言的启发。当您想要一个尚未计算的节点的值时，该函数将计算它。当它已经被计算出来时，函数返回它。这允许在不使客户端代码变得更复杂的情况下，这个函数可以做很多创造性的事情。

这个“无标签”部分是的，在 SPJ 的“在库存硬件上实现功能语言”一文中进行了描述。

也有人反对这种“无标签”的东西。基本上，这涉及到函数指针，这是计算机体系结构术语中的间接跳转。间接跳转是分支预测的障碍，因此通常是流水线的障碍。因为要么架构认为对跳转参数存在数据依赖性，因此停止流水线，要么架构假设它不知道目的地并停止流水线。

于 2013-06-08T00:52:51.503 回答
3

你想阅读 SPJ 关于函数式 PL 实现的书：

于 2012-08-12T20:22:45.547 回答
3

migle 的答案正是 STGM 的无旋转和无标签的含义。今天不值得尝试理解这两个特性的名称，因为这些名称源于图缩减技术的历史：来自 G-machine、Spineless G-machine 和 Spineless and Tagless G-machine。

G 机器同时使用书脊和标签。脊椎是从函数应用程序的根节点到函数节点的边列表。例如，“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 机器中，因此脊椎是由 left_n -> left_n-1 -> ... -> left_2 -> left_1 组成的边列表。它实际上是功能应用程序的脊梁！

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

在下一个称为 Spineless G-machine 的高级 G-machine 中，通过在一个连续的块中表示这样的功能应用程序，没有这样的脊椎，该块的第一个插槽指向 f，第二个插槽指向 e1，...，并且第 n+1 个时隙指向 en。在这个表示中，我们不需要脊椎。但是该块开始一个特殊的标签，指定插槽的数量等等。

在最先进的 G 机器中，即所谓的 Spineless Tagless G 机器中，这种标记被替换为函数指针。评估函数应用程序是通过函数指针跳转到代码。

不幸的是，Simone Peyton Jones 的 STGM 论文并没有给出一些抽象层次的编译/评估规则，因此人们不容易理解 STGM 的本质是很自然的。

于 2017-03-02T11:46:46.660 回答