SSブログ
[PR]本のベストセラー

ビューティフルコード (THEORY/IN/PRACTICE) [プログラミング]

いろいろな人が美しいコードとはなにかで書いた本。
印税はアムネスティに寄付されているそうだ。
33の章がそれぞれ独立しており、興味ある章をよむことができる。範囲もコードそのものからデバッガまで広い。

第1章 正規表現マッチャ ブライアン・カーニハン
正規表現・・・テキスト中のパターンを指定する記法の一つ
正規表現にはバリエーションが多いので、使うときには注意が必要
正規表現は有限オートマトンの記法として発明されたもの。
プログラミング作法を教えるうえで、正規表現にふれるため、grepのコードなどを使おうとしたが500行以上あった。
そこでページ1枚におさまるような、正規表現の基本的な考え方がわかり、有用なコードをかいてもらった。
それが「プログラミング作法」の9章に掲載されている。
この内容についてポイントを解説。
改善案を解説。
実用性の検討
発展課題の例
このコードが美しいポイント・・・正規表現の機能がうまく選ばれている、再帰がうまくつかわれている、ポインタというプログラミング言語の特性をうまくつかっている。

第2章 Subversionの差分エディタ:存在論としてのインターフェース カール・フォーゲル
Subersion・・・オープンソースのバージョン管理システム
差分エディタ・・・ディレクトリツリーの差を表現する、また他方のツリーに変換するときにも使われる

Subersionの差分エディタはプログラマが良いデザインに乱す複数の特性を体現している。
 ・問題を非常に自然な境界に沿って分割しているので、新しい機能を追加するとき、だれでもいつ何のためにそれぞれの関数を呼べばいいかわかる、効率を最大化するための機会をごく自然に提供する。追加作業を簡単に組み込める。設計が機能強化や改訂に対して弾力的。
作ったのは1人でほんの数時間。
Subversionの処理解説。リビジョン番号とツリー構造、差分エディタのインターフェースの解説、最初はかなり面倒だったが、ジム・ブランディが作ったシンプルなものが最終的に使われている。コードがのっており、最初に処理の内容がテキストで1ページ分くらい書かれている。さらに関数の使用法が2ページ半くらいあって、コードがコメント入り2ページかかれていた。
 結果として深さ優先順にかかれているそのコードは、最初は美しいと思わなかったが、使用しているうちに美しいとおもうようになったという。
 一つのツリーを編集して2つ以上の異なる変更を行う必要がある場合の例。
 Subversionでツリーを変更する操作は共通のやり方に統一されている。だから既存のコードを学ぶために費やされる時間は少なくてすむ。また設計方法にあれこれ悩み迷う必要もない。それは大きな利点。


第3章 私が決して書かなかった、一番美しいコード ジョン・ベントリー
 コードを削ることで機能を追加する。
 これを語るためにクイックソートのプログラムの実行時間について新しい分析をする。
Cで実装したクイックソート12行。
最悪の場合、クイックソートがn個の配列要素を整理する時間はn×n時間。
最良の場合は2を帝都するNの対数=2を何乗するとNになるかの答えになる。
ではnこの値がランダムに並んだ配列では平均何回比較を行えば整列できるか。
ホーアの分析は美しいが、難しい。今回は実験でたしかめながらその分析にちかいところまでいく。
最初のCプログラムに改良を加えながらコードを削っていく。
次にクイックソートを解析するのに使ったプログラムの発展をまとめる。最終的には漸か式に解釈していた。
おまけの解析として「データ構造は凍りついたアルゴリズム」ならクイックソートのアルゴリズムが凍りつくと2分木だとして、2分木に要素を一つ挿入する平均コストについて述べていた。
プログラムは傾倒だって導き出された正しいものだが、実装はしていないと筆者はいっている。美しさが損なわれないようにだって。
プログラムの名言がのっていた、
プログラムを書くヒント・・・プログラムの解析(計測のしくみをつけて代表的データで実行する)、小片のコード(プログラミングは実用スキルであり、マネと練習で手に入る、美しいコードを読もう)、ソフトウェアシステム(ここに表れている原理は大きなプログラムや巨大システムでも使える)


第4章 ものの見つけ方 ティム・プレイ
 現在のコンピュータの最も多い使われ方は検索である。データの増大で探し出す仕組みはより重要性をましている。
 探索手法を選ぶことにもトレードオフがある。
 
探索に要する時間
 実際に検索を実行する時間、探索プログラムが完成するのを待つ時間

著者のブログへのトランザクション記録を例に探索プログラムを解説。
正規表現(Ruby)で探す方法解説、

記事の参照頻度を計算するプログラム
基本的検索パターンはキーに基づいて対応する値をみつける(連想記憶)、Rubyプログラム。

実行時間をくらべるためにPerlでも書いてみると実行時間は半分だったので最適化を行う例

誰が、何を、いつ取り出したかを調べるプログラムを作る。
巨大なハッシュ表を使う例。
2分探索での例と、そのトレードオフ解説。

ウェブの探索も基盤はテキスト検索。
変わったのは結果のランク付けを行うやり方
ポスティング・・・ドキュメントを全部読みながら、各単語について「単語XがドキュメントYの位置Zに現れた」を生成、単語で整列させた固定長のデータ。
ポスティングを扱う自然な方法は2分探索。
探索自体は(複合探索も含めて)難しくないが、結果のリストを並べ替えて、良い結果=品質の高い結果が短い時間で現れる、が上のほうにくるようにするのは難しい。
Googleではページランクで実現している。
ページランク・・・あるページについてそのページを指しているハイパーリンクが多数あると人気があるとみなす。
巨大な検索エンジンが、データ量やユーザ数の増大に追従してきたのは、並列処理を大規模に適用(小さなコンピュータに処理)してきたことによる。ポスティングは並列処理にむいている、例えば英単語ならアルファベット順に26にわけるのは容易。

コンピュータアプリケーションのほとんどが、データを格納しておいてそれを内容に基づいて探して取り出す処理を含んでいる。ウェブ検索はその代表。
プログラマにとっては様々な種類の探索プログラムを実装することは楽しいことの一つ。


5章 正しく、美しく、早く(この順番で):XML検証ソフトの設計から エリオット・ラスティ・ハロルド
XMLの入力検証を行う2つのルーチンJDOMとXOMのはなし・
JDOMからわいたアイデアはXOMに伝わり、速度の向上を目指すたびにコードが美しくなった。
最新の最適化コンパイラ JTT,RISCアーキティクチャ、マルチコアCPUの影響を考慮すると、美しさの改善=速度の向上になる。

XML検証の役割
 XMLの正しさを完全に保つため、以下の2つの冗長性をチェックする
 1 入力に対する検証。開始タグには終了タグがある、規定された位置にあるなど、文書が妥当であるか検証。
 2 出力に対する検証。XML APIを使ってXML文書を生成するとき、パーサはAPIを通して受け取った文字列すべてをXMLの文法に合っているかどうか確認することで、出力全体が正しいXMLであることを保証する。

JDOMの最初のベータ版での問題とその改善を解説。
 最初はJavaで普通にかいたが
 BNF記法をまねてコードはながくなったがわかりやすくなった
 検証方法を工夫して最適化
 重複チェックを省略とか
 キャッシングとか

まず設計をちきんとすること、CPUが早くなるのだからプログラムが最初の段階より遅くなることはない
きちんと設計して上で実行性能について検証すべき。
早いけれど醜いコードを美しくするのは大変
美しいけれど遅いコードを早くする方が簡単。


6章 テストのための統合的フレームワーク:脆さから垣間見る美しさ ミカエル・フェザーズ
プログラマは実践を通して作り上げた「よいデザインとはなにか」の見解を持っている。
 Publicを使おうとするときは普通は悪いデザインだと考えたり、実装のため継承を使うときには継承よりも委譲のほうが子好ましいと思い出したりする。
しかし、経験則はかえって仇になることがある。
FIT・・・ソフトウェアテストを自動化するフレームワーク
 実行可能なアプリケーションテストをHTMLの表で書くことができる。
 HTMLの表ごとにフィクスチャオブジェクトを生成、結果が期待通りかチェックしてセルを塗りつぶす

FITは美しいコード、初期リリースの一つをみながら、設計について著者に再考をうながした部分をみていく。

FITの3つのクラス、Parse,FIxture,TypeAddapterの解説

フレームワーク設計のもっとも大変なところは、そのフレームワークを使うコードを制御できないこと。
FITは他のフレームワークと違う。フレームワークの核になる部分はほとんどすべてデータさえもPublicである。
これはFITがオープンフレームワークでフレームワーク全体が拡張できるようにデザインされているから。
FITのHTML構文解析のすべてをクラスParseがおこない、コンストラクタ内で構文木全体をつくりあげる。
それまでコンストラクタであまり多くのことをやらないという経験則をうけいれていたが、Parseは違うしかしエレガントである。HTMLを扱うように設計を制限したことで、フレームワークを小さく保ち、理解しやすくしている。
正しいことを定数に固定してしまえば、得るものは大きい。
また隣への参照をもっておくためにコレクションオブジェクトを使っていない、代わりにpartsとmoreを直接のリンクとして使っている。

