メモ化

関数型プログラミング言語のコンパイラでは、名前呼び出しによる評価戦略が用いられることが多いため、メモ化が多用されています。引数値の計算に伴うオーバーヘッドを回避するため、これらの言語のコンパイラは、サンクと呼ばれる補助関数を多用して引数値を計算し、これらの関数をメモ化することで計算の重複を防いでいます。

メモ化は、上記のメモ化されたバージョンの実装とほぼ同じ方法で、コンピュータ プログラマによって関数に内部的に明示的に追加できますが、参照透過関数は外部的に自動的にメモ化することもできます。^{[ 1 ]}ピーター ノーヴィグが採用した手法は、 Common Lisp (彼の論文で自動メモ化を実証した言語)だけでなく、他のさまざまなプログラミング言語にも適用できます。自動メモ化の応用は、項書き換え^{[ 4 ]}や人工知能^{[ 5 ]}の研究でも正式に検討されています。factorial

関数が第一級オブジェクトであるプログラミング言語（ Lua、Python、Perl ^{[ 6 ]}など）では、指定されたパラメータセットに対して値が計算された後、（実行時に）関数をその計算値で置き換えることで、自動メモ化を実装できます。この値と関数オブジェクトの置き換えを行う関数は、参照透過的な関数であれば何でも汎用的にラップできます。次の擬似コードを考えてみましょう（関数は第一級値であると仮定します）。

関数メモ化呼び出し（Fは関数オブジェクトのパラメータ）Fに配列値が添付されていない 場合は、valuesという名前の連想配列 を割り当てます。Fに値を 関連付ける。 end if; F.values [arguments]が空の場合 、F.values [ arguments] = F (arguments); end if; return F.values[arguments] ; 関数終了

factorial上記の戦略を使用して、factorial直接呼び出すのではなく、自動的にメモ化されたバージョンを呼び出すには、コードが を呼び出します。このような呼び出しはそれぞれ、まず結果を格納するためのホルダー配列が割り当てられているかどうかを確認し、割り当てられていない場合はその配列をアタッチします。位置( が連想配列のキーとして使用される) にエントリが存在しない場合、指定された引数を使用して に実際の呼び出しが行われます。最後に、キー位置にある配列のエントリが呼び出し元に返されます。memoized-call(factorial)(n)values[arguments]argumentsfactorial

上記の戦略では、メモ化対象の関数を呼び出すたびに明示的にラップする必要があります。クロージャを許容する言語では、デコレータパターンでラップされたメモ化関数オブジェクトを返すファンクタファクトリを介して、暗黙的にメモ化を実行できます。擬似コードでは、次のように表現できます。

関数コンストラクタ（Fは関数オブジェクトのパラメータ）memoized-version という名前の関数オブジェクトを割り当てます。 メモ化バージョン(引数)をselfに配列値が添付されていない 場合、[ selfはこのオブジェクトへの参照です]values という名前の連想配列を割り当てます。自身に値を 関連付ける。 end if; self.values [arguments]が空の場合 self.values [arguments] = F (arguments); end if; return self.values [arguments] ; end let; メモ化バージョン を返す。 関数終了

を呼び出す代わりにfactorial、次のように新しい関数オブジェクトmemfactが作成されます。

memfact = construct-memoized-functor(factorial)

上記の例では、関数が呼び出し前に既に定義されていることを前提としています。このfactorial時点以降、nの階乗が必要な場合はいつでも が呼び出されます。Lua などの言語では、関数を同じ名前の新しい関数に置き換えることができる、より高度なテクニックが存在し、次のようなことが可能になります。construct-memoized-functormemfact(n)

階乗 = 構成メモ化ファンクター(階乗)

基本的に、このような手法では、元の関数オブジェクトを作成されたファンクタにアタッチし、実際の関数を呼び出す必要がある場合（無限再帰を回避するため）、エイリアスを介してメモ化される元の関数への呼び出しを転送します。以下はその例です。

関数コンストラクタ（Fは関数オブジェクトのパラメータ）memoized-version という名前の関数オブジェクトを割り当てます。 メモ化バージョン(引数) をselfに配列値が添付されていない 場合、[ selfはこのオブジェクトへの参照です]values という名前の連想配列を割り当てます。自身に値を 関連付ける。alias という名前の新しい関数オブジェクトを割り当てます。自身にエイリアス を付与する。[後で間接的にFを呼び出すことができるようにするため] self.alias = F ;​ end if; self.values [arguments]が空の場合 self.values [arguments] = self.alias ( arguments); [ Fへの直接呼び出しではありません] end if; return self.values [arguments] ; end let; メモ化バージョン を返す。 関数終了

