CTMCP 6章：明示的状態
明示的状態の導入とそれに伴う色々。
要点
システム構築の原則
システム構築の原則は抽象化である。抽象化を行うということは、仕様と実装を分けて考えるということである。仕様に意識を集中できることで、それを元にさらに複雑なものを構築したりすることができるようになる。システムを、中心に向かう層の連なりとして構築できるようにするということである。
システムの構成要素がコンポーネントである。状態を導入することで、コンポーネントは「記憶」を持てるようになる。コンポーネントに「知識」を注入できる、とも言える。そのできることが全て「引数」として外部化されていた宣言的モデルにおけるコンポーネントとは違い、状態をもつコンポーネントは「成長」させることができる。
既に見たとおり、宣言的モデルに並行性を持たせることでも、ある側面から見た「記憶」を持たせることができるようになる。ストリームオブジェクト、ポートオブジェクトがそれである。並行性による状態の実現は、明示的状態を導入するのと違い、プログラムの各部分が全順序の依存関係を持たないという利点がある。別の見方をすれば、明示的状態は、並行性を導入することなく、コンポーネントに「記憶」を持たせることができるようになる、とも言える。
明示的状態（explicit state）
まず、状態を次のように改めて定義する。計算の入出力のみではなくその途中に注目していることに注意。
状態（state）とは、必要とされる途中の計算結果を含む、値の時系列である。明示的状態を導入する動機は既に述べたとおり。計算モデルに値可変格納域という新たな格納域を追加する。
これは「コンテナ」、「代入」という概念を導入することであり、これによって、値が時系列化し、「状態」が表面化する。（抽象的な立場を貫くのであれば、明示的状態とは、ある「識別子」が指し示す「値」が、別の「値」に付け替えられる、ということであり、「値」自体が変化するということではない。）
データ抽象の必要性
状態を導入するということは、プログラムの各部分が、別の部分から見える状態を自由に変更できるようにプログラム可能になるということである。このようなプログラムは非常に推論しにくい。であるから、状態はカプセル化と一緒に使うのが有効である。こうすることで、独立に推論することが可能になる。
カプセル化を行う、ということは、手続きをデータと一緒に使う、ということに他ならない。データという抽象的な型と、それに対する操作を知れば十分になる。この有用な形の発展として、オブジェクト指向プログラミングが現れる。
本章の計算モデルの限界について
本章の計算モデル（オブジェクト指向プログラミング含む）は直列であるため、現実の並行性をうまくモデル化できない。そういうものの解決として一つには前章で見たメッセージ伝達並行モデルがある。のちに、これとは別の、状態共有並行モデルを見る。
感想
宣言的モデルに、なぜ明示的状態を導入する必要があるのか。明示的状態がなぜオブジェクト指向に導かれるのか。
関数型やオブジェクト指向の良い部分の独立した説明はたくさんあれど、その他の計算モデルとの対比や、あるモデルが別のモデルを取り入れる動機の説明ってなかなかなくて、それがこの本に書かれていて良かった。なのでその点を重点的にまとめてみた。実際の中身としては、上のような抽象的な話にとどまらず、大規模なシステムの設計に際してのコンポーネントの扱いから依存性の情報の扱い、開発の進め方、とかまで話が及んでいて、読み応えある。
あと面白いと思ったのが、宣言的モデルの上で可能な技法をすでに一通り見てるから、明示的状態を導入したというだけでは、それほど本質的に説明すべきものがないという点。技法の基礎を説明するシンプルなプログラミング言語としてしばしば明示的状態を持つCが想定される（ようなイメージがある）けれど、実はその多くはもっと単純な計算モデルの上でも成り立つものだ、という勝手な理解を得た。
演習問題
つまみ食いになってきてる。
https://github.com/Altech/ctmcp-answers/
CTMCP 5章：メッセージ伝達並行性
Declaretive Concurrencyに続きまして、Message-Passing Concurrencyになります。明示的状態を制限された形で並行性に持ち込みます。スレッドスケジューリングの非決定性が現出します。
要点
前章で定義した宣言的並行性は、並行でありながら実行結果が決定性という、非常に単純で扱いやすいモデルだった。反面、観測可能な非決定性が扱えなかった。例えば、いくつかのオブジェクト（クライアント）があるオブジェクト（サーバー）と適当に通信するというようなことができなかった。そういうものを扱えるようにモデルを拡張したい。非決定性を扱えて、なおかつそれほど複雑でない形で。そこで、非同期通信チャンネル（ポート）という概念を持ち込む。これにより、個々のオブジェクトの実装は宣言的に行うことができ、オブジェクト間のやりとりにのみ非決定性が現れる。具体的には、対応する二つの文を核言語に追加し、モデルを拡張する。
S={NewPort P}でポートPを定義する。Pは一意の名前を持ち、そのポートに対応する。ポートに送られてくるメッセージの列がストリームSになる。{Send P X}でポートPに対して、Xを送る。送ったXはストリームSの末尾に追加される。ポートは、内部的にストリームの末尾への参照を持っている。Send操作で新たに値が送られてくる度に、参照を更新する。つまり、参照は明示的状態である。データフロー変数の使う単一代入格納域のほかに、値可変(mutable)格納域を追加することで実行モデルを拡張する。
こういう操作を追加すれば、オブジェクト間のやりとりで明らかに非決定性が現れる。ある二つのオブジェクトが、ポートにメッセージを投げるとして、その順序はスレッドスケジューリングの非決定性を受ける。結果として、ポートに対応するストリームにはどういう順序でメッセージが現れるかは分からない。
とはいえ、個々のオブジェクトの実装・推論は宣言的並行性と変わらない。ある入力ストリームがあり、それに適切な処理をする。変わるのは、オブジェクト間の協働である。どういう順序でメッセージがやりとりされるか？そのときのオブジェクトの状態はどういうのがありうるか？
本章では、モデルを拡張したのち、並行コンポーネントが統制された形でやりとりするための決まり（プロトコル）を、RMI（遠隔メソッド起動）を例に説明する。そして、並行コンポーネントの集まりとしてシステムを設計・実装するためのモデル・手法を説明し、例としてエレベータの制御システムを見る。また、メッセージ伝達並行性に基づいた例としてErlangを見る。
感想
話の流れとしては前章からの続きだけど、状態を共有しない複数の状態ありコンポーネント間のやりとり一般に適用できる話だったので、面白かった。分散システムでのプログラミング（11章）につながっていく。
あと、最後の論理型プログラミングで使われる非決定性並行モデルの説明がよくわからなかった。サーバー参照を埋め込めないとかいうあたり。日本の第五世代コンピュータの主要計算モデルだったとか書いてあるけど。
演習問題
この章はなんだか重い問題が多い感じがして、軽く解けそうなのしか解いてない。
https://github.com/Altech/ctmcp-answers
非決定性について少し
昨日のCTMCP 4章：宣言的並行性について整理しきれてないところがあったので補足。
非決定性と明示的状態
明示的状態を持つ、ということと非決定性である、というのが別々の概念なんだけど関連していて少しややこしいので整理。
非決定性、というのは現実の色々なところに存在している。突き詰めると物理学の世界になるんだと思うけれどプログラマ的にはそれは興味ないので置いておきたい。そこで、プログラムのコードから見て予測不可能なことがあることが、観測可能な非決定性が存在する、ということの定義だとする。
そうすると、例えば外から来る情報というのは非決定性だ。乱数なんかも非決定性だ。ただ、例え入力が非決定的だとしても、その要素をコンポーネントの入力（引数）と考えるのであれば、それぞれの引数の場合について、そのコンポーネントは決定性であるということは言える（観測に基づいて考える）。ここまでは直列モデルでも現れる話。
並行モデルだとどうか。並行性というのをプログラムの意味に導入するということは、スレッドのスケジューリングを導入するということだ。スレッドのスケジューリングは様々な要素に左右される非決定的なものである（少なくとも、プログラムのコードからは分からない）。直列モデルにはない非決定性が現れる。この非決定性はプログラムの入力として捨象するということはできない（もしそういうことをするのなら、それは直列モデルの中で並列モデルでやりたいことをシュミレートしているに過ぎず、結局、並列モデルで得られる抽象化は得られない）。
こういう並列モデルに本質的に付き纏う非決定性を、データフロー変数を使うことで「見えなく」できるというのがこの章のモデルである。そして、データフロー変数というのは束縛されているとしたら一つの値であるという意味でimmutable（不変）な変数であり、明示的な状態であるmutable（可変）な変数に対応する。だから、明示的状態を持ち込むということが即、観測可能な非決定性につながるというわけではなく（ただ宣言的ではなくなるが）、並行性を前提とした場合にはそうであるという話。本書は章立てから既に分かるとおり並行性を前提としているので、その辺の言及が少なくて少し混乱した、かもしれない。
CTMCP 4章：宣言的並行性
前章から半年以上経ってしまったけど。「コンピュータプログラミングの概念・技法・モデル」という本を読んだ記録です。
途中事故があって内容飛んだけどまとめることで頭整理するみたいな目的はとりえあず果たしたのでそのままにしてる。いつか再読したら書き足すかも。
要点
並行性の導入
二章で、宣言的な計算モデルというものを考え、ひとつの言語を定義した。三章で、その中で出来ることを見た。ここで言う宣言的とは、ざっくり言えば、いつ呼ばれても同じ結果を返すということであり、宣言的モデルとは言語（モデル）としてそれが保証されているものである。「宣言的」ということの意味について詳しくは宣言的(declarative)であるとはを参照。
さて、これまで定義したモデルは直列であった。そのモデルの中では自然に書けないような問題が存在する。「独立に実行するアクティビティの集合」として表されるようなものである。そこで、宣言的であるという特徴をそのままに、宣言的モデルを拡張したい。すなわち、並行性（Concurrency）を付加する。具体的には、thread
これをthread文を使って以下のようにできる。
declare A B C
B=1
C=2
A=B+C
三つのスレッドが生成され、それらが適当な順序で実行される。三つめの文は、BとCが束縛されるまで加算ができない（ブロックする）ので、一つめまたは二つめが実行され、そののち三つめが実行され、最終的にAは3に束縛される。これをデータフロー実行という。
declare A B C
thread B=1 end
thread C=2 end
thread A=B+C end
このように任意の部分をスレッド化して実行しても、常に結果は変わらない。これを「観測可能な非決定性が存在しない」という。これはデータフロー変数の、一つの値にしか束縛されないという特徴に依っている。値可変(mutable)変数をデフォルトとする言語では、それぞれのスレッドの実行タイミングによって結果が変わってくるので、このようなことは保証されない。
並行性を使う
ToDo（ストリームを入出力するオブジェクトを抽象として使う）
実行順序を再考する
ToDo（性急実行であるという前提を見直して、遅延実行を見る）
実際の言語との対応
ToDo（部分値／完全値、性急／遅延、直列／並列の切り口で）
宣言的プログラムの限界
宣言的なコンポーネントは、独立に構築し、デバッグすることができるので、システム構築を簡単にする。こういう利点をどこまで持っていくことができるか？
結論から言えば、どこかで明示的状態を導入しなければならない。その理由は、
- 効率が悪い…現実のコンピュータは値を新たに生成するよりもその場で修正することに最適化されている
- 自然なプログラムを書くという観点から、(i) モジュラ性がない (ii) 非決定性がどうしても必要になる (iii) IOなど現実とのインターフェースで問題が起こる。
モジュラ性について。あるプログラムが変更に関してモジュラである、とは別の部分を変更することなしにその変更を行うことができる、ということである。例えば、あるコンポーネントにその呼ばれた回数を記憶できるようにしたい。明示的状態があればコンポーネント内部に変更を施すだけで済むが、宣言的コンポーネントは状態を持てないのでその回数を常に受け渡してやる必要がある。コンポーネントが遠くでも使用されていれば、変更は全域に及ぶかもしれない。
非決定性について。定義した宣言的並行モデルでは、例えば一つのサーバと二つ以上のクライアントがランダムに通信するようなプログラムを書くことができない。サーバーの入力ストリームは、片方の出力ストリームしか束縛することができない。サーバーを二つに分けても、マージする段階で同じ問題が起きる。観測可能な非決定性が扱えないことによるものである。
複数のモデルを使う
宣言的モデルは単純だが、プログラムが複雑になることがある。明示的な状態のあるモデルは複雑だが、表現力が増す分プログラムは簡潔になることがある。
モデルが複雑だと、推論が難しくなる。例えば、明示的状態を導入すると非決定性が現れ、推論が難しくなる。ではどういうモデルを使うべきか？その問題を解くのに自然なプログラムを記述できる中で最小の表現力を持つモデルを使うべきである（表現力最小原則）。
この考えに拠れば、問題の部分部分によって適切なモデルが異なるということがありうる。表現力が大きいモデルの中で、より小さいモデルを使うことは自然である。例えば、明示的状態の中で宣言的コンポーネントを使える。ほとんどの場合、適切な抽象を使うことで、あるモデルの中で別のモデルを使うことができる。これをインピーダンスマッチングという。例えば、シリアライザを使うことで、並行モデルの中で直列モデルを使える。
感想
並行性を導入する、というと相互に通信するような実体の集まりを最初に想像するけど、この章はそういう内容ではなかった（それは次の章）。この章の内容は、プログラムの実行を宣言的なまま別スレッドに分けられるよーということで、さらに一般化して、そもそも実行順序とは？みたいな話に踏み込んでいった。遅延評価って時々出てくる「おまけ」みたいなイメージがあったのだけど、宣言的な枠組みで見れば性急実行に対極する一つの考え方だった。
あと、そもそもモデルってなんだしみたいな漠然とした思いがあったのだけど、章末でモデル間にトレード・オフがあること、異なるモデルを組み合わせることができる（ゆえに複数のモデルを学ぶことに意味があること）が明快に説明されているのが気持よかった。
演習問題
解いたのでここに上げた。 https://github.com/Altech/ctmcp-answers
補足
書いた→非決定性について少し
実用期を迎えた関数プログラミング
というフォーラムをRubyのメーリスを眺めてたら見かけたので、ちょっと行ってきた。最初にOCamlベースで関数プログラミングの説明が90分ほどあって、そのあと1.HaskellのWebアプリケーションフレームワークYesodの説明（に見せかけたHaskellの説明）、2.Scalaの採用事例特集、3.仕様記述言語における関数型 4.議論 みたいな感じだった。2.の熱烈なHaskellアピールが一番たのしかった、関数型と言いつつそれぞれのテーマ・アプローチが全然違っててカオスだった、など。
参加した動機としてはいくつかあって、
- Scalaとか結構よく使われる。既存の言語の延長上の概念としての関数型の有用性を確認したかった。
- 一方でHaskellみたいにPurelyFunctionalな言語も取りざたされてる。これって、Ruby、Scalaみたいなのと出発点・立場が違っていて、似て非なるアプローチだと思うんだけど、そっちのほうの状況ってどうなの？
みたいなのがあった。感想としては、一つ目については確認できた感じで、二つ目は半分わかって半分わからなかった。なんというか、機能としての有用性はすごい分かったんだけど、マーケティングとか人気取りの面での見通しはちょっと分からなかった感じ。まあ自分が手を入れたいと思わせるには十分良かった。あと薄々感づいてたけど静的型付け言語ぜんぜんわかってないなって改めて思った。
以下はそのとき取ったメモ。
続きを読むhtml5.jpの中の人の話聴いてきた
ウェブ系の会社でバイトしてるんだけど、最近のウェブのフロントエンドとかよく知らんなーって思っていたところ、html5.jpの中の人がお話するというのがあったので、聴いてきた。以下はその時話してたことの思い起こし。事情あって現場でメモ取れなかったので内容伝えきれてない感あるけど、まあメモ書き程度ということで。
前半―HTML5の本当のインパクト
歴史
HTML5の以前=HTLM4
このHTML4が10年間、ウェブの標準で在り続けた（驚くべきこと）
HTML4―ウェブが文章を読むために存在した時代に策定されたもの
…この間にウェブの役割が変化した：リッチな体験、アプリケーションプラットフォームとしての役割
…結果、様々な「プラグイン」が生まれた（e.g. JavaApplet,Flash,Silverlight）
つまり…
HTML4は、明らかにウェブで当たり前に求められているものを提供できていない。
HTML5は、何でもできるようにするというよりは、そういったウェブで当たり前に必要なものを提供しようというもの。
実際には、そういったプラグインからHTML5への移行は徐々に進む…と思われていたが、この流れを一気に加速させたのがAppleのFlash不搭載。
中身
HTML5=HTML+API.
このAPIというのは、例えば絵を書くだとか、デバイスにアクセスするだとか、そういうこと。これは本来OSの提供する機能だった。
こういった機能が充実してくると、App基板（プラットフォーム）としてウェブが機能するようになる。
キーワード：マルチ・デバイス化
Mac、WindowsなどのいわゆるPC以外に、iPhone、Androidなどのスマートフォン、さらにはPS3、テレビなどの家電。
- もはや、PC向けにアプリを開発し、それをモバイル用に縮めるというアプローチではない（MobileFirst,TouchFirst）
- それぞれのデバイスにおいて、同じ体験を提供したい。e.g. 'Buy once Read everywhere'(Kindle), 'Pay once Play anywhere'
これが、ウェブがプラットフォームであることを求められる一つの背景。
そーはいってもネイティブアプリケーションに比べて使いにくいんじゃないの？
- ブラウザを開いてURLを入力するなんて手間
- アイコンない
- パフォーマンス
ユーザーからすれば、それがHTMLで書かれているのか、ネイテイブ言語で書かれているのかはわからない（関係ない）
もはや、ブラウザを通すかどうか、というのはそれほど重要ではない
後半―HTML5の理想と現実
整理
前提：HTML5というのは、仕様としてのそれと、バズワードとしてのそれ、二つの側面。バズワードとしてのHTML5は、HTMLの仕様に加えて、様々なAPIが加わったもの。（でもHTML5（仕様）にも部分的にAPI）
- HTML5（仕様）
HTML4の時代は、勧告があって、初めてブラウザが実装した（W3C=天の声）だったが、HTML5においては、ブラウザがある程度実装して枯れてきたら勧告（Reccomend）になる。つまり、2014年HTML5勧告予定とかあんま意味ない（実装ベース）。 - API
WebSocketなどの様々なAPIは、HTML5（仕様）とは別々に策定、策定されていく。これがどんどん終わりなく繰り返されていく。
つまり、何年に何ができるようになるとかじゃなくて、それぞれの技術を実装状況を見ながら導入していく感じ。
過度な期待：HTML5でできる！と言われていることは全てFlashやSilverlightでできる（逆に、著作権保護などはHTML5ではできない）
実例
・WebAudioAPI(仕様策定中)
GoogleChromeがフル実装している
サンプル(Chrome)：http://www.htmlfivewow.com/demos/hal/index.html…音声をリアルタイムで解析し、点滅させている
・iPhoneのSafariでは、javascriptから加速度などが細かく取れる
現実問題
- Androidはバージョンのフラグメント化が激しい（http://satoshi.blogs.com/life/2011/12/android2.html）
- Polyfill:古いブラウザでHTML5を動かすための様々な工夫（e.g. socket.io(WebSocket),html5shiv(css),CSS3PIE(IEでcss3)）
- ハードウェアごとのパフォーマンス差（特にゲーム系）
- 向こう数年は現場の苦労が続くだろう
感想
ウェブプラットフォームっていう言葉（概念）を自分が初めて聞いたのが、三年前くらい。学校の課題をきっかけにしてWeb2.0関係の書籍を色々読んだりしたことを思い出す。その時は技術的なことはよく分からなかったけどね。HTML5は昔サークルのサイト作ったときにhtml5.jp参考にしながら使ったけど、APIの部分は触ったことなかったので、今回の話は新鮮だった。
特にiPhoneアプリとかそうだけど、HTMLベースで作られているものが多くて、iPhone買って最初触ったときはへえと思った。それが今回、マルチ・デバイス化などの話を聞いて、現実的な流れの中にあるんだなという感覚を得た。もはやPCはメインターゲットではない。と同時に、最近タスク管理ソフトを反応性の悪さやキーボードショートカットを理由にウェブアプリからネイティブアプリに変えたばかりだったこともあり、やっぱネイティブアプリ便利だなーって感じもあった。
自分の今やってるアルバイトはフロントエンドではないのだけど、自分は使い勝手やUIみたいなことには非常に敏感みたいで、ソフトウェア開発的な部分をベースにしつつも、その辺も活かせるようなことできたら楽しいかなあとかなんとなく思ってる*1。
あ、そういえばはてなブログとか言うのができて、はてなダイアリー無くなっちゃう（？）っぽいんで、春あたりにこっちに移行するかなと。今のデザイン結構気に入ってたので、ちょい残念。
*1:一方で、もっとみんなが行かなそうな、変な方向ないかなあってずっと考えてる
CTMCP 3章：宣言的プログラミング技法
この章の内容は色々細かいものが多いのでだらだらと。
要約
三章では、二章で定義した宣言的モデルの上で使用される、プログラミング技法を幅広く概観する。
反復計算というトピックから入り、より一般的な場合として、宣言的プログラミングの核心である再帰計算を示す。反復計算は、ある関数の末尾で自身を呼ぶが、再帰計算は、ある関数のどこでもよく、かつ何回でも、自身を呼ぶことができるので、より一般的である。反復計算では、同じプログラムを何通りもの方法で書き、クロージャーの外部参照の使い方などを検討する。再帰計算では、主に再帰的データ構造を例に、様々なプログラムを書いていく。リスト、木などは再帰的データ構造であり、多くの場合、再帰的データ構造の処理は、その定義をなぞるような場合分け（パターンマッチング）により、処理することができる。もちろん、ある問題を解くにあたって、それより小さい部分問題として解く、というのが基本的な考え方である。具体的には、木であれば、木の追加、削除などの操作から、深さ優先探索、幅優先探索、木の描画、下降型パーサーなどを書いていく。ただし、再帰計算一般には、スタックの大きさが一定で実行できないものが多い。従って再帰関数を反復関数に書きなおす状態変換という方法や、初めから反復形で書くための、アキュムレータという技法を導入する。
高階プログラミングは、これらの中でも度々使用されるが、それについてもまとめる。高階プログラミングのためには、どのような基本操作が言語に必要かを確認し、プログラムを書いていく。ここで、様々なイテレータ、ループを実装し、最後にその言語抽象としてforループを導入する。明示的遅延計算、カリー化についても少し触れる。
効率についても触れる。効率には、時間効率と空間効率がある。時間効率は最悪時計算量の他に、償却的計算量という観点もある。後者は、何度も操作を繰り返して全体として計算量が抑えられれば、それでよいという観点である。空間（メモリ）効率にも、その瞬間にどれだけ消費するかという基準と、どれだけのメモリ空間が必要かという基準がある。時間計算量は、入力について適切なパラメータを設定し、漸化式を用いて算出する。
再帰的な技法をひと通り見たあとで、抽象データ型（ADT）という概念を導入する。ある型がADTであるとは、その機能が、内部の実装に依らず、その操作のみで定義されているということである。例として辞書をリストと順序付き二分木の二通りで実装、比較する。これらの辞書は、ユーザーにデータの中身が見える実装になっている。この危険性と、安全な抽象データ型の必要性を説く。そのために、「鍵」という概念を宣言的モデルに付加し、辞書を安全にする。そして、そこから資格とセキュリティという、より一般的な話題を導き、プログラミング言語のセキュリティ機構の側面を考える。
他、宣言的でない必要物として、GUIやファイルI/Oの方法を説明する。
そして、まとめとして、WordCountを例に、小規模なプログラムをどのようにして設計するか、ということを見る。普通の言葉で書かれた仕様から、どのような技法が必要かを調査、コーディング、テストのステップを繰り返す。また、プログラムは一枚岩として書くのではなく、論理的な単位で分割し、コンポーネント化する。モジュールやスタンドアロンのプログラムのための言語抽象を導入し、GUIやI/Oを含めたWordCountを完成させ、この章を終える。
感想
トピック盛りだくさん。再帰的な関数―特にリストについての関数―を書くのにはある程度慣れたかな。カリー化とか話半分にしか触れてないので、ガンガン実際に使うとかはわからない感じ。
