2011/09/01

アラビア数字・ローマ数字変換

お題：アラビア数字・ローマ数字変換 - No Programming, No Life

アラビア数字 <=> ローマ数字変換を行う関数、arabicToRoman および romanToArabic を実装せよ。

条件）

• ローマ数字の表記法についてはローマ数字 - Wikipediaを参考にすること。
• ローマ数字は半角英「I,V,X,L,C,D,M,i,v,x,l,c,d,m」のみ使用した文字列とし、それ以外はエラーとする。
• アラビア数字は整数 1 から 3999 のみ使用するものとし、それ以外はエラーとする。

Common Lispには時々わけのわからない機能がある。formatの~@Rもそのひとつ。

roman->arabicの方はちょっとズルした。formatの~@Rに対称な機能がparse-integerに無いのは美しく無いよなあ。

実行例

cl-user> (arabic->roman 11)
"XI"
cl-user> (arabic->roman 1888)
"MDCCCLXXXVIII"
cl-user> (roman->arabic "mdccclxxxviii")
1888
cl-user> (roman->arabic "McmXLv")
1945

Gaucheのformatはさすがにこの機能まで実装していないけれど、 slibのformatが使える。

(追記2011/09/03 09:19:59 UTC): さすがSmalltalk、そこにシビれる！あこがれるゥ！ アラビア数字・ローマ数字変換をSqueak Smalltalkで

自由気ままなSqueak Smalltalkにはわけの分からない機能がいやというほどあります。Integer>>#printStringRoman や String>>#romanNumber もそのひとつ。Integer と String に対象の機能があるのは美しいですね。^^;

Tags: Lisp, Programming

2011/08/30

テストの話

因果律を否定するバグ の話が意外に受けてて、そこから派生してテストについての色々興味深いコメントが読めておもしろい。

で、まあ、テストには再現性のあるデータを使おうねってのは一番基本のところで、それがなってなかったから今回の件がボーアバグになった、っていうのはあるんだけれど、では最初からseed固定にしていたら良かったのかというと、潜在的なテストアルゴリズムの問題 (特定の系列でヒープが爆発する) は残ったままだ。

今回はテストアルゴリズムの問題だったんだけど、以前にプロダクト本体で面倒なアルゴリズムバグに当たったことがある。データをbucketに分けて保存する。bucketの個数はあまり増えて欲しくないので上限を設けるが、総データ量はディスクの許す限りにおいて上限無し。で、最初は各bucketの容量を低く決めといて、bucketが増えすぎたらいくつかのbucketをマージして大きなbucketにして、っていうコードだった。その中で、どのbucketをマージするかを選択するアルゴリズムに問題があって、bucketの容量分布がある特定の条件を満たした時に、マージ候補がひとつも選ばれないことがあり、bucketの数が減らせない。 その場合はしばらく待ってリトライするんだけど、これまた特定の条件において、bucketの状態を変え得るプロセスがマージ終了を待つことになっていた。この二つの条件が合わさると、bucketの状態が変化するまでマージできない vs. bucketがマージされるまで状態を変えられない、というデッドロックになる。

このうち、「bucketの容量分布が特定の状態を満たした時」というのはかなり特異な条件で、このバグを開発者に話した時も「え、そんな偶然、現実に起きるのか?」と驚かれたのだが、実データで起きたんだから仕方ない。起き得ることは、いつかは起きるのだ。

で、こういう話だと、ランダムデータでテストしてもまず発見できない。ユニットテストでのテストカバレッジ100%にしても発見できない (この特定のデッドロック状態を検出してエラー出す、ってコードを入れてれば、その分岐が実行されないからわかったかもしれないけど、そもそもそういう状態が起き得るとわかってないからなあ)。

そういうわけで私は盲目的なランダムデータテストには消極的で、

1. ホワイトボックステストでは人為的に境界条件を突くデータを用意する
2. ブラックボックステストでは「Pという条件を満たす入力xに対して、出力yは条件Qを満たす」というふうに定式化した上で、P(x)を満たす範囲でxをできるだけ自動生成する

