d.y.d.

03:14 08/08/31

LLFuture

行ってきました。まとめ記事は何百人も書いてそうなので、以下、これにかこつけて自分語りをする。

☆ Larry Wall の基調講演。ひたすら Parser の話をしてて素晴らしかった。 ☆ 100年の言語…は、 Ypsilon の藤田さんが、エラーメッセージのわかりやすさについて考えてますか？という問いかけをされてたのが印象に残っています。個人的にこの頃から気になってるんですけども、言語内DSL のようなものを作ること＆そのDSLが正常動作するときに裏でホスト言語で何が起きているかをまったく気にしなくていいようにすることは簡単でも、そのDSLがそのDSLのシンタックスや静的セマンティクスとして間違っているときに適切なエラーを出せるようにするのは非常に面倒、という感覚があります。ホスト言語の意味でのエラーを出されてもユーザ側としては「エラーがある」ことだけしか情報が伝わらなかったりする。なんかどうにかならんかねー、という。DSLじゃない通常の言語のエラーメッセージのわかりやすさもある意味で同じ問題のような気がしている。

1000年のスパンだと……もの凄い昔にここの日記に一遍書いたけども、個人的には、プログラミング言語に限らず "General Unmisusability" が達成されているといいなあ、という夢が。夢のまた夢が。言語で言うと、「１：よろしくないプログラムを動かすと何が起きるかわからない」 → 「２：よろしくないプログラムを動かすと実行時に正しくなくなった時点でそれがわかる」 → 「３：よろしくないプログラムを動かす前に、テストなり静的な検証なり証明なりで検出できる」 → 「４：よろしくないプログラムなど（黒魔術を駆使しないと）書くことすらできない ─ コンパイル時に型チェックで怒られるとかいうレベルではなく、怒られるようなモノを書こうにも書きようがない」 → 「５：同、黒魔術を駆使しても書くことすらできない」というような段階があると思う。んで、「よろしくなさ」のうちの細かい部分部分については、いろんな人の工夫の結果４の段階に達しているものもある。もちろん、大部分はそうでない。それが、1000年の未来なら、プログラミング言語なんぞに限らず任意のシステムについて４を達成するための汎用理論みたいなものができあがってるといいなあ、という。セッション中に質問の出てた「セキュリティ」もそういう方向に解決されたり。

☆ Webフレームワークの話は正直あんま期待せずにいったんですけど面白かった。ひがさんかこいい。 ☆ LLでアートの話はもっと期待してなかったんですがもっと面白かった。ビジュアルプログラミング言語のデモ中に「とにかくさくっと線で繋いで好き勝手値を見られるのが便利」というのがあって、それはまさにその通りだと思う。そういうことができる環境… 実行中のコンテキストのブラウザとか実行中のサーバにつないでREPLプロンプト出してというのは本当にLightweightに見えるし、いろんな言語がそういう方向に向かっていくと面白いと思う。あと、JavaScript の開発はそういう方向になっててるらしいよみたいな話を昼食時にGusさんに聞いた気がする。

☆nishio/tokuhirom/yugui/shinh を集めてする話がゴルフ、というのはいくらなんでももったいなくないですか！みたいな！☆LLVMとかの話はまさかのなつたん登場(違)しかあんまり覚えてない。 ☆LTは自走式サーバー素晴らしすぎた。あーゆーガジェット（？）を物凄い勢いで作れるのはプログラミングの楽しさの一つだよなあ。あとPitの話おもしろかった。

09:01 08/08/26

今週～来週の予定

8/28の朝：成田に着く。 8/30：LL Future 見に行く。 8/31：あろはさんを問い詰める。 9/2か3：Ｄ論の中間発表であわあわする。 9/4の夜：成田を発つ。なんか用事がある人は適当に捕まえてください。適当にっていうか、去年も思ったんですけど、LLのみたいなデカいイベントに行っても誰が誰だかわからないまま「あの人も来てたのかー」と後から悔やむのはもったいない気がするので、古典的ですけど何か目印でもつけてった方が面白いのかな。『乱択アルゴリズム』を常に小脇に抱えてます見かけたら声かけて下さい！とか。

IF

Independence Friendly Logic というのを id:ytbさんのとこで知って色々読んでみてるところです。

普通の論理の量化子は、内側の変数は外側の変数に依存して決まることになっている。　"∀x∃y. yはxの親"　は、「どんなxに対しても、xに応じてうまくyを選べば、 "yはxの親" がtrueになる」という意味だ。「誰にも親がいる」。これは、量化子の順番を変えると意味が変わる。　"∃y∀x. yはxの親"　は、「うまくyを選べば、どんなxに対しても、"yはxの親" がtrueになる」という意味。これだとyはきっと女王アリとかそんなの。いや、そんなのでもダメか。まあどうでもいいです。数学で出てくるε-δ論法による連続の定義で ∀x∀ε∃δ を ∀ε∃δ∀x にすると一様連続の定義になったりする。

そういう風に内側外側という位置関係で暗黙の依存具合を固定しちゃうんじゃなくて、もっとその辺りフリーダムにするとどうなるよ？というのが Independence Friendly Logic。例えば、"∀x∃y/x. yはxの親" というIF論理の式は、「どんなxに対しても、xに依存しないでうまくyを選べば、"yはxの親" がtrueになる」を意味する。スラッシュが「○○には依存しない」の意味。この例だと結局のところ "∃y∀x. yはxの親" と意味が変わらないんですが

　　∀a∃b∀c∃d/a. hoge(a,b,c,d)

こんな論理式（bはaに依存する。dはcに依存するけどaに依存しない）を考えてみます。

　　「どの県aにもその県を舞台にしたマンガbがあって、どんな人cにも知り合いdがいて、dはbを読んだことがある」

という日本語は意図的に曖昧ですが、曖昧さを活かして２通りの読み方をしてみよう。 ∀a∃b∀c∃d/a. hoge(a,b,c,d) で解釈すると、d を決める時に a に依存してはいけないので、この主張は、「誰にも、全県の代表的なマンガを読破してるようなマンガ好きの知り合いがいる」という主張になります。一方で、∀a∃b∀c∃d. hoge(a,b,c,d) と解釈すると、a に依存して d を決められるので、「誰にも、どの県の県代表マンガでも、知り合いを総当たりすれば読んだことある人がいる」くらい。クレヨンしんちゃんを読んだことある知り合いと幕張サボテンキャンパス読んだことがある知り合いが別人でもいい、という意味になる。

実は、普通の、順番だけで依存関係を決める方式では、どう量化子を並べ替えても ∀a∃b∀c∃d/a と完全に等価な意味の論理式を記述することができません。つまり、IF論理を使うことで、よりキメ細かな条件の記述も可能になってるわけです。実際、見た目以上にこの論理は強力らしく、一階論理のままでありながら二階論理（"人"のような個体だけでなく、集合や関数に関して∀や∃で量化できる論理）並に色々書けるらしい。

