Skip to content

Instantly share code, notes, and snippets.

@marihachi

marihachi/gll.md

Created February 16, 2022 15:09
Download ZIP

Revisions

  1. marihachi created this gist Feb 16, 2022.
    454 changes: 454 additions & 0 deletions gll.md
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,454 @@
    https://epsil.github.io/gll/ の一部の翻訳です。(Google翻訳)

    # Continuation-passing style

    これまで、多くの文法をプログラムに直接翻訳できるという事実を利用してきました。このようなプログラムは、文字列照合のレベルまで関数を呼び出す関数を備えた、単純な階層構造になります。単一の結果を返すか、まったく結果を返さないかのいずれかです。

    ただし、すべての文法がこれほど単純なわけではありません。再帰を導入すると、文法が明確に定義されている場合でも、文法が終了プログラムに変換される保証はありません。さらに、文法があいまいになる可能性があります。いくつかの一致する選択肢がある場合、文字列は複数の等しく有効な方法で解析できます。簡単にするために、altコンビネータは単一の結果（最初に一致した結果）のみを返しました。より完全な実装では、一連の結果が返されます。

    これらの問題に対処するために、パーサーをより柔軟な方法で書き直して表現します。継続渡しスタイルです。パーサーに結果を呼び出し元に返す代わりに、パーサーは結果を継続に渡します。その後、継続は構文解析を続行します。すべてのパーサーには、結果を渡す継続についての追加の引数があります。継続自体は1つの引数の関数です。 （Racketには実際にはネイティブの継続がありますが、実装をより移植性の高いものにするために、継続として関数を使用します。）

    成功関数を書き直すことから始めましょう。元の定義を思い出してください。

    ```
    (define (succeed val)
    (lambda (str)
    (success val str)))
    ```

    返されたパーサーを継続渡しスタイルに変換するために、2番目の引数 `cont`を追加します。 解析結果を返す代わりに、それを `cont`に渡します:

    ```
    (define (succeed val)
    (lambda (str cont)
    (cont (success val str))))
    ```

    パーサーを使用するには、継続を提供する必要があります。 1つの引数の任意の関数で実行できます。 たとえば、 `print`を使用すると、結果が標準出力に出力されます:

    ```
    > ((succeed '()) "foo" print)
    (success '() "foo")
    ```

    もちろん、これは少し面倒なので、最終バージョンでは、パーサーを呼び出すためのより単純なインターフェースを提供します。 今のところ、 `string`で進めます:

    ```
    (define (string match)
    (lambda (str cont)
    (let* (...)
    (if (equal? head match)
    (cont (success head tail))
    (cont (failure tail))))))
    ```

    これまでの定義は、元の定義と非常によく似ています。 ただし、 `seq`コンビネータの場合、` bind`の定義を変更する必要があります:

    ```
    (define (bind p fn)
    (lambda (str cont)
    (p str (lambda (result)
    (match result
    [(success val rest)
    ((fn val) rest cont)]
    [failure
    (cont failure)])))))
    (define (seq a b)
    (bind a (lambda (x) ...)))
    ```

    ここでは、継続を使用して物事を連鎖させます。 パーサー `p`は、結果を受け取り、それと照合する継続（lambda（result）...）で呼び出されます。 成功すると、継続が続行され、 `fn`が呼び出されます。 最終結果は、結合されたパーサーの続きである `cont`に渡されます。 便利なことに、変更する必要があるのは `bind`だけです。 `seq`の定義は変更されていません。

    別のスタイルで表現されていますが、これまでのすべてのコードは以前と同じように機能します。 ただし、 `alt`コンビネータについては、セマンティクスを変更します。 これで、すべての選択肢を試し、並行して分岐します:

    ```
    (define (alt a b)
    (lambda (str cont)
    (a str cont)
    (b str cont)))
    ```

    継続は2回呼び出されます。1回は最初のパーサー用で、もう1回は2番目のパーサー用です。最初のパーサーが成功し、2番目が失敗した場合、継続は最初に成功した結果を受け取り、次に失敗した結果を受け取ります。

    これで、パーサーが継続渡しスタイルに書き直されました。これ自体は、再帰的な文法で発生した問題を解決するものではありませんが、解決策の準備を整えます。 altコンビネータは2つの結果を生成しますが、同時にそれらを通過しないことに注意してください。実行はよりきめ細かくなります。コンビネータは、各結果を計算するための個別のブランチを作成します。

    言い換えると、ここには一種の並行性があります（現在の実装がシーケンシャルであっても）。重要な洞察は、再帰文法では、あるブランチが別のブランチに依存している可能性があるということです。再帰ブランチは、ベースブランチが結果を生成するまで続行できません。実行順序に関係なく、ブランチを連携させる方法はありますか？

    結局のところ、答えはメモ化です！これは、継続渡しスタイル関数をメモ化するときに、入力値と出力値だけでなく、それらの値に関心のある継続も追跡するためです。各テーブルエントリには、結果のリスト（関数が複数の値を出力する可能性があるため）と継続のリスト（同じ関数が異なる場所で呼び出される可能性があるため）が含まれます。

    したがって、文法のあるブランチから別のブランチに結果をブロードキャストして、関心のあるブランチを「目覚めさせる」ことができます。どうすればブランチを目覚めさせることができますか？その続きを呼ぶことによって！実際、同じ継続が再帰文法で数回呼び出される場合があります。これについては、以下で説明します。ビデオゲームのように、各継続はプログラムの「保存ポイント」であり、知識が進むにつれてその一部をリロードできます。

    継続渡しスタイルで記述された関数をメモ化するために、memo-cpsラッパーを定義します。わかりやすくするために、いくつかのローカル関数を定義します。プッシュ継続！エントリに継続を追加し、push-result！結果をエントリに追加します。エントリに特定の結果がすでに含まれているかどうかを確認し、make-entryは空のエントリを作成し、table-refはメモ化エントリを検索して、存在しない場合は空のエントリを作成します。

    ```
    (define (memo-cps fn)
    (let ((table (mlist)))
    (define entry-continuations mcar)
    (define entry-results mcdr)
    (define (push-continuation! entry cont)
    (set-mcar! entry (mcons cont (entry-continuations entry))))
    (define (push-result! entry result)
    (set-mcdr! entry (mcons result (entry-results entry))))
    (define (result-subsumed? entry result)
    (mmember result (entry-results entry)))
    (define (make-entry)
    (mcons (mlist) (mlist)))
    (define (table-ref str)
    (match (massoc str table)
    [(mcons str entry) entry]
    [_ (let ((entry (make-entry)))
    (set! table (mcons (mcons str entry) table))
    entry)]))
    (lambda (str cont)
    (let ((entry (table-ref str)))
    (match entry
    ;; first time memoized procedure has been called with str
    [(mcons (mlist) (mlist))
    (push-continuation! entry cont)
    (fn str (lambda (result)
    (unless (result-subsumed? entry result)
    (push-result! entry result)
    (for ((cont (entry-continuations entry)))
    (cont result)))))]
    ;; memoized procedure has been called with str before
    [_
    (push-continuation! entry cont)
    (for ((result (entry-results entry)))
    (cont result))])))))
    ```

    考慮すべき2つのケースがあります。メモ化された関数が初めて呼び出されたときと、以前に呼び出されたときです。関数が初めて呼び出されると、元の継続contがテーブルに挿入されます。次に、カスタム継続（lambda（result）...）を使用して関数を呼び出します。これにより、contと、その間にテーブルに挿入された可能性のある他の継続が呼び出されます。継続（ラムダ（結果）...）は、「内側の人」と考えることができます。それだけで、関数に渡されてその結果を受け取る作業を行います。次に、それらの結果を外部の続きにブロードキャストします。

    したがって、関数が以前に呼び出された2番目のケースでは、継続のリストに継続を挿入するだけです。その後、私たちの「内部の人間」は、新しい結果が生成されたときにその継続を通知します。その間、継続はすでにメモ化された結果を通過し、その後「スリープ状態になります」。

    これで、定義をメモ化する準備が整いました。通常の関数である、返されるパーサーにはmemo-cpsを使用し、パーサーコンビネーターにはmemoを使用します。以前と同様に、delay-parserは実行時にコンビネータが呼び出されるのを遅らせるため、メモを使用する必要があります。

    ```
    (define succeed
    (memo
    (lambda (val)
    (memo-cps
    (lambda (str cont) ...)))))
    (define string
    (memo
    (lambda (match)
    (memo-cps
    (lambda (str cont) ...)))))
    (define seq
    (memo
    (lambda (a b)
    (memo-cps
    (bind a (lambda (x) ...))))))
    (define alt
    (memo
    (lambda (a b)
    (memo-cps
    (lambda (str cont) ...)))))
    ```

    これで、左再帰文法を定義できます:

    ```
    (define-parser s
    (alt (seq s (string "a"))
    (string "a")))
    ```

    文字列「aaa」を解析してみましょう:

    ```
    > (s "aaa" print)
    (success "a" "aa")
    (success '("a" "a") "a")
    (success '(("a" "a") "a") "")
    (failure "")
    ```

    パーサーが文字列の最後に到達して失敗で終了する前に、3つの結果が得られます。 これにより、継続がどのように繰り返されるかを確認できます。（seq s ...）の自己参照が検出されると、sが以前に呼び出されたため、ブランチは「スリープ状態になります」。 次に、2番目のブランチが単一の「a」と一致します。 これはsの結果の1つであるため、標準出力に出力されますが、最初のブランチにもブロードキャストされます。 その分岐は別の「a」と一致し、結合されたシーケンスはsの別の結果になります。 結果は再び印刷され、文字列の最後に到達するまで最初のブランチにブロードキャストされます。

    ここで、パーサーを呼び出すためのより便利なインターフェースを定義しましょう。 run-parser関数は、成功したすべての結果をリストに収集する継続を使用してパーサーを実行し、リストが返されます。 文字列全体（残りの ""を含む）を消費する結果のみが収集されます。

    ```
    (define (run-parser parser str)
    (let ((results '()))
    (parser str (lambda (result)
    (match result
    [(success val "")
    (set! results (cons result results))]
    [failure failure])))
    results))
    ```

    Racketでは関数にオプションの引数を指定できるという事実を利用することで、さらに単純なインターフェイスを実装できます。 したがって、継続引数をオプションにすることができます！ パーサーが継続なしで呼び出された場合、デフォルトではrun-parserの継続が使用されます。 このインターフェースのラッパーは、次のように定義できます:

    ```
    (define (make-parser parser)
    (lambda (str (cont #f))
    (if cont
    (parser str cont)
    (run-parser parser str))))
    ```

    次に、このラッパーをdefine-parserに組み込むことができます:

    ```
    (define-syntax-rule (define-parser parser body)
    (define parser
    (make-parser
    (delay-parser body))))
    ```

    パーサーは、2つの方法で呼び出すことができます。1つは結果を継続に渡すcps関数として、もう1つは結果を呼び出し元に返す通常の関数としてです。 後者の例を次に示します:

    ```
    > (s "aaa")
    (list (success '(("a" "a") "a") ""))
    ```

    パーサーは、入力全体に一致する単一の結果を含むリストを返します。

    # Trampoline

    現在の実装の弱点は、メモ化されたパーサーの結果がいたるところに散在していることです。各パーサーには独自のメモ化テーブルがあり、現在の解析と以前の解析の両方からの累積結果が保存されます。これを維持および最適化することは困難です。

    もう1つの問題は、あいまいな文法を処理するときに、すべての結果が一度に生成されることです。このような文法の場合、結果の遅延ストリームを返し、一度に1つずつ結果を生成する方が柔軟です。 （無限に曖昧な文法は、無限に多くの結果を生み出す可能性があります！）

    これを実現するために、パーサーの結果とパーサーの呼び出しをトランポリンと呼ばれる共有データ構造にカプセル化します。トランポリンには、パーサー呼び出しを繰り返してパーサーをディスパッチするループが含まれています。各パーサーには、トランポリン用の追加のトランポリン引数があります。

    トランポリンをフィールドとメソッドを持つRacketクラスとして定義します。これは便宜上のものです。メモ化テーブルの場合と同様に、可変リスト構造を最初からつなぎ合わせることができます。結局、トランポリンは、あるパーサーから別のパーサーに受け継がれるステートフルオブジェクトにすぎません。

    トランポリン％クラスの概要は次のとおりです（慣例により、クラス名は％で終わります）:

    ```
    (define trampoline%
    (class object% (super-new)
    (define stack (mlist))
    (define table (mlist))
    (define/public (has-next?) ...)
    (define/public (step) ...)
    (define/public (push-stack fn . args) ...)
    (define/public (push fn arg continuation) ...)
    (define/public (run) ...)))
    ```

    トランポリンには、 `stack`と` table`の2つのフィールドが含まれています。 `stack`には関数呼び出しが含まれ、` table`にはメモ化された値が含まれます。 どちらも変更可能なリストであり、パブリックメソッド `has-next`、` step`、 `push-stack`、` push`、および `run`によって変更されます。

    パーサーは、呼び出しスタックでの実行を保存するように変更されます。 つまり、パーサーを直接呼び出す代わりに、パーサー呼び出しがスタックにプッシュされます。 次に、トランポリンループは、スタックが使い果たされるまでスタックを繰り返し、has-nextメソッドでチェックします。 このメソッドは、スタックが空でない場合はtrueを返し、スタックが空の場合はfalseを返します。

    ```
    (define/public (has-next?)
    (not (empty? stack)))
    ```

    `push-stack`メソッドは、関数呼び出しをスタックにプッシュします。 呼び出しは、関数とその引数を含むconsセル `（fn .args）`です。

    ```
    (define/public (push-stack fn . args)
    (let ((call (mcons fn args)))
    (set! stack (mcons call stack))))
    ```

    stepメソッドは、パーサー呼び出しをスタックからポップして呼び出します。 `（mcar stack）`で最初の要素を取得し、それと照合して関数とその引数を取得します。 スタックポインタを次の要素に進めてから、 `apply`を使用して関数を引数に適用します。

    ```
    (define/public (step)
    (when (has-next?)
    (match (mcar stack)
    [(mcons fn args)
    (set! stack (mcdr stack))
    (apply fn args)])))
    ```

    `run`メソッドは、スタックが使い果たされるまで` step`を繰り返し呼び出します。

    ```
    (define/public (run)
    (do () ((not (has-next?)))
    (step)))
    ```

    トランポリンの他の部分はメモ化テーブルであり、すべてのパーサーがその結果をキャッシュします。 メモ化ロジックは、 `push-stack`のメモ化フロントエンドとして機能する` push`メソッドに含まれています。 これは、2レベルのテーブルで動作することを除いて、以前の `memo-cps`関数に似ています。 初めて呼び出されたときに関数を直接呼び出すのではなく、関数が `push-stack`に渡されることに注意してください。

    ```
    (define/public (push fn str cont)
    (define entry-continuations ...)
    (define entry-results ...)
    (define (push-continuation! entry cont) ...)
    (define (push-result! entry result) ...)
    (define (result-subsumed? entry result) ...)
    (define (make-entry) ...)
    (define (table-ref fn str) ...)
    (let ((entry (table-ref fn str)))
    (match entry
    [(mcons (mlist) (mlist))
    (push-continuation! entry cont)
    ;; push the parser on the stack
    (push-stack fn str this
    (lambda (result)
    (unless (result-subsumed? entry result)
    (push-result! entry result)
    (for ((cont (entry-continuations entry)))
    (cont result)))))]
    [_
    (push-continuation! entry cont)
    (for ((result (entry-results entry)))
    (cont result))])))
    ```

    前述のように、テーブルには2つのレベルがあります（ネストされた関連付けリストです）。 第1レベルはパーサーをメモ化レコードにマップし、第2レベルは入力を出力にマップします。 これはすべて、ローカルの `table-ref`関数によって処理されます。この関数は、関数またはその入力が初めて参照されるときに、空のエントリを自動的に作成します。

    ```
    (define (table-ref fn str)
    (let ((pair (massoc fn table)))
    (match pair
    [(mcons fn memo)
    (match (massoc str memo)
    ;; parser has been called with str before
    [(mcons str entry) entry]
    ;; first time parser has been called with str
    [_ (let ((entry (make-entry)))
    (set-mcdr! pair (mcons (mcons str entry) memo))
    entry)])]
    ;; first time parser has been called
    [_ (let* ((entry (make-entry))
    (memo (mlist (mcons str entry))))
    (set! table (mcons (mcons fn memo) table))
    entry)])))
    ```

    これで、パーサーを書き直す準備ができました。 ほとんどの場合、これはトランポリンに追加の引数 `tramp`を追加するだけの問題です。 `succeed`および` string`パーサーは、トランポリンをまったく使用しません:

    ```
    (define succeed
    (memo
    (lambda (val)
    (lambda (str tramp cont)
    (cont (success val str))))))
    (define string
    (memo
    (lambda (match)
    (lambda (str tramp cont)
    (let* (...)
    (if (equal? head match)
    (cont (success head tail))
    (cont (failure tail))))))))
    ```

    パーサーのメモ化はトランポリンによって処理されるため、 `memo-cps`がないことに注意してください。 `seq`コンビネータは、` tramp`引数をあるパーサーから別のパーサーに渡すだけです:

    ```
    (define (bind p fn)
    (lambda (str tramp cont)
    (p str tramp
    (lambda (result)
    (match result
    [(success val rest)
    ((fn val) rest tramp cont)]
    [failure
    (cont failure)])))))
    (define seq
    (memo
    (lambda (a b)
    (bind a (lambda (x) ...)))))
    ```

    以前と同様に、変更は「バインド」にあり、トランポリンを通過します。 `seq`の定義は、` memo-cps`がなくなったことを除いて同じままです。
    `alt`コンビネータのみがトランポリンを直接使用します。 代替パーサー自体を呼び出す代わりに、それらをスタックにプッシュします。

    ```
    (define alt
    (memo
    (lambda (a b)
    (lambda (str tramp cont)
    (send tramp push a str cont)
    (send tramp push b str cont)))))
    ```

    `send`関数は、オブジェクトのメソッドにアクセスするRacketの方法です。 `tramp`オブジェクトの` push`メソッドを呼び出すには、（ `send`` tramp`` push` ...）とメソッドの引数を記述します。
    これで、トランポリンを作成し、それを継続とともにパーサーに渡して、 `run`メソッドを呼び出すことができます:

    ```
    > (define tramp (new trampoline%))
    > (s "aaa" tramp print)
    > (send tramp run)
    (success "a" "aa")
    (success '("a" "a") "a")
    (success '(("a" "a") "a") "")
    (failure "")
    ```

    もちろん、これは最も便利なインターフェースではないため、 `run-parser`関数を再定義して、成功した結果を遅延ストリームとして返します。 そのために、最初に `make-stream`コンビニエンスマクロを定義します。これにより、ストリームコンストラクター` stream-cons`をより簡単に使用できるようになります。 `stream-cons`関数は2つの式を取ります。1つは最初の要素を生成するためのもので、もう1つは残りのストリームを生成するためのものです。 `make-stream`マクロは、ストリームを生成するために単一の式を使用するだけです。これは、複数の結果が生成される場合に簡単です。

    ```
    (define-syntax-rule (make-stream body ...)
    (stream-rest
    (stream-cons '() (begin body ...))))
    ```

    これで、 `run-parser`を` make-stream`の呼び出しとして定義できます:

    ```
    (define (run-parser parser str)
    (let ((tramp (new trampoline%))
    (results '()))
    (define (compute)
    (when (send tramp has-next?)
    (do () ((not (and (empty? results)
    (send tramp has-next?))))
    (send tramp step)))
    (stream))
    (define (stream)
    (let ((result (sequence->stream results)))
    (set! results (mlist))
    (if (send tramp has-next?)
    (stream-append result (make-stream (compute)))
    result)))
    (make-stream
    (parser str tramp
    (lambda (result)
    (match result
    [(success val "")
    (set! results (cons result results))]
    [failure failure])))
    (compute))))
    ```

    まず、新しいトランポリンと空の「結果」リストを作成します。 いくつかのローカル関数を定義した後、成功した結果を `results`に追加する継続でパーサーを呼び出す` stream`を作成します。 ローカル関数 `compute`が呼び出され、少なくとも1つの結果が結果に表示されるか、スタックが使い果たされるまで、トランポリンのスタックをステップスルーします。 `results`は、ローカルの` stream`関数を呼び出すことによって遅延して返されます。この関数は、最初の結果が `results`から取得され、残りは` compute`を再度呼び出すことによって生成されます。

    つまり、 `run`メソッドを使用して呼び出しスタック全体を一度にステップ実行する代わりに、` run-parser`は `step`を使用してよりきめ細かい実行を実行します。 結果を取得するたびに、それ以上の生成を強制されない限り（そして、呼び出しスタックが使い果たされない限り）、実行を停止します。

    最後に、 `tramp`引数と` cont`引数がオプションであるよりクリーンなインターフェースを作成できます:

    ```
    (define-syntax-rule (define-parser parser body)
    (define parser
    (make-parser
    (delay-parser body))))
    (define (make-parser parser)
    (lambda (str (tramp #f) (cont #f))
    (if (and tramp cont)
    (parser str tramp cont)
    (run-parser parser str))))
    ```

    通常の方法でパーサーを呼び出すと、次のストリームが得られます:

    ```
    > (s "aaa")
    #<stream>
    ```

    ストリームをリストに変換することで、ストリームを強制できます:

    ```
    > (stream->list (s "aaa"))
    (list (success '(("a" "a") "a") ""))
    ```