コンピュータサイエンスの勉強計画

目標を決める

  • これを学んでどんなことが出来るようになりたいかというイメージを持つ。

方針

  • (TBD)
  • コンピュータサイエンスは、兎に角分野が多すぎる。正気の沙汰ではない。
  • しかも広くある程度深く学ぶ必要があるので、好きなものを適当に読むのではなく綿密な計画が必要になる。
  • マニアックと感じるものは学習を避け、必要と感じる勉強に取り組む。
  • 難度の高い書籍を読むために、数学や競技プログラミングなどの土台作りを怠らない。
  • 難度の高い書籍は、土台作りが一定以上ある前提において、丁寧に読むより繰り返し読むことを重視する。

教材

数学

  • 赤チャートIA/IIB/IIIC
  • やさしい理系数学
  • 線形代数入門 (斎藤正彦)
  • 解析入門 (杉浦)
  • これなら分かる応用代数
  • 群論入門
  • 統計学入門
  • いかにして問題をとくか

分散システム

  • Distributed Systems 3 (Andrew S. Tanenbaum)

言語処理系

  • TaPL
  • きつねさんでもわかるLLVM

プログラミング言語

関数型

Perl

アルゴリズム / 計算幾何学

機械学習・AI

  • 各数学の教科書
  • PRML
  • Artificial Intelligence

Linux / OS

コンピュータ構成と設計

  • パタヘネ上・下

セキュリティ

  • セキュリティコンテストチャレンジブック
  • 体系的に学ぶ安全なWebアプリケーションの作り方
  • C/C++セキュアコーディング

インフラ

  • 月刊や特集のやつ

ネットワーク

  • マスタリングTCP/IP 入門編
  • マスタリングTCP/IP 情報セキュリティ編
  • マスタリングTCP/IP ルーティング編
  • マスタリングTCP/IP IPv6
  • マスタリングTCP/IP OpenFlow編

ソフトウェア・エンジニアリング

EMC++ Chapter5

序文

用語

ムーブセマンティクス

  • コピー演算をムーブ演算に置き換え可能にする。
  • ムーブコンストラクタ、ムーブ代入演算子はオブジェクトのムーブセマンティクスを制御する。

完全転送

  • 任意の実引数を取り、他の関数へ転送する関数テンプレートの記述を可能にする。転送先関数は完全に同じ実引数を直接受け取ったかのように動作する。

rvalue reference

  • ムーブセマンティクスと完全転送を実現するための言語機能。
  • std::moveはrvalueへの無条件キャストを実行する。自身は何もムーブしない。
  • std::forwardは実引数がrvalueにバインドされている場合に限り、その実引数をrvalueへキャストする。
  • std::move, std::forwardともに、プログラム実行時には何も実行しない。

問題

  1. std::moveのサンプルの実装を示せ。
  2. 以下のプログラムはtextからvalueへ、ムーブとコピーのどちらが行われるか。その理由を答えよ。
class Annotation {
public:
  explicit Annotation(const std::string text) : value(std::move(text)) {}

private:
  std::string value;
};
  1. std::moveとstd::forwardの違いを答えよ。

解答

template<typename T>
decltype(auto) move(T&& param)
{
  using ReturnType = remove_reference_t<T>&&;
  return static_cast<ReturnType>(param);
}
  1. コピーされる。textはstd::moveによって、rvalueのconst std::stringにキャストされる。std::stringの実装は以下のようになっている。

class string {
public:
  ...
  string(const string& rhs);
  string(string&& rhs);
  ...
};

ムーブコンストラクタにはconstが付いていないため、textを渡すことは出来ない。 しかし、const lvalueのconst rvalueへのバインドは認められているため、textを渡すことが出来る。 その為、コピーコンストラクタが呼ばれる。

  1. std::moveは無条件でrvalueにキャストする。std::forwardは実引数がrvalueで初期化された場合のみ、rvalueにキャストする。

