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

2011/10/18

ソナタ形式

子供の頃、学校の音楽の授業で「ソナタ形式とは 主題提示部(第1主題、第2主題)-展開部-再現部 からなる」って教わったんだけどずーっと疑問に思ってたことがある。 「展開部を欠くソナタ形式」ってやつ。

「第1主題再現部を欠くソナタ形式」ってのもあるけどそっちはわかりやすい。 ショパンの第2,3番ソナタ好きだったし。展開部で第1主題を使いまくってるから、 再現部でまた繰り替えさなくてもいいだろうと。でも展開部が無かったら 提示部と再現部で「第1主題-第2主題-第1主題-第2主題」になるから二部形式とどう違うんだ? と。 まあ疑問に思ってても特に聞こうとか調べようとかせずそのまま忘れてたんだけど。

今「テンペスト」をやってて第2楽章が「展開部を欠くソナタ形式」ってあるから 四半世紀前の疑問が蘇ってちょいと調べたら目から鱗。 ソナタ形式の最大ポイントって展開部の有る無しじゃなくって、 第2主題の調性(提示部では主調以外で出てきて、再現部で主調になる)だったのか。 確かにどのソナタもそうなってるけど、なんとなくそういうもんだろうとしか 思ってなかった。

そんで、テンペストの第2楽章はテーマが3つあるように見えて、手元の楽譜では それぞれ「Main Theme」「Episode」「Sub Theme」と書いてあるんだけど、 なんで2番目のがSub ThemeじゃなくてEpisodeってわかるんだ、というと、調性を見れば 提示部ではB♭ major(主調)からF major、再現部ではE♭ majorからB♭ majorになってる。 Sub Themeなら主調で始まるのはおかしい。だからこれは提示部のSub Themeを属調で、 再現部のSub Themeを主調で始めるための経過句だ、ってことになるのか。

あーなんかすごくすっきりした気がする。これで合ってる? > 音楽わかる人

Tag: Piano

2011/10/17

下流から変える

自分の開発過程でありがちなこと

1. Aという要素について、すげー改善のアイディアを思いついた。
2. 興奮して実装してみているうちに、その変更によってBという要素も変えないとならないと気づいた。
3. Bを変えると一緒にCとDも変えないとならないなあ。全部変えてテストするまでコミットできないなあ。
4. 変更の作業量が2日を超えて、 だんだん萎えてきた。
5. masterブランチの方でバグ対応やらなんやら。だんだん元アイディアのトピックブランチが遅れてゆく。
6. 久々にブランチ切り替えてとりあえずrebaseするんだけど、さて、どこまでやったんだか思い出せない…

3の段階で、とりあえず動かして有効なことを確認したら、 実際のコミットは逆方向にやると良いのだ。つまり、

1. 最下流のCとDを、現状のBでも変更したB'でも動作するように直してコミット。
2. 次にBを、現状のAでも変更したA'でも動作するように直してコミット。
3. 最後にAの変更をコミット。

これだと、常に動いている状態で小刻みにコミットできる。

下流の変更を、上流からの二種類の情報形式 (データ構造なりAPIなり) に対応させなきゃ ならないのは若干面倒ではあるけれど、上流も複数ある場合には 後で片方づつ変更できるから便利だし、うまい対応を考えてるうちに よりよい抽象化を思いつくこともある。

ただまあ、最下流の変更が一見何をしたいのかわからないような場合もあって、 共同開発してるときにはそのパッチの有効性について説得するのが難しいこともある。 個人プロジェクトだとわりと自由にできるんだが。

このパターンによく出会う気がするのでメモしておく。

Tag: Programming

2011/10/14

らむ太と言葉

最近こんなことが増えてきた。

• ら：ねえねえ、「かりん」ってなーに?
• 私：「かりん」? どういう時に使うの?
• ら：ひとが、こうやって、せんになってるでしょ。そこに、べつのひとがこうやってこんなふうになるんだよ (身振り手振りで必死に説明。数分のやりとりののち)
• 私：あああ、わかった! "cutting" か。"cutting in line" ね。日本語だと「よこはいり」だ。

耳で聞いて覚えてきた単語を文脈なしで唐突に尋ねて来るのでだんだん難易度が増している。ハワイ語の単語も学校で使うらしくて聞いてくるけどそっちはお手上げだ。

Tag: 生活

2011/10/14

runonce

『プログラミングClojure』に、マルチスレッド環境でも 与えた関数を一度だけ実行するrunonceという仕組みを作る例が出てくる。 似たようなことをGaucheでやる必要が出てきたのでちょいと書いてみた。

runonceは関数を引数に取り、

• その関数が既に実行されたかどうかを調べる関数 (has-run?)
• 初期状態に戻す関数 (reset)
• 引数を与えてその関数を実際に実行する関数。但し、既に実行されていた場合は実行せずに前の結果を返す。(once)

という3つの関数を返す関数だ。

Gauche風に書くとこんな感じになるかなあ。

atom は名前をClojureから取ったんだけど、使い勝手はかなり違うので注意。 Gaucheにトランザクションはないので、atomicな領域で副作用を起こして構わない。

gosh> (define-values [print-has-run? print-reset print-once] (runonce print))
#<undef>
gosh> (print-has-run?)
#f
gosh> (print-once "Aloha")
Aloha
#<undef>
gosh> (print-has-run?)
#t
gosh> (print-once "Mahalo")
#<undef>
gosh> (print-reset)
#f
gosh> (print-once "Mahalo")
Mahalo
#<undef>

なお、fnが引数を取らず、resetとかhas-run?が不要で 「引数なしの関数を一度だけ走らせれば良い」ということなら、単にdelayを使えば済むのだけれど。 (但し、0.9.2までのforceはスレッドセーフになっていないので注意。 開発版は安全。)

Tags: Programming, Gauche, Clojure