如何缓存 AST 的哈希码？

Question

我正在使用 F# 开发一种语言，经过测试，我发现运行时 90% 以上的时间都用于比较是否相等。因此，该语言太慢以至于无法使用。在检测期间，GetHashCode 函数作为开销来源在列表中显示得相当靠前。发生的事情是，在方法调用期间，我使用方法体 (Expr) 以及调用参数作为字典中的键，这会触发对 AST 段的重复遍历。

为了提高性能，我想在 AST 中添加记忆节点。

type Expr =
| Add of Expr * Expr
| Lit of int
| HashNode of int * Expr

在上面的简化示例中，我想要的是 HashNode 表示其 Expr 的散列，这样 GetHashCode 就不必为了顺序在 AST 中走得更深计算它。

话虽如此，我不确定应该如何覆盖 GetHashCode 方法。理想情况下，我想重用内置的哈希方法并使其仅以某种方式忽略 HashNode，但我不确定该怎么做。

更有可能的是，我将不得不制作自己的哈希函数，但不幸的是我对哈希函数一无所知，所以我现在有点迷茫。

我的另一个想法是用唯一 ID 替换节点，同时保持哈希函数不变，但这会给代码带来额外的复杂性，我宁愿避免，除非我必须这样做。

Answer 1

我最近在 TheGamma (GitHub) 中需要一个类似的东西，在那里我构建了一个经常重新创建的依赖图（有点像 AST）（当你在编辑器中更改代码并重新解析时） )，但我有实时预览，可能需要一些时间来计算，所以我想尽可能多地重用以前的图表。

我这样做的方式是将 "symbol" 附加到每个节点。具有相同符号的两个节点相等，我认为您可以使用它来进行有效的相等性测试：

type Expr =
  | Add of ExprNode * ExprNode
  | Lit of int

and ExprNode(expr:Expr, symbol:int) = 
  member x.Expression = expr
  member x.Symbol = symbol
  override x.GetHashCode() = symbol
  override x.Equals(y) = 
    match y with 
    | :? ExprNode as y -> y.Symbol = x.Symbol
    | _ -> false

我保留了一个节点缓存 - 关键是节点类型的一些代码（0 代表 Add，1 代表 Lit，等等）和所有嵌套节点的符号。对于文字，我还添加了数字本身，这意味着两次创建相同的文字会得到相同的节点。所以创建一个节点看起来像这样：

let node expr ctx =  
  // Get the key from the kind of the expression
  // and symbols of all nested node in this expression
  let key = 
    match expr with 
    | Lit n -> [0; n]
    | Add(e1, e2) -> [1; e1.Symbol; e2.Symbol]
  // Return either a node from cache or create a new one
  match ListDictionary.tryFind key ctx with
  | Some res -> res
  | None ->
      let res = ExprNode(expr, nextId())
      ListDictionary.set key res ctx
      res

ListDictionary 模块是一个可变字典，其中键是一个整数列表，nextId 是生成下一个 ID 的常用函数：

type ListDictionaryNode<'K, 'T> = 
  { mutable Result : 'T option
    Nested : Dictionary<'K, ListDictionaryNode<'K, 'T>> }

type ListDictionary<'K, 'V> = Dictionary<'K, ListDictionaryNode<'K, 'V>>

[<CompilationRepresentation(CompilationRepresentationFlags.ModuleSuffix)>]
module ListDictionary = 
  let tryFind ks dict = 
    let rec loop ks node =
      match ks, node with
      | [], { Result = Some r } -> Some r
      | k::ks, { Nested = d } when d.ContainsKey k -> loop ks (d.[k])
      | _ -> None
    loop ks { Nested = dict; Result = None }

  let set ks v dict =
    let rec loop ks (dict:ListDictionary<_, _>) = 
      match ks with
      | [] -> failwith "Empty key not supported"
      | k::ks ->
          if not (dict.ContainsKey k) then 
            dict.[k] <- { Nested = Dictionary<_, _>(); Result = None }
          if List.isEmpty ks then dict.[k].Result <- Some v
          else loop ks (dict.[k].Nested)
    loop ks dict


let nextId = 
  let mutable id = 0
  fun () -> id <- id + 1; id

所以，我想我是说您需要实施自己的缓存机制，但这对我来说效果很好，并且可能会提示如何在您的情况下执行此操作！

如何缓存 AST 的哈希码？

How do I cache hash codes for an AST?

compiler-construction

hash

f#

memoization

abstract-syntax-tree