「Beautiful Code」を読む(下)

「Beautiful Code」をついに最後まで読了。３回目、最後のふりかえりです(１回目の中間ふりかえり、２回目の中間ふりかえり)。こんな企画(？)、始めるんじゃなかったと、何度後悔したことか... まあ、それでも最後まで辿り着けた要因の１つに、つぶやかないといけないという緩い義務感があったのも確かです。

第23章 MapReduceでの分散プログラミング
解決したい問題を解くコードの詳細と並列化のための詳細を分離して、並列化処理をフレームワーク化。並列/分散プログラミングの経験がなくとも並列/分散が容易に可能。
MapReduceは「Googleを支える技術」西田圭介(技術評論社 WEB+DB PRESSプラスシリーズ)で読んでいた内容で、復習になりました。

第24章 美しきかな、並列
昨日に引き続き、並列処理が問題。並列処理間で動作を協調させる手法としてのロックにはデッドロックやロック漏れ等色々と問題があるが、もっとも基本的な弱点はモジューラプログラミングをサポートしていないこと。
ロックに替えてHaskellにあるソフトウェア・トランザクショナル・メモリ(STM)を使用することで、うまく解決できる。が、詳細はちょっと消化不良です。
前章のMapReduceはデータをうまく分割して並列処理間でのロックによる動作協調を不要にしている。但し複数種類のトランザクションが同一データに対して実行が必要なときには、何らかの排他処理が必要で、それを解決するのがSTM。

第25章 構文の抽象化：syntax-caseマクロ
読み飛ばし。LISPもSchemeも知らないし「The Scheme Programming Language」も読んでられませんので。

第26章 労力節約のアーキテクチャ：ネットワークソフトウェアのためのオブジェクト指向フレームワーク
ネットワークプログラミングの非本質的な複雑さの多くは、CレベルのOS APIを使うことに起因する。
ソケット通信やマルチプロセス/スレッド用のAPIは、OS間の互換性がないだけなく、同じOSのバージョン間でも互換性がない場合がある。包囲ファサードパターンを用いてAPIとそのデータとを安全なオブジェクト指向クラスの内部にカプセル化する。

第27章 ビジネスパートナーをRESTfulにまとめ上げる
URLとリクエスト文字列でコマンドディスパッチを行い、データを取得/更新し、レスポンス文字列を生成して返す、というのがWebサービスの基本構造。
ディスパッチされたコマンドに対応する処理をファクトリパターンで行うなど、基本を確認するのに良い内容です。文中の例でデータ取得にPOSTを使用しているは、リクエストXMLが長くなってGETで処理しきれないからでしょう。

第28章 美しいデバッグ
プログラマにとっては、機能に富んだデバッグツールの使用方法を習うよりも、系統立ったデバッグ手法の訓練をする方が重要。仮説検証サイクルを回しながら欠陥のある場所の範囲を狭めていきます。
欠陥混入前のコードと混入後のコードのテストコードを用いて自動的に差分デバッグすることで、完全自動デバッグが可能となる。つまり人間による対話的なデバッグが全く必要なくなります。

第29章 エッセイのごときプログラム
プログラムの美しさは、効率良くプログラムを書き、効率良くプログラムを読解し、効率良くプログラムを修正できるところにある。簡潔さ、保守的、シンプルさ、柔軟性のバランスが大切。
抽象化とは、いくつかの概念の塊をまとめてより高次の概念を作り出すこと。一度に扱わなければならない概念の数が減るので理解を助け、再利用や保守も容易になる。言語が積極的に抽象化を行うことで、プログラムをより簡潔にすることを支援できる。
軽量言語の仕様、文法、ライブラリ量は少しも軽量ではない。目標はプログラマの労力の軽量化であって言語自身の軽量化ではない。本質的に複雑な問題を解決するための言語のシンプルさを追求すると、プログラマに複雑さを押し付けることもあり得る。