産業界では困難にブチ当てるスタイルの学校で学んできた人が多い。選択を制限して拡張性を保とうとする経験則を身につけているひとが多い。
FITはフレームワークをできるだけ柔軟で簡明に作るようにするため、フレームワークを数十のクラスに分解するのではなく、各クラスを内部でどのようない構造化するかに注意を払い、ユーザーが通常のコースからはずれたいと思ったときはそうできるようにメソッドをPublicにするという過激なもの。
そうすると、変更は困難なものの、他の人は利用しやすくなり、新しいものを作り始める。
著者にとってFITは美しいフレームワーク。


7章 ビューティフル・テスト アルベルト・サボイア

テストの本質は組み合わせや探索の問題。
物事の組み合わせがテストを美しくする。

テストを美しくする3つの手法
・簡潔さゆえに美しいといえるテスト
 数行のテストコードで対象コードの基本的な動作を文書化したい検証したりできる。JUnitを使って検証
・コードの優雅さ、保守性、テストしやすさを増す方法がわかるために美しいと言えるテスト
 コードをもっと美しくするのを助けてくれるようなテスト。テストを書いているうちに気が付く。
・幅と深さゆえに美しいテスト
 綿密かつ網羅的なテストはすべてのケースについてコードが期待通り動くという確信を強化してくれる。

例題に2分木探索をあげていた。
 2分木探索は非常に簡単でありながら実装を間違いやすいので格好の例

著者の2分木探索のテストの初期戦略
 ・スモークテストからはじめる・・・そのコードをもっとも基本的な形で使用した場合正しいことをすると確認するテスト。
 ・境界値のテストを付け加える・・・データの配列と目的の値それぞれについて境界について考える
 ・さまざまな種類のテストを完全に尽くして行う・・・ランダムなテスト
   1 データ量が多く、かつ多様な入力セットを生成する方法・・・著者の実装を(負の数もはいる)をあげていた
   2 どのような入力にも適用できる、汎用的な検証方法・・・定理を4つをあげて解説
 ・最後に実行性能に関するテストを付け加える・・・システムクロックでは早すぎて測定できないので比較回数を使う。

テストのコードを書くことは対象コードをかくのと同じくらい創造的で挑戦的である。
テストとは自分のカンバスから一歩下がって自分の仕事を批判的な眼で異なる視点からみること。


8章 画像処理のためのその場コード生成 チャールズ・べゾルド
コードとデータは分けられているのが普通だが、障壁が破られることがある。コンパイラはコードとデータの区分がない。
その場生成コード(on-tye-fly)・・・コンパイラ出ないプログラムが実行中にコードを生成すること
その場生成コードはWindows1.0にでグラフィカル関数に広範囲に採用されている
限られた時間で動作する必要のあるサブルーチンが多くの演算を繰り返し実行する。その反復において条件分岐する。
こういったときその場生成コードは実行速度に大変有効にはたらき、著者はそれを美しいと表現していた。


9章 下向き演算子順位解析 ダグラス・クロックフォード
下向き演算子順位解析は1973年にボストンで開催された第1回POPLシンポジウムにおけるボーガン・プラットによる発表論文の題名。
再帰下降解析とロバート・フロイドによる演算子順位を用いる解析手法の良い点を組み合わせた解析手法を提案。
理解しやすく、実装しやすく、使いやすく、極めて効率的で非常に柔軟性があるといわれているが、著者はさらに美しいといっている。
論文ではLisp言語でほとんど労せずしてトークン列から解析木を構築しているが、Lispに構文がないことが称賛されがちなんでうけない。
また普通の性的手続きではこの方法は使わないのでうけない。

しかし今はJavaScriptがある。
これをつかってトークンの配列を生成し、配列を順次みながら解析木を組み立てていく方法を解説。

構築した構文解析器は容易に拡張可能。


10章 高速ビットカウントを求めて ヘンリー・S・ウォーレン
ビットカウント・・・コンピュータの1語の中で「1」であるビットの数を数えるアルゴリズム
この命令を実装していないマシン上でビットカウント関数を計算する方法について述べる。
ただし、RISC/CISCコンピュータが普通に備えているShift ass ansa load、条件分岐などは使えるとする。
ビットカウントの問題
・コンピュータの1語の中で1の立っているビットを数えるkと
・配列中の要素など多数の五の中で1の立っているビットを数えること

基本的な方法(シフトする)から始め、
分割統治法(16ビットの語に足してビットカウントを計算する方法があるとして、32ビットなら右と左半分に並列に操作を行う)応用事例は2分木探索、クイックソート、語のビットを反転する方法への適用など。
論理回路を使う方法を解説。

ビットカウント命令の用途
集合をビット列で表しているばあに、集合の大きさを求める
エラー訂正コード


安全な通信:自由のための技術 アシシ・グルハッチ
著者がLFCのために一人で作ったセキュアメールシステム(Cryptonite)の開発とその成果
・このシステムは大部分がヒマラヤ山脈でVSAT、無線LAN、Bluetooth FGPRSとCDMAらの無線技術を使ってかかれた
・既存のコードライブラリを最大限に再利用する。そのためPerlを選択
・エンドユーザ向けアプリではシンプルで使いやすいことが第一
・スタートダッシュのために動くプロトタイプを構築して本質部分の機能を実装してみてから
・システムはできる限りシンプルに保つ
・サクサク動くようにつくる
・ソフトウェアアプリケーションは生もの、更新、機能増強、テスト修正、マーケティング、サポートを何年も行う必要がある
・解こうとしている問題にあなたが興味をもっていること

セキュアなメっセージ送信の複雑さを解決する。
 鍵の認証問題方式の解説
ユーザビリティを保ち、セキュアであるものを作る。

基盤
設計上の目標と決定
基本システム設計
テスト郡・・・インターフェースとコアは切り離しているから別々にテストできる。テストコードの例
動作するプロトタイプ
整理し、つなぎ換え、動かすを続ける
ヒマラヤ山脈でハック
見えざる手が動く・・・市場にでていたから開発の優先順位をあげることができた
速度が問題・・・・IMAPにキリかえてメールボックスが大きくなると速度がおちる。その対応
これらについて解説。

個人の権利のための通信プライバシーについて必要性を解説
文明をハックする・・・コードは世界を何度もかえてきた。グローバルな数学的に保護された開かれた社会を実現することはマシンをつかさどる我々の責任。


12章 BioPerにおける美しいコードの成長 リンカーン・シュタイン

生物情報学(バイオインフォマティクス)はDNA配列解析マシンやマイクロアレイ技術による複雑な遺伝子発現パターンのスナップショットなど、テラバイト単位のデータを生成し、それをフィルタにかけたり、保存したり、操作したりデータマインニングするためのソフトウェア工学を応用する学問分野
ウォール街のソフトウェア工学と類似して足が速くなければならない。エクストリームプログラミングやあじゃいる開発手法、迅速なプロトタイピングと稼働を可能にするツールキットを好む。またデータの資格化やパターン認識に特に重きがおかれる

BioPerlは生物情報学向けに開発されたラピッド開発ツールキットのひとつ。Perlで書かれた再利用可能なコードを集めた広範なオープンソースライセンスライブラリ。DNAとタンパク質の解析、京討議の構築と解析、遺伝子データの解釈など生物情報学において最もよく扱う問題を処理するモジュールを提供する。

Bio::Graphicsモジュールを使ってゲノムとその前アノテーションを迅速に視覚化できる。
どんな風につかい、どんな出力があるか解説

Bio::Graphicsの要件
・問題のオープンさ
・フィーチャーの密度
・倍率の扱い
・対話的ウェブアプリケーションでの活用
・画像形式に依存しないこと
・データベーススキーマに依存しないこと

Perlはコード例をざっと読み通して、設計ロジックの全般的な感覚をつかめばよいといっていた。

Bio::Graphicsの設計プロセス解説
・オプション設定
・オブジェクトクラスを選ぶ Bio::Graphics::Panel Bio::Graphics::Track
・オプション処理
・コード例
・動的オプション
・Bio::Graphicsを拡張する
・ウェブ開発者をサポートする
・出版向け品質の画像をサポートする
・新しいグリフの追加

他の開発者たちに使われるソフトウェアの設計はチャレンジング。
Bio::GraphicsはPretty Goodで実装にあたり改善したいところもあるが、それでは既存のグリフクラスをかきなおさなければならないので、今の状態が最善であろうといっていた。


