问题标签 [spineless-tagless-graph]

我有个朋友说：

对我来说，Haskell 最有趣的不是语言和类型。它背后是 Spineless Tagless Graph Machine。

因为 Haskell 的人一直在谈论类型，所以这句话真的引起了我的注意。现在我们可以这样看一下 Haskell 的编译过程：

1. 解析
2. 类型检查
3. 脱糖+一些碎屑
4. 翻译为核心
5. 优化的最大份额
6. 翻译成 STG 语言
7. STG 语言转 C–</li>
8. C– 装配或 llvm

我们可以简化为：

1. ..前端的东西..
2. 将 IL 翻译成 STG 语言
3. 将 STG 语言编译为 C/ASM/LLVM/Javascript

即 - Haskell 被编译成一种中间“图形语言”，并且在它被编译成 LLVM/C 等之前在那里发生了各种优化。

这与如下所示的潜在 JVM 语言编译过程形成对比：

1. 在类中将 JVM 语言代码转换为 Java 字节码。
2. 在 Java 虚拟机上运行字节码。

假设可以在 Java 编译过程中添加一个中间 STG 编译​​步骤，我想知道这种变化会有什么影响？编译后的代码会有什么变化？

（我知道您需要一种纯函数式语言来充分利用无脊椎无标签图形机器，因此如果回答这个问题有帮助，假设我们正在编译Frege [Haskell for the JVM]。）

我的问题是：如果 JVM 语言编译过程有一个像 Haskell 这样的 STG 阶段，会发生什么变化？

Haskell令人惊奇的事情之一是Spineless Tagless Graph Machine (STG)。当时，（根据SPJ的说法）它是为了让函数式编程能够在当时有限的硬件上工作的惰性而编写的。随后，它被证明对函数式编程有任何额外的好处。

当我们看到像Scheme这样的语言时-递归功能非常突出（就像在 Haskell 中一样）。使这个特别有效的部分原因是被称为尾呼叫消除的功能。你想要尾调用消除的原因是因为如果一个函数调用自己 1000 次，它可能会破坏堆栈，甚至堆栈溢出。[原文如此]

现在Haskell 有一些有趣的Tail Call Elimination选项。我们看到的是：

Haskell 的递归函数不是以非常递归的方式计算的！唯一的一堆调用是乘法本身。如果 (*) 被视为一个严格的数据构造函数，这就是所谓的受保护递归（尽管它通常被称为非严格数据构造函数，其中剩下的是数据构造函数 - 当被进一步强制时使用权）。

我的问题是：尾调用优化的 Haskell 选项是否表示 Spineless Tagless Graph-machine？

（误导性标题：它只是下面众多相互关联的类似问题之一：这些听起来像是要求提供完整的参考手册，但请记住，对于这个主题，除了 GHC 的全部源代码之外，没有参考手册STG流水线阶段，以及其他人/“内部人员”的集体积累经验..）

我正在探索“转译”Haskell（从头开始寻找乐趣/学习，忽略现有项目；目标语言/s 类似的高级/“已经适合 STG 机器”与现有 GC + lambdas/func-values +闭包），所以我正在尝试更加熟悉 GHC 的 STG IR。反复浏览了十两篇不同年龄、深度和细节的在线文章/视频，这些文章/视频实际上涉及该主题（加上原始论文，加上 StgSyn.hs），并理解了许多可能是最基本的原理，看到-ddump-stged 输出在各个部分仍然让我感到困惑（我不会手动解析它，但当然稍后会重用 GHC API 的内存中 AST）——主要是我认为我坚持将我的“粗略已知”概念映射到“仍然-foreign”该 IR 的缩写/编码标识符。如果您对 STG 有一点了解，介意看看下面的小样本来澄清一些悬而未决的问题并帮助进一步巩固我（和未来的搜索者）的掌握吗？

从最简单的 .hs 模块中，我-ddump-stg编辑了两次，第一次（在左侧） with -O0，然后（在右侧） with -O2，都在这个 diff 中捕获。

逐个遍历所有内容。

• 第 L_|R5-11 行：所以在 O2 中，testX1并且testX2似乎是整数 4 和 5 的全局常量/文字 --- O0 没有它们。好奇的！