第30章 世界につながる手段がボタンだけだったら
理論物理学者のホーキング教授は、たったボタン１つで操作するソフトを使って書いたり話したりする。ボタン１つで手際よく使えるエディタを考案するのは、非常に興味深い技術的挑戦。
実はボタンは、ただ押した/押さないの２値の入力装置ではなく、押す時間の長さを変えて信号を出すことも出来るアナログ装置である。「長押し」の発想ですね。

第31章 Emacspeak：完全に音声のみのデスクトップ環境
GUIと同様の効率の良さを目を使わない環境でも達成することが音声デスクトップの目標。言葉だけでなく、言葉以外のオーディオ出力の表現力を活用する。
ACSS(音声スタイルシート)で発話のスタイルを指定する。CSSなのでカスケードが可能。コメント用の音声と太字用の音声を合成することで、コメント中の太字の音声を表現出来る。 また頻繁に発生する事象は音声アイコンで通知する。

第32章 働くコード
本のようであること、似たものは似て見えるようにすることについては全く同感。１画面で２バージョンのコードを並べて表示するdiffツールでも、行全体を見るために横スクロールが不要な程度に１行が短いのはすごい。
プログラマはコードを構文に応じて色づけしてくれるテキストエディタだけを通して読むわけではなく、diff、merge、パッチ、コンパイラのエラーメッセージ、デバッガ等を通じても読むので、コードの見た目は、結構重要。

第33章 「本」のためにプログラムを書く
この「本」は数学家ポール・エルデシュのいうところの「本」。「平面上に任意の３点が与えられたときに、その３点が同一直線上にあるか？」を判定するプログラムを考える。数学的には中学生でも解けるが、美しいプログラムにするには色々と問題がある。
素朴な第１案は、２点を通る直線の方程式を求めて３点目がそれを満たすかを判定。直線がy軸に平行な場合は傾きがゼロとなり、ゼロ除算回避の特別扱いが必要。
第２案としては、３点のうち２点を通る２組の直線が平行(傾きが同じ)であれば、同一直線上にある。直線の方程式中のy切片を考えずに、傾きだけに着目すれば良くなる。それでも傾きゼロの特例扱いは残る。
傾きゼロ特例をなくす第３案。３点を頂点とする三角形の長辺が、２短辺の和と同じであれば同一直線上にある。辺の長さの計算には平方根を使用し無理数が発生し、計算精度が落ちる。また、極度に平たい三角形は計算誤差のため直線と区別できない。
第４案。３点を頂点とする三角形の面積をベクトルの外積で求め、それがゼロであれば同一直線上にある。平方根は出てこず、極度に平たい三角形でも平たくするために長辺を延ばせば延ばすほど面積が大きくなるので、計算誤差にだまされない。
コンピュータが正確かつ美しく計算出し易いように、問題を幾何的に変形していくところが面白いですね。なお訳注では、第２案を代数的に処理して、第４案と同じ結論に辿り着く方法が示されています。

ソースコード静的解析の数理

「日経サイエンス」2012年03月号「NEWS SCAN 海外ウォッチ」の「がん検診の数理」に触発されて、というか殆どパクリですが、ソースコードの静的解析の数理について考えてみました。

条件
・全ステップの 0.4% (250ステップに1件) の割合で欠陥が存在する
・静的解析ツールで欠陥のあるステップを欠陥として検出する(陽性)確率を、99.5% とする
・静的解析ツールで欠陥のないステップを欠陥として検出する(偽陽性)確率を、1.0% とする

この静的解析ツールを10万ステップのコードがあるソフトウェアに適用するとすると
・欠陥ステップ数 　= 100000 / 250             = 400 ステップ
・陽性ステップ数 　= 400 * 0.995                = 398 ステップ
・偽陽性ステップ数 = (100000 - 400) * 0.01 = 996 ステップ
従って、
・ツール指摘欠陥ステップ数 = 398 + 996   = 1394 ステップ
・本当の欠陥ステップの割合 = 398 / 1394 = 28.6 %
となります。残念ながら、かなり少ない割合ですね。

