扩展不变类型（或：恒定类型快速缓存）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 

现在假设我映射到另一个表达式，我需要不断地检查一个expr的结果，有时不止一次同EXPR，有时为表达式最近使用模式

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

现在映射，结果功能是非常轻巧，但运行它多次为深AST不会非常优化。我知道我可以使用Hashtbl来缓存这个值，但是AFAIK Hashtbl只会做结构上的平等，所以它无论如何都需要遍历我的长期AST。 我知道最好的选择是在expr类型中包含一个可能不可变的“结果”字段。但我不能。

那么Ocaml有什么方法可以将一个值缓存到一个不可变的类型，所以我不需要每次需要时都急切地计算它呢？

谢谢！

Answer 1

您可以使用函子接口来控制散列表使用的相等类型。我相信（==）的语义对您而言是合法的;即如果A == B，则对于任何纯函数f，f A = f B。所以你可以缓存fA的结果。然后如果你发现一个物理上等于A的B，缓存的值对于B是正确的。

使用（==）散列的缺点是散列函数会将所有结构相同的对象发送到同一个哈希桶，在这里它们将被视为不同的对象。如果表格中有许多结构相同的对象，则散列法不会从中受益。行为退化为线性搜索。

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

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

Answer 2

哈希值为expr_expr。通过这样做，程序中结构相同的值将共享完全相同的内存表示，并且可以用物理相等（==）替代结构相等（=）。

这个paper应该让你快速开始在OCaml的散列考虑。

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