関数型プログラミング言語の定義&実装の仕方の例で「需要があれば後で書く」と書いた、「より効率的な実装」です(数件:-)の需要があったので)。前の記事は読んでいると仮定します。 さて、前の実装では、関数function(x){E}を値vに適用すると、本体である式Eの抽象構文木をすべて辿って、その中の変数xをすべてvで置き換えた式を作っていました(subst)。これは明らかに非効率的です。関数を呼び出すたびに、本体の抽象構文木を作り直しているのですから! そこで、変数に本当に値を代入して新しい式を作り直すかわりに、どの変数にどういう値が与えられた(束縛(binding)と言います)のか、覚えておくデータ構造を用意します。これを環境(environment)と言います。 環境は連想リストでもハッシュテーブルでも探索木でも、変数から値への対応(写像)を表していれば、何でも実装することができます。た
![環境とクロージャを用いた、より効率的な関数型プログラミング言語の定義&実装の仕方の例 - Qiita](https://cdn-ak-scissors.b.st-hatena.com/image/square/f78ed2483fe0232af267b278e20f2846fc7bc7ce/height=288;version=1;width=512/https%3A%2F%2Fqiita-user-contents.imgix.net%2Fhttps%253A%252F%252Fcdn.qiita.com%252Fassets%252Fpublic%252Farticle-ogp-background-9f5428127621718a910c8b63951390ad.png%3Fixlib%3Drb-4.0.0%26w%3D1200%26mark64%3DaHR0cHM6Ly9xaWl0YS11c2VyLWNvbnRlbnRzLmltZ2l4Lm5ldC9-dGV4dD9peGxpYj1yYi00LjAuMCZ3PTkxNiZoPTMzNiZ0eHQ9JUU3JTkyJUIwJUU1JUEyJTgzJUUzJTgxJUE4JUUzJTgyJUFGJUUzJTgzJUFEJUUzJTgzJUJDJUUzJTgyJUI4JUUzJTgzJUEzJUUzJTgyJTkyJUU3JTk0JUE4JUUzJTgxJTg0JUUzJTgxJTlGJUUzJTgwJTgxJUUzJTgyJTg4JUUzJTgyJThBJUU1JThBJUI5JUU3JThFJTg3JUU3JTlBJTg0JUUzJTgxJUFBJUU5JTk2JUEyJUU2JTk1JUIwJUU1JTlFJThCJUUzJTgzJTk3JUUzJTgzJUFEJUUzJTgyJUIwJUUzJTgzJUE5JUUzJTgzJTlGJUUzJTgzJUIzJUUzJTgyJUIwJUU4JUE4JTgwJUU4JUFBJTlFJUUzJTgxJUFFJUU1JUFFJTlBJUU3JUJFJUE5JUVGJUJDJTg2JUU1JUFFJTlGJUU4JUEzJTg1JUUzJTgxJUFFJUU0JUJCJTk1JUU2JTk2JUI5JUUzJTgxJUFFJUU0JUJFJThCJnR4dC1jb2xvcj0lMjMyMTIxMjEmdHh0LWZvbnQ9SGlyYWdpbm8lMjBTYW5zJTIwVzYmdHh0LXNpemU9NTYmdHh0LWNsaXA9ZWxsaXBzaXMmdHh0LWFsaWduPWxlZnQlMkN0b3Amcz1lMzlhNDg3ODRjYWNjYTRkMGM4ODFmOGVhMzU3NTA1Mg%26mark-x%3D142%26mark-y%3D112%26blend64%3DaHR0cHM6Ly9xaWl0YS11c2VyLWNvbnRlbnRzLmltZ2l4Lm5ldC9-dGV4dD9peGxpYj1yYi00LjAuMCZ3PTYxNiZ0eHQ9JTQwZXN1bWlpJnR4dC1jb2xvcj0lMjMyMTIxMjEmdHh0LWZvbnQ9SGlyYWdpbm8lMjBTYW5zJTIwVzYmdHh0LXNpemU9MzYmdHh0LWFsaWduPWxlZnQlMkN0b3Amcz00Mjk0NWIyMmZjZTliZDFmYWI1ODdkZTI5Yjk3NWM3Mw%26blend-x%3D142%26blend-y%3D491%26blend-mode%3Dnormal%26s%3D16b6aabf1d49ea1d309226c003967c55)