EMC++ Chapter5

序文

用語

ムーブセマンティクス

  • コピー演算をムーブ演算に置き換え可能にする。
  • ムーブコンストラクタ、ムーブ代入演算子はオブジェクトのムーブセマンティクスを制御する。

完全転送

  • 任意の実引数を取り、他の関数へ転送する関数テンプレートの記述を可能にする。転送先関数は完全に同じ実引数を直接受け取ったかのように動作する。

rvalue reference

  • ムーブセマンティクスと完全転送を実現するための言語機能。
  • std::move, std::foward はrvalueへのキャストである。

問題

  1. std::moveのサンプルの実装を示せ。
  2. 以下のプログラムはtextからvalueへ、ムーブとコピーのどちらが行われるか。その理由を答えよ。
class Annotation {
public:
  explicit Annotation(const std::string text) : value(std::move(text)) {}

private:
  std::string value;
};
  1. std::moveとstd::forwardの違いを答えよ。

解答

template<typename T>
decltype(auto) move(T&& param)
{
  using ReturnType = remove_reference_t<T>&&;
  return static_cast<ReturnType>(param);
}
  1. コピーされる。textはstd::moveによって、rvalueのconst std::stringにキャストされる。std::stringの実装は以下のようになっている。

class string {
public:
  ...
  string(const string& rhs);
  string(string&& rhs);
  ...
};

ムーブコンストラクタにはconstが付いていないため、textを渡すことは出来ない。 しかし、const lvalueのconst rvalueへのバインドは認められているため、textを渡すことが出来る。 その為、コピーコンストラクタが呼ばれる。

  1. std::moveは無条件でrvalueにキャストする。std::forwardは実引数がrvalueで初期化された場合のみ、rvalueにキャストする。

TPOP - UNIX思想 3.37〜 (WIP)

UNIX思想

UNIX設計思想の正しさ

  • UNIXは1969年に生まれて現在まで使われている。設計思想の正しさは長い実績が保証している。

モジュール化の原則

モジュールは自己完結させる

  • 理由
    • 問題の発生箇所がモジュール内に局所化できる。
  • 方法
    • 関連性の高いもののみを集める。
    • 極限までシンプルなインターフェースにする。

明確性の原則

人間にとって明確なコードはめったに壊れない

  • 複雑なコードは障害の発生箇所となる。

コードはマシンのためではなく、保守する人のために書く。

  • 保守作業は新規開発より高いコストがかかる。

- コードを解読する作業が高々1度で済むように留める。

  • 2度目の解読が発生した場合、3度目の解読を引き起こさないように改善をする。

組立部品の原則

ソフトウェアをテキスト形式のデータストリームのフィルタリングとして捉える

  • 入力と出力を意識し、ソフトウェアはどんな加工を行うか。
  • テキストストリームは、ソフトウェアを強制的に情報隠蔽する
  • 凝ったプロセス間通信は、互いに内部構造を曝け出してしまう。

入出力をテキストストリーム

  • コマンドラインから使用できる
  • 複数のソフトウェアを組み合わせて使用できる

分離の原則

メカニズムからポリシーを離す

  • ポリシーはソフトウェアの提供する機能に依存する部分。メカニズムは完結するような実装。メカニズムの例として、名前の付いたアルゴリズムの実装やエンジンなどがあたる。
  • ポリシーはソフトウェアの要件が変わることで、変更が必要になる。ポリシーとメカニズムの区別がついていないと、メカニズムに変更の必要が生じてしまうので、分離が必要。
  • ポリシーはフロントエンドやインターフェースがあたる。

単純性の原則

コードはシンプルにする

  • 技術誇示が複雑度をあげる。
  • 機能が外部から要求されることで、ソフトウェアが満たすべき本質的な要件が認められなくなる。
  • 図やドキュメントで、猿でもわかる設計思想と哲学を記述することが必要。

倹約の原則

