什么是主要的类型?(What is a principal type?)

2019-07-30 11:18发布

OCaml的编译器有一个“-principal”选项和术语“基本型”,在邮件列表中有时会提到。 究竟是什么意思? 在维基百科的定义是递归的,因为它假定读者已经熟悉的概念。

Answer 1:

类型推断的过程是猜测,给予用户编写的程序的事实,这是什么节目的类型。 在一般情况下,可能有几个正确类型为给定程序。 例如,该程序fun x -> x可以给出类型int -> intbool -> bool

给定一个计划,一类对这一计划是主要的 ,如果它是一个可以给这个程序,在这种意义上,所有其他可能的类型是专业化(实例)最普遍的类型。 随着我的fun x -> x例如,多态'a -> 'a是主要类型。

在某些类型的系统,并不总是存在的主要类型。 你有一个程序P有两种可能的类型T1T2 ,没有人比另一个更普遍的。 例如,在一些系统中,其中数字运算符过载,则程序fun x -> x + x可以是给定类型int -> int和类型float -> float ,并且没有类型涵括两者。 这是推理引擎出了问题,因为这意味着它必须作任意选择,挑选可能的类型之一不知道,如果它是一个用户打算。 如果您有主要类型,推理过程不需要做任何选择。

(为了解决这个例如,你可以:(1)不超载算术运算符(2)使任意选择(这就是F#不IIRC)(3)拒绝该方案,并要求类型注释消除不确定性(4)有更多的表达类型,如Haskell的Num a => a -> a )。

OCaml的语言的“简单”的子集,基于辛德米尔纳类型推断,有主要类型。 这意味着,推理引擎总是做正确的事(考虑到可能的类型的规格)。 (比如多态字段和方法)的类型系统的一些更高级的方面失去这个属性:在某些情况下,类型系统无法找到一个最普遍的类型,或寻找最普通类型将需要从理智更复杂的计算型推理机(其通常试图要快)。 该-principal选项是旋钮即会,如果我没记错的话:

  • 失败是其中类型检查器否则将接受一个非主要溶液(由任意选择)一些情况下
  • 尝试很难找到着力解决的问题,在较长的类型检查时间和内存使用成本

我不是很熟悉这个标志(我喜欢避免过于先进的类型系统的特点,所以我的程序通常不关心),那么你就必须仔细检查这一点,但是这是大概的了解。 该标志是在我看来,(你通常不会需要关心)相对不重要,但主要类型的想法确实是ML语言理论的重要组成部分。

如果你想走得更远两个更多的技术细节:

  • “主要类型”的ML概念是是否存在给定的固定类型环境中的最普遍的类型的问题; 一些学者研究它们是否存在最普遍的问题(环境,类型)对,所谓的一个“主要打字”; 这是一个更难回答的问题(你必须推断你从其他模块的期望,而ML你给你依靠外部模块签名;且推断多态性是很辛苦)未在大多数ML风格的编程中使用语言。

  • 主要类型的存在是类型系统的设计者一个微妙的平衡。 如果从ML类型系统删除功能(多态,类型,如'a -> 'a ),你失去公,但如果添加电源(从ML将会拥有更多的表现多态类型系统F)还可能丢失公国。 您可以通过移动到更复杂的类型系统,如MLF夺回失去公国,但它是一个困难的问题。

在实践中,编程语言的设计者的相当大部分近来放弃公国的想法。 他们希望有更宏大的类型系统(取决于类型等),它只是太努力去寻找公国,所以他们不是用非主要推论内容本身:它已经是一件好事,如果推理引擎可以找到某种类型 ,我们不要很难对结果的普遍性。 雅克常绿矮灌木丛,OCaml的类型系统的主要维护者,仍然关心它非常多,而且我认为这是OCaml的编程语言研究的一个有趣的方面。



Answer 2:

要建立在gasche的解释一点,这里有一个例子,从OCaml的自己的测试包,其中公,或缺乏,出现被盗。 免责声明:本使用对象。

class c = object method id : 'a. 'a -> 'a = fun x -> x end;;
type u = c option;;
let just = function None -> failwith "just" | Some x -> x;;
let f x = let l = [Some x; (None : u)] in (just(List.hd l))#id;;
let g x =
  let none = (fun y -> ignore [y;(None:u)]; y) None in
  let x = List.hd [Some x; none] in (just x)#id;;
let h x =
  let none = let y = None in ignore [y;(None:u)]; y in 
  let x = List.hd [Some x; none] in (just x)#id;;

当在顶级会话中运行这个,你会得到:

#     val f : c -> 'a -> 'a = <fun>
#     val g : c -> 'a -> 'a = <fun>
#     val h : < id : 'a; .. > -> 'a = <fun>

这些函数执行完全一样的事情,但会被分配不同类型的!

如果你与调用OCaml的-principal选项,前两个例子将触发:

Warning 18: this use of a polymorphic method is not principal.

有趣的是,如果要更换'a中的类型h'a -> 'a ,你会得到完全相同的类型fg ,因为类型c仅仅是一个类型的缩写(即扩展到) < id: 'a -> 'a; .. > < id: 'a -> 'a; .. >

什么编译器要在这里告诉程序员,有两个合适的类型fg ,并没有标准,这将有助于OCaml的决定哪一个是“最好的”(和“最好的”,我的意思是“校长“, 当然!)。



文章来源: What is a principal type?
标签: ocaml