っていうのを目標にはしている。ただ、これでも上のbucketのようなケースが見つけられるかというと心許ない。

因果律を否定するバグの場合は別の厄介さがあった。問題のテストはinvarianceが必要十分条件であることを確認するテストだったのだ。つまり、

 「入力xがPという条件を満たすとき、その出力yは条件Qを満たす」

というテストではなく、

 「入力xがPという条件を満たさないとき、その出力yは条件Qを満たさない」

という命題をテストしていた。定義域が有限集合ならPとQを単に~Pと~Qに置き換えれば 同じ話になるんだけれど、定義域が無限集合の場合、後者のテストは前者のテストよりも難しい。 (逆関数が計算できるなら、対偶を使って、 「条件Qを満たす出力yを生成するような入力xは条件Pを満たす」ことを テストすれば良いのだが、自動的に逆関数が導けるような コードならそもそもこんなにテストに悩んでない。)

で、結局こういう例をちゃんとテストしようとするとサンプルによるテストじゃ無理で、 静的検証だろうなという気はしている。が、今動いてる、ばりばりに最適化がかかったLispコード にそのまま使えるような静的検証機は無いだろうしな。 何らかのメタ情報をマクロで仕込めるようにして、部分的に静的検証をかけるような 仕組みは作れるかもしれないが。

それともうひとつ、今のプロジェクトではテストに時間がかかりすぎるって悩みがある。 これはあるコードパスを通すための状態を直接作る手段が用意されてないってのが問題で。 ある低レイヤのコードパスを検証したいんだけど、そのパスを通るための状態 (共有メモリとディスク上の永続ファイルや一時ファイルの状態)を作り出すために、 結局一番上のレイヤからデータを送り込んでやらないとだめ、っていう面倒な話になってる。 そのためにいくつもプロセスを起動してネットワーク経由でデータをやりとりする羽目になってて、 オーバヘッドがバカにならない。

中間状態をダンプしておけば、という話もあるけど、チューニングによって中間状態の データ形式が結構頻繁に変わるんであんまり意味がない。 モジュール毎に、特定の状態を作り出すテスト用APIを地道に実装してゆくしか ないと思うんだけど、既に動いてるコードがあるからなあ。

Lispなのでマクロで助かってる面はある。コードウォーカーを書いて、 コード特定の場所でfailするように仕向けるようなテストを生成するのは簡単で、 異常系のテストなんかはそれでやってるんだけど。

Tags: Programming, Lisp

2011/08/30

出演情報

公演が二つ重なってしまってちょっとキツいのだ。