大きなコードは書かない

  • はじめに小さなコードを書く。
  • コードを継ぎ足して大きくなったら分割する。判断基準は?1つのファイルにたくさんのコードが書いてあれば、それがそのまま悪というわけではない。SRPにもとづいて2つ以上の変更があるかどうかを基準にしてコードを分割したほうが良い。同じドメインでも、異なる2つ以上のコンポーネントが含まれていれば、分割を考えてもよい。

透明性の原則

透明性

  • ソフトウェアが外から見て何をどうするかが一瞬にして理解できるものである

開示性

  • 内部状態の監視が可能
  • 設計の初期から機能として組み込む
    • ログをやたらめったら表示するのは、コードが汚くなる
    • 変数の状態をString化するメソッドを作る

安定性の原則

コードレビュー

  • コードを書いたプログラマが内部構造を正しく説明できるようにする

特異な入力や極端に大きい入力に耐える

表現性の原則

情報はデータに寄せる

  • データ構造とロジックのどちらがか複雑になるのであれば、データ構造を複雑にする

驚き最小の原則

  • 想定通りのインターフェースにする
  • 一見似ているが微妙に異なる物を作らない
    • すでにある機能と似た名前で役割が微妙に異なるなら、命名を変える。

TPOP principle3.29 7つの設計原理

第3章

principle 3.29〜3.36 7つの設計原理

コード妥当性レビュー観点

  • 単純原理
  • 同型原理
  • 対称原理
  • 階層原理
  • 透明原理
  • 明証原理
  • 安全原理
  • 線形原理

単純原理

  • 局所的な完全性を重視する

    • ひと目で自明がいいに決まってる
  • 複雑なところにバグが出る

    • 基本的に独自のイディオムに頼らずきれいなコードを書きたい
      • マクロとか

同型原理

  • 形に拘る

    • レビューワーが一旦コードの形を捉えれば、そのノリでだいたい読めてしまうのが良い
  • 「異物」が目立つ

    • 突如違ったコーディングスタイルが入ってきたら気になる
  • 一貫性のあるコード

    • 他と同様の記法で書けるものに局所的に"ハック"しようとしても無意味
    • "ハック"の要求に狩られる場面が多ければ、別の言語を使うか、全体をライブラリ化してしまうことを検討する
      • 内部DSLとか構築する場合もある

対称原理

  • 形の対称性にこだわる
    • Aと¬Aを考えた命名規則や処理フローなど
    • 対称性は読み手に予測を促す
    • 一般的な命名の対称性を利用しよう
      • set/get
      • push/pop
      • start/stop
      • begin/end

階層原理

  • 主従関係、前後関係、本末関係などの階層関係を意識する
    • 階層的なアーキテクチャ
    • delegaterとdelegatee
    • コーディングを意味ごとの塊にまとめて、前後関係が混濁しないようにする
  • 同じ種類の処理が異なる階層を跨がないようにする
    • リソースの獲得/解放 RAIIに従う
      • vendorのライブラリの関数に生ポインタを渡した時、そのライブラリの関数内でdeleteされてしまうことはないだろうか?
    • mutexの獲得/放棄
  • 上位と下位の階層関係を明確にし、同レベルの階層に同一の処理を記述する
    • 適切な委譲をして、メソッドの責務が一言で表現する
    • 同一階層内でも、即時実行するラムダ式等を用いることで、階層関係を明らかにすることが出来る

線形原理(透過原理)

  • 処理の流れを直線的にすることを意識する(透過的にする)
    • メソッドが管理する状態を減らす
    • 反復しない
      • 上に行ったり下に行ったりすると読みにくい
      • 線形結合的なシーケンスの重ね合わせで機能を実現する
    • 制御文は処理のブランチを分けていることを意識してみる
      • 早期returnなど、ちょっとブランチ切ってもすぐにメインのブランチに復帰するから直線的な処理のフローが保たれる
      • Gitとかでマージしてないブランチがたくさんあったら管理しきれないイメージ(ほんまか)
    • switch文を使って各々個別の処理を書く行為は、同じ関数内に多くの異なるフローをもたせることになる
      • そのくらいだったら委譲、ディスパッチ、サブクラス化とかして、直線的なフローを独立して管理できるようにしたいよねという話

