2

根据 B. Ford 的硕士论文，我正在 OCaml 中实现一个 packrat 解析器。 我的解析器应该接收一个表示语言语法的数据结构并解析给定的符号序列。

我被记忆部分困住了。原始论文使用 Haskell 的惰性求值来实现线性时间复杂度。我想在 OCaml 中执行此操作（通过惰性进行记忆），但不知道该怎么做。

那么，如何通过 OCaml 中的惰性求值来记忆函数呢？

编辑：我知道什么是惰性评估以及如何在 OCaml 中利用它。问题是如何使用它来记忆函数。

编辑：我写的代表语法的数据结构是：

type ('a, 'b, 'c) expr =
| Empty of 'c
| Term of 'a * ('a -> 'c)
| NTerm of 'b
| Juxta of ('a, 'b, 'c) expr * ('a, 'b, 'c) expr * ('c -> 'c -> 'c)
| Alter of ('a, 'b, 'c) expr * ('a, 'b, 'c) expr
| Pred of ('a, 'b, 'c) expr * 'c
| NPred of ('a, 'b, 'c) expr * 'c
type ('a, 'b, 'c) grammar = ('a * ('a, 'b, 'c) expr) list

解析符号列表的（未记忆的）函数是：

let rec parse g v xs = parse' g (List.assoc v g) xs
and parse' g e xs =
  match e with
  | Empty y -> Parsed (y, xs)
  | Term (x, f) ->
     begin
       match xs with
       | x' :: xs when x = x' -> Parsed (f x, xs)
       | _ -> NoParse
     end
  | NTerm v' -> parse g v' xs
  | Juxta (e1, e2, f) ->
     begin
       match parse' g e1 xs with
       | Parsed (y, xs) ->
          begin
            match parse' g e2 xs with
            | Parsed (y', xs) -> Parsed (f y y', xs)
            | p -> p
          end
       | p -> p
     end
( and so on )

其中 parse 的返回值的类型定义为

type ('a, 'c) result = Parsed of 'c * ('a list) | NoParse

例如，基本算术表达式的语法可以指定为g，在：

type nt = Add | Mult | Prim | Dec | Expr
let zero _  = 0
let g =
  [(Expr, Juxta (NTerm Add, Term ('$', zero), fun x _ -> x));
   (Add, Alter (Juxta (NTerm Mult, Juxta (Term ('+', zero), NTerm Add, fun _ x -> x), (+)), NTerm Mult));
   (Mult, Alter (Juxta (NTerm Prim, Juxta (Term ('*', zero), NTerm Mult, fun _ x -> x), ( * )), NTerm Prim));
   (Prim, Alter (Juxta (Term ('<', zero), Juxta (NTerm Dec, Term ('>', zero), fun x _ -> x), fun _ x -> x), NTerm Dec));
   (Dec, List.fold_left (fun acc d -> Alter (Term (d, (fun c -> int_of_char c - 48)), acc)) (Term ('0', zero)) ['1';'2';'3';])]
4

3 回答 3

6

使用惰性进行记忆的想法不是使用函数，而是使用数据结构进行记忆。懒惰意味着当你写let x = foo in some_expr,foo时不会立即被评估，而只是在需要时评估，但是insome_expr的不同出现将共享同一个主干：一旦其中一个强制计算，结果对所有人都可用.xsome_expr

这不适用于函数：如果您在 中编写let f x = foo in some_expr和调用f多次some_expr，那么每个调用都将独立评估，没有共享的 thunk 来存储结果。

所以你可以通过使用数据结构而不是函数来获得记忆。通常，这是使用关联数据结构完成的：不是计算a -> b函数，而是计算 a Table a b，其中Table是从参数到结果的一些映射。一个例子是斐波那契的 Haskell 演示：

fib n = fibTable !! n
fibTable = [0,1] ++ map (\n -> fib (n - 1) + fib (n - 2)) [2..]

（你也可以用tailand来写zip，但这并不能说明问题。）

请注意，您不是记忆一个函数，而是一个列表：它是执行记忆的列表fibTable。您也可以在 OCaml 中编写此代码，例如使用Batteries库的 LazyList 模块：

open Batteries
module LL = LazyList

let from_2 = LL.seq 2 ((+) 1) (fun _ -> true)

let rec fib n = LL.at fib_table (n - 1) + LL.at fib_table (n - 2)
and fib_table = lazy (LL.Cons (0, LL.cons 1 <| LL.map fib from_2))

然而，这样做并没有什么兴趣：正如您在上面的示例中看到的那样，OCaml 并不特别支持按需调用评估——它使用起来很合理，但不是很方便，因为它被迫在 Haskell 中使用。其实直接用直接变异的方式写缓存结构也同样简单：

open Batteries

let fib =
  let fib_table = DynArray.of_list [0; 1] in
  let get_fib n = DynArray.get fib_table n in
  fun n ->
    for i = DynArray.length fib_table to n do
      DynArray.add fib_table (get_fib (i - 1) + get_fib (i - 2))
    done;
    get_fib n

这个例子可能选择不当，因为你需要一个动态的结构来存储缓存。在 packrat 解析器案例中，您正在对已知输入文本进行制表解析，因此您可以使用普通数组（由语法规则索引）：('a, 'c) result option对于每个规则，您将有一个数组，其大小为输入长度并已初始化到None. 例如。juxta.(n)表示Juxta从输入位置尝试规则的结果n，或者None如果尚未尝试。

Lazyness 是呈现这种记忆的好方法，但并不总是足够表达：如果您需要部分释放结果缓存的某些部分以降低内存使用率，如果您从惰性呈现开始，您将遇到困难. 请参阅此博客文章以获取对此的评论。

于 2012-05-14T13:49:10.063 回答
1

为什么要记忆函数？我相信，您要记住的是给定（解析）表达式和输入流中给定位置的解析结果。例如，您可以为此使用 Ocaml 的 Hashtables。

于 2012-05-14T13:39:47.037 回答
0

懒惰的关键字。

在这里你可以找到一些很好的例子。

如果它适合您的用例，您还可以使用 OCaml 流而不是手动生成 thunk。

于 2012-05-14T06:30:44.013 回答