"Mai Poina" (Don't Forget) Walking Tours

今年で3年目。1893年1月に、ハワイ王朝がクーデターによって倒される 激動の数日間を、実際に事件が起きたイオラニ宮殿周辺の土地を散策しながら 追体験するツアー。私は再び日本人移民労働者役で出演します。

• 2011/9/4(Sun), 9/9(Fri), 9/10(Sat)。各日5:00pm, 5:20pm, 5:40pm, 6:00pm スタート。所要時間45分。無料。要予約 534-8880。
  • 案内(pdf)。
  • 記事
  • 昨年の日記

Kumu Kahua Theatre: "Cane Fields Burning"

Kumu Kahua Theatreでの公演。今回は「能」のスタイルを採り入れた 脚本ということで、ちょっと普段と違う感じ。

• 2011/9/8(Thu) - 2011/10/9(Sun)。木・金・土曜 8:00pm、日曜 2:00pm。 チケットは 劇場にて発売中。 オンライン購入可。

実はかなりdepressingな話なので、見て楽しい舞台が好きな人には ちと薦めづらいんですが、役者としてはやりがいがあります。 私の役は幽霊。

あと、子供には怖いと思うので御注意を。映画基準だとstrong languageと violenceでPG-13かRになりそうな内容です。

ところでKumu Kahua Theatreの芝居に出るのは4回目だけれど、 そのうち3回はサトウキビ畑が燃えているな。

Tag: 芝居

2011/08/28

因果律を否定するバグ

変更が全く予想外なところに影響を及ぼした例。

金曜の朝に、「shiroのパッチを入れたらHudsonでのテストがこけたんで見てくれ」 とメールが届いた。パッチそのものはごくtrivialなもので、バグフィクスは 実質1行、それをテストするためのコードが80行くらい。ところがこけてるテストは 私のパッチのテストより前に実行されるテストで、メモリを喰い潰して落ちている。 そこでテストしてる部分は私のfixとも一見無関係。

まあ普通は最初にバグフィックスの1行の変更を疑うよなあ。 で、私のパッチを外すと確かに再現しない。 パッチを入れて、問題のテスト単独で実行しても再現しない。 パッチを入れて、かつフルテスト(3時間くらいかかる)を実行した場合に限り 再現するのだが、再現しない時もある。ただし再現する時にこけるテストはいつも同じだ。

コードを論理的に追う限りではおかしいところは思い当たらないので、 まずは確実に再現させる条件を追っかけた。結果、 「make cleanしてスクラッチからビルドした後にフルテストを流すと再現する」ことが わかった。(複雑ではあるが再現条件があるという点で、これはボーアバグであると言える)。

論理的に無関係な箇所に影響を及ぼすという点ではメモリ破壊かスレッド関係を真っ先に 疑うのだが、そっちの線で追っかけてもどうもわからない。試しに、バグフィクスの1行 だけをrevertしてみた。つまり本体のコードはパッチ適用前と同一で、テストコードだけ余分だ。そしたらそれでもこけるではないか。

すなわち、他の条件が同一で、私のテストコードがソースに存在する場合に限り、 そのテストコードが実行される前に 別のテストがこけるということだ。 将来実行されるであろう私のテストコードが悪さをして、 その影響が時間を遡って別のテストをこけさせているのだろうか。 だがそこでテストがこけるために、私のテストコードは結局実行されないのである。 タイムパラドックスだ。私は開けてはいけない扉を開けてしまったのだろうか。

恐ろしい可能性におののきつつ、落ちるテストで何が起きているのかを 注意深く観察してみた。そのテストは16通りの条件でデータの検索と追加を 行っている。n=0から15までループするのだが、それまでに追加した データに依存して新たにデータが追加され、総データ量はだいたいO(2^n)になっている。 n=0で1個追加されたデータが、正常時にはn=15の時点でだいたい数万個のオーダーになるということ。 ところが異常時にはn=12くらいからデータ量が若干上方向にぶれ始めて、n=15の開始時には 90万レコードとなり、n=15のサイクルでデータ追加が終わらないという事態になっている。

追加されるデータの一部は(random 1000)を使って疑似乱数で生成されている。 テストではrandom seedには触っていない。 そこで、正常時と異常時で生成される乱数系列をダンプしてみた。

 正常時: 955, 600, 330, 372, 760, 459, 241, 145, 423, 680, ...
 異常時: 330, 372, 760, 459, 241, 145, 423, 680, 496, 401, ...

むむ。

そう、異常時、すなわち、私の実行されないはずのテストコードが存在する時には、 乱数系列が二つ先に進んでいる。おそらく、 私のテストコードをコンパイル&ロードする際に処理系内部で 乱数をふたつ消費しているのだろう。

(Lispシステムでは、テストコードがコンパイルされていない場合、まず テストコードを全てコンパイルしてから同じプロセスが順にテストを実行 してゆくようになっていたので、たとえ私のテストコードが実行されずとも 影響はゼロでは無かったというわけだ。)

試しに、正常時のコードにダミーのrandomの呼び出しを二つ加えて同じ系列を 使うようにしたら、メモリを喰い潰して落ちた。 逆に異常時のコードにダミーのrandomを入れて系列をずらすと、通る。

すなわち、元々このテストは、特定の乱数系列によってデータ量が爆発するという 潜在的な問題を抱えていて、私のテストコードの追加が偶然にもその 系列を発生させてしまっていた、ということだったのだ。 本来的に指数増加するアルゴリズムなので、初期条件のわずかな違いが 指数増加によって極端に増幅されたとも考えられる。

なお、スクラッチビルドでない場合に再現しなかったのは、 テストコードは最初のフルテスト実行時にコンパイルされfaslになっていたため、 2回目以降は使われる乱数系列がずれるからであった。

これにて一件落着。因果律は破られず、宇宙の秩序は保たれた。奇妙なことに私の週末だけがどこかに消えてしまったのだが、宇宙の秩序にくらべれば些細なことである。

それにしても、random seedをrandomizeしていたら、これはボーアバグではなく ハイゼンバグになって、解決ははるかに困難になっていただろう。

 教訓: テストは常に再現可能なデータを使うべし。

テストコードの追加によって乱数系列がずれるのもまずいので、 疑似乱数を使うにしてもテストの直前でseedを特定の値にリセットすべきかもしれない。 あと O(2^n) は怖いよね、気をつけようね、ということかな。

(追記2011/08/31 04:29:49 UTC):続きみたいなもの: テストの話

Tags: Programming, Bug

2011/08/25

点と点とナード

ちょっと新鮮だった。

chibicode - 点と点がつながると信じてたバカへ。元アップルのインターンが、ジョブズ引退の日に思ったこと。

ジョブスの「将来、点と点がつながることを信じよ」のスピーチに感化されて、つなげるための点を置くためにいろいろ手を出したけれど、そんなに無理することなかったんだ、どう置こうがつながる点はつながるんだし、というような話が出てくる。そこでほほうと思った。

ジョブスの本意がどうかはわからないけれど、私はあのスピーチをナードに向けたメッセージと読んでいた。つまり、世間的な常識や評価、あるいは自分の将来の得失とかを考えると、どうもこういうことをやってて良いのか不安になるんだけれど、でもどうしても今これをやらずにはおれないんだ、という人に対して、「今それをやっておくことは将来必ず何かにつながるから、心配せずに好きなだけ入れ込みなさい」と言っているのかと。

だから、つなげるための点を置こうとする、という発想自体が新鮮に感じたわけ。

別にそれが悪いことってわけじゃなくて、ただ違うなあと。

Paul Grahamのエッセイなんかも、私感ではかなりナード向けに特化したメッセージが多いと思う。感想を見ていると、その対象にspot onした人とそうでない人で反応が違うなあと思うこともあるけれど、どちらが正解というわけでもない。それに、大事なのは言葉そのものではなく、それを聞いた人がどういう行動を起こすかってことだしね。

★ ★ ★

(追記2011/08/27 00:48:13 UTC): 以前書いた、関連するようなしないような話。

ハック

あくまで個人的な印象だけど、Paul Grahamのメッセージは実は非常に限られた種類の人間をターゲットにしてて、そこにメッセージを届けるためならそれ以外の人々に誤解されても構わないと割り切ってるふしがある。だから、彼の書いたものを読んでそれは自分向けではない、あるいはみんながみんなそう考えたら困るじゃないか、と思ったとしても、それは正しい。もともと万人に向けて書かれているわけじゃないから。 (ただ、ある人が対象でないということは、その人が「ふるい落とされている」ということにはならない。単に対象でないっていうだけ。)

そうやってブロードキャストしたメッセージが埋没している潜在的なハッカーに届いて、そのハッカーの背中を押すことができれば、社会が結果的に(ハッカー以外の人にとっても)より良い場所になると彼は思ってるのでは。

2005/01/25

たぶんあの頃の年代は、上の世代からハッパをかけられると、それが正しくても何か素直に従いたくないものがあるんだと思う。自分でやりたいから、先回りされてやることを言われるのが面白くないのだ。背中を押されるよりも、それで良い、という確認の方が素直に受け取れるんだろう。 (「あまり苦労をかけさせるなよ」と笑いながら、「やりたいならおやんなさい」と言ってくれた劇部の顧問の先生を思い出す。)

Tags: Career, PaulGraham