明証原理

  • 明証性にこだわる
    • 明証になるためなら、コメントやドキュメント、図を導入することをいとわない
    • コメントやドキュメントの作成などが面倒であるとなれば、コーディング自体を明証性のあるものにする
  • 不確実性を取りのずく
    • トリッキーなコードに注意

安全原理

(WIP)

TPOP principle 3.64 UNIX哲学9 - フィルタ化

第3章

principle 3.64 UNIX哲学9 - フィルタ化

ソフトウェアはフィルタである

  • データを生成するのは人間
  • データにフィルタをかけて別の出力を表示するのがコンピュータ
  • 故に、まず入力ストリームと出力ストリームに着目し、そのフィルタリングとして設計を考えればよい
  • UNIXではstdin, stdout, stderrをインターフェースとしてソフトウェア同士をコネクタブルにしている

UNIX哲学・小定理

  • 環境カスタマイズ

    • 最初の学習コストが高くても、ある程度学べばユーザがチューニングできるようになる方が長く使われるソフトウェアになる
  • 軽薄短小カーネル

    • カーネルにアプリケーションを組み込んだら、そのアプリケーションを保守する人がいなくなる
  • 小文字使用

    • 小文字で短く、目に優しくする
    • ソート時に大文字が目立つ
  • 森林保護

    • ドキュメントは電子化されていなければフィルタリング出来ない
  • 沈黙は金

    • 必要な情報が無駄な情報に埋もれてはならない
    • エラーなどには基本的に沈黙し、成功したときだけ有益な出力を返す
  • 並列思考

  • 部品コラボレーション
  • 90パーセント解

    • 90パーセントを効率的に処理することを保証し、10パーセントはユーザに任せる
    • 10パーセントの、時間のかかる処理や、プログラミングしにくい処理を故意に無視する
  • 劣るが勝る

    • 単一の巨大なソフトウェアよりも、小さい劣ったソフトウェアの最大公約数で勝負する
  • 階層指向

    • 階層構造アーキテクチャ
    • 各々の階層構造で成功実績を収める
      • プロセスツリー
      • Xウィンドウシステム
      • ネットワークサービス

TPOP principle 4.5 コードの臭い

第4章 視点

principle 4.5 コードの臭い Bad smell in code.

言葉の復習

  • 設計とは何か。
    • principle 1.2 コードは設計書
    • 「基本設計」「詳細設計」「プログラミング」「テスト」「デバッグ」全てを「設計」と呼び、「コード」は設計書、「リリースビルド」が製造である。

臭いの傾向

よく見る
  • 状態
    • そっくりのコードがあちこちに存在する
  • 改善策
    • 重複したコードを一つにまとめる
長過ぎる
  • 状態
    • 「この関数でやっていることはAである」と一言で言えない
  • 改善策
    • 関数を分割して、関数の責務を一言で表現できるようにする
大きすぎる
  • 状態
    • モジュールの責務が大きい
    • モジュールの修正の機会が多い
    • 時間経過に連れ、モジュールの規模が増加し続ける
  • 改善策
    • 分割して、モジュールの責務を一言で表現できるようにする
多すぎる
  • 状態
    • モジュールの数が多すぎて、依存関係、処理の流れを追うことが出来ない
  • 改善策
    • 仲介役の削除、統廃合によりモジュールの数を減らす
名前が合わない
  • 状態
    • 名前と実際のコードの内容が合わない
  • 改善策
    • 表現したい概念と合っていなければ、直ちに適切な名前に修正する
    • 以前正しかった名前でも、改修によって正しくなくなることがあるので、その時点で名前も修正する