Loading article…
コンピュータサイエンスにおいて、グラフ削減は、関数の引数がすぐに評価されない評価戦略である非厳密評価の効率的なバージョンを実装します。この形式の非厳密評価は遅延評価とも呼ばれ、関数型プログラミング言語で使用されます。この手法は、1971 年に Chris Wadsworth によって初めて開発されました。
モチベーション
算術式を評価する簡単な例を次に示します。
上記の削減シーケンスは、最外木削減と呼ばれる戦略を採用しています。同じ式を最内木削減を使用して評価すると、削減シーケンスが生成されます。
括弧を追加することで簡約順序が明示されていることに注意してください。加算は結合演算なので、この式は単純に右から左に評価することもできます。
上記の式 をツリーとして表すと、次のようになります。
ここからツリー削減という用語が生まれました。ツリーとして表現すると、最も内側の削減は下から上に向かって行われ、最も外側の削減は上から下に向かって行われると考えることができます。
この式は有向非巡回グラフとして表現することもでき、部分式を共有することができます。
木の場合と同様に、最外部と最内部の削減はグラフにも適用されます。したがって、グラフ削減が行われます。
最外部グラフ削減による評価は次のように進めることができます。
評価に必要なステップが 4 つだけであることに注意してください。最も外側のグラフ削減は遅延評価と呼ばれ、最も内側のグラフ削減は積極的評価と呼ばれます。
コンビネータグラフ削減
コンビネータ グラフの削減は、関数型プログラミング言語の基本的な実装手法です。この手法では、プログラムは、コンピュータ メモリ内の有向グラフデータ構造にマップされるコンビネータ表現に変換され、プログラムの実行は、このグラフの一部を書き換える (「削減する」) ことで構成され、有用な結果が得られます。
歴史
評価された値を共有できるグラフ縮小の概念は、1971 年の Chris Wadsworth 博士論文で初めて開発されました。[1]この論文は、遅延評価の概念を紹介した1976 年の論文「A lazy evaluator」 [2]で Peter Henderson と James H. Morris Jr. によって引用されました。1976 年にDavid Turner はコンビネータを使用してSASLに遅延評価を組み込みました。 [3] SASL は Turner が 1972 年に初めて開発した初期の関数型プログラミング言語です。
参照
注記
参考文献
- バード、リチャード (1998)。Haskellを使用した関数型プログラミング入門。Prentice Hall。ISBN 0-13-484346-0。
さらに読む
- ペイトン・ジョーンズ、サイモン・L. (1987)。関数型プログラミング言語の実装。プレンティス・ホール。ISBN 013453333X. LCCN 86020535 . 2022年4月15日閲覧。