Tcl で memoization

今読んでいる本のひとつに Higher Order Perl というのがあって―これは本当にすばらしい本で、いずれじっくり紹介したいのだが―その本の中で解説されているテクニックのひとつに memoization がある。

これは関数の結果をキャッシュして、キャッシュがヒットしたら再計算をせずにキャッシュを返すというものだ。

単純なバージョンではこんな memoize 関数を作る。

sub memoize {
  my ($func) =@_;
  my %cache;
  my $stub = sub {
    my $key = join ',', @_;
    $cache{$key} = $func->(@_) unless exists $cache{$key};
    return $cache{$key};
  };
  return $stub;
}

この関数は関数を引数にとって memoized 版の関数を返す。

新しく作られる関数の中では、引数をキーにしたハッシュを保持して、関数が呼び出されたときに引数に対応するハッシュ値があればそれを返して、無かったら元々の関数を呼び出してハッシュに今回の結果をキャッシュする、ということをしている。

例えば fib という関数があってそれを memoize するには以下のように使う。

sub fib {
	my ($month) = @_;
	if ($month < 2) { 1 }
	else {
		fib($month-1) + fib($month-2);
	}
}
*fib = memoize(\&fib);

このようにすると元の fib 関数には手をつけることなく、そっくりそのまま fib が memoized 版に置き換わる。

ちなみに fib というのはフィボナッチ数列というものを計算する関数で、これは内部で再起呼び出しを頻繁に行うのでキャッシュの効果が絶大に現れる例としてよく使われるようだ。

それでこれを Tcl でやったらどうなるだろうかと考えた。
でも Tcl の世界ではこういったことは大抵の場合自分が考える前に Tcler's Wiki に書いてあるものだ。実際探してみると以下のようなページがある。

http://wiki.tcl.tk/10981
http://wiki.tcl.tk/10779

でもここで提案されているコードはプロシージャの定義の先頭に memoize という記述を埋め込むものだったり　proc の代わりに memproc という定義をするものだったりして、「すでに存在するプロシージャに手をつけずに memoize する」という条件を満たすものではないようだ。

その要件を満たすための Tcl での正攻法は以下のようなものじゃないだろうか。

namespace eval memoise {
	variable id 1

	proc memoise {f} {
		variable id

		set oldname [namespace origin $f]
		set newname f$id
		rename $oldname $newname
		set fullnewname [namespace origin f$id]
		set curns [namespace current]

		proc $oldname {args} "
			if \[info exists ${curns}::cache${id}(\$args)\] {
				return \$${curns}::cache${id}(\$args)
			}
			set ${curns}::cache${id}(\$args) \[eval $fullnewname \$args\]
			return \$${curns}::cache${id}(\$args)
		"
		incr id
	}

}

proc fib x {expr {$x <=1? 1 : [fib [expr {$x-1}]] + [fib [expr {$x-2}]]}}

puts [time {puts fib30=[fib 30]}]

memoise::memoise fib

puts [time {puts fib30=[fib 30]}]

この memoize::memoize 関数は渡された名前のプロシージャをリネームして memoize 名前空間内に退避する。その後、元の名前のプロシージャを memoized 版として再定義する。

リネーム後のプロシージャ名は memoize が呼ばれるたびに memoize::f1, memoize::f2, ... と使われていくので衝突することはない。キャッシュの配列も同様に memoize 名前空間内に存在する。

proc $oldname のあたりはどういう置き換えが発生しているかじっくり考えないと分かりにくいかもしれないが、これは中カッコでなくて二重引用符なので内部の $ や [] が置き換わって、その結果がプロシージャの定義になる。

上記のコードの実行例は以下のようになる。

fib30=1346269
6401381 microseconds per iteration
fib30=1346269
2326 microseconds per iteration

計算結果に影響を与えずに実行速度が向上しているのが分かる。