（注：上記の手順の一部は、実装言語によって暗黙的に処理される場合があり、説明のために記載されています。）

トップダウンパーサーが曖昧な文脈自由文法(CFG)に関して曖昧な入力を解析しようとすると、すべての可能な構文木を生成するために CFG のすべての代替案を試すために (入力の長さに対して) 指数関数的な数のステップが必要になる場合があります。これは最終的に指数関数的なメモリ空間を必要とします。メモ化は1991 年に Peter Norvig によって構文解析戦略として検討され、指数関数的な時間計算量の問題を解決するために単純なバックトラッキング再帰下降パーサーに自動メモ化を導入することで、 Earley のアルゴリズム(1970)の動的計画法と状態セットの使用、および Cocke、Younger、Kasami のCYKアルゴリズムのテーブルの使用に似たアルゴリズムを生成できることが実証されました。^{[ 1 ]} Norvig のアプローチの基本的な考え方は、パーサーが入力に適用されると、同じパーサーが同じ入力に再度適用される場合に再利用できるように、結果がメモ可能に格納されるということです。

リチャード・フロストとバーバラ・シドロウスキーもメモ化を使用して、パーサーコンビネータの指数関数的な時間計算量を削減し、その結果をメモ化純粋関数型トップダウンバックトラッキング言語プロセッサと表現した。^{[ 7 ]}フロストは、基本的なメモ化パーサーコンビネータを構成要素として使用して、CFGの実行可能な仕様として複雑なパーサーを構築できることを示した。^{[ 8 ] [ 9 ]}

メモ化は、1995年にマーク・ジョンソンとヨッヘン・ドーレによって構文解析の文脈で再び研究されました。^{[ 10 ] [ 11 ]} 2002年には、ブライアン・フォードによってパックラット構文解析と呼ばれる形式でかなり詳細に研究されました。^{[ 12 ]}

2007年、Frost、Hafiz、Callaghanは、冗長な計算を控えるためにメモ化を使用し、多項式時間（左再帰文法の場合はΘ (n ⁴ ) 、非左再帰文法の場合はΘ(n ³ )）であらゆる形式の曖昧なCFGに対応するトップダウン構文解析アルゴリズムについて説明しました。彼らのトップダウン構文解析アルゴリズムは、「コンパクト表現」と「局所的曖昧性のグループ化」により、指数関数的に曖昧な構文木に対して多項式空間も必要とします。彼らのコンパクト表現は、Tomitaのボトムアップ構文解析のコンパクト表現に匹敵します。^{[ 13 ]}彼らのメモ化の使用は、構文解析器が同じ入力位置に繰り返し適用されるときに以前に計算された結果を取得すること（これは多項式時間要件に不可欠です）だけに限定されるものではなく、次の追加タスクを実行するように特化されています。

• メモ化処理（これはあらゆるパーサー実行の「ラッパー」と見なすことができる）は、入力長と現在の入力位置に関して深さの制限を課すことで、増大し続ける直接左再帰構文解析に対応する。
• このアルゴリズムのメモテーブル「ルックアップ」手順は、保存された結果の計算コンテキストとパーサーの現在のコンテキストを比較することで、保存された結果の再利用可能性も判断します。このコンテキスト比較は、間接的（または隠れた）左再帰に対応するための鍵となります。
• メモテーブル内で検索が成功した場合、完全な結果セットを返す代わりに、実際の結果への参照のみを返すことで、全体の計算速度が向上します。
• メモテーブルを更新する際、メモ化プロセスは（指数関数的に増加する可能性のある）曖昧な結果をグループ化し、多項式空間の要件を満たします。

Frost、Hafiz、Callaghanは、PADL'08でこのアルゴリズムの実装を、Haskellの高階関数（パーサーコンビネータと呼ばれる）のセットとして説明しました。これにより、言語プロセッサとして直接実行可能なCFG仕様を構築することが可能になります。彼らの多項式アルゴリズムが、トップダウン構文解析で「あらゆる形式の曖昧なCFG」に対応できる能力は、自然言語処理における構文解析と意味解析において非常に重要です。X -SAIGAのサイトには、このアルゴリズムと実装の詳細が掲載されています。

