Derive Your Dreams

コメント等は 掲示板 にどうぞ

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::option、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さん みたいなのを解くのに使えるもの。コードは見ての通りシンプルで、同値類を木構造で表現して、 木のルート＝代表元として扱う、それだけです。前者の解説にあるように、ちょっとした最適化として

とすると、頑張った解析の結果、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* 265536 = 5、 … なので、これも事実上5を超えることはないので定数みたいなものと思って良い関数です。

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

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

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

まとまってないな

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

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

16:04 08/08/10

Google Code Jam 2008 Round 3

Google Code Jam Round 3。283位。 通ったけどっ…。ううむ酷い。 あ、4位と5位 Japan だ。すごい。

Bのlarge、今動かしてみたらsmall用に出したコード（ O(マップサイズ^3) ） そのままでも6分で解けました。やればよかったー。ワープポイント片方は使う直前に設置するだけだから、 きっとちょっと考えれば 2乗 にできてそれが正解なんだろうなーと思って、でも考えずに他を やってました（その認識自体は間違ってないと思うんですが…）。 次数300の点が1677万個のBFSをsetでvisited管理しててこんなもんなのか。

次のボーダー100位は、今回でいうと45点が安全圏か。2問に絞って small/large 両取り狙いだな。

17:22 08/08/07

火星

Round 3 で早くも終わってました。チーム名 Macrott です。 全然駄目なことは自分でも承知てますがここまでサックリやられるとは思わなんだ。 Lightning のやつは火星人賢くない前提で回避してたような気がするからそのせいかな…。

街路ビュ

Google地図のストリートビュー、オーストラリアでも見られるようになってました。 自宅さらしあげ。 普段居るところ。 同じデータベースで、逆向きの検索…写真送ったら住所返すサービスも、難易度ははるか上だろうけど 技術的にある程度可能になってる気がするんですが、それは本当にプライバシー等々で難しいだろうなあ。

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での反論を否定されていて、私には何が得なのか未だに分かりません。

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

  1. 最初の記事 で提示された C++ のコードは Static な Duck typing です。 Dynamic なことはできません。
  2. Python の例は Dynamic なことができます。
  3. Static なことだけができても多態の例としては不完全です。 Dynamic なことができなければ意味ないです。
  4. ゆえに、最初の記事 ではまるで 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 というクラスの定義やそこからの派生の必要がなくなると、そもそも何故嬉しいのか？」 というポイントに立ち返ってみます。私の考えでは、大きく分けて２つ嬉しいポイントがあります。

  1. Pet というクラスを定義しなくていいので嬉しい。手間が省けて楽ちん
  2. 派生しなくていいので嬉しい。 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 コードを書く」 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++ 信者の自分としては朝飯前ですが、それが簡潔で美しいコードになるかというと疑問だなあ…と

presented by k.inaba   under NYSDL.