我正在研究方案编译器斯大林。它庞大而复杂。另外，如果我理解正确的话，作者正计划写一系列论文来详细说明实现的各个方面，但一直没有时间去做。
我感兴趣的斯大林方面是全局类型推断：根据事物在程序中其他地方的使用情况来推断事物的类型。斯大林真的这样做了吗？如果是，如何以及在其代码库中的位置？它是否使用 Hindley-Milner 算法的变体/扩展？
问问题
376 次
1 回答
4
从自述文件：
斯大林使用支持递归联合类型的软类型系统进行全局静态类型分析。斯大林可以在没有类型声明的任意 Scheme 程序中为每个源代码表达式确定一个窄的甚至是单态的类型。这允许斯大林减少或经常消除运行时类型检查和分派。斯大林还根据每个表达式进行低级表示选择。这允许对所有单态类型使用未装箱的基本机器数据表示，从而产生极高性能的数字代码。
斯大林使用基于集合的分析（SBA aka 0CFA）执行类型推断。该分析被扩充以支持多变量过程拆分。SBA 的结果用于减少运行时类型检查和分派。SBA 的结果也用于在每个表达式的基础上进行低级别的表示选择。这有两个好处。首先，可以消除单一类型的类型标签，允许使用基本机器表示来表示原始数据。其次，可以消除拳击，从而减轻与拳击相关的间接、分配和回收成本。消除装箱要求运行时组织允许变量、参数、结构槽和向量槽具有不同的宽度，具体取决于它们所保存的数据类型。此外，只有当这些结构是不可变的时，用户定义的结构才能被拆箱。SBA 被扩展以在编译时确定数据宽度和可变性。
实际的类型推断算法似乎主要在源文件中实现source/stalin3b.sc。
SBA/0CFA 似乎是一个完全独立于 Hindley-Milner 的算法。然而，Hindley-Milner 也可以用来实现软类型。
这是对 0CFA 算法的更好描述。
相关论文是 Olin Shivers 的 1991 年博士论文Control-flow Analysis of Higher-Order Languages 或 Taming Lambda和 Flanagan & Felleisen 的 1995 年论文Set-Based Analysis for Full Scheme and Its Use in Soft-Typing。
于 2014-07-15T11:21:15.947 回答