Norvig はメモ化によってパーサーの能力を向上させたが、拡張されたパーサーは依然として Earley のアルゴリズムと同じ時間複雑度であり、これはメモ化が速度最適化以外の目的で使用されている例を示している。Johnson と Dörre ^{[ 11 ]}は、メモ化の速度とは関係のない別の応用例を示している。それは、言語制約の解決を、制約を解決するのに十分な情報が蓄積された構文解析の時点まで遅らせるためにメモ化を使用することである。対照的に、メモ化の速度最適化の応用では、Ford は、メモ化によって、最悪の場合のバックトラッキング動作を引き起こす言語であっても、構文解析式文法が線形時間で構文解析できることを保証できることを示した。^{[ 12 ]}

次の文法を考えてみましょう。

S → (A c ) | (B d ) A → X ( a | b ) B → X b X → x [X]

（表記に関する注記：上記の例では、生成規則S → (A c ) | (B d ) は「SはAの後に c が続くか、Bの後にdが続くかのいずれかである」と解釈されます。生成規則 X → x [X] は「Xはxの後に任意のX が続く」と解釈されます。）

この文法は、文字列xac、xbc、xbdのいずれかのバリエーションを生成します（ここでx は1 個以上のxを意味します）。次に、この文法を構文解析仕様として使用した場合、文字列xxxxxbdのトップダウン、左から右への構文解析にどのような影響を与えるかを考えてみましょう。

ルールAは、 xxxxxb を認識します(まずXに降りて 1 つのx を認識し、すべてのxが消費されるまで再びXに降りて、次にbを認識することによって)、その後Sに戻りますが、cを認識できません。S の次の節は、B に降り、B は、Xに再び降りて、 Xへの多数の再帰呼び出しによってxを認識し、次にb を認識し、 Sに戻って、最後にd を認識します。

ここでの重要な概念は、 「再びXに降りる」というフレーズに内在しています。先を見据え、失敗し、後退し、次の選択肢を再試行するプロセスは、構文解析ではバックトラッキングとして知られており、構文解析におけるメモ化の機会を提供する主な要因はバックトラッキングです。RuleAcceptsSomeInput(Rule, Position, Input)次のパラメータを持つ関数を考えてみましょう。

• Ruleこれは検討対象となっている規則の名前です。
• Positionこれは、入力において現在考慮されているオフセットです。
• Input検討対象の入力値です。

関数の戻り値は、RuleAcceptsSomeInputによって受け入れられる入力の長さRule、または、そのルールが文字列内のそのオフセットで入力を受け入れない場合は 0 とします。このようなメモ化を伴うバックトラッキングシナリオでは、解析プロセスは次のようになります。

ルールA がオフセット 0 でXに降りてくると、その位置とルールXに対して長さ 5 をメモ化します。dで失敗した後、B は再びXに降りてくるのではなく、メモ化エンジンで位置 0 に対してルールXを照会し、長さ 5 が返されるため、実際に再びXに降りてくる必要がなくなり、以前と同じ回数だけXに降りてきたかのように処理を続行します。

上記の例では、Xへの下降が1 回または複数回発生する可能性があり、xxxxxxxxxxxxxxxxbdのような文字列が生成されることがあります。実際には、bの前に任意の数のxが存在する可能性があります。S の呼び出しは、 xの数だけ X に再帰的に下降する必要がありますが、B は、戻り値が16 (この特定の場合) になるため、X に下降する必要は全くありません。RuleAcceptsSomeInput(X, 0, xxxxxxxxxxxxxxxxbd)

構文述語を利用する構文解析器は、述語解析の結果をメモ化することもできるため、次のような構造を削減できます。

S → (A)? A A → /* 何らかのルール */

Aへの1回の降下へ。

構文解析器が構文解析中に構文木を構築する場合、特定の規則に対してあるオフセットで一致する入力の長さをメモ化するだけでなく、その規則によってそのオフセットで生成されるサブツリーも入力内に保存する必要があります。なぜなら、構文解析器によるその後の規則呼び出しでは、実際にその木を辿って再構築することはないからです。同様の理由で、規則が一致したときに外部コード（意味処理ルーチンと呼ばれることもあります）を呼び出すメモ化された構文解析アルゴリズムは、そのような規則が予測可能な順序で呼び出されるように何らかの仕組みを使用する必要があります。

バックトラッキングや構文述語処理が可能なパーサーであっても、すべての文法でバックトラッキングや述語チェックが必要になるわけではないため、入力の各オフセットに対して各ルールの解析結果を保存するオーバーヘッド（および解析処理が暗黙的に行う場合は解析ツリーを保存するオーバーヘッド）によって、パーサーの速度が低下する可能性があります。この影響は、パーサーがメモ化するルールを明示的に選択することで軽減できます。^{[ 14 ]}