最初にリンクした Wikipedia のページからたどりながら色々読んでたんですが、そこの参考文献の先頭にあった Feferman 先生の批判がそちらも面白くて、「一階論理のままでありながら」というところが本当かかいなと突っ込んだりそもそも推論規則に基づかないこれは「論理」か、という話があったり。他にも、この論理は元々ゲーム意味論で意味づける（「不完全情報ゲーム」を使う。 ∃に対応する手を打つときには、ゲーム相手∀の、依存してない手に関して目隠しして手を決めないといけないという制約）らしいんですが、どれで読んだのかメモるの忘れましたが、相手の手だけじゃなくて、自分の前に打った手も忘れて戦略を決めるような状況も考えるような話も楽しかった。さっきのマンガの例だと、「dはaに依存しちゃいけない」を「dを決めるときはaでの選択は見えない」としてだけ解釈すると、「aは見えないけど自分の手bは見える」ことになってしまって、それはほとんどaが見えてるようなものではないか等々。単に∃と∀の交代制ゲームとして定式化する時はその辺り気にならなくても、compositional な意味を考えようとすると気になるらしい。etc, etc

20:49 08/08/20

例外と継続とジャンプ

昨日の続き…になるかな。(2) の方ですね。要はまず自分の中に

Stream s;
try {
  s = File.Open(".tcshrc");
} catch( FileNotFoundException e ) {
  try {
    s = File.Open(".cshrc");
  } catch ( FileNotFoundException e ) {
    s = new EmptyStream();
  }
} // あるいは if(s==null) try{s=...}catch(...){}  の羅列

というコードは

try {
  for(int i=0;; ++i)
    array[i].doSomething();
} catch( ArrayIndexOutOfBoundsException e ) {}

と同じ種類の醜さを感じるので避けられるなら避けたい、という感覚があります。完全に正常な制御フローを実現するのに例外を経由するってどうなの？っていう。なので、例外ではなく return で分岐ができた方が嬉しい場面ってのは存在するだろう、というのが一つ。あるいはちょっと別の見方をすると……

Multi/Long Jump

「エラー処理」や「例外的な状況」のようなそこに人間が付与している意味ではなく、純粋に言語の表現能力としての「例外」には、（排反ではないですが）二つの機能があると思うのです。「複数の継続」と「大域ジャンプ」。複数の継続というのは…要は、例外なしでは関数はreturnでしか呼び出し元に戻れない、１カ所にしか戻れないこととの対比を意味しています。「こういう状況ではここに戻ってここのコードの続きを実行する、ああいう状況ではあっちに戻ってあそこのコードの続きを実行する、…」というのが、例外ならばできる。その複数の戻り先を、必要なら、いくらでも関数呼び出し地点から遠くに置けるというのが大域ジャンプ。

エラー処理としての例外は、「大域ジャンプ」まで含めて初めて本質だろうと思っています。「実行したいこと」からエラー処理のコードを切り離せることや、無視したら次々親に向かって飛んでってくれるのが嬉しいところですし。 try～catch の構文は、そういうエラー処理の専用構文としてスマートになるように作られていて、そうではない本当に必要なのは「複数の継続」だけというケースには、より適した書き方が考えられるのではないか。

※ 逆に言うと、「エラー」からの復帰コードを書きたい、っていうときには try-catch を使うべきでしょうからガンガン使うといいと思う。Informative Null Pointer を使ったら try-catch が使えなくなる、なんてことはないので。

Normal/Exceptional

もちろんそういう場合には、「CPSやcall/ccを使って、あるいは言語組み込みのreturn先指定機能で本当に真っ向から複数の継続を取る」や「Maybe や Error や option のような付加情報をもつオブジェクトでreturn値をラップして、使う側はパターンマッチetc」、あるいは「多値の二個目の返値に付加情報を入れといて必要ならそっちで分岐」のような、色んな方法が考えられます。

前二者と今回のエクストリームぬるぽを比べた時の差は、基本的には、「普通にノーマルなオブジェクトが返されてそれを使うというケースだけを考えたいとき」に書かなければならないコード量が増えるか増えないかの差、それだけです。そういう使い方を想定しないケースではまったく要らない子です。なのでもし十分使いやすいシンタックスシュガーがあればMaybeやOptionで十分ということには同意。どこまで可能でしょうか。

※ ただ、その用途で「無効値であった」という 1 bit 情報しかない Maybe や Option を使うのは無情報 null を返すのと変わらないので、それよりはせめて Error 辺りを基本にしたいなーというのはあるかも、昨日の(2)の話に至る以前の(1)の動機として。多値バージョンについても同じく。 (1) については「ぬるぽってだけ言われても"たいてい"エラー行の周りを"見れば"原因わかるだろ」とゆー突っ込みが大いにあると思うんですけど、うーん、「エラー行の周りとか "見るまでもなく常に" 原因わかる方が絶対楽だろ」かな。それによってnullを返す側が大変になるということは…あるかなあ…

あるいは、「例外投げる版」と「情報入り返値返す版」を二つ用意して使い分ければ変な NullPointer など要らずに行けますが、ほとんど同じことをするメソッドを２つ並べるってわかりにくいと思うのだ。

あとで考える

22:33 08/08/18

Informative Null Pointer (1)

　　Λ＿Λ　　＼＼
　（　・∀・）　　　|　|　ｶﾞｯ
　と　　　　）　　 |　|
　　Ｙ　/ノ　　　人
　　　 /　）　　 < 　>_Λ∩
　＿/し'　／／. Ｖ｀Д´）/
　（＿フ彡　　　　　　　/

最初に言いたいことをまとめておくと「null はもっと情報量を持ってるべき」。

以下、こういう言語及びAPI設計が仮にあったらどうだろうかと考えてみた、というお話です。具体的な実装とかは何もありません。あと、引き合いに出してる例がだいたい Java ですが、自分の知ってる範囲で Java が一番例外をAPIの前面に出しててわかりやすいかと思ったのが理由で、他の言語でも基本的に同じことが言えると思います。それと、例によって「それ○○でできるよ」「それ○○でダメ出しされてるよ」募集中。

ぬるぽ！って言われて何で困るかっていうと、どのファイルのどの行のどの変数が null なせいでエラーになったのかまではわかっても、「何故」その変数が null なのかわからんことだと思うのです。どこかでうっかり初期化を忘れてた変数を set したのが原因でフィールドが null になってるんだったら、それがわかった方が嬉しい。どこかでタイポのせいで Map から存在しないキーを get しちゃってたのが理由だとしたら、どこでなんて言う存在しないキーを叩いちゃってたのか知りたい。ただの「NullPointerException」ではなく。

