Расширение неизменяемых типов (или: быстрый кеш для неизменяемых типов) в OCaml - PullRequest
Новая
       22

Расширение неизменяемых типов (или: быстрый кеш для неизменяемых типов) в OCaml

5 голосов
/ 03 февраля 2012

У меня есть рекурсивная неизменяемая структура данных в 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, иногда более одного раза для одного и того же выражения, а иногда длявыражения, которые недавно были сопоставлены с использованием шаблона 

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

Теперь функция результата очень легкая, но многократный запуск ее для глубокого AST не будет очень оптимизирован.Я знаю, что могу кэшировать значение, используя Hashtbl, но AFAIK Hashtbl будет выполнять только структурное равенство, поэтому ему все равно придется пересекать мой длинный AST.Я знаю, что лучшим вариантом будет включение, вероятно, неизменяемого поля «результат» в тип expr.Но я не могу.

Так есть ли в Ocaml способ кэшировать значение для неизменяемого типа, поэтому мне не нужно вычислять его с нетерпением каждый раз, когда мне это нужно?

Спасибо!

Ответы [ 3 ]

5 голосов
/ 03 февраля 2012

хеш-минусы значения expr_expr.Делая это структурно равными значениями в вашей программе, вы будете использовать одно и то же представление памяти, и вы можете заменить структурное равенство (=) физическим равенством (==).

Эта бумага поможет вам быстро начать работу с хэшем в OCaml.

4 голосов
/ 03 февраля 2012

Вы можете использовать функторный интерфейс для управления типом равенства, используемым хеш-таблицей.Я считаю, что семантика (==) является законной для ваших целей;т. е. если A == B, то f A = f B для любой чистой функции f.Таким образом, вы можете кэшировать результаты f A. Тогда, если вы найдете B, физически равный A, кэшированное значение будет правильным для B.

Недостатком использования (==) для хеширования является то, что хешФункция отправит все структурно равные объекты в одну и ту же корзину, где они будут обрабатываться как отдельные объекты.Если у вас есть много структурно равных объектов в таблице, вы не получите никакой выгоды от хеширования.Поведение переходит в линейный поиск.

Вы не можете определить хеш-функцию для работы с физическими адресами, потому что сборщик мусора может в любое время изменить физические адреса.

Однако, если вы знаете, что ваша таблица будет содержать только относительно немного больших значений, использование физического равенства может работать для вас.

1 голос
/ 04 февраля 2012

Я думаю, что вы можете объединить две идеи, описанные выше: использовать методы, подобные хеш-методу, чтобы получить хэш части «чистого выражения» ваших данных, и использовать этот хеш как ключ в таблице памяток для 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
...