• Str=DmdType与严格有关吗？“严格是按需类型”还是类似的？但是然后一个顶级/堆式/“全局”常量文字不能是“懒惰”的可以吗..（我不能随便在 StgSyn.hs 中按 Ctrl+F 的事情之一 --- 这是不在那里！这本身就很奇怪，为什么在 StgSyn.hs 中没有 STG 语法）

• Caf对常量应用形式有一个粗略的了解，但是Unf=OtherCon？“其他构造函数”（未装箱/原生Type.S#相关？）..

• 第 L6|R14 行：惊讶地仍然在其中看到类型类信息Num（运行？（我当然希望在 STG / pre-CMM 后期阶段至少在 O2 中尽可能解决和内联。毕竟 GHC 还决定 type-default4和5to Integer）。一般来说，我理解 STG 是“无类型的”，而不是表示 prim 类型、饱和的 cons，也许是字符串（稍后在底部看起来），所以这样的“typeclass”注释只能是……我想读者可以找到他们的方式在 ddump-ed *.stg 周围。但如果没有，请纠正我。

• GblId可能只是“全局标识符”又名顶级 CAF 对吧？阿里蒂清楚。

• L7|R18 线：现在Str=DmdType是testX，仅在 O2 中，然后是一个怪异的<S(LLC(C(S))LLLL),U(1*C1(C1(U)),A,1*C1(C1(U)),A,A,A,C(U))><L,U>！那是什么，SKI微积分？;D 不认真，LLC.. LLLL.. 堆栈或 CMM 的其他内存布局提示？任何想法？必须进行一些优化，想了解which-and-how..

• L8|R20 行：（$dNum_sGM左）和$dNum_sIx（右）让我有点担心，它们似乎没有在任何地方“在模块级别定义”。Typeclass“方法调度字典查找”之类的东西？会例如。CMM 将其与上述Num注释一起设置吗？它总是与inputfunc arg 一起出现。

• 左右两侧的整个函数“body”在这里基本上可以看作是“3 lets 具有 3 个原子的 lambda-ish 形式，其中 2 个是静态已知的字面常量”——我想这是标准的，并且预计在 STG IR AST 中？对于其中的第一个，有趣的是，我们可以说 O0 已“内联全局（O2 中的 testX1 或 testX2 是什么）而 O2 没有”（使后者更短，因为这适用于这两个常量文字）。

• 我只见过Occ=Once，其他是什么以及如何解释？Once因为其中一个甚至不在 StgSyn.hs 中。

• 现在LclId遇到了之前遇到的对应GblId。那是表示标识符的范围吗？在这个表达式上下文中，它还可以是其他什么吗？如：如果遍历 AST 我大致知道我有多深，我可以忽略这一点，因为如果我处于顶层，它必须是GblId，否则LclId？嗯..也许更好地接受STG给我的东西，但是我需要确定语义和可能性..伙计们，使用StgSyn.hs我有错误的源文件，对吧？那里也没有任何内容..（总是充满希望，因为它的评论做得很好）

• 其余的只是作为字符串常量的元数据，好的.. 哦等等，看看 O2，有Str=DmdType m1and Str=DmdType m，m/是什么m1，另一件事我在这里看不到“在模块级别的任何地方定义”？它不在O0..

• 依然强劲？只是一个额外的问题（现在），告诉我们srt:SRT:[]；）

我正在学习惰性函数式语言评估并遇到了 STG 机器。为了理解它，我正在为功能语言（STG）构建一个小型玩具编译器。

然而，有一件事我无法真正理解：根据 1992 年的论文，stg 表达式可以是：let绑定、case表达式、应用程序、构造函数、内置操作或未装箱的文字。

因此，如果我有一个只使用变量而不调用它的程序，它仍然必须编译为应用程序，因为 stg 表达式变体中没有“var”选项（本文第 20 页）。例如：

编译为

但是，如果这个id函数需要一个原始值呢？( id :: Int# -> Int#) 它无法编译为应用程序，因为您无法“输入”原始值，但没有其他选择吗？

非常感谢

（编辑：链接到我所指的论文）