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の異なる出現は同じトランクを共有します: それらの1つが計算を強制するとすぐに、結果はそれらすべてに利用可能です. .xsome_expr

これは関数では機能しません: を書いてlet f x = foo in some_exprでf数回some_expr呼び出すと、各呼び出しは個別に評価され、結果を格納するための共有サンクはありません。

したがって、関数の代わりにデータ構造を使用してメモ化できます。通常、これは連想データ構造を使用して行われa -> bます。関数を計算する代わりに、 を計算しますTable a b。ここで、Tableは引数から結果への何らかのマップです。1 つの例は、フィボナッチの次の Haskell プレゼンテーションです。

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

tail(これをandで書くこともできますが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 は call-by-need 評価を特に好んでいません。実際には、直接変更によってキャッシュ構造を直接書き込むのも同様に簡単です。

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)ルールを試行した結果、またはこれがまだ試行されていない場合を表します。JuxtanNone

怠惰は、この種のメモ化を提示するための優れた方法ですが、常に十分に表現力があるとは限りません。たとえば、結果キャッシュの一部を部分的に解放してメモリ使用量を減らす必要がある場合、怠惰なプレゼンテーションから開始すると問題が発生します。 . これに関するコメントについては、このブログ投稿を参照してください。

于 2012-05-14T13:49:10.063 に答える
1

関数をメモ化したいのはなぜですか？メモ化したいのは、入力ストリーム内の特定の (解析) 式と特定の位置の解析結果だと思います。たとえば、そのために Ocaml の Hashtables を使用できます。

于 2012-05-14T13:39:47.037 に答える
0

怠惰なキーワード。

ここでは、いくつかの素晴らしい例を見つけることができます。

ユースケースに適合する場合は、サンクを手動で生成する代わりに OCaml ストリームを使用することもできます。

于 2012-05-14T06:30:44.013 に答える