部分評価を使った自己反映言語のコンパイル技法

点击翻译按钮获取中文摘要

自己反映言語のコンパイルを目指して、おもにその基礎技術である部分評価法の研究を行った。部分評価器を自己反映言語のコンパイラとして使用するためには、使用する部分評価器が(1)十分、強力で、かつ(2)効率的に動くこと、の2点が重要である。これらに対応して以下のような結果を得た。1. 部分評価器の能力として、構造データをきちんと扱えることが重要で、そのためには部分評価時に各式の値とコードの両方を保持することが重要であることを発見した。これに基づいて実際にonlineの部分評価器を作成し、その効果を確かめた。しかし、この方法はonlineのため効率に問題があることがわかった。2. より効率的な部分評価を実現するべく、上記の方法をofflineに拡張する方法を提案した。この方法は、構造データをうまく扱う特化器の作成と束縛時解析器の作成というふたつの部分からなる。このうち前者は、必要に応じて値とコードの両方を保持し、かつコードの複製を避けるためコード部分を必ずlet式に残すことでうまくできることがわかった。この特化器を使って実際にいろいろな特化を行い、自己適用によるコンパイラジェネレータの作成を含めてうまく動くことを確認した。後者に関しては、従来の束縛時解析の手法を拡張することで、値とコードの両方を持つべき場所を特定できることを示した。その過程で、束縛時解析は、比較的、素直に制約を生成する型システムとして定式化できるが、制約を解くためには従来の手法と違い、2段階にわける必要があることがわかった。束縛時解析は実際に実装を行い、うまく動くことを確認した。今後の課題としては、ここで提案した束縛時解析の多段の部分評価への応用、今回は行うことができなかった自己反映言語のコンパイルへの実際の適用などがあげられる。