13章 遺伝子ソータの設計 ジム・ケント
遺伝子ソータ・・ヒトゲノムの約25000の遺伝子を素早くふるいにかけて、科学者たちが自分の研究に関係する遺伝子をみつけるための手伝いをするプログラム。約2万行のサイズの中規模プログラム。その本当の美しさは全体の読みやすさ、理解しやすさ、拡張しやすさにある。
概要紹介
 遺伝子ソータのユーザインターフェース
 ウェブ上でのユーザーとの対話管理
コードの重要な個所を注目
 少しのポリモルフィズムを使い倒す。
 フィルタで関連する遺伝子の実に絞る
数千行を超える長いプログラムを楽しく、そしてさらには美しく扱っていくためには、どんな留意点があるか議論。
 プログラミングにおける最大の制約となる資源は人間の記憶。
 コードの各部分についてそれを理解するのに必要な範囲が1画面に収まる必要がある。
 名前付けの選択がうまいこと、
 できるだけ局所的なスコープを使う
 関数は返り値を返すだけで、どの変数も変更しないようにする

遺伝子ソータはC言語で書かれた、素直なポリモルフィズムを使ったオブジェクト指向の設計になっているので、列を追加するのに簡潔なテキストファイルを編集するだけで済む。
ディスクシークも最小になるようにしている。

14章 エレガントなコードはハードウェアに合わせて進化する:ガウスの消去法の場合 
ジャック・ドンガーラ ピョートル・ラスツゼック

線形代数、とくに連立1次方程式をとくことは多くの科学技術計算の中心部分になっている。
密行列に対する問題をガウスの消去法(LU分解)で取り上げる。
LU分解は比較的簡潔で、境界要素法を用いるいくつかの科学技術計算(電磁散乱、計算流体力学)において重要な役割をはたす
 
効率の良い線形代数アルゴリズムを設計する際の鍵となる動機、データがメモリ階層の間を移動する頻度を最小にする。
考慮するコンピュータアーキティクチャ
・ベクトルマシン・・・1ステップでベクトルレジスタに格納されているかなり多数のオペランドに対して1つの演算を実行できる。行列アルゴリズムをベクトル・ベクトル演算として表現するのが自然
・キャッシュ階層をもつRISCコンピュータ・・・最初はベクトルマシンより遅かったが、CPUの性能向上でそれほど遜色なくなった。
・分散メモリ方式の並列システム
・マルチコアコンピュータ

行列データを任意の自明な方法で分割しただけでは、アムダールの法則によって述べられるスケーラビリティの問題がすぐ表面化してしまう。ほとんどの計算が独立に実行可能でない限り、並列度を増しても高速化しなくなる。

行列分解・・・行列Aに関係する問題があたえられたとき、Aをより簡単な行列の積に分解することにより、問題が簡単に解けるようになるというアイディア

連立方程式 Ax=bを解く問題を考える。
A=LU
単純版としてLU分解の素直な実装をします。n-1個のステップからなる。対角線より下をすべて0にしていく
美しさを犠牲にして効率を上昇する方法。
LINPACKのDGEFAサブルーチンを使う方法
再帰的LU分解
ScaLAPACK PEGETRFを使う方法
マルチコアシステムのためのマルチスレッド化
誤差解析と操作数について・・・実行性能をあげるためにエレガントさを犠牲にすることは受け入れられても、数値的安定性は重要であり犠牲にはできない。

将来の研究動向
ハードの変化(マルチコア)などによってソフトウェア開発者が直面する問題は複雑化しており、いま効率的なコードでも将来もそうとは限らない。


15章 美しいデザインの長期にわたる恩恵 アダム・コラワ
丸め誤差の問題など、うわべは素直で単純な数式のアルゴリズムで現実に実装するのは極めて大変というものがある。
力任せの方法では時間がかかりすぎるものがある。
データセットが異なると違うアルゴリズムの方がうまくいくこともあるので、美しいコードと美しい数学は必ずしも同一物ではない。
CERNの数学ライブラリを例に理論と実践の違いを解説。

コードの究極の目的は使われること。
信頼できるコードのなかに美がある。

数学ライブラリの最大の問題点の一つは丸め誤差と浮動小数点演算が解の不安定さや間違った結果になること。
各アルゴリズムがうまく働く範囲をきめる、丸め誤差が互いに相殺するように書く必要がある。

外側の美しさ
CERNライブラリはアルゴリズムは非常に明確な方法で記述されており、どのルーチンも何をするのか説明が付されている。
言語は問題でなく。どこからでも呼び出せるインターフェースがあるのがよい。

内側の美しさ
コードの実装の詳細
美しいコードは短い。コードが何をするのか理解するために数百行のコードを読む必要はない。
サブシステムのルーチンに分かれており、他のドライバルーチンからも呼び出すことができる。
明快かつ簡潔なコードがコードの再利用を促す生命線。
C++で書かれているものの多くが軽傷とオーバーロードの濫用のしすぎでコード自体が本当は何をやっているかわからない。美しくない。
コンピュータの有限な処理速度を考慮しているモノが美しい。
流れの中にある美しさ、タスクがサブルーチンへと論理的に再分割されており、本を読むように読めるのが美しい。

短くて、明確で、質素で、現実を考えて書かれているモノが美しい。
CERNライブラリはその一つ。


16章 Linuxカーネルのドライバモデル:一緒に働くことの恩恵 グレッグ・クローハートマン
LinuxカーネルでUSBで接続された2つのプリンタをどちらに先に電源をいれても、Linuxカーネルがどちらを先にみつけても同じ名前をもつようにしたいという問題を解決する。
Linuxカーネル内部でドライバとデバイスを統合するモデルで解決する

カーネル中のすべてのデバイスのための「基底」クラスの構造体
型チェックをしないことで種別チェックに寄り掛かることなく論理でコーディングすることを強制していくれる

C言語で書かれているマルチスレッドのプログラム構造が持つ主な問題点は構造体が占めているメモリを安全に開放できる時点を見極めるが難しい。
構造体の参照カウントを行う構造体のフィールドを一つにして構造体を安全に開放できる時点を決めている。

小さいので数千個のデバイスへの規模拡大ができた。
LinuxのドライバモデルはC言語を使って多数の小さなオブジェクトを生成する行動にオブジェクト指向的なモデルが実現できる。
Linuxカーネルの開発方式がもつ、興味深く強力な二つの側面
第1 開発プロセスは極めて反射的。システムが変化する環境で生き延びていくために進化の必要性がある。モデルの様々な面を抽象化して変化にそなえる。
第2 デバイス管理コードの歴史をみると、開発プロセスが極めて協調的なことがわかる。開発がそれぞれ独立したアイデアを実現しようと、ソースコードをよんで改良をくわえていった。それが1人ではたどりつけない共通解をもたらした。


17章 もう一段の関節参照 ディオミディス・スピネリス
バトラー・ランプソンの言葉「コンピュータ・サイエンスにおける問題のすべては、もう一段の関節参照によって解決できる」
複数のまったく異なるファイルシステム形式をサポートする典型的なオペレーティングシステムの問題を考える。

Switchを使って実装する方法
FreeBSDのreadシステムコールにおける関節参照のレイヤー構造一覧
関数の引数を引数ポインタにする
システムコール内のバイパス関数を経由した呼び出し図

先の言葉には続きがあって「しかし、そうすることで、たいてい、新たな問題が作り出されるのだ」
間接性や階層構造は空間的、時間的オーバヘッドとコードの理解しにくさをもたらす。
時間的、空間的オーバーヘッドはあまり重要でない、しかしり理解しやすさが損なわれるのは重要な問題。
なにか漠然として、明記されていない要求で将来表れるのでは想像しているもののために階層を増やすことには慎重になるべき。
パート・スマールダーはアンチパターンの議論で「層はケーキにあるべきもの、ソフトウェアじゃない」といっている


18章 Pythonの辞書実装:すべての人々にすべてのものであること アンドリュー・クッヒリン
プログラミング言語Pythonにおいて、辞書は基本的データ型。awkの連想配列やPerlのハッシュのように、辞書には一意的なキーから値への対応表が格納されている。
辞書にたいする基本操作
・新しいキーと値の対を追加する
・あるキーに対応する値を取り出す
・既存の対を削除する
・キー、値、またはキーと値の対を列挙する
Pythonインタプリタのプロンプトに向かって辞書を扱っている例をあげる

辞書の内部の構造の解説
特別扱いのコードをまぜることで効率をあげるアイデア、ただし、やりすぎ注意
ハッシュが小さい場合の特別な最適化・・・8スロットのハッシュ表
特別なキャッシュが負荷に見合うとき・・・文字列しかうけつけないケースのデータ型
Java版の実装:もう1つの特別扱いによる最適化
C版の実装:記憶関数をダイナミックに選ぶ

