像 OCaml 这样的语言如何实现模式匹配？

Question

假设我有一个像这样的代码片段：

type 'a mylist = | Nil | Cons of 'a * 'a mylist

let rec last l =
    match l with
    | Nil -> None
    | Cons(x, Nil) -> Some(x)
    | Cons(x, xs) -> last xs

显然，这个模式匹配mylist-Nil和的构造函数Cons。我的问题是你将如何实施这样的事情。你不能只提供值，Cons直到找到一些匹配的值l，所以我假设 OCaml 编译器实现了类似“反向构造函数”的东西，它接受类型的值mylist并尝试将其转换为组成部分？

例如，在 psudo-ocaml 中：

type 'a mylist = | Nil | Cons of 'a * 'a mylist

Cons : ('a * 'a mylist) -> 'a mylist

UnCons : 'a mylist -> ('a mylist * 'a) option

这是正确的，还是采取其他方法？比如说，haskell 或 sml 怎么样？

Answer 1

OCaml 在底层使用统一的值表示。每个值要么是一个带标签的整数（例如1），要么是指向块的指针（例如 ）[|1;2|]。块本身就是一个包含标签的数组。当定义变体类型时

type t =
 | A
 | B
 | C of int
 | D of int

不带参数的构造函数表示为标记整数，而带参数的构造函数则映射到块。了解有关此表示的更多信息的一个好方法是使用内部Obj模块，该模块包含对 OCaml 值的内存表示进行操作的函数。例如，我们可以查看构造函数的底层表示。首先，通过检查

Obj.(is_int @@ repr A)

返回真。此外，我们还可以检查它是否在内存中A表示为标记：0

assert (Obj.repr A = Obj.repr 0)

类似地，C 1是一个带有标签 0 的块，其第一个字段中包含一个整数

assert Obj.(
  tag @@ repr (C 1) = 0
  && field (repr (C 1)) 0 = repr 1
)

通过这种统一的表示，模式匹配可以编译成决策树或回溯自动机。看看你的例子：

type 'a mylist = | Nil | Cons of 'a * 'a mylist

let rec last l =
    match l with
    | Nil -> None
    | Cons(x, Nil) -> Some(x)
    | Cons(x, xs) -> last xs

模式匹配可以恢复为：

• 检查参数是否为Nil（又名0），然后返回None
• 如果不检查参数的第二个字段是否为Nil（又名0），则返回Some (first_field of the argument)
• 否则打电话last (second_field of the argument)。

然后，您可以通过要求 OCaml 编译器发出其 lambda 中间表示来将该想法与实际的 OCaml 实现进行比较ocamlc -dlambda：

(letrec
  (last/271
     (function l/272
       (if l/272
         (if (field_imm 1 l/272) (apply last/271 (field_imm 1 l/272))
           (makeblock 0 (field_imm 0 l/272)))
         0)))

仔细观察这个 IR，我们可以观察到模式匹配已被编译为两个if，第一个在列表l/272本身上，第二个在 上field_imm 1 l/272，换句话说，在第二个字段上l/2

请注意，在这种特定情况下，没有太多可能的优化，因此编译后的 IR 非常接近原始模式匹配。

然而，对于更复杂的match，只有很少的优化层来通过移动子句、合并或拆分它们以及在子句失败时尝试保留尽可能多的上下文信息来确保生成的代码小而高效。

目前到 2022 年，OCaml 编译器实现主要遵循https://dl.acm.org/doi/10.1145/507669.507641描述的算法，用于将模式匹配编译为高效的回溯自动机。

Answer 2

Spineless Tagless G-machine（STG 机）是一篇描述 GHC 评估表达式的一般方法的论文。它已经很老了，GHC 已经放弃了这种方法，但作为对聪明人认为是个好主意的一种方法的描述，它仍然很有趣。

不过，处理数据构造函数和 case 表达式的方法只是它涵盖的主题之一，并且很难仅提供该部分的摘录，而不必总结前面的所有部分。但是，从广义上讲，语言中的每个值都表示为指向可执行代码的指针，并且使用该值就是跳转到它指向的代码。Cons 指向的代码与 Nil 指向的代码不同，因此您可以通过这种方式进行区分。

您可能会考虑一个相关的事情：如何仅使用函数来实现 cons 列表，而type语言中没有显式定义新类型的工具？事实证明，这可以通过一种相当机械的方式对任何数据类型完成，即通过将值表示为函数，其中该函数需要函数作为参数，该类型的每个构造函数都有一个参数。第 n 个参数表示“如果该值属于第 n 个构造函数，我想要做什么”，并且它需要构造函数的每个字段一个参数，以便您获取其字段中的值。

这在散文中有点难以理解，所以让我们看一个使用 cons 和 nil 的示例。我将使用我更熟悉的 Haskell 表示法，但相同的想法应该可以在 OCaml 中表达。在教学上我不满意的一个部分是一开始的新类型。通过定义新的数据类型看起来像是“作弊”，但只有在类型级别才有必要，作为避免无限类型的间接级别。在术语层面上，它只是函数的包装。

{-# LANGUAGE RankNTypes #-}

import Prelude hiding (head, tail, last)

newtype List a = List
   (forall r. -- Client can choose any return type
     r -> -- Value to return in case of Nil
     (a -> List a -> r) -> -- Called with Cons's two fields
     r) -- The result

nil :: List a
nil = List (\n c -> n)

cons :: a -> List a -> List a
cons h t = List (\n c -> c h t)

head :: List a -> Maybe a
head (List list) = list Nothing (\h t -> Just h)

tail :: List a -> Maybe (List a)
tail (List list) = list Nothing (\h t -> Just t)

nil和cons是该类型的构造函数， 和head是tail示例简单消费者。观察nil是由一个仅返回其第一个参数的函数表示的，而cons是由一个将其头部和尾部传递给第二个参数的函数表示的。head并tail演示如何使用列表：每个人都必须调用他们的列表，向其传递两个参数来分别描述他们想要如何处理空列表和非空列表。

我们将如何实施您的last？当然，递归地：

last :: List a -> Maybe a
last (List list) = list Nothing (\h t -> Just (go h t))
  where go :: a -> List a -> a
        go curr (List rest) = rest curr go

这个练习的目的是表明，具有多个构造函数或字段的数据类型从根本上来说没有什么特别之处——它们都可以被视为闭包和函数的语法糖。任何真正的语言实现都不会像我的示例那样粗糙，但 STG 机器将每个值视为函数的方法在某些方面只是这个想法的（更）更复杂的实现。

如果您研究过面向对象语言的设计模式，这个想法可能看起来非常熟悉：这就是访问者模式！这并非偶然：访问者模式类似于模式匹配。您可以使用它来模拟没有模式匹配的语言。