というわけで、null というただ一つの値じゃなくて、未初期化変数にはデフォルトで UninitializedNull クラスのオブジェクトが入って、get は存在しないキーに対しては KeyNotFoundNull を返し、 Integer.getInteger は問題の種類に応じて KeyNotFoundNull か NumberFormatErrorNull を返せばいいと思う。そして、どの null も参照したら単なる NullPointerException ではなく、それぞれ対応する例外を飛ばす、と。

Ruby なんかだと、nil と同じメソッドだけ用意してあとは method_missing で自分自身を raise するようなオブジェクト作れば、かなりの程度↑これに近い物ができるんじゃないでしょうか。「それがnil的値である」ことの汎用の判定手段をどうにかしないと使い物にはならなそうですが。

型

null はどんな型の変数にも代入できてこその null なので、例えば Java の型システムは、リテラルの null には特別な型 <nulltype> を与えて、これは全ての型のサブタイプ、という定義になってると思います。上に書いた色々な Null クラスも、型システム的にはこいつらのインスタンスの型は全て null の型と同じということにしたらだいたい型チェックは何とかなるんじゃないでしょうか。適当です。

実装するとしたら

「普通のオブジェクト」と「Nullオブジェクト」の区別は何とかして高速にできるようにしておいて（ポインタの最下位ビットをフラグに使うとかそういうアレで）、今まで null チェック (== 0?) だった部分をその高速チェックに置き換えれるようのコンパイル/解釈すればだいたい良いんじゃなかろうか。再び適当です。

どのくらい情報を載せる？

単に「ぬるぽ」が「あんいにしゃらいずどぬるぽ」に変わっても正直大して変わらないので、「クラスXXのオブジェクトがここのnew式で作られた時にフィールドyyが初期化されてないぬるぽ」くらいの情報が無いとあまり意味がありません。ただ、毎回実行時にここまで情報を持ったオブジェクトを生成するのはコストが大きすぎる気がしますね。UninitializedNull に関しては、コンパイル時に作っておける程度の情報を載せるので我慢するべきか。Java のような２パス初期化でなくて１パス初期化する言語なら、「全てのフィールドをちゃんと初期化するように書かないと未初期化で放っておくのはすごい重いよ」と脅すのも手かもしれません。 KeyNotFoundNull 辺りは遠慮無くスタックトレースまで載っけても怒られないのではないでしょうか。

Informative Null Pointer (2)

ここから同意してくれる人がガクッと減りそうなので話を分けてみる。

自分で上の文章を読み直してただちに浮かんだ疑問は「KeyNotFoundNull とかは例外を投げるべきところじゃないの？」っていうのと「そもそも null って必要なの？全ての変数にちゃんとvalidな値を与えるようにプログラム書いたら？」っていうのでした。その辺りに関係なくもない内容をつらつらと考えました。

例外と Invalid Value

ちょっと話がそれますが、一言で言うと、そうですね、「Integer.valueOf が気に入らない」。

Integer n;
try {
  n = Integer.valueOf(someStringData);
} catch( NumberFormatException e ) {
  n = 0xdeadbeaf;
}

Integer.valueOf に数値として解釈できない文字列を渡すのは、渡した側のバグなんでしょうか、それともそれは正当な入力なんでしょうか。渡した側のバグだとするなら…「整数として解釈できる文字列ならその整数値、そうでなければデフォルト値」というコードを上のように書くのは間違いということになります。でも他に手段がない。Integer クラスには、整数として解釈できる文字列か否かのチェックメソッドが存在しないし、でもそういうチェックをしたいことは実際ある。 …ということは、おそらくそれはバグではなく、正当な入力なのでしょう。しかし、正当な入力に対して例外を返すAPIというのは、自分の感覚ではどうも受け入れられないのです。「try～catch は常に意図しないor不可避のエラー処理」「if～else は意図した正常パスの分岐」とすっきり分けた方が、コードが読みやすいのでは。分けられないとしたらそれは言語に問題があるのではないか。

これを if 文にするには、Integer ではなく「Integer が入ってるかもしれないし入ってないかもしれない型」を返すメソッドとして作る手があります。C++ならboost::optional、OCamlならoption、HaskellならMaybe。

Maybe<Integer> mn = Integer.valueOf(someStringData);
Integer n = case mn of Just v  -> v
                       Nothing -> 0xdeadbeaf;

これの問題はひたすら面倒くさいところで、Integer.valueOf の使用例の9割は「整数として解釈できないものは来ない」状況でしょうから（だからこそ NumberFormatException は「例外」なんだと思う）、その9割のコードが余計な皮のせいで一回り面倒になるのは嫌です。別に Maybe とか使わなくても、null 返せばいいじゃん null。

Integer n = Integer.valueOf(someStringData); // 整数として解釈できなければnullを返すものだった場合
if( n == null ) n = 0xdeadbeaf;

このパターンなら、9割の「整数として解釈できないものは来ない」と信じられる状況では null チェックを省いてそのまま n を使えばいい。例外を投げるインターフェイスで catch を省くのと同じ。面倒くさくない！

Integer n = Integer.valueOf(someStringData);
... あとで n を使う ...

問題は、「整数として解釈できないものは来ないと信じていたのに裏切られた」場合です。元々の例外を投げるバージョンなら、そこで直ちに NumberFormatException 例外が飛びます。そして、この部分のコードが頼っていた暗黙の仮定が破られたこと、つまりバグの存在がすぐに判明します。パーフェクト。素晴らしい。null を返す場合どうでしょう。「... あとで n を使う ...」で n を使った時に初めて、NullPointerException が飛びます。まあ同じメソッド内ですぐに n を使っていたら大差ないのですが、「ここではメンバ変数にnを値を格納して、100年後くらいに別のメソッドで使う」ような処理だった場合、100年後にぬるぽに飛ばれても、絶対どこのバグなのかわかりません。めちゃめちゃ困ります。

INP returns

…というわけで、やっと話が戻りました。このパターンを、先程の "Informative Null Pointer" で救えるのではないかと思うのです。ここでただの null ではなく NumberFormatNull を返していれば、「チェック有り版をif文で書ける」「チェック無し版を書くのが面倒くさくない」「チェック無し版でバグが出たときに、nをいつ使っても十分な情報量の例外が飛ぶ」ようになります。さて、どうでしょう。