ハッシュ表の実装で重要な判断事項になるのは
2つのキーが同じスロットにわりあてられたときどうするか
連鎖法と開アドレス法の解説

辞書のハッシュ法の大きさはキーが付け加えられていくうちに、調整が必要になる。
辞書の管理コードは表の3分の2がうまっていることを目標にする。
辞書の大きさは4倍を目安にする
メモリのトレードオフが見合うとき・・フリーリスト。未使用のデータ構造をリサイクルして、malloc()とfree()の呼び出し回数を減らす
繰り返しとダイナミックな変更をおこなっているとき、項目の追加と削除を禁止

Pythonの辞書は多くの機能やオプションを提供し、処理系内部で広範囲に使われている。Cpyrhonにおける辞書の実装は全般にとても素直。
ソースファイルを読んでみて、コメントとコードを読むのをすすめていた。


19章 NumPyの多次元イテレータ トラビス・E・オリファント
NumPyはPython言語のオプションパッケージで、強力なN次元配列オブジェクトを提供する。
 一次元配列は音の波形のサンプリングデータ、2次元配列は白黒画像、3次元配列は(3つの次元のうちの1つに3または4の長さをもたせる)カラー画像を、4次元配列にはコンサートの時間ちゅの部屋の各店の圧力値を格納することができる。
配列の任意の部分をスライシングという概念で選択で来たり、見境なくコピーして計算資源を食い尽くさないという特徴がある。

これを実現しているループ、メモリモデル解説。
イテレータがどのような由来をもち、設計され、進み方、終了の仕方を解説。
イテレータがつくられるとき、カウントをたどる方法、イテレータの構造、インターフェースを解説。

イテレータの利用として
次元を一つだけ除外して他の全要素を繰り返すを解説。

イテレータはNumPyのコードベースのいたるところで、N次元ループの構築を簡単にするために使われている。
イテレータを効果的に活用することでデータ配列から配列へコピーするコードがNumPyのブロードキャストの定義と矛盾しないよう手直ししたときの例をあげていた。

NumPyのイテレータオブジェクトはプログラミングを簡単かするコーディングの抽象化の一例。


20章 NASAの火星探査機計画のための高信頼エンタープライズシステム ロナルド・マック
NASAの可視探査機計画に作られた協調的情報ポータルシステムCIPについて、
エレガントのアルゴリズムや小さなプログラムとは違う巨大なソフトウェアにおける美を解説。
火星探査機の目標
 火星の表面に液体の水が流れたことがあるかどうか調べる。
 2003年と2004年に打ち上げられた地質学者ロボット。星の表面を自力走行でき、関節のある腕の先端に搭載されたスペクトラム測定機などの科学機器、ドリルと顕微鏡画像装置で表面の岩の下を調べる。これを無人でおこないデータと画像を地中に送信する。

ミッションのニーズ
 時刻管理
 関係者の管理
 データの管理

システムアーキティクチャ
CIPの3層サービス指向アーキティクチャ図、クライアント、ミドルウェア、データ
重要な設計原理
 標準に基づくこと
 ゆるい水美月
 言語独立
 モジュラリティ
 スケーラビリティ
 信頼性

事例としてミドルウェアの一つであるストリーマサービスをみる。
JPLに設置されているミッション用ファイルサーバーからユーザーが自分の個人用ワークステーションやラップトップマシンにデータや画像ファイルをダウンロードするための検索用メタデータが生成されている。ストリーマサービスはファイルのダウンロードとアップロードのサービスを行うミドルウェア。
サービスアーキティクチャの図解 遠隔クライアントアプリケーション→アプリケーションサーバー→ミッション用ファイルサーバー2階層のサービスでファイルのダウンロードを行う様子を図解、クライアントアプリケーション→ストリーマサービスプロバイダ→ファイルリーダ
同様にアップロードも図解

CIPプロジェクトにおけるシステムの本質的信頼性を確かめるための速度基準
・業界標準とベストプラクティスに従う。J2EEなど
・適用可能な個所についてはCOTSソフトウェアを採用する。
・モジュール化されたサービス構成のサービス指向アーキティクチャ(SOA)を採用する
・ミドルウェアサービスの実装を簡単かつ直線的なものとする。
さらに著者たちは信頼性を高めるために「ログをとる」「モニタする」を行った。
コードとモニタリング画面がのっていた。

頑強さのために
・ミドルウェアサービス中ではパラメタを直接ハードコーディングすることを避ける
・すでに運用に入っているミドルウェアサービスへの変更が、クライアントアプリケーションに及ぼす影響を最小限にとどめる

動的な再調整
パラメタ値をハードコートしない。これは巨大なアプリケーションでは特に重要

ホットスワップ
 すでに実行している状態のミドルウェアサービスを落とすことなくミドルウェアサービスを新しいものに置き換えさせてくれる。
巨大エンタープライズでは特に意味がある。

巨大アプリケーションのための美しさは必ずしもエレガントアルゴリズムはない。CIPではサービス指向アーキティクチャの実装と多数のシンプルな、しかしよく選び抜かれた要素群の中に美しさがあった。熟練したソフトウェア製作者の選択の勘所が美の極み。


21章 ERP5:高水準の適応性に向けた設計 ロジェリオ・アテム・デ・カルバルホ  ラファエル・モネラ
ERP5は、ERPシステムのオープンソース。システムのコアを構成する5大要素にちなんでなずけられた。
ERP5はドキュメント中心のアプローチを選択したことで、開発者でもユーザでも容易に機能向上できる。

著者たちが作ったプロジェクト管理モジュールERP5Projectを創り出すためにどのようにラピッド開発手法を用いたか解説。

ERPは組織のすべてのデータとプロセスを1つのシステムとして統合することを目的とするソフトウェア。

ERP5で使用されるZopeの要素の主なもの
・ZODB・・オブジェクトデータベース
・DCWorkflow・・・ワークフローエンジン
・コンテンツ管理フレームワークCMF・・コンテンツを追加したり削除したりする基盤
・ZopeページテンプレートZPT・・XMLベースの簡易GUIスクリプト

ERP5でビジネスプロセスを表現するための土台となる5つの抽象概念
・資源・・・個々のスキル、商品、機械など
・ノード・・・資源を受け取ったり送り出したりするビジネスエンティティ
・パス・・・あるノードが他のノードから必要な資源にアクセスする方法の記述
・移動・・・ある時点、一定期間のノード間の資源移動の記述。
・品目・・資源の一意的なインスタンス。例CDドライブはPCをくみたてる資源だが、商品番号のついた品目でもある。

Zopeプラットフォーム基盤解説
動作タブ画面とシステムクラスの解説

ERP5 Projectのコーディング
タスクのワークフロー図・・・発注とか計画済みとか
タスク報告のワークフロー図

ERP5は高度な柔軟性をもつツールを実装できた。
再利用は日常的であり、新しいモジュールをつくるときも、GUI要素を取り換え、ワークフローを調整するだけで済む。
オブジェクトデータベースの問い合わせは抽象レベル=特定のビジネス分野の概念が取り出されるないし、ポータル型のメタクラス=UBMの汎用概念に関係する全オブジェクトが取り出されるで処理される。


22章 スプーン一杯の汚水で ブライアン・キャントリル
たる一杯のワインにスプーン一杯の汚水を注ぐと、たる一杯の汚水になる  ショーペンハウエルのエントロピーの法則

ソフトウェアの正しさは2進法。正しいかそうでないか、そこは数学に似ている。
普通の工学のように負荷率や最高速度、環境条件などはない。
そうであるから、一つの欠陥がソフトウェアに情けない失敗をもたらす。

著者が1999年にSolarisカーネルの重要なサブシステム開発中に遭遇した、深い設計上の欠陥がどのようにしてバグとしてあらわれてくるか。そして複雑で重要なソフトウェアを完璧に動作させようとするとその詳細がいかに悪魔的であるかを解説する。

ターンスタイル・・・Solarisオペレーティングシステムにおいてスレッドをブロックしたり起こしたりするのに使われるメカニズム。mutex(排他ロック)やリーダライタロックのような同期の基本操作の土台部。

ターンスタイルの概要をコード10行のほど、コメントは15行ほどで解説
そして問題になった実装コード2行とコメント3行を紹介。

ターンスタイルが古典的問題優先度逆転についてどのように処理するか解説。
解決方法1 優先度継承 Solarisで採用されていた。

