プログラミング原論
価格:3,080円 (消費税:280円)
ISBN978-4-501-55370-8 C3004
奥付の初版発行年月:2015年11月 / 発売日:2015年11月上旬
プログラミング言語で実装されたアルゴリズムが、最も汎用的な数学を用いて定義できることを説いた書。経験豊富な著者たちが何年間も教えてきた、プログラミングの本質に対する「極意」を学べる。
この本は,プログラムに抽象的数学理論を関連付けることで,演繹的方法をプログラミングに応用するものです。抽象的数学理論により,プラグラムが目的通りに動作するようになります。それらの理論の詳細,理論の観点から記述されたアルゴリズムおよびアルゴリズムの特性を記述する定理(theorem)と補題(lemma)を一緒に示します。実際のプログラミング言語によるアルゴリズムの実装が,この本の重要な部分です。人間のための仕様は,厳密でありながらも形式張らないようにすべきですが,コンピュータに対するコードは,どのようなものであっても絶対に正確でなければなりません。
化学やエンジニアリングのほかの領域と同様に,プログラミングの基盤は演繹的方法なのです。演繹的方法は,複雑なシステムを数学的に記述された振る舞いを持つ要素に分解することを容易にします。このことは,効率的で,信頼性が高く,堅牢で,無駄のないソフトウェアを設計するための必要な前提条件です。
この本はプログラミングを深く理解したい人々向けに書きました。フルタイムでのソフトウェア開発者であるか,専門的活動の重要な部分にプログラミングを利用している科学者とエンジニアであるかは関係ありません。
この本は,最初から順に読んでください。コードを読み,補題を証明し,演習を行うことで,題材を理解することができます。さらに様々な課題を提示していますが,そのいくつかは結論が出ないものです。この本は簡潔明瞭なので,注意深い人は各章と題材を選択した理由の関連にいずれ気付くことでしょう。この本の構成の原則を発見することを,みなさんの目標にしてください。
みなさんが,初頭代数演算を知っていることを前提としています。離散数学にかんする大学の講義レベルの論理と集合の理論に関する基本用語も理解していることを前提としています。使用する表記は,付録Aにまとめてあります。アルゴリズムを記述するために必要な抽象代数学のいくつかの概念の定義も示します。プログラミングに慣れていて,コンピュータ・アーキテクチャと基本的なアルゴリズムとデータ構造を理解していることを前提としています。
この本では,C++を選択しました。その理由は,C++は強力な抽象化機構を利用でき,またハードウェアの忠実な表現が可能だからです。この本では,C++ 言語のサブセットを使います。また,必要条件をコメントとして記述しています。C++言語にまだ慣れ親しんでいない人も,この本の内容を理解できるよう配慮しました。付録Bに,この本で使用しているC++のサブセットを記述しています。数学的記法とC++間に相違がある場合には,使用しているコンセプトとプラグラムに対応するものがSTL(C++Standard Template Library)にありますが,この本では,STLにおける設計上の決定のいくつかと異なっています。また,この本は,STLなどのような本物のライブラリが対応しなければならない,名前空間,可視性,インライン指定といった問題も無視しています。
第1章は,値(Value),オブジェクト(object),型(type),手続き(procedure),および,コンセプト(concept)を説明しています。第2章から第5章までは,半群(semigroup)や全順序集合(totally ordered set)などの代数構造に対するアルゴリズムを説明します。第6章から第11章までは,メモリの抽象化に関するアルゴリズムを説明します。第12章は,他のオブジェクトとを包含するオブジェクトを説明します。あとがきでは,この本で示したやり方に関する著者らの振返りを述べています。
日本語版の読書者へ
私達は,日本語版の読者向けにまえがきを書く機会を提供してくれた出版社および訳者の柴田芳樹氏に深く感謝しています。
この本の精神は,日本の美学にあります。この本は,必要最低限の数の言葉で,できる限り多くを説明しようとしています。古くからの俳句のように17語まで減らすことはできませんが,俳句が少ない語数で表現することに影響を受けました。この本は,あまり厚くはありません。実際,無駄な厚みが全くないことを願っています。私達は,すべての言葉が意味を持つように努めました。
故障しない自動車や修理を全く必要としないテレビでもって,日本のエンジニアが世界を変え始めた頃に,私達は大人になりました。私達の望みは,ソフトウェアに対する私達の取り組みによって,自動車やテレビと同じように頑強なものを,プログラマが作り出すことを可能にすることです。日本のエンジニアのおかげで,一般の人々が自動車に関する機械知識を持っている必要がなく,自動車は常に走ると想定できるようになってもらいたいと思っています。そうすれば,ソフトウェアは,直感的で芸術家肌のプログラマではなく,有能なプログラマによって生み出されるようになるでしょう。
この本は,出発点に過ぎません。ソフトウェア開発を工業化するための努力のほとんどは,これからの未来に行われます。この本の読者の方々が,その未来をより現実的にしてくれることを望んでいます。
訳者である柴田芳樹氏には,注意深い翻訳だけでなく,誤りを見つけてくれたことにも感謝します。
Paul McJones,Alexander Stepanov
米国,カリフォルニア州
2015年8月
目次
第1章 基礎
1.1 分類学の概念:実体,種,属
1.2 値
1.3 オブジェクト
1.4 手続き
1.5 正則型
1.6 正則手続き
1.7 コンセプト
1.8 結論
第2章 変換と軌道
2.1 変換
2.2 軌道
2.3 衝突点
2.4 軌道サイズの測定
2.5 アクション
2.6 結論
第3章 結合演算
3.1 結合規則
3.2 べき乗計算
3.3 プログラム変換
3.4 特別ケースの手続き
3.5 アルゴリズムのパラメータ化
3.6 線形回帰
3.7 累積手続き
3.8 結論
第4章 線形順序
4.1 関係の分類
4.2 全順序と弱順序
4.3 順序選択
4.4 自然な全順序
4.5 派生手続きの一群
4.6 順序選択手続きの拡張
4.7 結論
第5章 順序代数構造
5.1 基礎代数構造
5.2 順序代数構造
5.3 剰余
5.4 最大公約数
5.5 gcdの一般化
5.6 Steinのgcd
5.7 商
5.8 負数の商と剰余
5.9 コンセプトとそのモデル
5.10 コンピュータの整数型
5.11 結論
第6章 イテレータ
6.1 読み込み可能性
6.2 イテレータ
6.3 区間
6.4 読み込み可能区間
6.5 区間の増加
6.6 前方イテレータ
6.7 インデックス付きイテレータ
6.8 双方向イテレータ
6.9 ランダムアクセス・イテレータ
6.10 結論
第7章 座標構造
7.1 分岐座標
7.2 双方向分岐座標
7.3 座標構造
7.4 同型,同値,順序
7.5 結論
第8章 可変サクセサーを持つ座標
8.1 リンクイテレータ
8.2 リンク再配列
8.3 リンク再配列の適用
8.4 リンク分岐座標
8.5 結論
第9章 コピー
9.1 書き込み可能性
9.2 位置ベースコピー
9.3 述語ベースコピー
9.4 区間交換
9.5 結論
第10章 再配列
10.1 置換
10.2 再配列
10.3 逆順アルゴリズム
10.4 回転アルゴリズム
10.5 アルゴリズム選択
10.6 結論
第11章 分割とマージ
11.1 分割
11.2 バランスした簡約
11.3 マージ
11.4 結論
第12章 複合オブジェクト
12.1 単純な複合オブジェクト
12.2 動的シーケンス
12.3 実際の型
12.4 結論
あとがき
付録A 数学的表記
付録B プログラミング言語
B.1 言語定義
B.2 マクロとトレイト構造体
参考文献
訳者あとがき
索引