もちろんまだ問題はあります。たとえば、当然みなさま突っ込む準備万端だと思いますが、「最後まで n を使わなかった場合バグが判明しない」じゃないか、という。まあその通りです。どうしたものでしょうね。伝統的な「エラーを戻り値で示すのは良くない」という警句の理由は、「エラーを無視して先に進めてしまうから」なわけですが、今回の場合、エラーコード専用の戻り値を返すのではなく、メソッドの存在意義となっているような返値にエラー情報を「載せる」形になっている分、握りつぶされる可能性は大分少ないはずではあります。とはいえ、フィールドに保存しておいて結局最後まで使わなかった、みたいなのは大いにあり得ます。専用のエラーチェックモードで動かしていたら、（あるいはパフォーマンスが許すなら常に）、 GCで解放する直前にフィールドチェックしてUninitialized以外のXXXNullオブジェクトが入ってたら例外飛ばすのはどうだろう。いや、そもそもフィールドへのXXXNullの代入やクロージャへの囲い込みは全部その時点で例外でいいような気もしてきました。はてさて。

他には、「あとで」例外に飛ばれても、その時点でデバッガでデバッグ開始しても手遅れになってるかも、というのも問題かな。スタックトレースだけ残ってても、その時点の色んな変数の値とかが残ってないと困りますよね。これも深刻な問題。

そもそも / 補足

そもそも Integer.valueOf の場合は、「不正な文字列を渡すのは渡した側のバグなので例外飛ばす」という仕様でよくて、別にチェック用のメソッド、Integer.isParsableAsInteger とか用意するのがベストだろうと自分では思っていたりします。ただ、アトミック性を考えると、チェックと実際の処理を分けられないこともあって、

File fp;
if( File.exist(".tcshrc") )
  fp = File.open(".tcshrc");
else if( File.exist(".cshrc") )
  fp = File.open(".cshrc");
else
  ...

なんかAPIがJavaじゃなくなってきてますが気にしないことにして、こういうコードは、existからopenの間にファイルを消されたら死にます。というわけで、File.open が例外を投げるインターフェイスの場合、「○○が存在したら△△、しなかったら☆☆」という制御フローを try～catch 無しで書くのは非常に難しい。でも正常な制御フローに try～catch は使いたくなくない？

File fp = File.open(".tcshrc");
if( fp instanceof <FileNotFoundNull> )
  fp = File.open(".cshrc");
if( fp instanceof <FileNotFoundNull> )
  ...

っていう。

19:35 08/08/14

信長の野望

「烈風伝　速攻クリアーへの道」というページを見かけたのでやってみました。結論としては1540年代同盟無し単独統一は可能（ただし武田家だと今川家と最初から同盟状態で始まるので、49年の頭くらいまで待って手切れ）。ゲームスタート時に即同盟切るのは忠誠度的に厳しそうだし、初期位置が東寄りなのも実は不利なので、本気で単独最速を目指すなら斉藤か織田でスタートかなあ。 1548年の内にクリアも可能だと思う。ポイントは、(1) 絶対に[建設]特技持ちに門を壊させること。力押しに比べて必要な兵力がぐっと減る (2) 支城は兵数1でいいので別働隊を隣接させると本隊が横を通り抜けられるようになるのでそれで全て通過する (3) 好戦的な大名と領地を接する期間をできるだけ短くするように進む

証明

id:uskz さんのこれとかこれとか。自分の場合、ややこしいと言われている方の証明の気分の方がわかるので（あすこで背理法はしないような気もしますが、まあ、どうだろ）、なんとなくその感覚について考えてみる。どっちが良いとか悪いとかでなくて、こういう感覚と思うと多少読みやすいのでは、というお話です。

たとえば『(A-B)∩(A-C)=Φ ⇒ A-B⊆C を証明しろ』といわれた瞬間に、何も考えないと脳内で自動的に『仮定「(A-B)∩(A-C)=Φ、xは任意、x∈A-B」から「x∈C」を証明しろ』に変換される感があります。とりあえず ⇒ と ∀ はすべてはぎ取ってあとで演繹定理等でくっつける。 Coq でいうと、いきなり intros と打ってみてから後のことは後で考える。 Haskell でいうと、point-free style で書こうとするんじゃなくって、とりあえず引数は全部引数名をつけて変数に置いてみる。あと、あんまり今はabstractな性質を考えてない（と感じられる）記号 ⊆ が結論部に来たときは定義まで戻ってバラしてしまったりする。

で、そういう風にプリミティブな形に結論をバラせば、あとは適当に式の形を見ながら、てきとーに構文的に組み合わさるところを組み合わせてけばなんか証明になるだろ、みたいな。わりと機械的にできる感が嬉しい。閃きが要らない。背理法がありがたがられるのは、しめすべき結論が「矛盾」というさらに超シンプルな目標になるので、適当に式を組み合わせて最終形を目指すときに組み合わせ先がわかりやすいから的な感覚はあるかもしれない。で、それで証明できなかったら初めてマジメに式を睨み始める。「A1ΔA2=B1ΔB2 ⇒ A1ΔB1=A2ΔB2」もそうで、集合の = は⊆かつ⊇の略記でΔは-と∪の略記なので、とりあえず機械的にその『仮定 A1ΔA2=B1ΔB2 結論４つ』に脳がバラしてしまって、それでその流れで証明できたら終わりで良いんじゃないの？という考え。必ずしも美しい証明にはならないかもしれませんが。

式をバラさないで同値関係の書き換えでやろうとすると、目標に向かうときに最初にどこをどう書き換えたら良いのかが見た目明らかでなくて（いや、今回の例くらいだとわりと明らかかもしれませんが）、なんか何をしたらいいのかがよくわからんというか。

18:17 08/08/12

Union-Find と Ackermann と私

Union-Find というデータ構造があります。同値関係を求めるパズル @ rubycoさんみたいなのを解くのに使えるもの。コードは見ての通りシンプルで、同値類を木構造で表現して、木のルート＝代表元として扱う、それだけです。前者の解説にあるように、ちょっとした最適化として

二つの木を併合するときには、必ず大きい木のルートの下に小さい木をくっつけるようにする
代表元を求める計算（find）のついでに、通ったノードの親ポインタを全てルートに張り替える

とすると、頑張った解析の結果、n 回の union/find 操作にかかる計算時間は O(n A(n)) ─ A(n) はアッカーマン関数の逆関数 ─ になることがわかっているが詳細は略、と、大抵のデータ構造の教科書には書いてあります。そしてアッカーマン関数は有り得ないぐらい急激に増大する関数なので、その逆は実質定数みたいなものだ、と書いてあります。

　「ところで、なんでここにアッカーマン関数がでてくるの？？」

というのは誰しもが抱く疑問だと思いますが、先日ふとこの疑問を思い出したので調べようと思い、 "Top-Down Analysis of Path-Compression" を読み始めてみました。

Hyper-Log

といっても、実はまだアッカーマンまで理解していないのであった。 O(n log^* n) で押さえられるところまで把握。log^* n というのは、「n に何回 log2 を適用したら 1 になるか」を表す関数。 log^* 2 = 1、 log^* 4 = 2、 log^* 16 = 3、 log^* 65536 = 4、 log^* 2⁶⁵⁵³⁶ = 5、 … なので、これも事実上5を超えることはないので定数みたいなものと思って良い関数です。