ブロッキングチェーン・・・待ち状態のスレッドの連鎖
例としてカーネルのメモリアロケータとゼタバイトファイルシステムの間のやりとりをあげていた、
ある優先度のスレッドが待ち状態に入ったときには、対応するブロッキングチェーンに連なるスレッドすべてが整合性を保った状態で優先度を上昇させるひつようがある、
Solarisではスレッドのディスパッチ状態はスレッドロックとよぼれる特殊なスピンロックで守られている。
整合性を保つためにはすべてのスレッドロックを獲得すればいいが、スピンロックへのポインタで実装されているのでうまくいかない。
ブロックキングチェーンが巻き戻されるのは待ち状態にない側からに限られるので、同時に2つの連続した要素のロックを保持しておきさえすればよい。
しかし、ターンスタイルテーブル(同期プリミティブの仮想メモリアドレスをキーに持つハッシュ表)中のロックとブロッキングチェーンをたどり二つのロックを保持するという状況があわさるとロックの順番という問題が発生する。
これにも対処したはずだったが、OSの欠陥は発見される。
著者と同僚はコアダンプをつかい(検死デバッグ)から原因をつきとめ、それが設計上の問題であることに気が付いたという。
著者のバグレポートがのっていた(スレッドA,Bについて優先権のかくとくを細かくおったもの)
ユーザレベルのロックを獲得解放するときにもカーネル内のロックを獲得記録解放することが必要。
ブロッキングチェーンがループになっているように見える場合があり、カーネルはそこで緊急停止してしまう。
これをもとにバグを発生させるテストケースを書く。・・・満塁ホームランの気分
さらに偽デットロックが発生する場合があると気が付く。
いくら議論してもそれを避ける方法が見つからないので、問題の状態がおきる2つの場合、パニックと偽デットロックがおきたとき対応する方法を考えた。
そして修正して負荷テストをおこなったところ、OSがただハングするというさらに暗黒な問題が発生
ユーザレベルの優先度継承を行う獲得と解放の時、カーネル内のロックの獲得・解放が必要。しかしカーネルレベルロックとユーザレベルロックのハッシュ関数がたまたま同じで同じターンスタイルテーブルにエントリしているとデットロックになる。
さんざん悩んだ末に、ターンスタイルテーブルをユーザレベルの優先度継承の状態をガードするためのロックのハッシュ表とそれ以外に分ける。抽象かよりも、特定で問題を解く。
これで問題は修正されたが、もっとも低級な解き方であることは認めるといっていた。

良いソフトウェアエンジニアリングの原理
・早く実装する。
・集中的に攻める
・境界条件に注意する
これらが行われればプロジェクトの初期段階で最も難しい問題を実装することに注力することになり、全体構造がうまく働く検証になる。設計上の変更がまだ間に合う時期にとらえられて、ワインが汚水に代わることはなくなるだろう。


23章 MapReduceでの分散プログラミング ジェフ・ディーン サンジェイ・ゲマワト

MapReduceは大規模なデータ処理問題を解くプログラミングシステム。Googleで開発された。日用的マシンのクラスタ上
で並列実行される。実行時システムが入力データを分割する手順の詳細を担い、一群のマシン上でのプログラム実行をスケジュールし、マシンの障害に対処し、またヒチョウとなるマシン間の通信を管理する。

単語検索の例題
200億個の文書があって、それらの中にある1つの単語がなんかいでてくるか数えたいものとする。
文書の平均サイズ20kbとすると1台のマシンで合計のデータ量400テラバイトを読み通すのには、だいたい4か月かかる。
コードの例 素朴で並列化してないバージョン。
次は並列化バージョン
記憶域を分割した並列化バージョン
プロセッサ分割を用いた並列版

これらをみると、単語を数えるという単純な作業が並列化を管理するための多数の詳細な点にうもれてしまったことがわかる。
並列化のパターン(下の二つ)をつきとめ、問題を解く手順の詳細と分割するのをめざす。
・各々の入力レコードについてそこから関心を持つキーと値の対を抽出する。
・抽出されたキーと値の対それぞれを、同じキーを持つ他の対と結合する。

単語計数プログラムMapとReduceに分割する例
そのためのドライバのコード

MapReduceを使った別の例
・分散Grep
・ウェブリンクの逆フラグ
・ホストごとの単語やベクトル
・逆引き検索
・分散ソート

分散MapReduceの実装
さまざまな計算プラットフォームに対して、それに合ったMapReduceプログラミングモデルの実装が可能。
ただしい選択は環境に依存する。

Googleの計算環境は、多数の日用的なPCがスイッチを用いたイーサネットで互いに接続され、大規模なクラスタを構成しているもの。
ここでの実行の概要を解説。

実践的に役立つことがわかった基本モデルの2・3の拡張機能について説明
・分散関数
・順序の保証
・悪いレコードを飛ばす

2007年初頭、Googleでは6000個以上のMapReduceプログラミングモデルが付くアラレいて、一日に35000個のMapReduceジョブが実行されている。
ウェブサーチのサービス用に索引付のシステムを書きなおそうと開発されたが、機械学習、統計的機械翻訳、ログ解析、情報検索の実験、汎用の大規模データ処理や計算処理などに役立つことがわかってきている。

付録 単語計数問題の解法


24章 美しきかな、並列 サイモン・ベイトン・ジョーンズ

次世代プロセッサを購入すればプログラムが速くなる時代は終わった。
次世代チップは多くのCPUをもつが、個々のCPUは前年のモデルより速くない。
自分のプログラムを速くしたければ並列プログラムの描き方を学ばなければならない。

並列プログラムは非決定的に実行されるため、テストは困難で、バグはほとんど再現できない。

美しいプログラムは単に明らかな間違いがないだけでなく、明らかに間違いがないと一目でわかるような単純でエレガントなプログラム。

並列プログラムは逐次プログラムに比べて美しくなく、モジュラリティが低いことがしばしばある

STM・・・ソフトウェアトランザクションメモリは共有メモリ型並列プロセッサをプログラミングする有望なアプローチ。著者にとっては現在の技術がサポートしていない形でのモジュラープログラミングをサポートしていると感じるそうだ。

例題 銀行口座問題
ある銀行口座から別の銀行口座にお金を転送する手続きを書く。
どちらの口座もメモリ内に格納されていて、データベースとの交信は不要とする。
多数のスレッドが同時に転送手続きを呼ぶ可能性のある並列プログラムでも正しく稼働する。

同期メソッドでロックと条件変数を使う例

ロックの問題点
 獲得したロックが少なすぎる
 獲得したロックが多すぎる
 間違ったロックを獲得する
 間違った順序でロックを獲得する
 エラーの回復
 スレッドを起こしそこなったり間違って起きた時の処理を忘れる。

言語HaskellとSTMを使って上の問題を解決する過程を解説。
言語とSTMの解説もおこなっていた。

STMの解説にサンタクロース問題をあげていた。
Haskellではアクションが値であることが特徴といっていた。

STMを使うことでロックによる平行プログラムを苦しめる標準的な問題の多くを回避できる。
特にHaskellと組み合わせることでエレガントになる。
STMを使うのはアセンブリの代わりに高水準言語を使うのに似ている。


25章 構文の抽象化:syntax-case マクロ ケントディヴィグ

コンピュータのプログラムを書くとき何度も同じパターンが出てくるときがある
こういう時に「構文の抽象化」を行う仕組みが用意されうことがあり、C言語のプリプロセッサマクロやLispのマクロなどである。
どちらもマクロ呼び出しフォーム内部に出てくる識別子のスコープは入力側できはなく出力側になるので、変数参照の意図しない補足がおきる可能性がある。

syntax-caseは元のアルゴリズムへの欠陥を克服するために開発された。
ローカルなマクロ束縛をサポートし、定数オーバーヘッドで済み、しかもマクロがScheme言語の表現力をフルに使えるようにする。
そのかわり展開アルゴリズムは複雑になり、コードも大きくなるので、この章ではアルゴリズムの基礎と実装の最重点の説明のみ解説。

syntax-case使用例
展開アルゴリズム
構文オブジェクトとして表現
展開出力の生成
構文オブジェクトのそぎ落とし
構文エラー
構造に関する述語
wrapの生成
環境の操作
識別子の判別
エクスパンダ
コアの変換
構文オブジェクトの解析と構築
識別子の比較
変換
展開の開始

例題をあげて追跡

簡単化したマクロエクスパンダはsyntax-caseの完全版の実装が用いている基本アルゴリズムを説明するもの
複雑なパターンマッチ機構、内部定義の処理、コアフォームの追加は省いた、
環境の表現方法も1変数版のものを使った
syntax-caseマクロエクスパンダは健全なマクロ展開アルゴリズムKFFDに局所的な束縛構文、制御された補足機構などのサポートを追加し、計算量が2時である点を改良している。
KFFDの展開プログラムの方が美しいコードになるが、設計通りなことをするsyntax-caseのエクスパンダのなかにも複雑なソフトウェアの美しさがあるはずだ。


26章 労力節約のアーキティクチャ:ネットワークソフトウェアのためのオブジェクト指向フレームワーク 
ウィリアム・R・オッテ ダグラス・C・シュミット 

