氏名: 西田 直樹 (089631390)

論文題目: ごみ集めを意識しない利用が可能なライブラリの設計法


論文概要

 リストなどの可変長の資源を用いるプログラムにおいて、もっとも厄介な問題のひ とつはごみ集めである。ごみ集めは不要になったデータの記憶領域を回収することで ある。C言語などの通常の言語ではごみの回収をユーザがプログラム中に指示しなけ ればならず、指示の誤りは時として重大なエラーを起こす。
 本論文では、ユーザがごみ集めを意識せずに利用が可能なライブラリの設計法を提 案し、それに基づいて、可変長整数のライブラリを作成し、評価を行った。さらにこ の可変長整数のライブラリを、項書換え系(TRS)を入力としてそれと同等の動作を するC言語プログラムを生成するCdimpleに組込んだ。

 ユーザがごみ集めを行うには、(1)ポインタ変数を更新する際の旧データ、(2) ライブラリ関数の合成の際に使われる中間データ を指定しなければならない。(1) の場合、例えばx=f(x)のようにポインタ変数xが更新されるときには、f(x)を計算しx が指すデータ領域を回収した後、f(x)の値をxに代入する必要がある。これをプログ ラマが行うためには、一時変数を導入する必要があり煩雑である。また、(2)の場 合にも同様に中間データへのポインタを一時的に保管する変数なしではデータ領域の 回収は不可能である。本論文での設計法では、(1)については、代入を行うための マクロを用意し、その中で不要な領域を開放した後に代入が行われるようにすること によって、一時変数を用意する必要なしにプログラムすることを可能にする。また (2)については、ライブラリが確保し変数への代入が行われていないデータ領域の 先頭にタグをつけておくことにより、データを利用する側のライブラリでの領域の開 放を可能にする。
 次に、提案した設計法に基づいて可変長整数のC言語のライブラリを作成した。 データ構造は、b-進数の各桁ごとに1つのセルに入れた双方向リストを基本として構 成した。このデータ構造に対して、int型整数や文字列の可変長整数への変換、可変 長整数の表示、比較演算、四則演算のライブラリを作成した。
 最後に、実際に可変長整数のライブラリを使って指定された桁数のeの値を求める プログラムの作成、ならびにこのライブラリのCdimpleへの導入を行った。その結 果、ごみが蓄積されないことが確認された。また、通常のごみ集めの場合と比較した 手間の評価を行い、本手法が十分有効であることを明らかにした。


目次に戻る


asakura@nuie.nagoya-u.ac.jp