2

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

例如，如果我有

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

我什至如何确定这个表达式的类型？它是否涉及任何聪明才智，或者我可以遵循一个简单的算法来帮助我思考如何确定任何表达式的类型？

4

2 回答 2

8

不需要聪明。实际上，有一种算法来确定类型。Ocaml 基于Hindley-Milner类型系统。类型推断算法很少，您可以在文章中找到详细信息。至于您的示例，让我们尝试逐个弄清楚：

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

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

  • z是 type () -> D，因为它被调用()并传递给x

  • 所以，类型z ()是D

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

  • 让我们C成为y

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

  • 的类型(x y) (z ())只是E

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

于 2013-08-30T19:39:52.217 回答
3

要搜索的词是“<a href="http://en.wikipedia.org/wiki/Hindley%E2%80%93Milner" rel="nofollow">Hindley-Milner 类型系统”。你应该在网上找到大量的资源，只是避开可能是基本系统任意复杂扩展的研究文章。

有一个算法和一个类型系统。类型系统不是语法指导的：在任何步骤都必须选择遵循语法或实例化/概括。

“算法”是语法导向的（在任何步骤中只有一条规则适用），这就是它被称为“算法”的原因。这使得它非常高效，尽管它仍然以一组推理规则的形式呈现。通过使用可变引用进行统一可以提高效率。

于 2013-08-30T19:29:30.583 回答