斜め方向から fib を高速化する方法

id:sumim:20100910:p1 に絡めて、せっかくなら Smalltalk ならではの変わった方法もひとつ…とひねり出してみたのがこちら。

Integer >> fib
   | temp1 temp2 mine me sender |
   temp1 := 0. temp2 := 1.
   self > 1 ifTrue: [(self - 1) fib].
   mine := temp1 + temp2.
   me := thisContext method.
   sender := thisContext sender.
   sender method  == me ifTrue: [sender tempAt: 2 put: mine].
   sender sender method == me ifTrue: [sender sender tempAt: 1 put: mine].
   ^mine

[1000 fib] timeToRun   "=> 3 ms "

二個手前までの実行時コンテキスト（スタックフレーム）をたぐって、それぞれ（一つ前のコンテキストでは二つ目の、二つ前のコンテキストでは一つ目の）一次変数を書き換え、その和をもって返値としています。再帰をしている（(self-1) fib のコール）のに、その返値は使っていない―というところで再帰の副作用しか使っていないことが（Smalltalk が読めなくてもなんとなく）おわかりいただけると思います。

Smalltalk ならでは―とか言いつつ、おそらく Ruby（の特に MatzRuby）以外であれば、今時の動的な言語ならできるはずです（実はよく調べないで書いているのですが、動的言語を名乗るからには、このくらいは出来て欲しいという期待を込めて^^;）。