空想犬猫記

※当日記では、犬も猫も空想も扱っておりません。(旧・エト記)

etolisp 進捗 (33) 〜 継続について考えてみる

なんでも継続」というテキストを読んで,継続について考えてみた。メモ代わりに文章化してみる。

ぶっ飛んだ理解

プログラミングにでてくる継続の概念が難しく感じるのは,私が馴染んでいるようなC/C++のような言語から見ると,継続は言語のランタイムによって隠蔽されており,普通にプログラミングしている限りは,目に見えないからだと思う。

これは,思ったよりも重要な考え方かも知れない。今頭の中にあるプログラミングの世界が2次元だとすると,継続というのは,もう1つの隠された次元で,コンピュータのプロセスはその次元でなめらかに動いている。しかし継続を明示的にサポートしない言語は,その隠された次元に自由にアクセスすることができない。そういう言語では,継続が操作された瞬間を,returnやgotoやfor文やsetjmpや例外処理を通して,不連続な「ジャンプ」として認識するが,継続を考慮した空間では,継続から継続へ渡り歩く連続的な振る舞いとして理解できる。2次元の世界ではテレポーテーションのように見えていたものが,実は隠された次元の通路を使って,繋がっていた。。継続には,そんな面白い世界が潜んでいる。

そもそもC/C++にはそれを記述するコトバがないから,継続を説明するのは難しい。C/C++で継続をサポートする言語処理系を書くことはできるけど,その時には,実装中の言語の継続と,C/C++のランタイムに隠蔽された継続の,2つの継続を相手にしなければならない。他言語とのバインディングが実現されるのは,2つの継続が交差する場所になる。

もちろん,機械語の中では本当に不連続に「ジャンプ」してるから,機械語の世界では,継続は単なる概念に過ぎない。しかし,何かこう,物理学の世界の余剰次元みたいに継続を捉えてみるってのは,面白いと思った。

ワープする宇宙―5次元時空の謎を解く

ワープする宇宙―5次元時空の謎を解く

実装に向けて

etolispはロクに文献も調べず,頭の中でスタックがひょこひょこ動いてる人によって実装されていたので,lispの関数がCの関数に対応しており,構文木のてっぺんから先っちょまで再帰的に評価されるような素朴な造りになっている。これから継続をサポートしようと思うと(またもや!)大手術となること必至である。その上,実装上の手間に較べて,速度上の恩恵に与れるかというと,それほど期待は出来ない。

leaf-countはツリーの深さ分だけスタックを消費するが、 leaf-count/cpsでは全ての再帰呼び出しが末尾再帰だからスタックは消費しない。しかしアクティブなクロージャの数がツリーの深さに比例するから、リソース消費量のオーダーは結局同じなのだ。 (したがって、非末尾再帰アルゴリズムを単純に継続渡し形式に変換するだけでは「最適化」したことには必ずしもならない)。(『なんでも継続』より)

と書かれているのが,まさに私が懸念しているところだ。結局,スタックと同じことをスタックよりも効率の悪いヒープで行ってるだけになりそうな気がしている。それに勝るメリットが必ずあるはずなので,それが何なのかを考えているところ。末尾呼び出しの最適化がよりエレガントに記述できるとかかな(いや,知らんけどね)。

とりあえず前に進んでみよう。より高い次元に行けるような気がするし,そこに何かがあるような気がするから。