氏名: 大久保弘崇 (d06724)

論文題目: オブジェクト指向プログラムに対する型検査アルゴリズム


論文概要

オブジェクト指向プログラミングにおける 特徴的な実行時エラーとして, オブジェクトが対応するメソッドを持たないメッセージを送信される, いわゆる “Message not Understood” エラー(以後 MNU-error) がある. オブジェクト指向の計算においては オブジェクト間のメッセージの送受が計算の進行そのものであり, それが妨げられる MNU-error は オブジェクト指向言語に対する型推論が 最も考慮するべきことがらである.

Palsberg らによって提案されている方法では, プログラム中のデータフローを制約式によって表現し, データの種別をクラスによって分類することで クラスの集合からなる型を推論する. この方法の問題点として, クラスの継承を単なるコードの複製と見なしていることから, 複製された同一のコードに型推論の計算がまた必要になること, 多相な型を表現する能力の不足が挙げられる. そこで本論文ではまず Palsberg らの方法論に基づいた 別の型推論アルゴリズムを提案する. このアルゴリズムは, クラスのテキスト記述から直接制約式集合を構成し, 継承がある時にはそれらの合成によって新たな制約式集合を構成する ことによりクラス継承を直接取り扱う. こうして得られた制約式はプログラムのデータフローを表しており, その解の存在はプログラムの MNU-error 安全な実行を保証する.

アルゴリズムの定式化のために言語を設定し、 この言語の動作的意味を状態遷移モデルによって定義する. このモデルの遷移関係を用いることで, 本アルゴリズムによって安全であると判定されたプログラムは 実行したときに MNU-error にならないこと, すなわちアルゴリズムの健全性を証明する.

この制約を用いるプログラムの解析の手法には 他のオブジェクトを格納するためのクラスの型付けが困難であるという 欠点が指摘されている. 本アルゴリズムではクラスを単位として記述する オブジェクト指向プログラムの局所性を利用して制約式を構成するため, これを単位として制約式の複製を作ることで 拡張してこれらの問題を解決する アルゴリズムの拡張方法を提案する.


目次に戻る