在OCaml中扩展不可变类型（或：不可变类型的快速缓存）

Question

我在OCaml中有一个递归的不可变数据结构，可以简化为以下内容：

type expr =
{
    eexpr : expr_expr;
    some_other_complex_field : a_complex_type;
}

and expr_expr =
    | TInt of int
    | TSum of (expr * expr)
    | TMul of (expr * expr)

这是一个AST（抽象语法树），有时它会变得相当复杂（非常深）。

有一个递归函数来评估表达式。例如，假设：

let rec result expr =
    match expr.eexpr with
        | TInt i -> i
        | TSum (e1, e2) -> result e1 + result e2
        | TMul (e1, e2) -> result e1 * result e2

现在假设我正在将一个表达式映射到另一个表达式，并且我需要不断检查一个表达式的结果，有时需要多次检查相同的表达式，有时需要检查最近使用模式映射的表达式。

{ someExpr with eexpr = TSum(someExpr, otherExpr) }

现在，结果函数非常轻量级，但对于深层AST的多次运行并不是很优化。我知道可以使用Hashtbl缓存值，但据我所知，Hashtbl只会进行结构相等性检查，因此它仍然需要遍历我的长AST。我知道最好的选择是在expr类型中包含一个可能是不可变的“result”字段。但我不能这样做。

那么，在Ocaml中是否有一种方法可以将值缓存到不可变类型中，以便每次需要时不必急切地计算它？

谢谢！

- Waneck

Answer 1

对expr_expr的值进行哈希共享。通过这样做，程序中结构相等的值将共享完全相同的内存表示，您可以通过物理相等性(==)替换结构相等性(=)。

这篇论文可以帮助您快速开始在OCaml中进行哈希共享。

- Daniel Bünzli

---

Hash-cons是一个很棒的功能！我不知道它的存在！但是我的AST有一些非常复杂的值，比如我提到的“a_complex_type”。它有惰性值、函数，通常没有办法用结构相等来比较a_complex_type。在这种情况下，Hash-cons会起作用吗？ - Waneck

此外，在我的 AST 中（它还包含位置信息），很可能找不到相同的值，但当我使用 { expr with eexpr =TAdd(expr, otherExpr) } 结构时，似乎 has-cons 是不必要的。但这是一篇很好、有启发性的论文。谢谢！ 现在，我已经阅读了 ocaml 物理相等性在不可变结构上具有未定义行为的内容。像 Jeffrey 建议的那样，在没有 has-cons 的情况下使用它是否安全？这应该就足够了！ - Waneck

关于您的类型比那个更复杂的事实，如果所有成分都可以用哈希共享构造器构建，那就不是问题。位置信息实际上是有问题的。如果没有它，您可以轻松地使用弱哈希表来记忆化“result”函数，也可以用于递归调用的中间结果。 - Daniel Bünzli

是的，我希望我能改变结构来使用哈希共享！但真的非常感谢您的建议！ - Waneck

Answer 2

您可以使用函数接口来控制哈希表所使用的相等性类型。我认为（==）的语义对您的目的是合法的，即如果A == B，则对于任何纯函数f，都有f A = f B。因此，您可以缓存f A的结果。然后，如果您找到一个与A物理上相等的B，则缓存的值对B是正确的。

使用（==）进行哈希的缺点是哈希函数将所有结构相等的对象发送到同一哈希桶中，在那里它们将被视为不同的对象。如果表中有许多结构相等的对象，则无法从哈希中获得任何好处。行为退化为线性搜索。

您无法定义哈希函数以处理物理地址，因为垃圾回收器随时可以更改物理地址。

但是，如果您知道您的表只包含相对较少的大型值，则使用物理相等可能适用于您。

- Jeffrey Scofield

---

感谢Jeffrey的出色回复！所以我很可能可以使用List和一个函数来实现相同的行为，这个函数将使用==查找列表，对吗？我在ocaml手册上读到，对于不可变结构，物理等式有未定义的行为，尽管当A == B时，A = B是被保证的（当然）。当我使用模式{ expr with eexpr = TAdd(expr, otherExpr) }时，能否保证在TAdd（thisExpr，_）中，thisExpr == expr？ - Waneck

哈希表比列表更好，因为它会通过近似结构相等（即通常的哈希函数）将其排序到桶中。除非您所有的值都是结构相等的，否则这比仅使用一个列表要好。（您可以定制哈希函数以查看最常见的差异部分）。就像我说的那样，我认为对于不可变值的（==）语义对于您的目的来说是可以的。没有强烈的保证是什么（==）到什么，运行时允许对纯值进行任意聪明的操作（FP如此酷的原因之一）。但我会说，在实践中是可以的。 - Jeffrey Scofield

我在考虑可能使用一个位置的Hashtbl，然后进行线性搜索。这对我的情况来说是最好的选择，但遗憾的是它是非常特定于我正在工作的应用程序设计的东西。 - Waneck

哈希函数不必遍历整个结构。它只是一个近似值。事实上，预定义的哈希函数并不遍历整个结构。你可以编写一个哈希函数，它可以执行任何你想要的操作（通过函子接口）。它只需要遵守明显的语义（通过你的相等函数比较相等的两个值必须哈希到相同的值）。 - Jeffrey Scofield

太好了，我知道了！但是因为我的数据（位置）相当独特，所以我想我会实现自己的哈希函数！所以我将使用“==”编写相等函数，并使用位置数据编写哈希函数！谢谢！ - Waneck

Answer 3

我认为你可以将上述两个想法合并起来：使用类似哈希共享的技术来获取数据中“纯表达式”部分的哈希值，并将此哈希作为键存储在eval函数的记忆化表中。

当然，这仅适用于您的eval函数确实只依赖于函数的“纯表达式”部分，就像您给出的示例一样。我相信这是一个相对普遍的情况，至少如果您限制自己存储成功的评估（例如，不会返回包含某些位置信息的错误）。

编辑：一个小的概念证明：

type 'a _expr =
  | Int of int
  | Add of 'a * 'a

(* a constructor to avoid needing -rectypes *)
type pure_expr = Pure of pure_expr _expr

type loc = int
type loc_expr = {
  loc : loc;
  expr : loc_expr _expr;
  pure : pure_expr (* or any hash_consing of it for efficiency *)
}

(* this is where you could hash-cons *)
let pure x = Pure x

let int loc n =
  { loc; expr = Int n; pure = pure (Int n) }
let add loc a b =
  { loc; expr = Add (a, b); pure = pure (Add(a.pure, b.pure)) }

let eval =
  let cache = Hashtbl.create 251 in
  let rec eval term =
    (* for debug and checking memoization *)
    Printf.printf "log: %d\n" term.loc;
    try Hashtbl.find cache term.pure with Not_found ->
      let result =
        match term.expr with
          | Int n -> n
          | Add(a, b) -> eval a + eval b in
      Hashtbl.add cache term.pure result;
      result
  in eval



let test = add 3 (int 1 1) (int 2 2)
# eval test;;
log: 3
log: 2
log: 1
- : int = 3
# eval test;;
log: 3
- : int = 3

- gasche

---

这是一个好的建议，但不幸的是按照我的数据存储方式，我认为我无法将纯表达式与大部分唯一数据分离开来，因为它们是相互递归的结构。 - Waneck

@Waneck：我添加了一个小的实现来进行分离，以展示我的想法。 - gasche