これはいわばアッカーマン関数を m=4 に固定した場合…いわば「アッカーマン第四形態」の逆関数に過ぎず、そして~~フリーザ~~アッカーマン関数はあと無限回の変身を残しているので足下にも及ばないのですが、まあ十分すぎるくらい十分デカいことはデカいわけです。（ちなみに第一 = n+1、第二 = 2n、第三 = 2ⁿ。変身するたびに「直前の関数をn回適用する関数」になる）

…話がそれました。その第四形態になる直感だけ書いておきます。えーと、具体的に何が示されるかというと、Union-Find する対象集合の要素数をn, find操作の回数をm としたときに、ポインタ付け替えが発生する回数は O((n+m) log^* n)」なことが示されます。

※ 細かい話：コスト評価を簡単化するために、「まずパス圧縮なしで union だけで作り上げた木構造」を考えてから、その上で、実際に起きたパス圧縮を実行、という考え方をするそうです。この場合、「パス圧縮」は、親ポインタをルートに張り替えるだけでなくて、ルートじゃない中間ノードに親ポインタを張り替えるパターンも含まれます。（元々ルートだったノードに下のノードをパス圧縮→unionでルートじゃなくなる、というパターンが unionでルートじゃなくなったノードの下のノードを、パス圧縮でそのルートじゃなくなったノードを指すように付け替え、みたいに表現される）。あと、値はだいたいなので切り捨て切り上げ±1しないと正しい言明にならないところは多々あると思いますが、色々とスルー推奨。

「大きい方の下に小さい方を」的にバランスを取ると、できる木の高さは、パス圧縮を考えなくても、高々 log n。全体に限らず、すべての部分木でそういう性質（高さは要素数のlog）が成り立つことが言える。
そういう木の場合、葉からの高さが r 以上のノードは高々 n / 2^r 個くらいしかない。（高さ log n のノードはルートだけなので１個。葉っぱに近いノードほど指数的に個数が多い）
h = 木の高さ ≦ log n とする。「TOP: 葉からの高さが log h 以上のノード集合」と「BOTTOM: 葉からの高さが log h 未満のノード集合」に分割統治してパス圧縮のコストを考える。
TOP におけるパス圧縮のコスト（ポインタ付け替え回数）は、祖先じゃなかったものが親になることはありえないことを考えると、ナイーブに計算しても、「ノード数 × 最大高さ」程度。すなわち (n / 2^log h) * h = n。
BOTTOM のノードがパス圧縮で TOP のノードを親に持つ回数は、せいぜい n+m 回。親がBOTTOMからTOPに付け変わるのはBOTTOMの各ノードに付き最高で1回なので、≦ n。 TOPの親からTOPの別の親に変わる回数は当たり前に≦m回。
BOTTOM に入ってる木の高さは全部 log h 以下なので、この分割統治の再帰は log^* h 回で終わる。
よって全体の計算量は O( (n+n+m) log^* h ) ≦ O((n+m)log^* n)

まとまってないな

「パス圧縮は木を上下に分割統治して考えられる」「木を (log 高さ) で上下に分割すると、バランス木なら、ルート側には n/高さ個しかノードが残らない」「残らないのでナイーブに評価してもルート側のコストは O(n)」「リーフ側は高さが log に減ってるので再帰が log^* 回で止まる」。

たぶん、上下分割を log ではなくてもっと別の逆アッカーマン第m形態でやって、ルート側やマージ処理の評価をナイーブにやるのではなく、一段階前のアッカーマン関数を使った評価にすると、本当にそれっぽい計算量が出てくるのではないかと思います（まだ読んでないけど）。

17:44 08/08/06

イヌネコＸ

Re: わんにゃん3 　　お忙しそうなところ、ホント長々とすみません。まとめる方向で…

私は、実行時にspeakすること（dynamic）が必要な状況を思いつきませんでした。今でも分かりません

私も、そもそもプログラムで犬猫を順番に鳴かせることが必要な状況を思いつきません。そういう話ではなく、あれは、あくまで多態のひとつの「例」です。speak の代わりに toString でもいいし、 redraw でもいいし、 uflow でもいいし ++ と * でもいい。「これら（に代表される）全てで dynamic 多態は不要」とお考えでしょうか。そうではないと思いますが…。

例の表で行くと、Bruce Eckel は「nonintrusive-implicit-dynamic だけあればいい（interfaceなしで多態はできる。静的型不要テストだテスト）」という立場です。その根拠としてあのエッセイのコードがあります。そういう文脈にある(*) Python や Java のコードに対して「C++ ならもっと（or 同程度に）巧くできるよ」と言って持ち出すコードは、論理的に言って、元でできた必要な多態のパターンをカバーしていなければならないはずです。そうなっていなかったので（dynamic な部分をカバーできていないので）、おかしい、というのが、繰り返しになりますが私の主張です。それだけです。

（* あ、たぶんそうではないと思いますが一応… 最初に本論はどうでもよかったと断っておられるのが「この文脈からも切り離してコードを論じようとしていた」という意味であれば、その文脈を切り離して元のコードを論ずるのはおかしいという主張、と言った方が適切になりますね。逆に言うと、この文脈から切り離して論じるなら、cons型リストや const char* で表示するのも完全な解だと同意します。その点については全く異論ありません。ただ、文脈を切り離すなら、「彼らは依然として、彼らの言語が最上であると信じている。よろしい、ならばC++だ」という言及は不適切でしょう。）

☆

「多態 ⇒ speakというメソッドを持った異なるクラスのオブジェクトを統一的に扱う、という図式」というのが「多態といえば必ずtrue polymorfisimじゃ無いと駄目だろう」的な意味であれば、そういった前提は特にありません。何かしらのtrue polymorfisimは無いと駄目という前提です。私個人は型大好き型が無いと死ぬ人間なので、static な方も無いと駄目だろうと思っていて、だから Bruce Eckel の主張には全く同意できませんが、それはまあ今回はどうでもよくて。

あの speak の例単体を static な方法で、C++ で書けるのは確かです。そして、C++ の static duck typing には静的な型安全性や実行効率、メタ情報処理の可能性等々、 dynamic な duck typing にない利点が多々あるのも（Bruce Eckel が同意するかどうかはともかく）確かです。なので元の例に対し、「dynamic な duck type はできないが、C++ なら代わりに色々なものを得たこんなコードが書ける」という一長一短な例として、最初のコードを出すのはアリだと思います。dynamic duck typing ができないことで失われる物との得失差を考えると C++ の方が凄いという方向に論を進めることさえ、可能であろうと思います。こう、データとアルゴリズムの分離によるコードの Generic 化を進めると static な多態の司る領域が増えていくよみたいな議論とか、パラメタ化された型に関するディスパッチは static な型情報を元にやると便利だよとか、自分としても色々考えてみたいことが（以下略。そういう主張を意図しておられたのであれば、すみません、まったく読み取れてませんでした、そしてそういう、dynamic じゃなきゃできないことだけが多態じゃないぜ、という方向には何ら異論ありません。

