代码之家 › 专栏 › 技术社区 › suhdonghwi

相互递归函数的Hindley-Milner型推理

hindley-milner compiler-construction ocaml functional-programming haskell

6

suhdonghwi · 技术社区 · 7 年前

我正在制作一种强类型的玩具函数式编程语言。它使用Hindley-Milner算法作为类型推理算法。

在实现该算法时,我有一个关于如何推断相互递归函数类型的问题。

let rec f n = if n == 0 then 0 else g (n - 1)
let rec g n = if n == 0 then 0 else f (n - 1)

f 和 g 是相互递归的函数。现在,当类型检查器推断函数类型时 f ,它还应该能够推断函数的类型 g级 ,因为它是一个子表达式。

但在那一刻,功能 g级 尚未定义。因此,类型检查器甚至不知道函数的存在 g级 ,以及函数类型 g级 明显地

真实世界的编译器/编译器使用哪些解决方案?

1 回复 | 直到 7 年前

1

4

PatJ 7 年前

在OCaml中,相互递归的值由关键字分隔 and 而不是另一个 let rec . 当类型系统到达递归定义时,它会将所有递归名称添加到环境中,然后像往常一样继续。

更新(感谢K.A.Buhr):

完全可以创建类型为的新变量 'a (带 'a 然后将其统一。确保在正确的位置概括变量(通常在定义之后)。