确定OCaml表达式类型的一般方法是什么

Question

我是OCaml和函数式编程的初学者。如果我有一个表达式，除了将它输入到顶级并编译它之外，我如何确定它的类型？

例如，如果我有

fun x -> fun (y, z) -> (x y) (z () )

我该如何确定这个表达式的类型？它是否涉及任何聪明之处，或者有没有一个简单的算法可以帮助我思考如何确定任何表达式的类型？

Answer 1

不需要聪明。事实上，有一种算法可以确定类型。Ocaml是基于Hindley-Milner型系统。类型推理算法很少，您可以在文章中找到详细信息。至于你的例子，让我们试着一件一件地弄清楚：

fun x -> fun (y, z) -> (x y) (z () )

• 整个表达式是一个函数，从某种类型的A = typeof(x)到B = typeof(fun(y, z) -> (x y) (z ()))。

• z属于() -> D类型，因为它是用()调用的，并传递给x

• 因此，z ()的类型是D

• 因此(x y)的类型是(D -> E)

• 设C为y 的类型

• 因此x的类型是C -> (D -> E)

• 而CCD_ 15的类型恰好是CCD_

• 知道x、y和最后一个表达式的类型，我们得出整个表达式具有(C -> D -> E) -> C * (() -> D) -> E类型

Answer 2

要搜索的单词是"Hindley-Milner类型系统"。你应该在网上找到大量的资源，只是要避开那些可能是基础系统任意复杂扩展的研究文章。

有一个算法和一个类型系统。类型系统不是以语法为导向的：在任何步骤中，都必须选择遵循语法或实例化/泛化。

"算法"是以语法为导向的（在任何步骤中只有一条规则适用），这就是为什么它被称为"算法"。这使得它非常有效，尽管它仍然作为一组推理规则来呈现。通过使用可变引用进行统一，可以使其更加高效。