メモ化はプログラムの高速化のための最適化手法の一種である. メモ化された関数は, 過去の呼出しの結果を当時の引数とともにテーブルに記憶しておき, 後で同じ引数で呼び出される際, 計算せずに記憶されている結果を返すことで, 重複した計算を省略する. メモ化を関数に適用するには, ソースコードを書き直す必要がある. この煩わしい作業からプログラマを解放するために, 自動メモ化技術が利用される. しかし, 自動メモ化可能な関数は参照透過性を備えるものに限られている. 関数が大域変数へアクセスする場合, 大域変数の値がこの関数の計算結果, あるいは次に呼び出される関数の計算結果に影響するので, メモ化を適用できない. その結果、大域変数へアクセスする関数が多いプログラムに対して自動メモ化を行う場合, 最適化効果が制限される.
自動メモ化をより広い範囲のプログラムに適用するために, 本研究では, プログラム変換によって大域変数へアクセスする関数をメモ化できる関数にする手法を開発した. 具体的には, 関数が大域変数への参照を含む場合, 参照される大域変数に相当する変数を局所変数として表すために, 関数のパラメータリストにその変数を加えるように変換する. また, 関数が大域変数へ代入する場合, 大域変数の代わりに, 対応する局所変数に値を代入する. その関数がリターンする際は, 大域変数へ代入される値及び本来の返値から成るペアあるいはリストを返すようにする. 関数がリターンした後に, 返されたペアやリストから代入された値を取り出し, その値で大域変数を更新する. このように変換された関数は大域変数へ直接アクセスしない. しかし, 局所変数を経由して, 大域変数への参照と代入は変換前の関数と同じように行われる.
本研究では, プログラム変換を行う変換器をScheme言語で実装した. 変換器は入力として受け取った各関数をメモ化できるように変換する. 実装した変換器はプログラム解析とプログラム変換の部分を含む. 解析によって, 各関数の中でアクセスされる大域変数情報が集められる. それらの情報に基づき, 変換を行う. また, 変換後の関数に対してメモ化を適用する実験を行った. メモ化を利用した効果はプログラムのパターンによって異なる. 本手法の活用例としては, イベントのログによるプロセス再演を高速化するためにメモ化を利用することを考えている. 今後, メモ化の最適化効果を上げるために, 大域変数へアクセスする関数をさらに区別してメモ化する必要があると考えている.