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