「コンピュータ・プログラミングの概念・技法・モデル」を読み始めてから読み終わるまで
二年前の夏くらいに読み始めて、ちょくちょくと読み進めていた「コンピュータ・プログラミングの概念・技法・モデル」という本をひと通り読み終えました。まあ読んだと言っても章末の練習問題は途中からやっていないので、おおよそ重要なことは一通り頭に入れた、という感じでしょうか。章によりますが大体２〜４回くらい読みました。
この本はちょうど自分がコンピュータ・サイエンスを学び始めたときから読み始めた本なので、過程をまとめることでこれまでどういうことを考えて何を学び、他にどういうことが足りていないか、というようなことを整理してみたいと思います。
各章まとめ
読んだことを整理するために書いた各章ごとのまとめ。
- 序文：プログラミングを学ぶにあたって - 2011-01-01
- CTMCP 1章：プログラミング概念入門 - 2011-01-04
- CTMCP 2章：宣言的計算モデル - 2011-07-20
- CTMCP 3章：宣言的プログラミング技法 - 2011-08-04
- CTMCP 4章：宣言的並行性 - 2012-03-18
- CTMCP 5章：メッセージ伝達並行性 - 2012-03-22
- CTMCP 6章：明示的状態 - 2012-03-22
- CTMCP 7章：オブジェクト指向プログラミング - 2012-05-15
- CTMCP 8章：状態共有並行性 - 2012-10-21
- CTMCP 9章：関係プログラミング - 2012-10-21
- CTMCP 11章：分散プログラミング -2012-10-21
- CTMCP 12章：制約プログラミング - 2012-10-23
きっかけと動機
大学一年の夏休みに「情報工学科に入ったわけだしコンピュータ・サイエンスのちゃんとした本を一冊読みたいなー」と思っていたところ、サークルのOBで当時なぜか部室に常駐していたdraftcodeさんからこの本を紹介してもらいました。ただこの当時はプログラミング経験やコンピュータ・サイエンス関係の基礎知識がほとんどなかったので、前提となる部分も一緒に読み解かなければならず、頁数としてはあまり捗りませんでした。
そういう状態でも無理矢理読み進めたのは、特定のプログラミング言語の「仕様」の上にプログラミングを覚えてしまえば、そういう先入観で考えるようになってしまう（そういう先入観は取り去るのが難しい）という予感があったからでした。ちなみに現時点では、これは半分正しくて半分間違っている、と思っています。そういう入り方をした場合でも多くの異なる言語に触れていけばおそらくだんだんと本質的な違いが整理されてくる。それに対してこの本はそういう本質を最初から扱ってそれに基いてプログラミングを教える本で、自分はそうしたいし、そうすることでより歪みなく本質的な理解をしたいと思ったのでした。
どういう本？
この本は深いところに裏付けされて書いてある本なのでどのくらいのものが得られるかというのは読み込み次第で、自分も折に触れて関係する部分を読み返したいと思っているのですが、扱っていることは題の通りプログラミングです。プログラミングが次の３つに別れるとして、
- 概念と技法
- アルゴリズムとデータ構造
- プログラム設計とソフトウェアエンジニアリング
このうちの1.を徹底的に扱い、2.と3.は入門程度に扱います。そして1.と3.は強い相互関係がある（と序文で言っています）。例えば「合成可能」あるいは「合成可能なコンポーネント」という概念と合成可能なコンポーネントを性能良く実現するための技法（e.g. メモ化）は、疎結合なプログラムを設計するにあたって必要な概念と技法です。自分の印象ですが、一般的にプログラミング言語にどういう機能があってどういう技法が可能というのを解説するプログラミング入門書は多くありますが、それと同時により大きな立場（つまり3.の観点）でどうすべきかということが説明されることはあまりないように思います。対してこの本は1.と3.を並行的に教えているので、3.についても比較的しっかりとした土台ができるように感じました。例えば、ソフトウェア・エンジニアリングの古典である「人月の神話」と言った本を読んでも（それほど開発経験はなくても）すんなりと納得できました。一方で、アルゴリズムとデータ構造については基本的なところは抑えてはいますが、まだまだ足りないと感じています。どうしよう。
これから
やってみると誰でも普通にわかることですが、コンピューティング、情報システムといった、情報を対象としたエンジニアリング、あるいはコンピュータを使ったエンジニアリングというのは別にプログラミングだけから構成されているわけではなく、その意味でこの本は一部に過ぎません。まずハードウェアがないとプログラミングはできませんし、プログラミングする対象についての知識があって的確に問題設定ができないとそもそもプログラミングしても意味が無い。あとはプラットフォーム（OS,ブラウザ, 言語処理系）とか環境（ライブラリ, コミュニティ, 人）とか解決手法とか自然言語とか。たぶんまだまだ見えてないものがあるはず。
そもそも自分がなにをしたいのかというのはまだ特に定まっていないのですが、日常を楽に（あるいは楽しく）するための手段としてコンピューティングは対象が広くて面白いと思いますし、何か思い立ったときに自分でできるようにしておきたいと思っています。ずいぶん抽象的な話になってしまったので具体的な話に戻すと、僕は、Ozから始めてRubyに至るまで抽象度の高いレイヤーにいることが多く、低レイヤーな部分を正確に理解していないなあと感じているので、とりあえず次はOSについて勉強してみようかなあとかなんとなく思ってます。
CTMCP 12章：制約プログラミング
第二部の最終章。制約プログラミング。
要点
制約プログラミング自体は、何らかの論理的な制約(constarint)を満たす解を求める技法の集合である。制約プログラミングでは解を求めるにあたって、力ずくの探索を可能な限り避けて…（つづき）
感想
計算空間という概念が出てきました。一種の内部にスレッドを持つ状態オブジェクトなのですが、抽象化が良くて、並行性や明示的状態を上手く使って「探索戦略」、「分配戦略」、「制約（解きたい問題）」などを上手に分離していました。あとはこの制約プログラミング自体は非常に強力だなと思ったのですが、現実の問題の場合それを定式化された制約に落とし込む所が難所になりそうだと思いました。冒頭に書いてますが、これは一般的に使う計算モデルというよりは特定の問題領域に適用する手法という感じですね。
第二部はこれで終わりです。残りは 第三部：意味 で一つだけ章があって、これまでのモデルを踏まえて一般的計算モデルとして形式的な意味を与え直すという内容。それを読んで終わりかな。
CTMCP 8章：状態共有並行性
しばらく積み残していた八章以降を消化してしまおうと思います。状態共有並行性です。
関係ないですが書き物は軽量マークアップ言語がいいだろうということでemacsのorg-modeを使っていたのですが、コードの断片を埋め込めるのと記号の選び方が良くてプレーンテキストでも見やすいのでmarkdownを最近は使っています。あとはgithubに上げれば綺麗に見れますしね。
要点
状態共有並行モデルは、宣言的並行モデルに値可変変数であるセルを追加した計算モデルものである。一方、前章：メッセージ伝達並行性では、宣言的並行モデルに同じく値可変変数の一種であるポートを追加した。値可変変数を使っているのでこれらをまとめて状態あり並行モデルと言うことができるが、実際には双方のプログラミングスタイルは全く異なる...（つづき）
感想
今までバラバラだった並行キュー、ロック、モニタ、トランザクションといった原子的アクションの関係が見えたのが良かった。トランザクションはデータベースでしか出てこないイメージを持っていたけど、永続性を除外した軽量トランザクションを汎用プログラミングでフォールトトレラントのために使えるというのはなるほどと思う。すごく欲しいと思ったし、実際「うまい形で言語モデルに取り込むべき」みたいなことが書いてあった。最後の方にあったトランザクションの実装の節は、あまりに簡潔すぎて（あるいは理解が足りないのか）ちょっと理解できない部分があったけど保留にしておいた。どうせこの辺りは手を入れるときは確実に本一冊は読まないといけない分野だろう。
CTMCP 11章：分散プログラミング
第十一章：分散プログラミングです。Oz はネットワーク透過なプログラミングを可能にするとかなんとかで、そういうの得意っぽいです。ちょっとすごいです。
感想
ネットワーク（プロセス）間の通信というのはライブラリのレイヤーで明示的に提供されるのが普通だと思うのですが、Oz は言語として分散プログラミングを組み込んでいて、オブジェクトや関数が別プロセスにあろうと別マシンにあろうと言語意味上は変わらない（性能は変わりうる）、ということを実現しています。「ネットワーク透過」というのはネットワークを意識せずに済むというそのままの意味で、そういう理想的な状態をまず考えて可能な限りそれに近づける、というアプローチを取っています。
Smalltailkのなんかの実装（？）は分散オブジェクトを実装しているらしいですが、ここまでできるのかは分からないです。Rubyでも簡単なクロージャ（Procオブジェクト）を送れたらなーと思うことは非同期処理をしたいときに時々思うのですが、こういうのがあるとすごい素直にやれますね（実装はとても大変でしょうけど）。今は文字列やJSONみたいな静的データしかキューイングできなかったり、gem だと delayed_job みたいにメソッド名と引数を文字列としてキューイングしておいて、処理側プロセスは同じコードをロードして同じ環境を立ち上げて（たぶんそうしてるんだろう）処理するみたいな、相互に何らかの「お約束」をしておく必要があってちょっとめんどくさいですね。
CTMCP 9章：関係プログラミング
第一部：一般的計算モデル の最終章、関係計算モデルです。論理型プログラミングを扱います。ちなみに第二部は特殊化された（Specialized）計算モデルで、GUIプログラミング、分散プログラミング、及び制約プログラミングを扱います。GUIプログラミングはあまり得るものがなさそうなので飛ばす予定。
要点
第一部：一般的計算モデルの最終章。この章では、これまで扱ってきた宣言的モデルの関数（一章〜四章など）という見方を一般化して関係に基づいた計算モデルを考える...（つづき）
感想
この章はすごいと思いました。ここまで来てようやく、どうしてデータフロー変数（まだ束縛されていない変数）などといったものが必要なのか、どうして手続きを使うのか、といった言語設計上の選択の全体的な理由が見えます（念の為に言うと、それまでにもちゃんと説明はありました）。関数的手続きを一般化すると関係的手続きになる、入力と出力を逆転させても解が出るというのは、実用上の制約はあるとはいえ、アイデアとしてすごい面白いですし、逆にそれまでのモデルがどういう実装上の制約に基づいているのかが分かります。非決定性選択と単一化であいまい性のある文法をさくっと解析するのも良かったです。
CTMCP 7章：オブジェクト指向プログラミング
明示的状態を導入した計算モデルの上に構築された抽象とその利用について。特に、その意味定義・抽象の設計上の決断と他の計算モデルとの関係、使い方に関する注意、など。
要点
前章で、明示的状態を導入することで増大する複雑さは、データ抽象によるカプセル化で抑制するのがよいということを見た。データ抽象の中でも値とその操作が一緒になったオブジェクトというスタイルを利用する。これによって、多態性が得られる。さらに、オブジェクト指向プログラミングは、継承という概念を付加することで漸増的な構築を可能にする。
継承は、威力は大きいがかなり注意して使う必要がある概念である。共通の部分を括り出す可能性は増大するが、同時に、あるインターフェースの実装がプログラムの至る所にばら撒かれる。また、オブジェクトを理解するに際してその祖先も一緒に考えなければいけなくなり、プログラムの理解や設計の維持、デバッグが困難になることがある。
オブジェクト指向プログラミングの追加したものは、計算モデル上のものではない。クラスは、ある値と操作のセットをラッピングした値を返す関数として、継承はクラスを入力としてクラスを出力する関数として考えられる。よって、高階プログラミングの一種である。オブジェクト指向プログラミングの追加したものは、どちらかと言えば、その抽象をどう設計し構文に組み込むか、という装飾にある（あくまで計算モデルの立場からの見方であり、実装は最適化を考慮する）。
継承の見方は２通りあり、一つは型と見る見方、もうひとつは構造と見る見方である。ほとんどの場合において、型と見るべきである。これは、クラスは代替性（substitution property）を満たすべき、ということを含む。Aを継承したクラスBが代替性を満たすということは、Aに対して使える操作がBに対しても行え、その基本的な表明を満たすことである。
感想
明示的状態を素直に使ったいわゆる手続き型のプログラミングと、オブジェクト指向のプログラミングの間に感じていたジャンプを解消できたのが良かった。手続き型にオブジェクト指向を追加する例としてCからJavaみたいなのを想定してしまうと、単純な装飾という以上に、1) 第一級の関数の追加、2) 名前値などによるセキュリティ機構の追加 というもっと根本的なレベルでの変化が混ざっていて、そこがジャンプを感じる原因だったと思う。
Ozは動的な言語で、クラスもオブジェクトに対するメッセージ（メソッド呼び出し）も第一級なので、リフレクションや委任（delegation）などが自然に実装できる。ここで構築したオブジェクト指向システムは、広く使われている言語で言うとRubyに近い、と思う。C++, Javaなどのコンパイルを行う静的型付け言語が第一級のメッセージをサポートしてなかったり（C++）、多態性に制限があったりするのが性能やプログラムの保証上の理由であることを考えると、オブジェクト指向を純粋に理解するという観点からは動的で制限のない言語の方がいいのかなとか。
