2011/10/18

Primary Abstraction

これは面白い考察。

steps to phantasien(2011-10-15)

プログラミングが要するに何なのか, いちばん自在に扱える抽象は何か. 私はプログラマの Primary Abstraction (PA) と勝手に呼んでいるけれど, それはたぶん人によって違うとおもう. 技術的側面の PA を持つひともいれば, アプリケーションドメインの PA を持つ人もいる. 間にある人もいる. 仕事の数だけ抽象がある. 人々はどんな抽象を背にコードを書いているのだろう.

自分のPAは何かなーと考えてみた。「ツリートラバーサル」というのは かなり近く、実際自分はコードをツリーとして考えてると思うんだけど (Lispの構文は頭の中のツリーをそのままダンプできるからとても楽なのだ)、 ツリーだけだとちょっと制限がきつすぎて問題をちゃんと反映してない気がする。

多分、自分の頭の中で操作してるのは有向グラフ(DG)だなあ。 これは空間的にデータ構造を眺める時もそうだし、時間的に状態遷移を眺める時もそう。 ツリーはDGの特殊な場合なので、上のエントリの「プログラミング=ツリートラバーサル」と 「プログラミング=状態遷移」はどちらもサブセットになってる。

ツリーというのはとっても素直なモデルで、問題がそれで表現できるなら話がうんと簡単になる。 モデルの途中の任意のノードに注目すると、そこから下のサブツリーだけ 切り出すことが出来るからだ。したがって問題を、独立した部分問題へと分割して それぞれを解決し、後で組み合わせることができる。分割統治はアルゴリズムの基本ですな。

でも現実の問題は、分けたはずの木が先のほうでまたくっついちゃったり ぐるっと回って前の方に合流したりしてて、 そうなると好きなノードから分割するというわけには行かなくなる。 データ構造で先が合流してると、ナイーブにトラバースすると同じところを 何度も通って指数的時間がかかるし、循環があると終わらないかもしれない。 時間的な面でのグラフの合流の例は、mutableなデータの変化だ。 ある時点であるmutableな構造が特定の値をとったとして、その状態に どうやって至ったか、いくつもの可能な経路があるので、トラブルシューティングが難しい。

ツリーじゃなくなるとかように色々面倒なので、 できる限りツリーで済ませられるところはツリーにしようとする、 というのは自然なことだろう。 プログラミング言語のモデルの選択に、そういった気持ちが反映されているような気がする。 でも現実はツリーに収まらないので、ある面をツリーに押し込めようとすると 別の面にしわよせが来る。

手続き型言語では、関数の呼び出し関係(制御の流れ)をツリーに保とうと頑張っているようだ。 ループ構文はあるけれど、ひとつのループはひとつの関数の中に制限される。 手続き型言語だけ見ていればそれは当然の選択に思えるかもしれないが、 関数型言語では相互末尾呼び出しを使って、ループが複数の関数にまたがることは普通で、 そっちから見れば、ループ構文は関数呼び出しをツリー関係に保とうとしたがための制限に見える。

手続き型言語から入った人が、末尾再帰を不自然に感じるのは、 関数呼び出し関係＝ツリー、というモデルが頭の中にあるからじゃないかと思う。 継続も、関数の途中から制御の流れを別の場所につなげるものなので 制御ツリーモデルに馴染まない。それが、継続が理解しにくい理由のひとつだろう。

制御の流れをツリーに押し込めようとしたしわよせは、mutableなデータの時間的遷移に 押し付けられている。問題が純粋なツリーでない場合、どこかにmutableなデータを 用意してそれを書き換えてゆくような形にすることが多い。いやもちろん、動的に 新しいデータをアロケートして情報を付け加えてゆけばimmutableにも書けるんだけれど、 それはあまり一般的でないようだ。手続き型言語によるプログラミングでは、 関数呼び出し関係でツリーに固執するわりに、データ構造をがんがん書き換えて データの時間的遷移についてはぐっちゃぐちゃのグラフになることに抵抗が 無いみたいだ。自分もCで書く時はそんな感じだし。

一方、純粋な関数型言語では、データ構造に合流や循環は現れない。 データのidentityがその内容でしか判断されないので、あるノードが上流から 共有されているのか、それともノードのコピーがそれぞれあってツリーになっているのか ということは判断できないし、区別する必要がない。循環を表したい時は サンクを挟むことになって、それはどっちかというと制御の循環になる。

そう、関数型言語では関数呼び出し関係の方が有向グラフになっている。 末尾呼び出しはcall/returnではなくてジャンプなのだ、というのは 単なる最適化の知識ではなく、頭の中のモデルがそうなっているのだ。 だから、関数をまたげないループ構文はひどく不便に見える。

「末尾呼び出し最適化してるとスタックトレースが見られないじゃないか」、 という議論があるけれど、それは「データを書き換えちゃったら 後でデータの履歴がわからなくなるじゃないか」っていうの話の裏返しかもしれない。 どっちのモデルで考えるかによって、どっちが重要かが逆転する。

んで、純粋関数型で合流や循環がぐちゃぐちゃしてる問題を解こうとすると、 データ自体は綺麗なツリーに保っておいて、 DGのノードは関数の方にマップすることになる (モナドもsyntax sugarを取り除けば関数の末尾呼び出しからなるグラフですな)。

まあ、理屈の上では全てそれで書けるはずだけれど、問題によっては関数へのマップに ちょっと無理があるように感じられることもあるんだよな (そんで、モナドはその 無理をがんばって隠しているような)。いやきっとこう感じるのも、自分の頭の中の モデルが、両者の混合になってるからなんだろうけど。

• 関連エントリ: グラフ指向理解

Tag: Programming