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 でも平気で返してくるところが非常に気持ちいいですね。ただ、メモ化のところがすっきりと書けなくなってしまって、なんか本末転倒のような…。