ネットワークアプリケーションのソフトウェア開発が大変なのは、分散システムに固有な複雑さの他に、非本質的な複雑さがある。それはCレベルのOSAPIをつかっていること、これは機能分解による開発を奨励する設計になっており、機能分解では保守や改訂は複雑になる。幸いC++、Java,C# などのオブジェクト指向言語、方位ふぁさーだ、アダプタなどのデザインパターン、ACE、javaネットワーククラス群などのフレームワークが低レベルのOSAPIをカプセル化してくれるようになった。

しかし、そのようなフレームワークをいかにして作るかはブラックアートのままだ。
ネットワークソフトウェア向けのオブジェクト指向フレームワークの事例研究について述べる。

簡単なアプリケーション:ログ記録サービス
アーキテクチャの図
・開発者がログレコードを送ったり受け取ったりするのに使えるような、プロセス間通信のための各種機構(ソケット、SSL,共有メモリ、TLI、名前付きパイプ)
・開発者がログレコードを処理するのに使えるような、各種の並列処理モデル(反復型、反応型、接続ごとのプロセス、各種のスレッドプール)
・開発者が複数スレッドの共有資源(回数を数えるカウンタ等)へのアクセスを順次かするのに使えるような、各種のロック方式(スレッドレベル/プロセスレベルの再帰mutex、非再帰mutex、リーダライタロック、null mutexなど)
・クライアントからサーバへ伝達されるログレコード形式、サーバが受け取ったらそのろぐレコードはさまざまな形で処理される。例、コンソールに出力される、1つのファイルに保存される、あるいはディスクへの並列書き込みを最大化するためにクライアントごとに1つのファイルに保存される。

これらのどれを選択しても実装は比較的素直に行える。
しかし、顧客の要求や動作環境がちがうとすべてのログ記録のニーズをみたすことはできない。
チャレンジすべきは柔軟に構成可能なログ記録サーバを設計すること。
そのチャレンジの核心はデザインパターンと関連する設計技法を理解したうえで、
・基底クラスやジェネリッククラスを用いて共通の構造と動作を補足
・サブクラス化やジェネリッククラスのパラメタ化による選択的なカスタマイズの実施

上記を踏まえたオブジェクト指向ログ記録サーバ用フレームワークの設計の図
設計の核になっているLogging_Serverクラスでは
・C++のパラメタ付きの型を使う。開発者はジェネリッククラスで使われているデータ型や機能の選択をインスタンス生成時点まで延ばすことができる。
・テンプレートメソッドパターンを使う。個々のステップはサブクラスによりオーバライドされる可能性のあるメソッドにまかせながら、アルゴリズムの骨組みを定義する。
・包囲ファサードパターンを使う。オブジェクト指向でないAPIとデータを、型安全なオブジェクト指向クラスの内部にカプセル化する。

ログ記録サーバ用フレームワークのオブジェクト指向設計
重要な概念
・ドメインに特化したオブジェクト構造と機能を具現した半完成品のアプリケーションを定義
・フレームワークは能動的であり、実行時に制御の反転を伴う
・スコープ・・・ドメイン(フレームワークが記述する問題範囲)とフレームワークのコンテキスト定義
・共通性・・・フレームワークに基づくファミリー製品すべのものに繰り返し現れる属性の記述
・可変性・・・ファミリー製品の個々のものに固有な属性の記述

フレームワークによって実装される共通性とサブクラスやパラメタによって特化される必要のある部分(可変性)にわける、
ログ記録サーバのメインループ図
変化に対応するための、テンプレートメソッドパターンとそのログ記録サーバへの応用の図
IPCと同期メカニズムを並列性戦略に関連づける方法を考える。
 ・Strategyパターンを使ってアルゴリズムをオブジェクトとしてカプセル化し、実行時に入れ替え可能にする。利点と欠点・。 
 ・C++のパラメタ付きクラスを用いてIPCと同期のための特定の包囲ファサードを持ったログ記録サーバを実体化すること。
2番目の方法でコードがのっていた。

逐次的なログ記録サーバの実装
 すべての処理が1つだけのスレッド内で実行されるような、ログ記録サーバの実装。反復型と反応型の2つを説明
この方法では一つのクライアントの処理だけを行うのではなく、複数クライアントのサービスをインターりーぷするという点はよいが、OSの並列実行機能を利用し枝いないので、マルチプロセッサの能力を有効利用することはできない。新しいレコードを読み込むのと並行して炉グレードを処理することもできない。それでクライアント数が増大した場合のスケーラビリティがない。
 しかし、簡潔であるのでオブジェクトフレームワークに基づいた美点を浮き彫りにしてはいる

並列ログ記録サーバ実装
OSが提供するAPIを使ってスレッドやプロセスを作るのは、それらの理由が本質的な理由でないのに複雑で気が遠くなる作業である。その複雑さを克服する解決策としてプラットフォームをまたがる一貫したインターフェースを提供する包囲ファサードを使用して、Logging_Serverのオブジェクトフレームワークに統合する。

接続ごとスレッドによるログ記録サーバ
 クライアントからの接続を受け付けるmainスレッドを実行、接続が来たら新しいワーカスレッドを生成し、ワーカスレッドがその接続からのログレコードを処理する。
 プロセスの手順と実装の検討を解説。

接続ごとプロセスによるログ記録サーバ
 上と同様だが、スレッドではなく新しいプロセスを作って各クライアントからやってくるログレコードを処理すること。
 並列性のためにプロセスを使う場合、プラットフォーム間でのプロセス生成セマンティクスの差異に対応できるような設計上の選択が必要。例としてLinuxとWindowsのプロセスAPIの相違点とカプセル化がのっていた。

並列ログ記録サーバはマルチスレッド実行をサポートするハードウェアやOSを活用してクライアント数が増えてもスケーラビリティを発揮するという面で強力。プラットフォームを関知しない形で開発するために包囲ファサードを使った。

ログ記録サーバアプリケーションはオブジェクト指向設計/プログラミング技法、デザインパターン、フレームワークをネットワークアプリケーションのためのソフトウェア実装に適用する方法を示すための、消化しやすいけれど現実的例題。


27章 ビジネスパートナーをRESTfulにまとめ上げる アンドリュー・パッツァー
 著者が経営コンサルタントだったころ、だれもかれもが自分のビジネスソリューションのためにウェブサービスを必要としていると思っている時期があった。しかしそれは流行によるものであることも多い。
 ビジネスパートナーに一連のサービスを提供する現実のプロジェクトをみてみて、その過程でなされた設計上の選択について議論する。
 Jave(J2EE)、XML,e-ビジネスプロトコルRosettanet、AS/400で実行されるプログラムとの通信に使われる関数ライブラリのはなしがでてくる。

プロジェクトの背景
 大きな電子部品工場から「我々のシステムを販売店の1つと統合するためのウェブサービス一式を整えたい」という要求
 採用していたのはMAPICSというAS/400で実行するRPGで書かれた製造システム
 販売店は独自のビジネスシステムを採用していた。
 これまでは、販売店のオペレータは工場のAS/400システムに遠隔接続してからホットキーを押して必要な画面にアクセスしていた。
 将来加わる販売店のことも考えて、どんなプロトコルや要求がきても対応できるようにする
 ソフトウェアの保守と拡張をするスタッフのスキルは低いので、シンプルで容易に拡張できる必要があった。

 最初はSOAPを考えたが、その後HTTP経由のGETとPOSTリクエストで表されるサービスを使ってリクエストやレスポンスをXMLで行う方法が適していると判断した(これはのちにRESTと呼ばれる)
 判断ポイント
  ・何種類の異なるシステムがサービスにアクセスするのか、またそれらのすべてが現時点でわかっていない
  ・提供するサービスはごく限られた高度な知識をもつユーザが使うのか、それとも自動的に接続してくる不特定のユーザにサービスの説明を見ながら使ってもらうひつようがあるようなものか
  ・1つのトランザクションを通じて維持される状態は何種類か?前の結果に依存するリクエストをすることはあるのか?

サービスインターフェースを決めるにあたり、最初はユーザがどんなふうにリクエストをだし、レスポンスを受け取るかきめる、
HTTP POST リクエストをXML文書でだし、HTTPレスポンスのXML文書を受け取る。

ファクトリパターンを使ってサービスを振り分ける
 実装を一つのコマンドインターフェースまで最小化し、そのインターフェースに多様なリクエストにこたえるのに必要な基本メソッドを提供させることで、その要求仕様を満たす。受け取ったリスエストデータのリクエスト種別を教えてくれる特別な文字を探して振り分ける。

e-ビジネスプロトコルでデータを交換する
 著者にとって新しかったのは標準的e-ビジネスプロトコルを使うこと。
 まず特定の文書のダウンロードを行い、ダイアグラムとXMLのリクエストとレスポンスの仕様をみつけた。
 試行錯誤が必要そうだったので、最初に自分で実行できる販売店とのやりとりのシュミレーションテストを設定
 これでさまざまなタイプのリクエストを試してその結果をみることができたので、理解が加速度的に増えた。
 著者はできるだけ速くコーディングに飛び込む主義の信奉者であるといっていた。