22:12 08/08/05

Runtime Concept

何か書こうと思って調べてたら、既にこのテーマのちゃんとした解説が存在していました！みんな→ 今週の茶袋：introduction to runtime concept 見るべき。見たらここから下読む必要ないですが、えーと、一応、問題としては、

#include <iostream>

class Cat {
  public: void speak() { std::cout << "meow!" << std::endl; }
};
class Dog {
  public: void speak() { std::cout << "woof!" << std::endl; }
};
int main() {
  Speakable s = new Cat;
  s.speak();
  s = new Dog;
  s.speak();
}

こういうことができる、「speak できるものならなんでも格納できる型 Speakable」を C++ で作りたい衝動にかられた時どうすればいいか、という話があります。解としては、例えばこう。メモリ管理手抜きですが。（あと "speak" が 3 回に分かれて登場しているのが汎用性の点で面倒なので実際はトリックで 1 箇所にまとめられたりしますが余りにも例示としては酷いので普通の書き方で。）

#include <boost/shared_ptr.hpp>

class Speakable {
  struct ProxyBase {
    virtual ~ProxyBase() {}
    virtual void speak() = 0;
  };
  template<class T>
    struct Proxy : ProxyBase {
      boost::shared_ptr<T> p;

      Proxy(T* p) : p(p) {}
      virtual void speak() { p->speak(); }
    };
  boost::shared_ptr<ProxyBase> p;

public:
  Speakable() {}
  template<class T> Speakable(T* p) : p(new Proxy<T>(p)) {}
  virtual void speak() { p->speak(); }
};

まあ、詳細はどうでもよくてですね、お気づきの方も多いと思われますが、これは「operator() できるものならなんでも格納できる型が欲しい」と全く同じ形の問題です。つまり、 Boost.Function や Loki の Functor と同じことをやっていて、実装に使われているテクニックも全く同じ。Modern C++ Design で１章割いて解説されています。あるいは、 Boost.Any が、これのメソッド無し版のようなものなので、ソースは非常にシンプルですがキーアイデアは全部詰まっています。こっちのソース見るのもわかりやすいかも。要は、界面（この例では Speakable のコンストラクタ）ではテンプレートで静的な型情報 T を捕まえて、内部に変数として保持するときは継承と virtual 関数を使って動的な形で、静的には型 T を忘れた形(ProxyBase)で持ちます。

この技法自体のライブラリ化も過去に何通りかの方法でなされていて、 dynamic_any (template ベースのインターフェイス)、 BIL (preprocessor ベースのインターフェイス) などが有名です…が、どっちも絶賛放置中ですね。

分類

shinhさんとこの分類表だと nonintrusive-implicit-dynamic-typed かな。 C++ でも、nonintrusive-implicit-static-typed が必要なだけならこんなテクニックまったく要らないので、そこんとこ注意。

（"X" を定義する側は一切何もしなくていいという意味で implicit なんだけど、 "Duck"として使いたい側が"Duck"と明示しないといけない＆"Duck"とはなんぞやを明示的に定義しないといけないという意味では explicit なんだよね。そこんとこどうなのか問題）

08:43 08/08/05

イヌネコ３

Re: わんにゃん２（※申し訳ない。リンク張り忘れてました…）

元々の例を別の言語で書き直したら良くなったと主張するなら、元と同程度の拡張性を保った例でなければ意味がありませんとstaticでの反論を否定されて、ご自身でdynamicでの反論を否定されていて、私には何が得なのか未だに分かりません。

わかりにくくてすみません。私の主張をまとめると、こうです。

最初の記事で提示された C++ のコードは Static な Duck typing です。 Dynamic なことはできません。
Python の例は Dynamic なことができます。
Static なことだけができても多態の例としては不完全です。 Dynamic なことができなければ意味ないです。
ゆえに、最初の記事ではまるで Python の例より C++ の例の方が優れているように書かれていますが、そんなことはありません。（Bruce のコードとの比較でいえば、Pet クラスがない、型安全、の二点では優れていると言うことはできるでしょう。しかしその代わりに Dynamic なメソッド呼び出しを無くしては、そもそも例として成立してません）

1. と 2. は同意いただけているように思います。3. はどうでしょうか。もちろんそちらはstatic/dynamicなんて書いていないです。これは id:gnarlさんが提示した主張 ── 多態の例を論ずるのに Dynamic な話を外すのはおかしい、という主張です。「staticだけで良いとも書いていません。」とのことなので、 3. については否定も肯定もされておられないようです。しかし私は「static だけでは良くない」と主張します。そして、1. 2. 3. から 4. が論理的に導かれます。そして 4. が私の言いたいことです。 他に言いたいことはありません。

追記：あ、これでは Dynamic な例を持ち出すと何が得なのか～の直接的な答えになっていませんでした。すみませんすみません。ええと、Dynamic な例抜きでは、上の 1. の最後 "Dynamic なことはできません" や 2. の "Dynamic なことができます" という議論をすることができません。そしてそれを論じなければ、（この点ではまだ同意に至っていませんが）主張 3. より、元の Python での実装と C++ での実装の良し悪しを比較することはできません。その比較が可能になるところが「得」です。

枝道として

上記の主張 1. に対して、「あのC++のコードは Dynamic でないが、それは C++ があの例を Dynaminc に扱えないことを意味するものではない」という異論はあり得ると思いました。これはその通りです。しかし、そういうコードは明らかに基底クラス Pet を使うよりも複雑になります（これも同意いただけると思います）。従って、Dynamic なコードを書いてもやはり Bruce の元記事への反論にはならないだろう、という補足を、先日、先々日の私の記事には含めてあります。

上記の主張 3. に対して、「そもそも元の Bruce の例は多態の話ではない、なんでここで多態が出てくるの？」という異論がありうることは……想定していませんでしたが、結局、こちらとそちらの意見が合わない部分というのは、どうも、そういう話なのでしょうか。私の読解した限りでは、元の Bruce の記事の例は、「speakというメソッドを持った異なるクラスのオブジェクトを統一的に扱いたい場合（要は多態したい場合）、 Javaだといちいちinterface定義して継承しないといけない面倒くさい。Pythonならそんなもの要らぬ」という例であって、「"meow!\nwoof\n" という文字列を標準出力に表示したい場合、 Javaだといちいちinterface定義して継承しないといけない面倒くさい。Pythonならそんなもの要らぬ」という例ではないと思うのですが。後者のように解釈されているのであれば、それは誤読だと思いますよ。

