型デバッガの理論と実際

平成 26 年度は、前年度までの研究をより進め、実際に使われている言語で型デバッガを使用可能にすることを目的に、実装の拡張と、大きい言語かつサイズが大きいプログラムで使用するためのアルゴリズムの改良を行った。1. 実装の拡張:型エラースライサ・型エラーメッセージの改良に関してもユーザテスト・評価を行うために、実装の拡張を行った。プロトタイプでは小さなサブセットしか扱っていなかったが、関数型言語の初級の授業で使われる範囲程度までの拡張を行ったことで、評価が可能となった。2.計算量を押さえるための改良:これまでに提案した型エラースライサ・型エラーメッセージの生成では理論的側面から、単純なアルゴリズムとしていた。しかし、それでは大きい言語の大きいプログラムを対象に実行する際に計算時間が問題となる。そのため両手法の計算量を押さえるための改良を行った。具体的には型エラースライサでは、型エラースライスを作る際に削って行く部分プログラムの量を型エラースライス候補の大きさ等で適宜変更することで、型推論の回数を減らし、全体としての計算量を減らすことに成功した。型エラーメッセージの改良では、これまでは複数のメッセージの候補を作る際に元々の型エラーのプログラムを使用していたが、型エラースライスを一つ作り、それから複数の候補を作ることで、探索時間を削減し、計算量の大幅に削減に成功した。実際の言語を対象に使用可能な型デバッグ実装が複数完成したことで、どの手法がどのようなプログラムに対して効果的か等の評価が可能になり、型デバッグの実用化に近づいたと言える。

平成 26 年度は、前年度までの研究をより進め、実際に使われている言語で型デバッガを使用可能にすることを目的に、実装の拡張と、大きい言語かつサイズが大きいプログラムで使用するためのアルゴリズムの改良を行った。1. 実装の拡張:型エラースライサ・型エラーメッセージの改良に関してもユーザテスト・評価を行うために、実装の拡張を行った。プロトタイプでは小さなサブセットしか扱っていなかったが、関数型言語の初級の授業で使われる範囲程度までの拡張を行ったことで、評価が可能となった。2.計算量を押さえるための改良:これまでに提案した型エラースライサ・型エラーメッセージの生成では理論的側面から、単純なアルゴリズムとしていた。しかし、それでは大きい言語の大きいプログラムを対象に実行する際に計算時間が問題となる。そのため両手法の計算量を押さえるための改良を行った。具体的には型エラースライサでは、型エラースライスを作る際に削って行く部分プログラムの量を型エラースライス候補の大きさ等で適宜変更することで、型推論の回数を減らし、全体としての計算量を減らすことに成功した。型エラーメッセージの改良では、これまでは複数のメッセージの候補を作る際に元々の型エラーのプログラムを使用していたが、型エラースライスを一つ作り、それから複数の候補を作ることで、探索時間を削減し、計算量の大幅に削減に成功した。実際の言語を対象に使用可能な型デバッグ実装が複数完成したことで、どの手法がどのようなプログラムに対して効果的か等の評価が可能になり、型デバッグの実用化に近づいたと言える。