16 0 0 0 OA 表示的意味論に基づくパターンマッチングコンパイル方式の構築と実装
- 著者
- 大堀 淳 纓坂 智
- 出版者
- 日本ソフトウェア科学会
- 雑誌
- コンピュータ ソフトウェア (ISSN:02896540)
- 巻号頁・発行日
- vol.24, no.2, pp.2_113-2_132, 2007 (Released:2007-05-31)
本論文では,パターンマッチングとそのコンパイルを系統的に理解するための表示的意味論を提示し,それを基に,パターンマッチング構文を効率よいコードにコンパイルする系統的なアルゴリズムを提案する.まず,パターンを値の部分集合と見なし,パターンマッチング構文を,マッチングの対象項が含まれる部分集合を決定する機構と見なすことにより,パターンマッチングの集合論的意味論を与える.次に,各パターンの表示的意味を表現する木構造を定義し,それに基づきパターンマッチングのコンパイルアルゴリズムを導出し,このアルゴリズムの正しさを証明する.導出されたアルゴリズムは,分岐の選択に関して正しいばかりでなく,実行時の値のテスト回数に関して最適であり,かつ,冗長なパターンや網羅的でないパターン集合を常に正確に検出することが保証されている.以上構築したアルゴリズムは,Standard MLの拡張言語であるSML#言語に対して実装され,SML#コンパイラのパターンマッチングコンパイルモジュールとしての使用を通じてその実用性が確認されている.
2 0 0 0 OA 型に基づくパターンマッチングコンパイル方式の構築と実装
- 著者
- 纓坂 智
- 巻号頁・発行日
- 2004-03
Supervisor:大堀 淳