fix と memoize

Derive Your Dreams 発、結城さんのところほか、いろいろなところ経由で。なんだか流行っているみたいなので…(^_^;)。

まず、fix 。

Smalltalk のブロックを使ったプログラミングにおいて、一番身近な存在といえる Scheme 版を id:SaitoAtsushi さんのものを拝借して直訳してみました。

| fix fibMaker fib |

fix := nil.
fix := [: g | g value: [: x | (fix value: g) value: x]].

fibMaker := [: f | [: x | x <= 1 ifTrue: [1] ifFalse: [(f value: x-1) + (f value: x -2)]]].

fib := fix value: fibMaker.

^ (1 to: 10) collect: [: x | fib value: x]

=> #(1 2 3 5 8 13 21 34 55 89)

で、これを memoize 。

| fix fibMaker fib |

fix := nil.
fix := [: g | 
   | memo f |
   memo := Dictionary new.
   f := nil.
   f := [: x | memo at: x ifAbsentPut: [f value: x]].
   f := g value: f].

fibMaker := [: f | [: x | x <= 1 ifTrue: [1] ifFalse: [(f value: x-1) + (f value: x -2)]]].

fib := fix value: fibMaker.

^ (1 to: 10) collect: [: x | fib value: x]

ただ、この Scheme 版をを含めて一連の fix は再帰しているので（してちゃ悪いってことはないのですが…）、Squeak の化石がごとき(笑) Smalltalk のばあい、ちゃんとクローズしていない古典的仕様のブロックを、本格的なクロージャ（モダンな Smalltalk のブロック）にする ClosureCompiler が必要になります（ClosureCompiler のちょー手抜きなインストール手順は こちら）。

そこで、再帰せずに（ClosureCompiler を必要とせずに）同じことを可能にする関数を導き出す過程を描いてみました。もちろん、そんなものを私なんぞが考えつくはずもないので（ぉぃ…）、羊堂本舗さんの「Fの不動点」や、Love Ruby Net. な 青木さんの「Y Combinator」のほか、いくつかの資料を参考にさせていただいております。

ステップ１：自身（のコピー）を受け取ってそれを使う fib

| fib |

fib := [: ff : nn |
   nn <= 1 ifTrue: [1] ifFalse: [
      | aa bb |
      aa := ff copy fixTemps value: ff value: nn-1.
      bb := ff copy fixTemps value: ff value: nn-2.
      aa + bb]].

^ (1 to: 10) collect: [: nn | fib copy fixTemps value: fib value: nn]

ClosureCompiler がインストール済みなら、copy fixTemps は不要。

ステップ２：自身を受け取って fib を返す wrappedFib

| wrappedFib fib |

wrappedFib := [: ff |
   [: nn | nn <= 1 ifTrue: [1] ifFalse: [
      ((ff fixTemps value: ff) value: nn-1) + ((ff value: ff) value: nn-2)]]].

fib := wrappedFib value: wrappedFib.

^ (1 to: 10) collect: [: nn | fib value: nn]

ClosureCompiler がインストール済みなら fixTemps は不要（以下同じ）。

ステップ３：wrappedFib を受け取って fib を返す unwrapper

| wrappedFib unwrapper fib |

wrappedFib := [: ff |
   [: nn | nn <= 1 ifTrue: [1] ifFalse: [
      ((unwrapper value: ff) value: nn-1) + ((unwrapper value: ff) value: nn-2)]]].

unwrapper := [: ff | [: arg | (ff fixTemps value: ff) value: arg]].

fib := unwrapper value: wrappedFib.

^ (1 to: 10) collect: [: nn | fib value: nn]

ステップ４：fibMaker を受け取って fib を返す fix

| fibMaker fix fib |

fibMaker := [: ff |
   [: nn | nn <= 1 ifTrue: [1] ifFalse: [(ff value: nn-1) + (ff value: nn-2)]]].

fix := [: gg |
   [: hh | gg value: [: arg | (hh value: hh) value: arg]] 
      value: [: hh | gg fixTemps value: [: arg | (hh value: hh) value: arg]]].

fib := fix value: fibMaker.

^ (1 to: 10) collect: [: nn | fib value: nn]

ステップ５：fix を分解

| fibMaker fix fib |

fibMaker := [: ff |
   [: xx | xx <= 1 ifTrue: [1] ifFalse: [(ff value: xx-1) + (ff value: xx-2)]]].

fix := [: gg |
   | kk ll |
   ll := [: hh | [: arg | (hh value: hh) value: arg]].
   kk := [: hh | gg fixTemps value: (ll value: hh)].
   kk value: kk].

fib := fix value: fibMaker.

^ (1 to: 10) collect: [: nn | fib value: nn]

ステップ６：メモ化した fibMemo を返す fixMemo

| fibMaker fixMemo fibMemo |

fibMaker := [: ff |
   [: xx | xx <= 1 ifTrue: [1] ifFalse: [(ff value: xx-1) + (ff value: xx-2)]]].

fixMemo := [: gg |
   | kk ll memo |
   memo := Dictionary new.
   ll := [: hh | [: arg | memo at: arg ifAbsentPut: [(hh value: hh) value: arg]]].
   kk := [: hh | gg fixTemps value: (ll value: hh)].
   kk value: kk].

fibMemo := fixMemo value: fibMaker.

^ fibMemo value: 10000

=> 544383731135652813387342609937503801353891845546959670262\
477158412085828656223490170830515479389605411738226759780263\
173843595847511162414391747026429591699255863341179060630480\
897935314761084662590727593678991506779600883065979666419658\
249377218003814411588410424809979846964873753371800281637633\
177819279411013692627509795098007135967180238147106699126442\
147752544785876745689638080029622651331113599297627266794414\
001015758000435107774659358053625024617079180592264146790056\
907523218958681423678495938807564234837543863426396359707337\
562600989624626687461120417398194048750624437098686543156268\
471861956201461266422327118150403670188252053148458758171935\
335298278378003519025292395178366894676619179538847124410284\
639354494846144507787625295209618875972728892207685373964758\
695431591724345371936112637439263373130058961672480517379863\
063681150030883967495871026195246313524474995052041983051871\
683216232838597946272459197714546282183996957892237989121994\
317754697052161310810965599506382972612538482420078971090547\
540284381496119304650618661701229832889643527337507927860694\
447618535251444210779280459799045612981294238091560550330323\
389196091622366987599227829231918966880177185755555209946533\
201284465023711537151417492909131048972034555775071966454252\
328620220195060914835852238827110167084330511699421157751512\
555102516559318881640483441295570388254775211115773957801158\
683970726025656148249564605387002803313118614853998053970315\
557275296933995860798503815814462764338588285295358034248508\
454264464716815310015331804795674363968156533261525095711274\
804119281960221488491482843891241785201745073055389287178579\
235094177433833315068982393544219888054293324403711948672155\
435765485654991345192710989198026651845649278278272129576492\
402355075955582056475693653948733176590002063731265706435097\
094826497100387335174777134033190281055756679317894700241188\
030946040343629534719974613922747915497303564126330742308240\
519999961015497846673404583268529603883011207656292459981362\
516523470939630497340464451063653041636308236692422577614682\
88461791843224793434406079917883360676846711185597501

fib では 30 くらいでもうかなり待たされるのに、メモ化された fibMemo では 10000 でも平気で返してくるところが非常に気持ちいいですね。ただ、メモ化のところがすっきりと書けなくなってしまって、なんか本末転倒のような…。