Clever Geek Handbook

OCaml语言的活动模式扩展的实现

关于该项目



在2020年春季，作为计算机科学中心春季实践的一部分，我在Dmitry Kosarev的严格指导下开发了OCaml编程语言的新设计。



为什么选择OCaml



OCaml是工业编程合一性（因此具有多范式，多平台，非常快速的编译器，生成的代码的生产率高）和数学（因此具有强大的类型推断，可表达性和可扩展性的最先进类型系统）最成功和开发的实现之一语言，与数学符号和语义的接近度）。



同时，语言社区非常有选择性，并且在不向现有语言引入限制的前提下，仅向语言要求很高的结构中缓慢添加。因此，该语言的核心非常小巧且直观，并且工业开发人员和圣彼得堡国立大学高级代数与数论系的数学家都很喜欢使用OCaml 。



为了深入探讨该主题，我建议您阅读针对大众的OCaml文章以及为什么选择OCaml。



当前，正在为实现OCaml的多核系统以及代数效应而工作，这将同时提高该语言的整体性能并消除与该语言允许不纯计算有关的类型系统的现有限制。



模式匹配和活动模式



我的工作主要集中在模式匹配结构上，该结构已在功能编程语言中广泛使用。

为了说明，请考虑一个旋转二叉树中的节点的简单示例。在最常见的命令式样式中，代码可能如下所示： 







type 'a tree =
  | Node of 'a tree * 'a * 'a tree
  | Nil
let rotate_left' t =
  if is_node t
  then
    let a = get_left  t in
    let p = get_value t in
    let r = get_right t in
    if is_node r
    then
      let b = get_left  t in
      let q = get_value t in
      let c = get_right t in
      Node(Node(a,p,b),q,c)
    else t
  else t


这是使用模式匹配结构编写的相同代码： 



let rotate_left = function
  | Node(a, p, Node(b, q, c)) -> Node(Node(a, p, b), q, c)
  | Node _ | Nil as x -> x


使用此设计时，我们具有以下优点：



  • 高表现力
  • 完整性检查，这是正确性检查和程序重构的关键属性；
  • 高效的编译方案。


完整性检查意味着，知道类型定义的编译器可以检查每个匹配项，是否确实已经解析了所有可能的替代项，并且无论样本多么复杂，以及它们如何相交，都没有不可达的分支。因此，如果您更改类型定义（添加新的替代方案，删除或更改现有的替代方案），则编译器将为您提供代码中所有直接受影响的位置。



例如，如果我在语法树中添加了新的构造，则编译器将向我展示AST类型的代码直至功能体，在这里我需要编写新结构的类型代码：







此属性使OCaml非常抗重构和其他代码更改。



尽管描述了所有优点，但在适用性上也有一个非常严重的限制。你注意到了吗？类型定义必须是公共的（以便编译器可以显示组成它的替代方法）。当然，这甚至会破坏最简单的抽象。例如，如果我们要定义最简单的列表接口，则无法提前告知要导出的类型定义： 



module type List = sig
  type 'a t (* = ? *)
  val cons:  'a -> 'a t -> 'a t
  val empty: 'a t
  val head:  'a t -> ('a * 'a t) option
end


但是，这个问题不是根本性的，正如1987年所指出的，有可能在抽象类型上实现模式匹配。



问题的提法



自1987年以来，文献中提出了许多不同的设计来解决这个问题，其中仅几个：







在项目开始时，已经在合理，客观地选择特定的实现方案方面进行了工作，最有利的是以F＃语言实现的Active模式扩展。



该项目的目标是开始为OCaml编译器实现活动模式，并尽可能相处融洽。



活动模式



活动模式（以及类似的扩展名）的想法非常简单：由于抽象是通过将实现隐藏在函数内部来实现的，因此有必要允许在模式匹配内调用函数，以将抽象数据类型的未知值转换为已知的替代列表。活动模式会在函数名称内对该替代列表进行编码。因此，必须将以下功能添加到上面列表的接口中(|Cons|Nil|)： 