「では次のコードは拡張性のないコードにあたるのでしょうか、あたらないのでしょうか」で上げてくださったコードは、今度は、対象とするメソッドが全て定数文字列を標準出力に表示するのみ、という場合に固定されてますよね。拡張性無いです。

Pet or Object

いえ、前の例も上の例もJavaのようなObjectをテンプレートで実装すれば可能ですよね
　～(略)～
で、おっしゃる通り、C++ だと、「派生しない」ように書くことはできても、 Pet クラスに似た何かの定義を省くことはできそうにありません。

PetではなくObjectです。

いえ、不可能です、少なくとも私の知識の範囲では。あと、Object ではなく Pet です。 Object クラスは speak() というメソッドについて何も知りません。 Pet クラスは speak() について知っています。端的に言えば、Object クラスの定義に speak という文字列は登場しませんが、Pet クラスの定義には登場します。私がデフォルトの共通基底型 Object や Pet クラスに似た何かと述べたときは、そのような区別を意図していました。わかりにくかったらすみません。

そして、私の知る限りでは、例えば C++ で

vector<SomeClass> pets;
pets.push_back( new Cat );
pets.push_back( new Dog );
command( pets[rand()%2] ); // ここでどうにかして speak メソッドを呼び出す

こういう書き方を可能にするためには、SomeClass クラスが speak メソッドについて知っている必要があります。なので、JavaのようなObjectでは不可能で、ObjectではなくPetに似たクラスの定義が結局必要になります。

もし speak という特定のメソッド依存でない方法でこれが可能なSomeClassクラスの作り方をご存じなら、それは物凄いことだと思いますので、コードを公開していただけると冗談でなく泣いて喜びます。あと、それが可能なら、上記の「枝道として 1.」の私の主張が崩れますのでその部分は撤回します。 C++ は犬猫の例を Python のように Dynamic に扱えることになると思います。

11:11 08/08/04

イヌネコ２

Re: わんにゃん

Objectを使えないのがC++のstatic duck typingと他のdynamic duck typingの違いですか？それとももっと別のものなのでしょうか。
　～(略)～
共通基底を使わないで書けといわれたら書けません。私にはObjectも共通基底にしか見えないのですが、ちがうのでしょうか。

別のものです。ちがいます。なぜなら、たとえ C++ に全オブジェクトのルートクラスたる Object があったとしても、先日私が書いた Java のコードのような書き方はできないからです。

Object* pets[] = {new Cat, new Dog};
for(int i=0; i<2; ++i)
  command( pets[i] );

command の中で speak() を呼ぶ手段は存在しません。（いや、正確にはこの例だけなら if( typeid(*obj)==typeid(Cat) ) ～ とかなんとかイヌとネコで分岐すれば書けますが、Bob が増えた瞬間にその command は使えなくなりますので、やっぱりそれでは書けてることになりません。）従って、「デフォルトの共通基底型 Object があること」は、この例においては、 C++とその他の言語の差ではありません。

Java には getClass().getMethod ～があるので、実行時に (dynamicに)、speakを実装している任意のオブジェクトから speak を呼び出せます。Python の例も構文は違いますがやっていることは全く同じです。C++ にはその手段がありません。共通基底型があることではなく、「dynamic にメソッドを取り出せるかどうか」が、違いです。 OCaml の例などはまた違うことが起きているので、そちらはまた別の話になりますけれども。

もちろん C++ でも class Pet { public: virtual void speak() = 0; } のように、speak を実装済みであることを示す共通の型 Pet を定義して、全ての speak できるクラスはこの Pet から継承するようにすれば、dynamic にメソッドを取り出せるようになります。でもこれだと、wiseler さんの言葉を借りれば Petという意味の無いclassが存在してしまいますね。

また共通基底を使うことが特定の例に特化した拡張性のないコードを書くことにあたるのですか？

いいえ。コンパイル時に配列の長さと全ての要素のとりうるパターンが有限通りに決定している場合にだけ適用できるコードを書くことが、特定の例に特化した拡張性のないコードを書くことにあたります。

何が正解か

というか、どうして犬猫からそういった発展をしなければいけないのかもよくわかりません。

あなたがプログラム上で使う配列は全てコンパイル時に長さと要素のとりうるパターンが有限通りに決定しているのでしょうか？それならばおっしゃる通り発展しなくてもよいと思いますが、そんなことはありませんよね。

あ、「犬猫の例のような duck typing 的使い方をする配列に関しては、全て、コンパイル時に長さと要素のとりうるパターンが有限通りに決定しているべきである」という可能性はあると思います。これが成り立つならば、確かにあのように発展する必要はまったくありません。その通りです。ただ、これがプログラマの間での自明の共有認識ということはないと思いますし、実際使われている Python や Ruby のプログラムもそうなっていないことも多いです。なので、もしそう主張されたいのであれば、「べきである」理由を論じていただけると嬉しいです。

例えばテンプレートをつかってclassを無理やり閉じ込めて、 std::vector使って書けば（私には書けませんが）書けるのでしょうが、それで共通基底を使わないことになるのかどうかも疑問です。それが正解だとすると、私にはこの例こそ疑問です。

この例こそ疑問な理由がわからないのですが、加算機生成の例と対比されてることからすると、 C++ の手足を巧妙にもぐような恣意的な例だから疑問、ということでしょうか。それでしたら、１個上の段落に戻って「こんなコードは実際のプログラムでは使うべきでない恣意的な例だ」と示していただけますか。私の感覚では、static ducktyping では足りない dynamic な処理は、 C++ でも実際にclassを無理やり閉じ込め云々する技法によって広く使われているので、特に恣意的とも思えませんので。

関連するようなしないような話になりますが、ちょっと「Pet というクラスの定義やそこからの派生の必要がなくなると、そもそも何故嬉しいのか？」というポイントに立ち返ってみます。私の考えでは、大きく分けて２つ嬉しいポイントがあります。

Pet というクラスを定義しなくていいので嬉しい。手間が省けて楽ちん
派生しなくていいので嬉しい。 Cat や Dog を定義する側がどういう使い方ができるかまで全部ガッチガチに規定するのではなく、あとで、使う側が、たとえば「"speak() できる" っていう基準でオブジェクトをひとまとめに分類したい」と思ったら好き勝手にそういう使い方ができる。（→ non-intrusive性）

で、おっしゃる通り、C++ だと、「派生しない」ように書くことはできても、Pet クラスに似た何かの定義を省くことはできそうにありません。なので、嬉しいポイントが 1. だけだとすると、手間は全然省けてませんから私にも共通基底を使わないことになるのかどうかも疑問です。ついでにいえば、元々の Bruce Eckel 氏の記事は（ナナメ読みですけど）ポイント 1. に話を絞ってるように思えたので、 classを無理やり閉じ込めて云々する解法は元記事に対する反論としては意味ないよなあ、と私は先日の記事を結びました（結んだつもりでした）。