XPathでXMLを構文解析する
 XMLリクエストデータは単純なXMLとは言い難いので、XPathで解析。マッピングはHashMapを使った。

XMLでレスポンスを組み立てる
 XMLは単なる大きなテキスト文字列なので、DOMや特別なXML生成ライブラリを使うよりもStringBufferで書きだすだけの方が普通は簡単。
 コードがのっていた。

著者が2年前に書いたコードなので、実装は変えたいところもあるが、デザインはよかったといっていた。だから時間の経過に耐えられるだろうと。
現在生態情報学部の学部長をしているが、オブジェクト指向設計お設計原理やXMLの構文解析技術を教えるときスタッフにデモとして使用しているコードなのだそうだ。


28章 美しいデバッグ アンドレアス・ツェラー
 デバックは魅惑的なものなどなにもない。
 エラーを避ける為にすべてのことをやったとして、それでもなおデバッグが必要なときがある。
 著者がであった美しいデバック(デバッグの生産性を本当に押し上げてしまうような新手法)について述べる。
 それは問題を解決する方法にあなたを導いてくれることを保証するだけでなく、ある程度まで「自動的」であなたが別の仕事をしていられるくらいである。

デバッガをデバッグする
 GNUデバッガgdbを内包して実現されたデバッガdddのバグ報告がくる
 原因はdgbの変更にあるので、diffをかけたところ178200行、8721か所の結果を返された。
 これを一つ一つつぶす前に美しい方法を考える

系統だった方法
 原因をみつけだすための一般的科学的手法
 1 プログラムの失敗を観察する
 2 観察と矛盾しない失敗の原因について仮説をたてる
 3 仮説を使って予測する
 4 予測を実験でテストして、さらに観察する
     実験と観察が予測を満たすなら、仮説をさらに精密なものにする
     満たさないなら別の仮説をたてる
 5 仮説がこれ以上精緻にできなくなるまで3,4を繰り返す

これをバグ報告にあてはめて、問題は解決した。
系統だったデバッグ手法の訓練をする方がデバッグツールを習うよりも大切。

探索問題
 変更による不具合とわかっているなら、過去から未来に向かって変更を加えながらデバッグすればよいが履歴がわからないのでできなかった。
 そこで変更をいろんな順番で試してみる方法をおもいついたが、計算すると量子コンピュータが発明されそうなくらいかかりそうだったのでやめた。
 ソースコードに加えられた前半の変更を加えてテスト、分割統治法をおもいつく

失敗の原因を自動的に見つける
 アイデア
  ・変更の半分を適用することで矛盾しないビルドを得られる可能性は小さい。でも得られたら変更点の集合が素早く狭まる
  ・変更点を1つづつ加えていけば意味のあるものを得られる可能性は高くなる。

折衷案で、半分から開始してどちらもビルドできない場合は4分割する、だめなら8、16、32に分割。
これをPythonで書いてみる。すると3日待ったあげくスペルミスでつまづいた。
今度は問題点を修正して5日間動かして原因箇所をつきとめた。
原因は埋め込みテキストの1行だった。

このアルゴリズムとツールを磨き上げ、差分デバッグとして公開。
 アルゴリズム
  ・リストc_passには「うまくいった」構成が入る。例題の場合プログラムを動かすためにくわえなければいけない変更点のリスト。空リスト
  ・c_failには「失敗する」設定が入る。例題の場合、プログラムを失敗させる変更点のリストで今回の例では8721個の変更点のリスト。
  ・関数testは変更点のリストを受け取り、それらの変更を適用してからテストを実行する
  ・関数ddは系統的にc_passとc_failの差を狭めていく。
実装のコードの例があった。

入力の最小化
 プログラムの入力に失敗の原因を探すのに差分デバッグを使う例

欠陥を狩り込む
 差分デバッグを使ってプログラム全体のコードを最小化し、重要なものだけを残すこともできるはず。
 例としてNTMLページを印刷している間にブラウザがクラッシュしたとしたら、そのプログラムコードに差分デバッグを適用すれば、クラッシュを再現する最小限のコードだけが残る。
 しかし、実際にはうまくいかない。なぜならプログラムコードの要素どうしは互いが密接に依存しているから。
 ソースコードの失敗の原因を刈込たい、それも自動で、このようなことを達成する差分デバッグを考える。
 問題
  ・プログラムの状態をどうやって取得するか
  ・2つのプログラムの状態を比較する方法
  ・状態と状態の間の差分を適用するにはどうする?
 うまくできれば億万長者になれるかも。

研究室では問題を絞り込んで上の問題を解決できたが、商品になるレベルではなく、脆い。
しかし、入力に対する差分デバッグを実装したコマンド行ツールが利用できる。Eclipseのプラグインddchangeがその一つ。

デバッグをするときは可能な限り苦痛のないデバッグ体験にするべき。
科学的手法で系統的に行う、そしてそれを自動化できればもっとよい。自分のコード開発プロセスに労力を投入しよう


29章 エッセイのごときプログラム まつもとゆきひろ
 プログラムはエッセイあるいは小説に似ている。エッセイであれば「何が書いてあるか」プログラムであれば「何をするか」、その他に「どのように書いてあるか」も重要。どんなに良いことが書いてあっても読めない、読みにくければそれは読み手に伝わらないから
 どんな優秀なプログラムでもプログラムを一気に完成させることはほとんどない。プログラムが段階的に成長するのは小説の推敲ににている。また、ほとんどのプログラムはデバッグや仕様変更や機能拡張があるから、読むことがあるものだ。
 読みやすいプログラム=美しいプログラム。
 プログラムの美の基準は効率。
 どんなプログラミング言語でも「ひどいプログラム」を書く人はいるが、美しいプログラムを支援するプログラミング言語はある。

簡潔さ
 プログラムの美しさを構成する要素の一つ。
 簡潔なプログラムを開発するための近道は簡潔なプログラム言語を選択すること。Rubyなどをはじめとする最近の「軽量言語」が支援してくれる。
 型宣言が不要で、本当に必要なとき以外クラス宣言やmainルーチン定義を要求しない、トップレベルで命令を実行できるというプログラムをjavaとRubyの階乗を求めるプログラムで示す。

保守的
 人間は手になじんたツールを取り換えたり、新しい言語を学ぶなどよっぽどでないとやらない。
 Rubyは純粋オブジェクト指向といわれながら、Smalltalkのような革新的な制御構造は採用せず、伝統的な手続き型言語の制御構造を踏襲している。革新的すぎない美がある。

シンプルさ
 そもそも人間が自分の手で解決するのではなく、プログラムを書くのは、その仕事が本質的に面倒で複雑だから。
 複雑さをできるだけコンピュータに押し付けるのに重要なのは人間が書くコードのシンプルさ。
 ややこしいのは人間がプログラムを書くときに使うツールも人間が書いたプログラムだということ。
 自分の作品をシンプルに保つために他の人の作品に複雑さをおしつけるのは本末転倒。
 Rubyはシンプルな言語ではないが、それを使って記述されたプログラムがシンプルになるように努力している。
 「軽量言語」といわれる言語は仕様や文法、ライブラリの量などは軽量でない。

柔軟性
 コンピュータの都合よりも人間の都合を優先させること
 状況の変化に対応が難しい硬直的なプログラムの例として引数としてうけとったファイル(IOオブジェクト)にログを出力するloggerというメソッドの例をあげていた。これの仕様が変更され文字列として読み出したいときRubyならどうなるか解説していた。

バランス
 「簡潔さ」「保守的」「シンプルさ」「柔軟性」どれかだけが突出していても美は実現されない。これらが調和してはじめてプログラムの美が実現され、書いて楽しく、読んで楽しい、幸せなプログラミングライフが実現できる。


30章 世界につながる手段がボタンだけだったら アラン・メータ
「スティーブン・ホーキング教授ができるのはボタンを押すことだけだ」が仕様。
現在教授が使っているEqualizerというシステムはソフトをボタン一つで操作する。しかしソースコードは失われテキストを音声にするための箱は製造されていない。
 そのため教授は重度の障害者のためのソフトを発注した。著者の会社がこの試みに挑んだ様子。

基本設計モデル
 言語はVB6を採用。組み込みの入力機能が豊富で、プロトタイピングが容易(おそらく多くの試行錯誤がいるとみて)なので。
 身体障害のある人の情報の受け取る量がすくない。選択肢のなかから望むものが表示されたときクリックする方法をとる。前方検索とユーザがみたいと思うものの予測をつけることで入力を効率化する。そのための画面がのっていた。
 入力予測のために、データベース、キャッシュ、特別なグループ化の知性が採用された。

