JSGP: 再帰とmemoization

ken 2件のコメント

割に気軽に構えていたのですがO’Reillyから出ている「JavaScript: the Good Parts」はなかなか骨太です。一級関数、関数閉包を使う例がどんどん出てきます。これはずばり Scheme ですね。

メモイゼーションを組込むための関数 memoizer を以下のように定義すると、

var memoizer = function (memo, fundamental) {
var shell = function (n) {
var result = memo[n];
if (typeof result != ‘number’) {
result = fundamental(shell, n);
memo[n] = result;
}
return result;
};
return shell;
};

フィボナッチ関数は以下のように定義できるようになるとのことです。

var fibonacci = memoizer([0, 1], function (shell, n) {
return shell(n – 1) + shell(n – 2);
});

fundamental は再帰における差分式ですね。さて、再帰の基底条件はどこに隠れたのでしょう？あと shell はなんでしょう？

「JSGP: 再帰とmemoization」への2件のフィードバック

  2. 小川さん、論文をダウンロードしました。ちらりと論文のなかのコードを見ただけなのですが、かつてモバイル言語がはやっていたときに Java で strong mobility (実行中のコンテキスト = スタックごと移動)を目指した人々のコードも例外処理を使っていたなぁと思い出しました。東大の関口さんや私のところにいた浅野さん、たしか首藤さんもこういうことをやっていたように思います。スタックの保存と call/cc はかなり近い関係にあって、特に Lazy にコンテキストを serialize するような場合には、ほとんど同じような実装になるんじゃないかな？部分継続 (partial continuation) の機能を実装するとさらに類似性が出てくるような気がします。

コメントは受け付けていません。