この問題は数学者にはよく知られているようで、比較的まれなものを検出しようとしているときは、結果が陽性と出ても誤りのある可能性が高くなります。ここでは、欠陥が全ステップの 0.4% というのがミソです。これが全ステップの1.0%なら約50%程度まで、2.0%なら約75%程度まで、本当の欠陥ステップの割合は跳ね上がります。

なお本当に問題があるかどうかの精密検査として、人の目でチェックするのにはコストがかかります。それだけでなく、静的解析ツールを通すための修正やコメント追加を行って可読性を低下させたり、最悪、別の欠陥を埋め込むことになれば、この静的解析はマイナスとなりかねない面もあります。
実際の数値は静的解析ツールや欠陥の種類によって異なりますが、静的解析ツールを導入するときは、検出できる欠陥だけでなく、偽陽性の扱いにも考慮が必要です。

この点、C++の静的解析ツールの１つである cppcheck は偽陽性0%「The goal is 0% false positives.」と掲げており、卓見だと思います。

参考
　ベイズの定理、及び、ベイズ推定

コード、デフォルト、ドライバ

IT用語には、日常の言葉や他業界の用語と紛らわしい言葉が色々とあります。今回は思いつくままに、コード、デフォルト、ドライバの３つを取り上げてみました。

1. コード
一般的には、紐、ケーブル、電線のことです。これは英語では「cord」です。
プログラマが使う場合は「code」で、ソースコードの省略系であり、プログラムの文章のことです。プログラムを書くとをコーディングとも表現します。元の意味は「暗号/規則」などで、Wikipediaによれば、「コンピュータの黎明期、機械語によるプログラムがまるで暗号のようだ、ということから」とのこと。分子生物学者の使う遺伝子「コード」もこのコードですね。
音楽家が使うコードは「chord」で和音のことだそうです。

2. デフォルト
一般的には、というか金融系の方々にとっては「債務不履行」という恐ろしい事態です。
プログラマが使う場合は、「システムによってあらかじめ選択された選択肢(初期設定)」となります。
英語でも同じ「default」で、元の語義は「成すべきことが成されない」状態だそうです。

3. ドライバ
一般的には、ネジ回し(プラスとかマイナスとかがあるやつです)や車の運転手を指します。
ゴルファが使う場合は、一番飛距離の出易い1番ウッド(1W)ですね。
プログラマが使う場合は、ハードウェアや他のソフトウェアを動かすソフトウェアを指します。たとえばプリンタを動かすソフトを「プリンタドライバ」と言います。
英語は全て同じ「driver」で「drive(動かす/駆動する)する人・もの」。つまり本来は、使用するときには、＊＊＊ドライバのように何をドライブするのかを示す必要がありますが、文脈によって明らかなので省略されているということですね。但し専門外の人からすると何が省略されているのかが分かり辛い場合があるので注意です。
なおスクリュードライバは、そのまま「ネジ回し」なのですが、日本ではウォッカベースのオレンジジュースカクテルの方が有名です。Wikipediaによれば「その昔、イランで働いていたアメリカ人作業員が、のどの渇きを癒すために即席のカクテルを作った。この作業員がそのときステアするために使用したものが、工具のスクリュー・ドライバー（ねじ回し）だったことからこの名前が付いた」だそうです。
このドライバの意味が分かっていれば、基本情報技術者試験の午前問題等で見かけたドライバとスタブの違いを見分ける問題は、簡単に回答出来ますね。 (^○^)

まだまだ他にも紛らわしい言葉があるかと思いますので、またいつか、第２弾を書きたいと思います。

「Beautiful Code」を読む(中)

「Beautiful Code」の３分の２にあたる22章まで読了しましたので、２回目の中間ふりかえりです(１回目の中間ふりかえり)。
なかなか毎日Twitterで呟くことはできていませんが、呟いていない日でも少しずつ読み進めていることもあります。そのままだと呟くポイントを見失ってしまいがちですが、別途メモしておくのも読書が断続的になり、効率が落ちてしまいます。そこで、今回はブックダーツを使用してみました。