入力インターフェース
 マウスの右ボタンを利用

ツリー
 すべての選択を2分木構造の形で順番に示すインターフェースしかありえない、このツリーをたどる方法、動的に再構築する方法をつくる。

マウスの長押し
 ボタンはクリックするだけでなく、長押しすることができる。これでナビゲーションの高速化をはかる、

他に単純な入力、単語補完と次に来る単語の予測、データベースの任意の文章をテンプレートとする方法、キャッシュの実装方法、共通の単語と好みの扱い、ツリーのパスの取り消し、入力バッファ、編集、スクロール、クリップボード、探索(スクロールの特殊ケース)、マクロ(一連のコマンドを実行する)、ユーザインターフェースの効率をクリック数で計る。ダウンロード先などがあった。

今後は重度の身体障害者でもMacやLinuxを使えるようになるといいといっていた。Emacsspeakなどの技術をつかったり、Emacsを拡張してボタン一つで操作できるようになるといいとも。
読み書きができないひとでも使えるコンピュータがあるといい。だれか一緒に挑戦しませんか


31章 Emacspeak:完全に音声のみのデスクトップ環境 T.V.ラマン
 目を使わなくても視覚を使うのと同じような作業場を実現できる音声デスクトップ開発(Emacspeak)の試み
 目標
  ・電子メッセージのあらゆる種類のサービスを使ってコミュニケーションできるようにする
  ・クライアントのローカル文書とウェブの文書を容易に使えるようにする
  ・目を使わなくても効率よくソフトウェア開発がdきる。
 目で見て読むために画面に書いた情報をよみあげるだけでなく、実際の情報からはじめて音声にしないと効率よく情報が伝わらない。
 音声デスクトップのために選ばれた環境に必須だったもの
  ・発話による音声出力と発話でない音声出力サービスがコア部分にあること
  ・音声出力化する価値のある既存のアプリケーションが豊富にあること。

音声出力の生成
 1994年10月、LinuxラップトップPCと研究室のワークステーションをターゲットに開発開始。DECTalkExpressを使用。
 クライアントサーバ方式で作ったので、Emacspeakをリモートマシンで実行させるのも楽にできた。

音声版Emacsは1時間で完成。
EmacsLispのアドバイス機能を参考に音声版Emacsにアドバイス機能をつける。ユーザが上下の矢印キーを押すとEmacsにかーそるのある行を読み上げさせる。
 音声出力用サーバーが受け取った個々の音声出力コマンドをキューにためて実行する。
 アドバイス機能の概要 before after around

良質な音声出力の生成
 voice-lockによる音声データの整形
 音声出力リスト作成のためのEmacsの拡張
 音声出力リストから整形された音声出力

ACSS(音声スタイルシート)で発話のスタイルを指定する
音声アイコンの追加
コンテンツを読み上げながら音声アイコンを生成する。
カレンダー:文脈依存の意味情報を用いた音声出力の高機能化
オンライン情報へのスムーズなアクセス
基本的なHTMLをEmacsW3とACSSで扱う
タスク指向サーチのためのモジュール emacspeak-websearch
ウェブコマンドとURLテンプレート
フィードリーダの出現

Emacspeakは日常のコンピュータ作業を目を使わずにフルパワーで行えるインターフェースとして計画された。
システムはデスクトップワークステーションのあらゆる計算の側面に直接アクセスが可能でなければならない。
目を使わないで流暢なやりとりをするために、単に画面に表示されている情報を読むだけでなく、音声出力と音声メディアを扱う必要があった。
土台となるアプリケーションのソースコードを変更することなく拡張した、

12年にわたりEmacspeakを管理する。
最初の6週間の開発のあと、Emacspeak自身で開発と保守を行ってきた。
複雑なコードを長期間管理するのに有効だったこと、技術者が一人きり。コードは小さく、ファイルは細分化されていて独立に改良しやすい。

Emacspeakを実装、使用した経験からのまとめ
・Lispのアドバイス機能やそのオブジェクト指向版であるアスペクト指向プログラミングは視覚インターフェースを音声出力できるようにするなどの横断的側面の実装に有効な手段
・アドバイス機能は、複雑なソフトウェアシステムにおいて、拡張可能な点を発見するための強力な手段
・基本的なウェブアーキテクチャに注目し、標準のプロトコルとフォーマットに裏打ちされるデータ指向のウェブを利用することで音声でのウェブへのアクセスを強力なものにできた
・スライダーやツリーコントロールなどの個々の対話用部品に着目する代わりに、最終的なユーザの体験に着目することで、視覚に頼らない高度に効率的な環境が構築できた。
・耳から視覚ほどの情報を聞き取るのは時間の無駄。
・視覚的な複雑さは、視覚を使わないユーザにとっては致命的。RSSフィードやTOMフィードは画面をほりおこさずタイトルなどを取り出す、Emacspeakでは内容をフィルタにかけるために2000年にXSLTを使いだした。

開発者コミュニティに対する謝辞


32章 働くコード ローラ・ウィンガード クリストファー・セイワルド
コードがどのようにみえるか、とりわけ人がみてわかるコーディングの様々な特性がどのようにして、ある人が書いたコードを別の人が読み、それを通じて共同作業を可能とさせるか議論する。

セイワルドの「整ったコードの7か条」
・「本のよう」であること・・ 本のように段組みされ塊になっていると読みやすい
・似たものは似て見えるようにすること・・whileの条件が4つのうち3つまで実質的に同類であると示す例、1つだけ他と違うと示す例
・字下げを克服すること・・字下げは理解を助けない、入れ子は理解を妨げる、入れ子の字下げはわかりにくいという表明、なるべく使わない。
・コードをもつれさせないこと・・・コードをナビゲートすること。
・コードにコメントをつけること・・・コードをナビゲートすること。
・ごちゃごちゃにしないこと・・・コードをナビゲートすること。
・既存のスタイルに溶け込むこと
これはコーディング規約以上のものである。

7か条を意識して書いたコードは可読性が高い
DiffMergeの例

働くコードにかかわるプログラマにとって、美しいコードは、できるだけ混乱なしに変更できるコード。
だからコードを読むプログラマがどれだけ読みやすいかにかかっている。
diff marge バッチ、コンパイラのエラーメッセージ、デバッガなどを通してもプログラマはコードを読む。


33章 「本」のためにプログラムを書く ブライアン・ヘイズ
 この世のどの図書館の棚にもない伝説の「本」そこに刻まれているのは数学の定理のこの上ない出来栄えの証明の数々。ならばプログラムやアルゴリズムの「本」をあるはず。
 ただ動くだけでなく、「本」に乗せられるようなプログラムを書きたいと思うはず。
 著者が苦闘の末、これなら「本」にのせられるのではと考えたプログラムにいきつくまでを書く

取り組んだのは計算幾何学
 最初は簡単に思えるのに詳細にわけいると本当は難題だとわかる分野
 「平面上の3点が与えられたとき、その3点が同一直線状にあるか」という問題に回答するプログラム。

Lisp関数定義の例
髪と鉛筆で問題を解くとしたら?
3点の共線性解説
あぶない傾きについて解説(3点目がその直線上にあるか)
三角形の不等性解説
「紆余曲折」・・・書く線分の交差を片っ端から調べる必要があるコードは判定の枝が1ダースもあって、不必要に複雑に見えた。交差問題を調べたりしていた、妙案をみつける。他の人も苦労しているとしって、コードを公開して意見をもとめるといっぱいよせられた。

アハ!体験
シュウチュク氏の「幾何学的頑健さに関する講義ノート」で示された共線性のアルゴリズムがピタリとはまった。
三角形の周囲の長さでなく面積を使うとというアイデア。

正しい解法を探すベストな方法は、すぐに助けを求めること。
ただやはり自分で解いてほしいけど。
成果のでないプログラムをどのくらいやればいいかはよくわからない
また、ただ動くだけでなく、美しいコードを追求するのをどこまで追求すべきかもわかない。


久野靖×まつもとゆきひろ 対談 コンピュータサイエンスをなめるな!
fjの思い出話とか、ビューティフルコードの面白さとか。



ビューティフルコード (THEORY/IN/PRACTICE)

ビューティフルコード (THEORY/IN/PRACTICE)

  • 作者: Brian Kernighan
  • 出版社/メーカー: オライリージャパン
  • 発売日: 2008/04/23
  • メディア: 大型本



タグ:Brian Kernighan
nice!(0)  コメント(0)  トラックバック(0) 
共通テーマ:

nice! 0

コメント 0

コメントを書く

お名前:
URL:
コメント:
画像認証:
下の画像に表示されている文字を入力してください。

※ブログオーナーが承認したコメントのみ表示されます。

トラックバック 0

[PR]Kindle ストア ベストセラー

この広告は前回の更新から一定期間経過したブログに表示されています。更新すると自動で解除されます。