理解STG

Question

理解STG

haskellcompilationghcbytecodeintermediate-language

52

GHC的设计基于STG，STG代表"无脊椎，无标记G机"。

G机是“图缩减机”的简称，它定义了如何实现惰性执行。未求值的推迟(thunk)被存储为表达式树，执行程序需要将其归约(reducing)到正常形式。(树是无环图，但Haskell的广泛递归意味着Haskell表达式形成一般图(graph)，因此采用图缩减而非树缩减。)

“无脊椎”和“无标记”的含义不太清楚。

我认为，“无脊椎”指的是函数应用节点没有“脊柱”。相反，你有一个对象来命名所调用的函数并指向它的所有参数。这个理解正确吗？
我曾认为“无标记”指的是构造节点没有标记构造ID，而是通过跳转指令解析case语句。但现在我不确定这个理解是否正确。相反，它似乎指的是节点没有标记其评估状态。谁能澄清这些解释中哪一个（如果有）是正确的？

- MathematicalOrchid

4个回答

17

你对于“Spineless”是正确的，如果我没记错的话。它基本上是在Burn、Peyton-Jones和Robson于1988年发表的文章《The Spineless G-Machine》中描述的。我读过这篇文章，但是我不太清楚了。在G-Machine中，所有堆栈条目都指向应用节点，除了顶部的一个，它指向表达式的头部。这些应用节点使得访问参数间接化，在一些G-Machine的描述中，在应用函数之前，堆栈会被重新排列，以便最后n个节点指向参数而不是应用节点。如果我没搞错，“Spineless”部分就是避免将这些应用节点（称为图的脊柱）全部放在堆栈上，从而避免每次规约之前的重新排列。

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

在STG机器中，不使用标签。标签被一组函数指针所取代，也许受到OO语言的启发。当你想要一个尚未计算的节点的值时，该函数将计算它。当它已经计算了，函数就会返回它。这允许这个函数在不使客户端代码更加复杂的情况下具有很多创造力。

这个“Tagless”部分确实在SPJ的《implementation of functional languages on stock hardware》一文中有描述。

对于这个“tagless”东西也有异议。基本上，这涉及到函数指针，这是计算机体系结构术语中的一种间接跳转。而间接跳转是分支预测的障碍，因此一般来说也是流水线的障碍。因为要么体系结构认为跳转参数有数据依赖性，从而停止流水线，要么体系结构认为自己不知道目的地并停止流水线。

- migle

4

migle的答案恰好阐述了STGM的无脊椎和无标记含义。今天，不值得试图理解这两个特征的名称，因为名称源于图减少技术的历史：从G机器，无脊椎G机器，到无脊椎和无标记G机器。

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机器中，脊柱是一个由左_n -> left_n-1 -> ... -> left_2 -> left_1组成的边列表。它实际上是函数应用的脊柱！

在同一函数应用中，有标记AP和FUN。

在下一个高级G机器中，所谓的无脊柱G机器，通过将这样的函数应用表示为一个连续块，其第一个槽指向f，第二个槽指向e1，...，第n+1个槽指向en。在这种表示中，我们不需要脊柱。但是该块以指定槽数等的特殊标记开头。

在最先进的G机器中，即所谓的无脊柱无标记G机器中，这样的标记被一个函数指针替换。评估函数应用程序就是跳转到函数指针处的代码。

很遗憾，Simone Peyton Jones的STGM论文没有在某个抽象层面上给出编译/评估规则，因此人们很自然地难以理解STGM的本质。

- user3509406

3

您想阅读SPJ关于函数编程语言实现的书籍：

http://research.microsoft.com/en-us/um/people/simonpj/papers/slpj-book-1987/index.htm

请点击链接。

- solrize

11

那本书早于G机器的“无脊椎”和“无标记”部分。 - migle

链接已失效... - ceving

这个链接有效： https://www.microsoft.com/en-us/research/wp-content/uploads/1987/01/slpj-book-1987-small.pdf - Łukasz Lew

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Mikhail Glushenkov · Accepted Answer

GHC维基包含了由Max Bolingbroke撰写的有关STG的入门文章：（链接请点击）

STG机器是GHC编译器中不可或缺的部分，该编译器是世界领先的Haskell编译器。它定义了如何在标准硬件上高效实现Haskell评估模型。尽管STG机器扮演着如此重要的角色，但它通常被GHC用户所理解的很差。本文旨在通过一系列简单的示例展示Haskell源代码如何被编译，从而提供STG机器现代、基于eval/apply和指针标记的概述。