しかし、ところでポイント 2. もまた嬉しいポイントです。 static 版はもちろん、dynamic 版も実際に Boost 等の鍵となる技術として使われています（→ 再びid:Cryolite氏の記事）。自分としては 1. はどうでもいいので 2. の方がよっぽど重要です。これが使えなくなると、かなり書けるコードに制約がかかりますので、 ducktyping は static で十分だとはとても思えないのです。

12:34 08/08/03

Google Code Jam 2008 Round 2

Google Code Jam の Round 2 でした。某Cup に撃墜されながら頭をコンテストモードに慣らして参戦。

A は、各ノードについて「ここを 0 にする最小コスト」と「1 にする最小コスト」(できないなら∞) をボトムアップに計算。例えば AND-CHANGABLE なノードを 1 にする最小コストは min(左の子を1にする最小コスト+右の子を1にする最小コスト, 1+min(左の子を1にする最小コスト,右の子を1にする最小コスト)) とかそんな感じに、下から計算していける。 O(M)。

B は、(x1,y1)=(0,0) と固定していい（範囲内の三角形は、平行移動すれば(0,0),(N,0),(0,M),(N,M)のどれかには必ず頂点をぶつけられるのでそこを原点と見なしてOK）ので残り4座標 O(N^2M^2) で全部試すコードで Small を通す。最初原点固定でいいことに気づかず30分近く苦戦してました。しばらく考えてたら (x2,y2)=(1,M) も固定でいい（三角形の面積は |x2y3-x3y2|/2 = |Mx3 - y3|/2 なので x3=(A+(M-1))/M, y3 はその余り, みたいにすれば 0～NM/2 の全ての面積が作れる）のに気づいたので Large はそれで。O(1)。これはひどい。

C は、3次元と絶対値と割り算と"10pt"を見て逃げることを決意。というか、もう点数は足りてると思ったので D の方ばっかり考えてました。

D は、Small は全Permutation試して実際に圧縮してみるだけ O(k! |S|)。 Large は、とりあえず、前計算しておけば Permutation を１個固定したときの圧縮後サイズ計算は |S| に依存せず可能。例えば Permutation が {3, 1, 2, 4} だったら、圧縮後サイズは、要は左から右に読んでって文字が変わる回数なので、(S[4i+3]!=S[4i+1] な i の個数) + (S[4i+1]!=S[4i+2] な i の個数) + (S[4i+2]!=S[4i+4] な i の個数) + (S[4i+4]!=S[4(i+1)+3] な i の個数) とかだいたいそのくらいになって、各 (～な i の個数) は O(k^2|S|) くらいかけて k*k のテーブル作っておけば定数時間で引ける、と。このテーブルを d として、あとは、最適なPermutationをメモ化探索。best(1, {2,3,4}) = min( d[1][2]+best(2, {3,4}), d[1][3]+best(3, {2,4}), d[1][4]+best(4, {2,3}) ) みたいな再帰。 best(ここまでに使った最右の添字, 残ってる添え字集合)。O(k 2^k) です。実際 Submit したコードは境界の処理をもっといい加減に総当たりしてたので Large 解くのに3分かかって焦りました。（※ あー、やっぱり端っこの処理で O(k^2 2^k) は要るかも？）

戦略

基本的には

一番ミスが少なく書けると思えるアルゴリズムで、とりあえず Small を解く。（それが計算量的に Large を解けないアルゴリズムでも気にしない。逆に、今回のAとかは全探索よりも上記のDPの方が絶対ミス少ないと思ったので、そういう場合はいきなり Small/Large 共用ソースで行く。）
Small 通す。これでテスト入力ゲット。Small 解が正しいことはシステムが保証してくれてるので、同時に正しい出力もゲット。
Large を頑張る。さっき入手したテストデータを使えば、間違ってるかどうか手元でテストできる上に、 Small の出力と比較するとどこが間違ってるかまでわかる。お得。

なんですけど、みなさんどんな感じなんだろう。最終的に見ると Small 専用コードを書く時間が無駄に見えなくもないのですが、他の選択肢「テストデータ無しでいきなり対 Large コードを書く」 or 「テストデータを自分の手で2,3個作る + 対 Large コードを書く」は、自分の場合それ以上に時間かかる気がするんですよね。

13:37 08/08/01

イヌネコ

そうですね、Javaの例もいただきたいのですが、誰も書いてくれませんということらしいので。

class Cat {
  public void speak() { System.out.println("meow!"); }
}

class Dog {
  public void speak() { System.out.println("woof!"); }
}

class Bob {
  public void speak() { System.out.println("hello, welcome to the neighborhood!"); }
}

public class PetTest {
  static void command(Object obj) throws Exception {
    obj.getClass().getMethod("speak").invoke(obj);
  }

  public static void main(String[] arg) throws Exception {
    Object[] pets = {new Cat(), new Dog(), new Bob()};
    for(Object pet : pets)
      command(pet);
  }
}

でいいんじゃないのかな。少なくとも、getClass().getMethod(" ～ ").invoke が C++ のテンプレートの嵐より簡潔さに欠けると言うことはないと思います。静的な型安全性が無いのは C++ 版に劣るところですが、id:wiseler さん的に Python や Lisp の例は OK らしいので、そこは最大の焦点でないととりあえず判断しました。さて、ところで、

  public static void main( String[] arg ) throws Exception {
    // 引数で指定された匹数ネコとイヌが交互に並ぶ
    int n = Integer.parseInt(arg[0]);

    Object[] pets = new Object[n];
    for(int i=0; i<n; ++i)
      pets[i] = (i%2==0 ? new Cat() : new Dog());

    for(Object pet : pets)
      command(pet);
  }

static/dynamic duck typingの違いを問題にして何が得になるかというと、「↑ こういうことは Java でも Common Lisp でも Scala でも Python でも楽勝で書けますが、 C++ はこれををまともに書けるんでしょうか？」という考察ができる所ではないかと思います。一番最初のコードのように、共通の基底クラス Pet から Cat や Dog が派生していれば、簡単ですね。でも共通基底を使わずに C++ でこれが書けますか？特定の例に特化した拡張性のないコードを書けば簡潔になるのは当たり前ですから、元々の例を別の言語で書き直したら良くなったと主張するなら、元と同程度の拡張性を保った例でなければ意味がありません。

※ いや、もちろん、Cat や Dog に基底クラスなんぞ導入せず型安全性を保ったまま上のように動的な配列にするくらい C++ 信者の自分としては朝飯前ですが、それが簡潔で美しいコードになるかというと疑問だなあ…と

Derive Your Dreams