module type List = sig
  type 'a t
  val (|Cons|Nil|): 'a t -> ('a * 'a t, unit) choice2
  val cons:  'a -> 'a t -> 'a t
  val empty: 'a t
  val head:  'a t -> ('a * 'a t) option
end


结果是一个匿名总和类型choice2，其定义如下（最多有相似的生成类型choice32）： 



type ('a, 'b) choice2 =
  | Choice2_1 of 'a
  | Choice2_2 of 'b


因此，该函数(|Cons|Nil|)会将列表转换为以下两种选择之一：转换为列表的首尾，或者转换为空替代（意味着列表为空）。



为标准列表定义这样的功能很简单，看起来像这样： 



let (|Cons|Nil|) = function
  | []      -> Nil
  | x :: xs -> Cons(x, xs)


作为使用示例，请考虑一个删除列表中连续重复项的函数： 



(* destutter [1;1;4;3;3;2] = [1;4;3;2] *)
let rec destutter = function
  | Nil -> nil
  | Cons(x, Nil) -> cons x empty
  | Cons(x, Cons(y, rest)) ->
      if x = y 
      then destutter (cons y rest)
      else cons x (destutter (cons y rest))


请注意，保留了模式匹配的所有好处：匹配语法相同，并且完整性检查可以完全进行。有效地编译这样的解决方案超出了本概述的范围，但是它也是可能的。



进展



作为这项工作的一部分，可以对OCaml编译器版本4.09进行扩展的解析和类型输入，结果在此处显示。



编译器解析器使用高级Menhir解析器生成器实现。 Menhir有相当完整和详细的手册，但是即使与他在一起，也并不总是很清楚如何设置推理规则，以及如何以及为什么。生成的解析器补丁很小而且很简单，但是通过10-15个shift-reduce和reduce-reduce冲突来解决，它的解析和修复花费了一些时间：







我要向Menhir开发人员表示敬意，并感谢他们为详细说明和澄清错误所做的工作。一旦解析器生成器无法说明冲突，就必须根据构建的1500个州的自动机解析冲突。当然，这需要更长的数量级。



扩展名键入特别困难。键入代码长约37,000行，几乎没有文档记录，这对于初学者来说很难理解。Oleg Kiselev撰写的一篇文章让我很受启发，该文章解释了实现的关键方面。



我为自己得出的另一个结论是不要忘记使用该项目的旧版本。例如，这是2019年和2005年版本的同一打字的定量比较：







2019版本包含编译器分析和警告以及我不感兴趣的其他技术详细信息。要理解，我只需要查看2005版，其中仅包含关键操作。



最后，我在工作中得出的主要结论是，确认开源项目的文档至关重要。作为传神的语言，源代码只能告诉怎样一个函数的行为，而不是什么它做或为什么它的方式它。阅读调用链type_self_pattern-> type_cases-> t ype_pat-> type_pat'->type_pat_aux并弄清楚您需要哪个功能是非常困难的。或仅一个参数名称constr猜测哪些构造函数以及为什么应在此处编写。



每次都需要查看用例，这会使程序员放慢速度，并且很快就会感到疲倦：让我提醒您“七个，正负两个”规则-一个人平均可以同时记住的对象数量也一样。当您终于了解了第六个嵌套函数中参数的含义并突然意识到自己不记得为什么需要它时，或者事实证明您不需要它时，由于花费了很多时间，它变得非常可悲。



结论



作为项目的一部分，我能够实现Active模式的解析和键入。我打过补丁的编译器可以使用任何使用Active模式的示例来解析和键入文件。



接下来，您需要修改编译方案（OCaml使用模式匹配的非平凡优化编译）和模式完整性检查，这几乎是在项目期间由OCaml编译器开发团队完全重写的。



我希望无论有没有我，这个实施过程仍将完成。尽管遇到了种种困难，但尝试自己喜欢的语言开发一种工业编译器还是很棒的。



作者：



亚历山大·巴什基洛夫（Alexander Bashkirov）是计算机科学中心的学生，并且是JetBrains的雇员，圣彼得堡国立大学软件工程专业的四年制学士学位。


More articles:


All Articles