Squeak Smalltalkで変態的に末尾再帰最適化をする。
Python や Ruby のような平凡な刀もとい言語でのクロージャーなどを使うフロー制御方法などもなかなか興味深いですし、それらをデコレーターやメタプログラミングと組み合わせて適用するところも秀逸なわけですが―
それはそれとして、ひとたび阿良々崎計紀が鍛えし無双の変体刀もとい言語のひとつである Smalltalk をふるうからにはそれ相応に、他の追随を許さない変態的な方法でないと。ｗ
というわけで、thisContext（実行中のコンテキストにアクセスできる擬変数。嘘刀流奥義としてはもはや奥義とも呼ぶのもためらわれる、おなじみの技です。ハイ^^;）から手をつっこみ、呼び出し元のメソッドやそのコンテキストを改変してしまうことで、再帰呼び出しを GOTO文のように振る舞わせよう、という奇策をとってみました。
まず #tco と #tco:with: という二つのメソッドを、どのオブジェクトからでもコールできるようにクラス Object に定義します。
Object >> tco | method index | method := thisContext sender method. (index := method indexOfLiteral: method selector) isZero ifTrue: [^self]. method literalAt: index put: #tco:with:. method literalAt: (method indexOfLiteral: #tco) put: #yourself
Object >> tco: arg1 with: arg2 | sender | sender := thisContext sender. {arg1. arg2} doWithIndex: [:val :idx | sender tempAt: idx put: val]. sender restart
メソッド#tco は最適化したいメソッド中で self tco のように書いて用いるメソッドで、（結果的に）初回呼び出し時だけコールされます。コールされると自身の実行中コンテキスト(thisContext）から自分の呼び出し元、つまり対象となるメソッドのコンテキストをたぐり寄せ（thisContext sender）、メソッドオブジェクトにあるリテラル（の、特にメソッド中で再帰呼び出しを含む他のメソッドのコールに使われているもの）を強制的に書き換えてしまいます。
具体的には、対象となるメソッド内における再帰呼び出しを別に定義した #tco:with: の呼び出しに、自分自身（#tco）の呼び出しを #yourself（自分自身を返すだけのメソッド）呼び出しに置き換えています。したがって、いったん #tco がコールされると、呼び出し元のメソッド中にある #tco自身も、対象メソッド自身も呼び出されることはなくなります。
他方で、再帰呼び出しの代わりにコールされるメソッド#tco:with: は二つのことをしています。ひとつめは、自分自身のコール時に添えられた仮引数（arg1、arg2）の値を、呼び出し元コンテキストにおいて対応する仮引数（下の例では int と acc）にそれぞれ代入することです。そしてふたつめは、これがこの方法のキモなわけですが、メソッドのプログラムカウンターを巻き戻す作業です。そして自らはそのまま終了します。
戻ると、そこでの実行時コンテキストのプログラムカウンターは勝手に巻き戻されているため、インタープリターは対象となるメソッドを仮引数の値が更新された状態のまま何の疑いもなく最初から繰り返し実行します。これにてめでたく GOTO的挙動が完成、とういわけです。
では実際に試してみましょう。たとえば次のような #sum1:acc: と、それに self tco. を書き加えただけの #sum2:acc: があったとして、
Object >> sum1: int acc: acc int < 0 ifTrue: [^ acc]. ^self sum1: int - 1 acc: int + acc
self sum1: 10 acc: 0 "=> 55 "
Object >> sum2: int acc: acc self tco. int < 0 ifTrue: [^ acc]. ^self sum2: int - 1 acc: int + acc
self sum2: 10 acc: 0 "=> 55 "
手元の環境では、単純な再帰の前者（#sum1:acc:）は 10000000 くらいで根を上げてしまいますが、それに self tco を加えただけの後者（#sum2:acc:）では同じ再帰呼び出しが内部的に書き換えられて GOTOのように振る舞うため、メモリを喰いつぶさずにちゃんと結果である 50000005000000 を返してこられるようになります。
――
「だけどさ、とがめ。これってかなり限定的な局面でしか通用しない技だよな？ 仮引数が増えた場合には #tco:with:with: とか #tcoWithArguments: とかで対応するとしても、敵が相互再帰とかだったらどうするんだ？」
「ちぇ…、ちぇりおーっ！！！」