左の写真は「第22章 スプーン一杯の汚水で」の「境界条件」云々の箇所。
右の写真は本の小口(こぐち)です。

第12章 BioPerlにおける美しいコードの成長
ライブラリの設計では、そのクラスや関数がどのように使われるかの(疑似)コードを書いてみながらブラッシュアップしていく。クラス(群)レベルのユースケースシナリオと考えると良いかも。
ライブラリは、初心者がすぐに使え、中級者が簡単にカスタマイズでき、上級者が簡単に拡張できる、というのが理想。Perlのコードリファレンス値(コールバック関数オブジェクト)でライブラリを拡張可能にしている。

第13章 遺伝子ソータの設計
遺伝子解析関連のお話が続きますね。小さなプログラムの構造はアルゴリズムやマシンの都合で決めて良いが、大きなプログラムの構造は人間の都合で決めるべき。
人間の記憶は連想による部分が大きく、一度詳細に読み込んだことがあるコードであれば、概略を読んだだけで詳細を思い出せることが多い。結局、構造化プログラミングというか、本の目次のようにコードを書くことが大切ですね。

第14章 エレガントなコードはハードウェアに合わせて進化する：ガウス消去法の場合
効率的なアルゴリズムというのはコンピュータのアーキテクチャに依存するが、可読性とのせめぎ合いもある。
私はアプリケーション寄りの人間。ハードウェア(コンピュータアーキテクチャ)の違いは基本的にはOSで、足りなければフレームワークやライブラリで吸収しておいて欲しいものです。但し、OS/フレームワーク/ライブラリを選定する能力は必要ですが。
なおアプリケーション側でも、ハードウェアを意識していないと非常に非効率になることはあります。そのときは、第５章にあったように、正しく->美しく->速く で最後に計測しながら考える(もしくは得意な人にお願いする)のが私の道でしょう。

第15章 美しいデザインの長期にわたる恩恵
美しいコードと美しい数学とは、必ずしも同一物ではない。メモリが無限にあり処理速度も無限に速いことを前提としたコードは横柄ですらある。
コードの究極の目的は使われることなので、芸術作品と同様に、時間の試練に耐えたものこそが美しいと言える。
数年〜数十年以上使い続けられているコードはそれほど多くない？

第16章 Linuxカーネルのドライバモデル：一緒に働くことの恩恵
C言語でオブジェクト指向。
優秀な開発者たちが強調し、必要に応じて反復的に開発してきたため、多くの問題を解決する美しい共通解となるコードができたということ。

第17章 もう一段の間接参照
C言語でオブジェクト指向その２。
「コンピュータサイエンスにおける問題の全ては、もう一段の間接参照によって解決できる」が、「たいてい、新たな問題が作り出される」とのこと。
間接参照による抽象化で柔軟に情報を構造化できると読む。間接化による時間的・空間的オーバーヘッドは、殆どのケースでハードウェアとコンパイラの性能で解決できる。しかし、ソースコードの理解し易さを妨げる可能性があり、過剰な間接化は避けるべき。

第18章 Pythonの辞書実装：すべての人々にすべてのものであること
CPythonの辞書は言語機構の土台で、クラスやインスタンスの属性値や、関数呼び出しのキーワード引数を格納することにも使用されている。
辞書の実装では、ハッシュ表の大きさやその変更、ハッシュ値の衝突など、様々な点で最適化が行われている。但し、最適化は基本的にはアルゴリズムに関するものであり、全体としてとて素直な実装になっている。

第19章 NumPyの多次元イテレータ
Python続きですね。NumPyはPython言語のオプションパッケージで強力なN次元配列オブジェクトが提供されています。メモリ上で不連続な配列も扱えます。
NumPyイテレータにより使用する配列が連続か否かに関係なく、連続した配列と同様のコードが使えて、それでいて常に十分高速なコードが得られる、ということ。
各次元毎にストライドを設定出来るのが面白いです。

