相互递归函数的 Hindley Milner 类型推断

Question

我正在制作一种强类型玩具函数式编程语言。它使用 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 的类型，显然。

现实世界 compilers/intepreters 使用了哪些解决方案？

Answer 1

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

更新（感谢 K.A。Buhr）：

完全可以创建一个类型为 'a 的新变量（'a 是新鲜的），然后再统一它。请务必在正确的位置（通常在定义之后）概括您的变量。