環境とクロージャを用いた、より効率的な関数型プログラミング言語の定義＆実装の仕方の例 - Qiita

関数型プログラミング言語の定義＆実装の仕方の例で「需要があれば後で書く」と書いた、「より効率的な実装」です（数件:-)の需要があったので）。前の記事は読んでいると仮定します。 さて、前の実装では、関数function(x){E}を値vに適用すると、本体である式Eの抽象構文木をすべて辿って、その中の変数xをすべてvで置き換えた式を作っていました（subst）。これは明らかに非効率的です。関数を呼び出すたびに、本体の抽象構文木を作り直しているのですから！ そこで、変数に本当に値を代入して新しい式を作り直すかわりに、どの変数にどういう値が与えられた（束縛(binding)と言います）のか、覚えておくデータ構造を用意します。これを環境(environment)と言います。 環境は連想リストでもハッシュテーブルでも探索木でも、変数から値への対応（写像）を表していれば、何でも実装することができます。た

[natsutan]

コメント欄も

[ruicc]

続編だ