第20章 NASAの火星探査機計画のための高信頼エンタープライズシステム
巨大アプリケーションでは常に、成功の鍵はコーディングではなく統合にあるということ。標準コンポーネントを粗結合で使うこと。
巨大なアプリの美しさは、必ずしもエレガントなアルゴリズムにはないということ。
熟練開発者のスキルの１つは、何をハードコーディングし、何を開始時にロードするパラメータとするのが適切なのかを見極められること。

第21章 ERP5:最高水準の適応性に向けた設計
プロセス中心やデータ中心ではなくドキュメント中心のパラダイム。全てのビジネスプロセスは一連の文書を作り出すことを通じてその目的を達成する？なんかちょっと官僚チック？
既存のビジネステンプレートを土台にして、GUI要素を取り替え、ワークフローを調整するだけで、新しいビジネステンプレートが作れる、ということかな。ERPの開発・運用のイメージが描けていないので消化不良。

第22章 スプーン一杯の汚水で
Solarisのカーネルメモリアロケータとゼタバイトファイルシステム(ZFS)間のやり取りにおけるブロッキングチェーンで生じる問題について(むずっ)。
ある問題を、こうすれば動くのでは動くのではないかという形ではなく、こうだから動かないという形で分析して解決する能力、つまり境界条件に注目する能力が大切ということ。なんか犀川創平氏を思い出しました。
どんなに格好の良い(ように見える)設計・実装(＝樽一杯の高級ワイン)であっても、(難解で)致命的なバグが1つ(＝スプーン一杯の汚水)存在すると、それは樽一杯の汚水になるので、全部捨ててやり直しになるというのが題意。

ふ〜っ。ということで、残り３分の１、がんばりましょう。

「新ネットワーク思考」と「エピデミック」

BeautifulCodeとRESTful元号が滞っていますが、それとは別に大量にある積ん読本の解消を少しずつ進めようかと(^▽^;)。

ということで、「新ネットワーク思考―世界のしくみを読み解く」アルバート・ラズロ・バラバシ(NHK出版)(初版2002年12月26日)を読了しました。
全般的にデジャヴ感があったのは、「日経サイエンス」2003年9月号の記事「世界の“なぜ”を読み解く　スケールフリーネットワーク」を読んでいたからでしょう。こちらは同著者のA.-L.バラバシ氏とE. ボナボー氏の共著です。
ざっくり抽象化すると、静的な要素還元主義だけでは色々と行き詰まりが出てきていた状況を、動的な関係性のトポロジーという新しいモデルで打破しようということですね。ロングテールとかウィルスマーケティングとか「ブラックスワン」とかの背景理論にもなっています。
ネットワークモデルの特徴を簡単に表にしてみました。

不慮の事故/故障には強いが攻撃に弱いというのが、WWWなどのスケールフリーネットワークの重要なポイントかと思います。

続けて「エピデミック」川端裕人(角川文庫)(単行本初版2007年11月)を読了。新興伝染病のアウトブレイクを制圧する疫学ミステリィ小説です。

伝染病の拡大規模によって エンデミック(endemic) -> エピデミック(epidemic) -> パンデミック(pandemic)と出世魚のように名前が変わるようです(Wikipediaの「伝染病」の項目参照)。アウトブレイクは、エピとパンの間くらいでしょうか？

たまたまですが、伝染病の広がり方が、ズバリ、成長と優先的選択をともなうスケールフリーネットワークです。ノード(罹患者/動物、保菌者/動物)、リンク(感染経路)、さらには運ばれるもの(ウィルス)も不明確な状態です。障害耐性は強いので、放っておくとどんどん広がります。しかし主要なハブに対する攻撃には弱いのでスーパースプレッダー(毒王)を隔離して、感染経路の「元栓」を閉めることで沈静化します。

その「元栓」探しが探偵小説になるのですが、「確率密度の雲のなかで持ちこたえる」という量子力学的(？、電子の雲からの連想。多分カオス的とか複雑系的という形容の方が正確なのでしょうが)なスタンスが良いですね。

なお、舞台となる(人間を含めた)生態系もスケールフリーネットワークと考えられています。