在OCaml中解析Packrat(通过懒惰进行记忆)

Question

我正在按照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

解析符号列表的(not-memoized)函数是:

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';])]

Answer 1

使用延迟进行memoization的想法不是使用函数,而是使用数据结构来进行memoization.懒惰意味着当你写作时let x = foo in some_expr,foo不会立即进行评估,只会根据some_expr需要进行评估,但是不同的xin some_expr会出现共享同一个trunk:只要其中一个强制计算,结果就可以被所有人使用.

这不适用于函数:如果你编写let f x = foo in some_expr并f多次调用some_expr,那么每个调用都将被独立评估,没有共享的thunk来存储结果.

因此,您可以通过使用数据结构而不是函数来获取memoization.通常,这是使用关联数据结构完成的:您不是计算a -> b函数,而是计算a Table a b,其中Table是从参数到结果的一些映射.一个例子是这个关于斐波纳契的Haskell演示:

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

(你也可以用tail和写它zip,但这并不能说清楚.)

看到你没有记住一个函数,而是一个列表:它是fibTable执行memoization 的列表.您也可以在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是否尚未尝试过.

懒惰是一种很好的方式来呈现这种记忆,但并不总是表达得足够的:如果你需要部分释放结果缓存的某些部分来降低内存使用量,那么如果你从一个懒惰的演示文稿开始就会遇到困难.有关此内容的评论,请参阅此博客文章.