継続渡しスタイルと末尾呼び出し最適化
先日からなんとか理解しようといろいろやっています。
- 元のJavaコードを写経して確かにStack Overflwが起きないことを確認。この時点ではまだコードがなにやっているかよく分かっていない。
- まず、継続渡しスタイルについて、C++で書きなおしたりして、なにが行われているか大体理解しました。
- ついで、手書きによる末尾呼び出し最適化のコードもC++で書きなおしてみました。なにを行っているか、こちらも解りました。
- ところがなんかちゃんと最適化されている感じがしない。
- 調べてみると、C++ではラムダの再帰はループ最適化されないみたいです。ラムダを束縛する変数の型はstd::functionにせざるを得ないのですが、std::functionは型消去によって汎用ファンクタを実現していて、型消去は継承構造が入っているので、これはgotoに最適化しようがない、というわけ。
- ふーん、勉強になります…と思いながら、同じことをscalaで書いてみました。
- 継続渡しスタイルで末尾呼び出しにした(けどtailrecを使っていない)sumとかfibonacciとかはStack Overflowになりました。
- scalaは末尾再帰を最適化するようだけど、ラムダが絡んでくるような複雑なのは最適化できなみたいです。
- 限定継続という機能があるようだけどサポートされなくなるみたい。
- 末尾呼び出し最適化についてはscala.util.TailCallsというObjectが既にあります。
で、今に至ります。全然整理できていないですね…
「Javaによる関数型プログラミング」は会社の資料室にあったので借りました。著者のVenkat Subramaniamさんって「アジャイルプラクティス」の人ですかね。とにかく、この週末で読みます。次の貸出予約が入っていて早く返してっていわれているので。
それにしても、継続渡しスタイルとか、手書きによる末尾呼び出し最適化とか、こういうプログラミングテクニックってどこで学ぶものなんでしょうか。SICPとかですかね?