Ampliación de tipos inmutables (o: caché rápida de tipos inmutables) en OCaml

Question

que tienen una estructura recursiva inmutable de datos en ocaml que se puede simplificar a algo como esto:

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) 

Es una AST, y a veces se pone bastante complejo (es muy profundo).

hay una función recursiva que evalúa una expresión. Por ejemplo, digamos que,

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 

Supongamos ahora que estoy mapeo de una expresión a otra expresión, y tengo que comprobar constantemente el resultado de una expr, a veces más de una vez por el mismo expr, y, a veces por expresiones que recientemente fueron asignadas utilizando el patrón

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

Ahora, la función de resultado es muy ligero, pero el funcionamiento es muchas veces para un AST profunda no será muy optimizado. Sé que podría almacenar en caché el valor usando un Hashtbl, pero AFAIK el Hashtbl solo hará igualdad estructural, por lo que tendrá que recorrer mi AST largo de todos modos. Sé que la mejor opción sería incluir un campo de "resultados" probablemente inmutables en el tipo expr. Pero no puedo.

Entonces, ¿hay alguna forma en Ocaml de almacenar en caché un valor de tipo inmutable, por lo que no tengo que calcularlo ansiosamente cada vez que lo necesito?

Gracias!

Answer 1

Puede usar la interfaz funcional para controlar el tipo de igualdad utilizada por la tabla hash. Creo que la semántica de (==) es legítima para sus propósitos; es decir, si A == B entonces f A = f B para cualquier función pura f. Para que pueda almacenar en caché los resultados de f A. Luego, si encuentra una B que es físicamente igual a A, el valor en caché es correcto para B.

La desventaja de usar (==) para el hash es que la función hash envíe todos los objetos estructuralmente iguales al mismo cubo de hash, donde se tratarán como objetos distintos. Si tiene muchos objetos estructuralmente iguales en la tabla, no obtendrá ningún beneficio del hash. El comportamiento degenera a una búsqueda lineal.

No puede definir la función hash para trabajar con direcciones físicas, ya que el recolector de elementos no utilizados puede cambiar las direcciones físicas en cualquier momento.

Sin embargo, si sabe que su tabla solo contendrá relativamente pocos valores de gran tamaño, la igualdad física podría funcionar para usted.

Answer 2

Hash-cons los valores de expr_expr. Al hacer esto, los valores estructuralmente iguales en su programa compartirán exactamente la misma representación de memoria y puede sustituir la igualdad estructural (=) por la igualdad física (==).

Este paper debería ayudarle a comenzar rápidamente con el hash-consing en OCaml.

Answer 3

Creo que puede unir las dos ideas anteriores: use técnicas similares a hash-consing para obtener el hash de la parte de "pure expression" de sus datos, y use este hash como clave en la tabla de memoizaciones para la función eval .

Por supuesto, esto solo funciona cuando la función eval solo depende de la función de "expresión pura" de la función, como en el ejemplo que proporcionó.Creo que es un caso relativamente general, al menos si se limita a almacenar las evaluaciones exitosas (que, por ejemplo, no arrojarán un error que incluya cierta información de ubicación).

Editar: una pequeña prueba de concepto:

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