archive.is webpage capture | Saved from | 15 May 2015 22:18:23 UTC | |
All snapshots | from host kenokabe-techwriting.blogspot.jp | ||
TextImage | |||
download .zipreport abuse |
私がよく知っている中で最も良い
結城浩 @hyuki 4月30日
ほんとうに詳しい方が、正確でわかりやすい関数型プログラミング(言語)の本を書くのが、最も大きな反論です。また、業界全体にとっても入門者にとっても意味のあることだと思います。私は「あなた」にお願いしているのです。よろしくお願いいたします。Eijiro Sumii @esumii 4月30日
@hyuki (私も含め皆さんが何度も言っていてすみませんが)http://www.amazon.co.jp/dp/4781911609 じゃだめですか?Eijiro Sumii @esumii 4月30日
@hyuki http://pllab.is.ocha.ac.jp/~asai/book-mov/ に解説ビデオやスライド等もあります(お茶大学部2年生の授業用ですが他の人が見ても有用だと思います)結城浩 @hyuki 4月30日
@esumii いや、私にそう言われましても…この本は、岡部さんをdisる人たちが、IQなんとかの本の代わりに推薦なさる本なのかしら。それならばそれで、まったく(私は)異論ありません。私は単に「本のdisり」より「本のオススメ」のツイートやブログ記事を見たいだけなんです…結城浩 @hyuki 4月30日
@esumii 素晴らしい。Eijiro Sumii @esumii 4月30日
@hyuki disるのが目的の人たちはわかりませんが、最近も(少なくとも私の観測範囲では)しばしばお勧めされていると思います。どうも失礼しました結城浩 @hyuki 4月30日
@esumii こちらこそ、オススメありがとうございます。いま買いました。2-3週間後に届くらしいですが…Eijiro Sumii @esumii 4月30日
@esumii (他の本をおすすめしないわけではなく、私がよく知っている中で最も良いと思う次第。他にも良い本はあると思います。これも何度もすみませんが http://d.hatena.ne.jp/akuraru/20150410/p1 … などをば)
<内容詳細>
デザインレシピを用いてプログラミングに必要な思考法を学び,メトロネットワーク最短路問題を解きながらデータ構造とアルゴリズムを身につける,関数型言語OCamlによる入門者のための教科・参考書.
<目次>
第1章 はじめに
1.1 デザインレシピ
1.2 使用する言語
1.3 準備
1.4 参考となる資料
第2章 基本的なデータ
2.1 整数
2.2 実数
2.3 文字列
2.4 真偽値
2.5 そのほかのデータ
第3章 変数の定義
3.1 変数の必要性
3.2 変数定義の構文
3.3 変数の実行方法
3.4 ほかの言語の変数との違い
第4章 関数の定義
4.1 関数定義の必要性
4.2 関数定義の構文
4.3 関数の型
4.4 型推論と型チェック
4.5 関数の実行方法
4.6 関数定義に対するデザインレシピ
第5章 条件分岐
5.1 条件分岐の必要性
5.2 条件分岐の構文
5.3 kyuyoの例
5.4 式としてのif文
5.5 条件分岐に対するデザインレシピ
5.6 真偽値を返す関数
5.7 条件分岐の実行方法
第6章 さまざまなエラー
6.1 構文エラー
6.2 未定義の変数
6.3 型エラー
6.4 実行時のエラー
6.5 論理的なエラー
第7章 組とパターンマッチ
7.1 組の構文
7.2 パターンマッチ
7.3 構造データに対するデザインレシピ
7.4 パターンマッチの実行方法
第8章 レコード
8.1 レコードの必要性
8.2 レコードの構文
8.3 レコードとパターンマッチ
8.4 そのほかの記法
8.5 ユーザによる型定義
8.6 データ定義に対するデザインレシピ
8.7 駅名と駅間の情報の定義
第9章 リスト
9.1 リストの構造
9.2 リストの構文と型
9.3 リストとパターンマッチ
9.4 再帰関数
9.5 再帰関数に対するデザインレシピ
9.6 テンプレートの複合
9.7 駅名リストと駅間リストの整備
第10章 再帰関数を使ったプログラミング
10.1 関数のネスト
10.2 リストの中の最小値を求める関数
10.3 局所変数定義
10.4 パターンマッチつき局所変数定義
10.5 ふたつのリストを結合する関数
10.6 ふたつの昇順に並んだリストをマージする関数
10.7 駅名・駅間リストからの情報の取得
第11章 自然数と再帰
11.1 自然数の構造
11.2 自然数に基づいた再帰関数
11.3 ベキ乗を求める関数
11.4 リスト上の再帰との違い
第12章 ダイクストラのアルゴリズム
12.1 グラフ上の最短路問題
12.2 ダイクストラのアルゴリズム
12.3 アルゴリズムの正当性
12.4 プログラムにおける頂点と辺の定義
12.5 駅名の重複の除去
第13章 一般化と高階関数
13.1 データの一般化
13.2 関数の一般化とmap
13.3 多相型と多相関数
13.4 値としての関数
13.5 関数を返す関数
13.6 確定点に隣接する点の最短距離の更新
第14章 高階関数を使ったリスト処理
14.1 条件を満たす要素を取り出す関数
14.2 各要素をまとめあげる関数
14.3 局所関数定義
14.4 名前のない関数
14.5 infix関数とprefix関数
14.6 完全数を求める関数
第15章 新しい形の再帰
15.1 再帰関数の構造
15.2 部分問題の生成
15.3 補助関数の作成
15.4 停止性の判定
15.5 一般の再帰に対するデザインレシピ
15.6 最短距離最小の点の分離
15.7 例の作成とデバッグについて
第16章 情報の蓄積
16.1 情報の欠落
16.2 アキュムレータ
16.3 アキュムレータの活用
16.4 最初の完動プログラム
16.5 プログラム作成のプロセス
第17章 再帰的なデータ構造
17.1 バリアント型
17.2 木
17.3 再帰的なデータ構造に対するデザインレシピ
17.4 2分探索木
17.5 多相型の宣言
17.6 停止性
17.7 get_ekikan_kyoriの高速化
17.8 全通りを尽くしていない場合の対処
第18章 例外と例外処理
18.1 オプション型
18.2 オプション型を使った例外処理
18.3 オプション型を使った例外処理の問題点
18.4 例外処理専用の構文
18.5 例外処理の実際
18.6 例外処理を使ったプログラミング
18.7 最短路問題における例外処理
第19章 モジュール
19.1 モジュールの構文
19.2 2分探索木のモジュール
19.3 モジュールインタフェース:シグネチャ
19.4 抽象データ型
19.5 そのほかのシグネチャの宣言法
19.6 ファイルの分割と分割コンパイル
19.7 2分探索木モジュールの使用
第20章 モジュールの開発
20.1 赤黒木
20.2 赤黒木への挿入
20.3 赤黒木の再構成
20.4 「または」のパターン
20.5 赤黒木のモジュール化
20.6 open文
第21章 逐次実行
21.1 副作用を持つ関数
21.2 unit型
21.3 逐次実行の構文
21.4 実行中の変数の表示
21.5 実行の順序
21.6 スタンドアローンのプログラム
21.7 引数の渡し方
第22章 値の書き換えと参照透過性
22.1 参照透過性
22.2 呼び出し回数のカウント
22.3 参照型と値の書き換え
22.4 参照透過性の喪失
22.5 変更可能なレコード
22.6 配列
22.7 配列の変更
第23章 副作用命令を使ったプログラミング
23.1 ダイクストラ法におけるデータアクセス
23.2 ヒープ
23.3 ヒープへの挿入
23.4 そのほかの操作
23.5 ヒープのインタフェース
23.6 副作用命令の影響について
23.7 ヒープ実装の概要
第24章 まとめ―プログラミングとは―
24.1 OCamlを習得して
24.2 この先の道
索引
第3章 変数の定義
3.4 ほかの言語の変数との違い
第6章 さまざまなエラー
第2章 基本的なデータ
関数型言語OCamlによる入門者のための教科・参考書
Eijiro Sumii @esumii 4月30日
@hyuki http://pllab.is.ocha.ac.jp/~asai/book-mov/ に解説ビデオやスライド等もあります(お茶大学部2年生の授業用ですが他の人が見ても有用だと思います)
「プログラミングの基礎」を使った授業紹介
浅井 健一
このページでは、お茶の水女子大学、理学部、情報科学科の2年生を 対象とした授業「関数型言語」のビデオほかを公開しています。 この授業は反転授業 (flipped class) を行っており、 受講生は授業前に以下の予習を求められます。
第1章 はじめに
1.1 この本の読み方
1.2 準備
1.3 OCamlに関する情報源
1.4 OCamlの特徴
1.5 OCamlの歴史
第2章 いろいろな式を評価してみよう
2.1 対話式コンパイラ
2.2 基本データ型とその演算
2.3 変数束縛による定義
第3章 関数型言語の醍醐味:関数
3.1 簡単な関数の定義
3.2 条件分岐と真偽値型bool
3.3 局所的変数束縛とlet式
3.4 構造のためのデータ型:組
3.5 再帰関数
3.6 高階関数
第4章 少ない手間で型付けをする:多相性と型推論
4.1 多相的関数とパラメトリック多相
4.2 型推論とlet多相
4.3 Case Study:コンビネータ
4.4 練習問題
第5章 再帰的多相的データ構造:リスト
5.1 リストの構成法
5.2 リストの要素へのアクセス:match 式とリストパターン
5.3 リストを操作するさまざまな関数
5.4 Case Study:整列アルゴリズム
5.5 練習問題
第6章 データ構造をデザインする:レコードとヴァリアント
6.1 レコード
6.2 ヴァリアント
6.3 ヴァリアントの応用
6.4 Case Study:二分木
6.5 Case Study:無限列
6.6 練習問題
第7章 例外処理
7.1 オプション型による例外処理
7.2 raise式とtry式による例外処理
7.3 exception宣言とexn型
7.4 練習問題
第8章 書き換え可能なデータ構造と入出力を使った命令型プログラム
8.1 unit型
8.2 書き換え可能なデータ構造
8.3 制御構造
8.4 Case Study:参照を使ったデータ構造ーーキュー
8.5 チャネルを使った入出力
8.6 練習問題
第9章 モジュールによるプログラムの構造化
9.1 ライブラリ・モジュールの使い方
9.2 モジュール定義
9.3 シグネチャを使った情報隠蔽と抽象データ型
9.4 練習問題
第10章 バッチコンパイラと分割コンパイル
10.1 バッチコンパイラによる実行可能ファイルの作成
10.2 モジュール単位の分割コンパイル
10.3 システム周りの関数・モジュール
10.4 その他
10.5 練習問題
第11章 モジュール関数:ファンクター
11.1 ライブラリモジュールのファンクターとファンクター適用
11.2 ファンクター定義
11.3 ファンクターと情報隠蔽
11.4 複数の引数をとるファンクター
11.5 練習問題
第12章 OCamlの“O”:オブジェクト
12.1 単純なクラス
12.2 自分自身のメソッドを呼び出す
12.3 継承によるクラスの拡張
12.4 オブジェクトのための型付け
12.5 より高度なクラス機能・型
12.6 練習問題
第13章 ラベル付き引数とオプション引数
13.1 ラベル付き関数を使う
13.2 ラベル付き引数詳説
13.3 オプション引数
13.4 まとめ
第14章 多相ヴァリアント
14.1 多相ヴァリアントの基本
14.2 関数定義の拡張
14.3 再帰的関数と多相ヴァリアント
14.4 その他
14.5 練習問題
第15章 GUI ライブラリ:LablTk
15.1 「銀行窓口」を作ってみる
15.2 ウィジェットの紹介
15.3 ウィジェットの配置:Tk.pack関数とPackモジュール
15.4 イベント処理の割り当て:bind
15.5 その他
15.6 練習問題
第16章 Case Study:お絵かきロジック
16.1 お絵かきロジックとは?
16.2 プログラム解説
16.3 まとめ
あとがき
第3章 変数の定義
3.4 ほかの言語の変数との違い
第6章 さまざまなエラー
第6章 データ構造をデザインする:レコードとヴァリアント
第14章 多相ヴァリアント
17.1 バリアント型
第8章 書き換え可能なデータ構造と入出力を使った命令型プログラム
第12章 OCamlの“O”:オブジェクト
12.1 単純なクラス
12.2 自分自身のメソッドを呼び出す
12.3 継承によるクラスの拡張
12.4 オブジェクトのための型付け
12.5 より高度なクラス機能・型
12.6 練習問題
第15章 GUI ライブラリ:LablTk
15.1 「銀行窓口」を作ってみる
15.2 ウィジェットの紹介
15.3 ウィジェットの配置:Tk.pack関数とPackモジュール
15.4 イベント処理の割り当て:bind
15.5 その他
15.6 練習問題
第16章 Case Study:お絵かきロジック
16.1 お絵かきロジックとは?
16.2 プログラム解説
16.3 まとめ
GUIライブラリ:LablTk
Library: LablTk
open GMain
let window = GWindow.window ~border_width:2 ()
let button = GButton.button ~label:"Hello World" ~packing:window#add ()
let () =
window#event#connect#delete ~callback:(fun _ -> true);
window#connect#destroy ~callback:Main.quit;
button#connect#clicked ~callback:window#destroy;
window#show ();
Main.main ()
let () =
let app = SFRenderWindow.make (640, 480) "OCaml-SFML Windowing" in
let rec loop() =
let continue =
match SFRenderWindow.getEvent app with
| Some SFEvent.Closed -> false
| _ -> true
in
SFRenderWindow.clear app SFColor.black;
SFRenderWindow.display app;
if continue then loop()
in
loop()
open Xlib
let () =
let d = xOpenDisplay "" in
let s = xDefaultScreen d in
let w = xCreateSimpleWindow d (xRootWindow d s) 10 10 100 100 1
(xBlackPixel d s) (xWhitePixel d s) in
xSelectInput d w [KeyPressMask];
xMapWindow d w;
let _ = xNextEventFun d in (* waits any key-press event *)
xCloseDisplay d;
;;
著者の五十嵐淳さんのサイトにおいて,本書のサポートページが開設されています。
第16章のプログラム
GUI とメインプログラム: gui.ml
http://www.fos.kuis.kyoto-u.ac.jp/~igarashi/OCaml/gui.ml
(** 各種ウィジェット操作 **)
(* マス目にマウスポインタが来た時の動作 *)
let focus label _ = Label.configure label ~background:selcol
(* マス目からマウスポインタが離れた時の動作 *)
let unfocus label st _ =
Label.configure label ~background:(color_of_state !st)
(* マス目の上でマウスボタンが押された時の動作 *)
let pressed label st _ =
st := toggle !st;
Label.configure label
~relief:(relief_of_state !st) ~background:(color_of_state !st)
(* マス目をクリア *)
let clear label st _ =
st := NotPressed;
Label.configure label
~relief:(relief_of_state !st)
~background:(color_of_state NotPressed)
(* 全マス目をクリア *)
let clear_all cells states =
List.iter2
(fun (_::c_row) st_row ->
List.iter2 (fun c_row st_row -> clear c_row st_row ())
c_row st_row)
cells states
st := toggle !st;
st := NotPressed;
st
というミュータブルな状態変数に、破壊的代入を繰り返していることが容易に確認できます。State
や、または私が開発した
three foci of phenomena
三つの現象
物事の「新結合」「新機軸」「新しい切り口」「新しい捉え方」「新しい活用法」(を創造する行為)のこと。一般には新しい技術の発明を指すと誤解されているが、それだけでなく新しいアイデアから社会的意義のある新たな価値を創造し、社会的に大きな変化をもたらす自発的な人・組織・社会の幅広い変革を意味する。つまり、それまでのモノ・仕組みなどに対して全く新しい技術や考え方を取り入れて新たな価値を生み出して社会的に大きな変化を起こすことを指す。(Wikipedia)
その時代や分野において当然のことと考えられていた認識や思想、社会全体の価値観などが革命的にもしくは劇的に変化することを言う。パラダイムチェンジとも言う。(Wikipedia)
パラダイムシフト
本書の前半半分は、命令形プログラミングと関数型プログラミングのパラダイムの違いを非常に分かりやすく説明されています。自分が今まで書いていた命令形プログラミングはフローを作成して機能毎に分割して作っていましたが、関数型プログラミングはフローや状態を排除し論理毎に機能を作成し、必要になった時に必要な分だけ計算する(イベント駆動)という方法を取ります。「論理」と「計算」を分けて考えるという説明はわかりやすかったです。
これはひょっとして次にくる古くて新しいパラダイムなのではないかと思ってワクワクした。そこで目に入ったのがこの本。
お姉さんにプログラミングの手ほどきを受けるという素敵な場面に出くわしたことのない僕は年甲斐もなくワクワクしながら読んだ。使われているのはJavaScriptだ。思ったとおり。まともな関数型言語だった。お姉さんはパラダイムの変化を哲学の視点からも説明してくれる。関数型の足元がしっかり固まるようで心強い。よし、ここしばらくこれにハマってみようということで、JavaScriptの関連本を買い、彼女が使っているAtomというエディタをUbuntuに入れようとしているのがまさに今。仕事で受け入れられるようになるにはひょっとすると10年かかるかもしれない。そのころには定年だ。だけどこのワクワク感。逃す手はない。少々煙たがられてもLispの時のように挫折せずにモノにしたい。そう思うのである。表紙に騙されてもいいから、プログラマーなら読んでおくべき本だ。
以前からぼんやりと関数型プログラムが出来るようになりたいと思ってましたが、ネットでちょっと調べる程度で出来るものではなかったです(自分にとっては)。
でたまたま平積みされていた本書を立ち読みすると、ストーリー仕立てで面白そうだったのと、1300円と安価だったので即購入。GW一杯かけて読むことにしました。本書は丁度5月1日に発売されていたのでそういう読み方も想定していたと思う。ちょうど5日間だし。内容としては「0から9までの数をすべて足すコード」を、関数型プログラムで書くまでが前半の100ページ以上かけて説明されています。関数を一個一個定義していって最後に関数型のコードで「0から9までの数をすべて足すコード」ができるところ、フィボナッチ数列を関数型プログラムで求めるところでかなり感動してしまった。この前半はかなり充実した内容だと思う。関数型プログラムがどうしてもよく分からない、そもそもなんでオブジェクト指向ではダメなのか、何から始めればいいのかとか、最初の取っ掛かりが掴めずにいた自分にはピッタリ嵌ってしまった。また読み物として前から後ろに読んでいっても復習の章があったりして自然と考え方が定着します。普通技術書は重要なことが書いてあるページは読者が覚えておいて何度も開き直すような読み方になると思いますが、読み物として読んでいってる人にも理解させようという気概がある書き方みたい。
なんというか、ストーリー仕立てということもあるしとても情熱的な書き方になっている。一度オブジェクト脳になってしまった頭をパラダイムシフトさせるにはこのくらいの熱意が感じられないと難しいのかも。今まで関数型プログラムの壁に当たって引き返していたのが、女子高生にダサいコードと罵られたことで何としてでも超えてやろうと思えたわけだ。読み終わってアマゾンを見ると本書に関して内容が薄いとかそもそも誤解に基づいた主張とか、レビューの点数があまりに低いのでビビった。
まぁ本の内容が正しい、ということより、内容がどうであれその本に影響を受けて関数型プログラムの習得に強い動機付けがなされた人、あるいは最初の壁を突破した人が一人いる、ということの方が重要なので、個人的には超おすすめ。関数型プログラムをやりたいけどよく分からない、って状態で(女子高生に罵られるのがそんなに嫌いじゃない人が)読むと絶対面白いと思う。
というか普通に考えて発売から1週間足らずでこれだけのレビューを集めてる、そんでほとんどが低評価ってのがなんていうか、、本の内容がどうというより余程嫌われてるんですねこの作者w。
Amazonのレビュー見てると、どうもこの作者の人となりによって不当に評価されている気がする。この本のターゲット層は関数型プログラムなんか出来ないって人で取っ掛かりを求めてる人なんじゃないの?
言語として、関数型プログラムなんか出来ない人にも馴染みの深い、関数型プログラムが書けるものって、JavaScriptがぴったりだと思う。
で関数型をこれから始める取っ掛かりって意味で関数型の考え方とか作り方とかをここまでページ数使って簡単に解説してるものは他にないと思うけど。変な先入観を持ってこの本読まずに、難しい本を最初に手に取って「やっぱ関数型って意味わかんね」ってなるくらいなら、この本を最初に読めばいいと思う。
まぁ、表紙が良いのと値段も安いので買う人多いと思うけど。。
まじめな話、いろいろある関数型言語の入門書の中で一番理解しやすく一番神髄的なところを説明している本ではないでしょうか。文体や表紙にだまされることなく、関数型言語の考え方の核になる部分がわかりやすく書かれています。下手に圏論やモナドなどを持ち出さないところも重要です。Amazon等でいろいろ批判されていますが、それらの用語を多用する小難しい事オレがんばっておぼえた的なところがにじみ出すぎている、良くある関数型入門的なWebサイトより256倍マシです。小難しく書かれたHaskell本を読んで挫折した人は、この本でセキヤくんと一緒にJavaScriptでやり直してみるのが良いのではないかと思います。しかも1300円です。ほかの関数型言語の書籍がいったいいくらすると。個人的には、良くある「フロント技術者」の人たちが書いているFacebookのReactの記事を読んでもその重要性や目的がさっぱりわからなかったのですが、この本を読んですとんと落ちました。もうそれだけで1300円分の価値が十分ありましたよ。あと本書で大事なのは、哲学と計算機科学との関係についてちゃんと触れられている点で、こんな事まで理解している高二怖いと思いましたが、そこはすごく大事な点です。どちらかというと本書はオブジェクト指向にたいして否定的なので、そちら文脈での哲学や仏教思想については触れられていませんが、オブジェクト指向と仏教の因果律との関係なども面白いテーマでしょう。結局対象をどう捉えるかというパースペクティブはどの様なパラダイムであれ重要で、そのパースペクティブを与えるのが哲学だからです。ということで、内容の濃い、でも読みやすい1300円でした。
three foci of phenomena
三つの現象
私はあなたの指導教官ではないし、教える義務もありませんので、これ以上の努力はいたしません。最低限の指摘はすでに終了しています。
幸いなことに世の中には、すぐれた書籍があふれております。いい世の中です。ぜひ、一読することをおすすめしたします。
この分野に関わりたいのであれば、避けては通れないコンピュータサイエンスの基本ばかりです。
[1] “Structure and Interpretation of Computer Programs” http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-1.html#titlepage
[2] “Introduction to the Theory of Computation” http://www.amazon.co.jp/Introduction-Theory-Computation-Michael-Sipser/dp/113318779X
[3] “Types and Programming Languages” http://www.amazon.co.jp/Types-Programming-Languages-Benjamin-Pierce/dp/0262162091
以上を参考文献として上げる理由を以下に述べておきます。
[1] - Kenokabe さんは、評価(eval) と 関数呼び出し(apply) の基本的区別がついていないようです。私がこれまで出会ってきた学生ならば、これらの区別は100人中100人が学習によりできるようになります。Kenokabe さんの中における「評価」と、100人中100人が共通の語彙として相互理解している「評価」がどのように異なるか、ぜひ、SICP を読むことをおすすめします。
[2] - Kenokabe さんは、コンピュータプログラミングにおいて「計算」するということがどういうことかその原理を理解していないようです。この本は、「計算」するとはどういうことか?時間と空間との関係についてもきちんと数学的な証明をもって述べています。ぜひ一読を。
[3] - λ計算についての深い知識はここでの議論ではそれほど必要ないかと思われますがやはり身につけておいたほうが今後は他人とのコミュニケーションがスムーズになると思われます。
この分野に関わりたいのであれば、避けては通れないコンピュータサイエンスの基本ばかりです。
[1] “Structure and Interpretation of Computer Programs” http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-1.html#titlepage
Structure and Interpretation of Computer Programs” http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-1.html#titlepage
魔術師本: (名詞) MITの入門コースで使う計算機科学の優れた教科書 ハル・エイブルソン, ジェリー・サスマン, ジュリー・サスマン共著(和田英一訳)「計算機プログラムの構造と解釈 第二版」(ピアソン・エデュケーション 2000年). 表紙の魔術師ゆえにそういわれる. LISP/Scheme世界の聖典のひとつ. まれに紫本としても知られている.
ハッカー英語辞典 第2版(MITプレス 1993)より
SICPとは何か?
SICPとはMITが作成した何も知らない新入生向けのプログラミングの教科書です。
プログラミングと強調したことには理由があります。この本は良くあるプログラミング言語の教科書ではなく、あくまでもプログラミングを勉強するための教科書だからです。このことはこの本の中でも、最初の前書き、序文にて何度でも繰り返し強調されています。筆者達がこの本をそれまでの教科書から著しく際立たせる特徴として誇る理由です。
米国の新聞、ボストングローブ紙のMITの創立150周年記念企画にて作成されたMITでの最も重要な発明リストにもこのSICPは選ばれています。127番 もっとも重要な本
Harold Abelson and Gerald Jay Sussman, a pair of MIT computer science professors, wrote “Structure and Interpretation of Computer Programs,” which remains a classic for encouraging the teaching of not one specific programming language, but big-picture themes students could apply across a range of programming scenarios.
MITの計算機科学の二人の教授、Harold AbelsonとGerald Jay Sussmanは”SICP”を出版しました。
これは1つの特定のプログラミング言語を教えるのではなく、学生が一連のプログラミングの
シナリオに渡って適用できる大局的なテーマを教えることを促す古典としてあり続けています。
4 超言語的抽象
… 魔法は言葉にある. —アブラカダブラ, 開け胡麻, など— しかしある物語の呪文は, 次の物語では呪文ではない. 真の魔法はどの呪文がいつ, 何のために働くかを理解することである. トリックはトリックを学ぶことである.
… そしてこれらの言葉は, アルファベットの文字で出来ている; ペンで書ける二十字余りの記号である. これが鍵だ. そこに手が届きさえすれば宝でもある. それは宝への鍵が宝であるようなものだ.
John Barth キメラ
Foreword
Educators, generals, dieticians, psychologists, and parents program. Armies, students, and some societies are programmed. An assault on large problems employs a succession of programs, most of which spring into existence en route. These programs are rife with issues that appear to be particular to the problem at hand. To appreciate programming as an intellectual activity in its own right you must turn to computer programming; you must read and write computer programs – many of them. It doesn’t matter much what the programs are about or what applications they serve. What does matter is how well they perform and how smoothly they fit with other programs in the creation of still greater programs. The programmer must seek both perfection of part and adequacy of collection. In this book the use of “program” is focused on the creation, execution, and study of programs written in a dialect of Lisp for execution on a digital computer. Using Lisp we restrict or limit not what we may program, but only the notation for our program descriptions.Our traffic with the subject matter of this book involves us with three foci of phenomena: the human mind, collections of computer programs, and the computer. Every computer program is a model, hatched in the mind, of a real or mental process. These processes, arising from human experience and thought, are huge in number, intricate in detail, and at any time only partially understood. They are modeled to our permanent satisfaction rarely by our computer programs. Thus even though our programs are carefully handcrafted discrete collections of symbols, mosaics of interlocking functions, they continually evolve: we change them as our perception of the model deepens, enlarges, generalizes until the model ultimately attains a metastable place within still another model with which we struggle. The source of the exhilaration associated with computer programming is the continual unfolding within the mind and on the computer of mechanisms expressed as programs and the explosion of perception they generate. If art interprets our dreams, the computer executes them in the guise of programs!
序文
教育者, 将軍, 栄養士, 心理学者, 親はプログラムする. 軍隊, 学生, 一部の社会はプログラムされる. 大規模な問題への攻撃はプログラムを次々と利用するが, その殆んどは途中で現れる. プログラムには手元の問題に特有と思われる議論が多い. プログラミングをそれ自身で知的活動と評価するには計算機プログラミングに向わなければならない. 計算機プログラム—その多くを読み, 書きしなければならない. そのプログラムが何に関するものか, どの応用のためかということには関係しない. 関係するのはいかにうまく動作するか, 更に大きいプログラムを作るために他のプログラムといかにうまく適合するかということである. プログラマは部品の完成度と集積の妥当性の両方を求めなければならない. 本書では「プログラム」の利用は, 電子計算機の実行に使うLispの一方言で書いたプログラムの創作, 実行と研究を対象とする. Lispの使用はわれわれが何をプログラムするかではなく, プログラム記述の記法だけに限定し制限する.本書の主題との関係でわれわれは三つの現象: ひとの心, 計算機プログラムの集積と計算機に関る. 計算機プログラムは心に生れた物理的, 心理的プロセスのモデルである. ひとの経験と思考から生じたこれらのプロセスは数において巨大であり, 細部において複雑であり, 一時には部分的にしか理解されない. それらは計算機プログラムによって永遠に満足出来るようにモデル化されることは殆んどない. 従ってプログラムが注意深く細工した離散的な記号の集積, 相互作用する関数の組合せであっても, 絶えず進化する. われわれはモデルの認知が深まり, 広まり, 一般化するにつれ, まだ苦闘中の他のモデルの間で, モデルが究極的に準安定な場所を得るまで変化を続ける. 計算機プログラミング対応した陽気な気分の源泉は, プログラムとして表現した機構の心の中と計算機の上での絶えまなき解明と, それらが生成する認知の拡大である. 技術が夢を解釈するなら, 計算機はプログラムを装って夢を実行するであろう.
(https://github.com/minghai/sicp-pdf による翻訳)
この本の主題は 3 つの事象に焦点を当てます。人の心、コンピュータプロ
グラムの集合、そしてコンピュータです。全てのコンピュータプログラムは人
の心の中で生まれる現実の、または精神的な過程のモデルです。これらの過程
は人の経験と思考から浮かび上がり、数はとても多く、詳細は入り組んで、い
つでも部分的にしか理解されません。それらはコンピュータプログラムにより
稀にしか永遠の充足としてモデル化されることはありません。従って、例え私
達のプログラムが注意深く手作りされた別個の記号の集合だとしても、連動す
る機能の寄せ集めだとしても、それらは絶えず発展します。私達のモデルの知
覚がより深まるにつれ、増えるにつれ、一般化されるにつれ、モデルが究極的
に準安定な位置に逹っするまで変更を行い、その中には依然として私達が格闘
xivするモデルが存在します。コンピュータプログラミングに関連する歓喜の源は
プログラムとして表現された仕組みの心の中とコンピュータ上で絶え間無く続
く発展であり、それにより生まれる知力の爆発です。もし技巧が私達の夢を解
釈するならば、コンピュータはプログラムとして現わされるそれらを実行する
のです!
Our traffic with the subject matter of this book involves us with three foci of phenomenaOur traffic with the subject matter of this book involves us with three foci of phenomena: the human mind, collections of computer programs, and the computer. Every computer program is a model, hatched in the mind, of a real or mental process.
本書の主題との関係でわれわれは三つの現象: ひとの心, 計算機プログラムの集積と計算機に関る. 計算機プログラムは心に生れた物理的, 心理的プロセスのモデルである.
If art interprets our dreams, the computer executes them in the guise of programs!
技術が夢を解釈するなら, 計算機はプログラムを装って夢を実行するであろう.
three foci of phenomena: the human mind, collections of computer programs, and the computer.
三つの現象: ひとの心, 計算機プログラムの集積と計算機
three foci of phenomena
三つの現象
If art interprets our dreams, the computer executes them in the guise of programs!
技術が夢を解釈するなら, 計算機はプログラムを装って夢を実行するであろう.
Our design of this introductory computer-science subject reflects two major concerns. First, we want to establish the idea that a computer language is not just a way of getting a computer to perform operations but rather that it is a novel formal medium for expressing ideas about methodology. Thus, programs must be written for people to read, and only incidentally for machines to execute. Second, we believe that the essential material to be addressed by a subject at this level is not the syntax of particular programming-language constructs, nor clever algorithms for computing particular functions efficiently, nor even the mathematical analysis of algorithms and the foundations of computing, but rather the techniques used to control the intellectual complexity of large software systems.
この計算機科学の入門科目の設計には二つの主要な関心事があった. 第一に計算機言語は単に計算機に演算を実行させる方法だけでなく, 方法に関する考えを表現する新しい形式的媒体であるという考えを樹立したかった. そこでプログラムは人びとが読むように, そして計算機はたまたま実行するように書くべきである. 第二にこの科目が扱う実質的な材料は, このレベルが特定のプログラム言語の構成の構文でも, 特定の関数を効率よく計算するアルゴリズムでも, アルゴリズムの解釈や計算の基礎でもなく, 巨大なソフトウェアシステムの知的複雑性の制御に使う技法であった.
First, we want to establish the idea that a computer language is not just a way of getting a computer to perform operations but rather that it is a novel formal medium for expressing ideas about methodology. Thus, programs must be written for people to read, and only incidentally for machines to execute.
第一に計算機言語は単に計算機に演算を実行させる方法だけでなく, 方法に関する考えを表現する新しい形式的媒体であるという考えを樹立したかった. そこでプログラムは人びとが読むように, そして計算機はたまたま実行するように書くべきである.
Second, we believe that the essential material to be addressed by a subject at this level is not the syntax of particular programming-language constructs, nor clever algorithms for computing particular functions efficiently, nor even the mathematical analysis of algorithms and the foundations of computing, but rather the techniques used to control the intellectual complexity of large software systems.
第二にこの科目が扱う実質的な材料は, このレベルが特定のプログラム言語の構成の構文でも, 特定の関数を効率よく計算するアルゴリズムでも, アルゴリズムの解釈や計算の基礎でもなく, 巨大なソフトウェアシステムの知的複雑性の制御に使う技法であった.
(Even while it changes, it stands still.)
(変化している時にも静止している.)
アラン・ケイやスティーブ・ジョブズを引き合いに出すくらいはまだ良かったのですが、プラトンのイデアとか汎神論、精神世界と物質世界、大日如来の真言(マントラ)、果てはスピノザの神とか言い始めたときには、ほんとマジ超ヤバいと思いました。
ここまで来ると完璧に宗教の勧誘です。(検閲削除)や(検閲削除)などのように、実際には母親が指導しているのかもしれません。このままではセキヤ君が(検閲削除)になってしまいそうで、読んでいて気が気ではありません。
岡部イズム満載で素晴らしい。
読者は…、上級者向けかもしれません。この世界観を楽しめる人には良書でしょう。
むむっ!と唸らせる表現もチラホラ。時間はバージョン番号だ!とか、慧眼で(゚д゚)!
価格も安い!この内容で1,300円は安い。使える言い回しも多数!
値段以上にエンターテイメントの要素は散りばめられています… と思う。
なんといっても、「物質」だの「精神」だの、読者の理解を超越していて頭が下がります。
著者本人ですら、自らの書こうとしている内容を理解していないのでしょう。
蒙昧主義的で曖昧な言葉で不理解を誤魔化そうとするため、結果としてとても他人が読める文章にはなっていません。
このため、間違いを指摘しようにもこの駄文を理解するのが面倒で、まともな人なら黙殺するということになります。
何も知らない初心者や、自分に理解できないものを有り難がる愚かな人が、煙に巻かれて本書の内容を信じないことを祈ります。
こんなオカルトが出版まで至ってしまったとは、編集者や出版社の罪は深いなと思います。
何というか、フィネガンズ・ウェイクを彷彿とさせるような人智を超えた形而上学的な幻想世界が本書の中では展開されています。
本書のカテゴリは「技術書+ラノベ」ではなく「宗教」や「奇書」と謳ったほうがより正確かもしれません。
Our traffic with the subject matter of this book involves us with three foci of phenomena
本書の主題との関係でわれわれは三つの現象three foci of phenomena: the human mind, collections of computer programs, and the computer.
三つの現象: ひとの心, 計算機プログラムの集積と計算機
To a large extent, then, the way we organize a large program is dictated by our perception of the system to be modeled. In this chapter we will investigate two prominent organizational strategies arising from two rather different “world views” of the structure of systems. The first organizational strategy concentrates on objects, viewing a large system as a collection of distinct objects whose behaviors may change over time. An alternative organizational strategy concentrates on the streams of information that flow in the system, much as an electrical engineer views a signal-processing system.
大きいプログラムを組織化する方法は, われわれがモデル化するシステムをどう認識するかにかなりなところまで左右される. 本章では, いくらか異ったシステム構造の二つの「世界観」から生じる顕著な組織化戦略を研究する. 第一の組織化戦略は オブジェクト(objects)に注目するもので, 巨大システムを, 時間とともに変化するいろいろなオブジェクトの集りと見るものである. もう一つの組織化戦略は,電気技術者が信号処理システムを見るように, システム内を流れる情報の ストリーム(streams)に注目するものである.
本章では, いくらか異ったシステム構造の二つの「世界観」から生じる顕著な組織化戦略を研究する
第一の組織化戦略は オブジェクト(objects)に注目するもので, 巨大システムを, 時間とともに変化するいろいろなオブジェクトの集りと見るものである. もう一つの組織化戦略は,電気技術者が信号処理システムを見るように, システム内を流れる情報の ストリーム(streams)に注目するものである.
Both the object-based approach and the stream-processing approach raise significant linguistic issues in programming. With objects, we must be concerned with how a computational object can change and yet maintain its identity. This will force us to abandon our old substitution model of computation (section 1.1.5) in favor of a more mechanistic but less theoretically tractable environment model of computation. The difficulties of dealing with objects, change, and identity are a fundamental consequence of the need to grapple with time in our computational models. These difficulties become even greater when we allow the possibility of concurrent execution of programs. The stream approach can be most fully exploited when we decouple simulated time in our model from the order of the events that take place in the computer during evaluation. We will accomplish this using a technique known as delayed evaluation.
オブジェクト準拠の解決法とストリーム処理の解決法は, どちらもプログラミングの重要な言語学的論点を持ち込む. オブジェクト間には, 計算オブジェクトが, どう変化出来, しかも同一性を保持出来るかという点に注意しなければならない. そのため, より機械的だが理論的には制御し難い, 計算の 環境モデル(environment model)の方がよく, 古い置換えモデル(1.1.5 節)を捨てることになる. オブジェクト, 変化, 同一性を扱うことの難しさは, 計算モデルに時を取り込む必要性の根本的な結果である. これらの難しさは, プログラムの並列実行の可能性を許すと大幅に増大する. ストリームの解決法は, 評価中に計算機の中で発生する事象の順序から, モデルでのシミュレートされた時を分離すると, 十分な利用が可能になる. われわれはこれを 遅延評価(delayed evaluation)という技法を使って達成しよう.
We’ve seen the power of computational objects with local state as tools for modeling. Yet, as section 3.1.3 warned, this power extracts a price: the loss of referential transparency, giving rise to a thicket of questions about sameness and change, and the need to abandon the substitution model of evaluation in favor of the more intricate environment model.
局所状態を持つ計算オブジェクトのモデル化の道具としての力を見てきた. だが, 3.1.3節で注意したように, この力には参照透明性の喪失, 同一性と変化についての山なす疑問の到来, そしてより複雑な環境モデルに近づいたために評価の置換えモデルの放棄という代価があった.
The central issue lurking beneath the complexity of state, sameness, and change is that by introducing assignment we are forced to admit time into our computational models. Before we introduced assignment, all our programs were timeless, in the sense that any expression that has a value always has the same value. In contrast, recall the example of modeling withdrawals from a bank account and returning the resulting balance, introduced at the beginning of section 3.1.1:(withdraw 25)
75
(withdraw 25)
50Here successive evaluations of the same expression yield different values. This behavior arises from the fact that the execution of assignment statements (in this case, assignments to the variable balance) delineates moments in time when values change. The result of evaluating an expression depends not only on the expression itself, but also on whether the evaluation occurs before or after these moments. Building models in terms of computational objects with local state forces us to confront time as an essential concept in programming.
状態, 同一性および変化という複雑性の下に潜む, 中心的論点は, 代入を取り入れたため, われわれの計算モデルに時(time)を認めさせられたということである. 代入を取り入れる前は, プログラムには, 値を持つ式は常に同じ値を持つという意味で, 時はなかった. それに対し3.1.1節の最初に述べた銀行口座からの払出しと, 結果の残高を返すモデルの例を思い起そう:(withdraw 25)
75(withdraw 25)
50
同じ式の連続する評価は異る値を生じている. この振舞いは, 代入文の実行(この場合は変数balanceへの代入)が, 値が変る時の一瞬 (moments in time)をかいま見させることによる. 式の評価の結果は, 式そのものに依存するだけでなく, このような瞬間の前か後に起きたかにもよる. 局所状態を持つ計算オブジェクトを使ってモデルを作ろうとすると, プログラミングの本質的な概念として, 時に立ち向わざるを得ない.
このような瞬間の前か後に起きたかにもよる. 局所状態を持つ計算オブジェクトを使ってモデルを作ろうとすると, プログラミングの本質的な概念として, 時に立ち向わざるを得ない.
プログラミングの本質的な概念として, 時に立ち向わざるを得ない.
「n = n + 1
です。」「それは『論理』と言えるのかしら?」宣言型のコードは問題の論理のみを扱い、計算結果は扱わない 問題の論理には結果など含まれていない
セキヤは一瞬、眼を見開いた。
『インクリメント』にはあまりにも慣れ親しんでいて、
『論理』ではないとか、これまで一度も考えたこともなかったからだ。ようやく意味が理解できたセキヤは悟りを開いた
禅僧のような落ち着いたトーンでサクラに言う。「なるほど先輩。確かにこれは論理ではないです。
方程式の左辺と右辺の値が異なります。」「そのとおり。これは論理ではないの。セキヤ君、もしもあなたが
数学の授業でこんな数式を答案用紙に書いて提出したらどうなるかしら?」「軽く減点されちゃいますね。
そして中学校の数学からやり直せと教師に言われてしまうでしょう。」「そうね。ありえないわ。
宣言型のコードは問題の論理のみを扱い、計算結果は扱わないの。
覚えているかしら?
問題の論理には結果など含まれていない。」「あ、そうだったですね!」論理を破壊する代入『破壊的代入』
「では、命令型プログラミングでは、何故、n = n + 1
という論理破綻が普通に起こるのかも理解できるかしら?」「これは、数学の方程式というよりも、
命令型プログラミングのn
にn+1
を代入する、という命令になっています。
だから、方程式の左辺と右辺は釣り合っていないのだと思います。」「そうね。こういう論理を破壊するような代入のやりかたを特に
破壊的代入って呼んだりするわね。
宣言型のコードの上ではやってはいけないことよ。
理由は単に論理破綻だから。」「破壊的代入ですか。」「破壊的代入は計算の命令なので命令型のコードになる。」命令型プログラミングのコードの上下左右に、同じ変数が異なる時間をもって異なる値で存在している混乱
「命令型のコードでの問題は、
『物質世界』の時間要素がコードの中に紛れ込んじゃうことよ。
n = n + 1
という方程式の
右辺にあるn
は、命令前の値。
左辺にあるn
は、命令後の値。命令前と命令後、つまり『時間』が違うの。
方程式という論理に『時間』が違う『同じ変数』があり、
=されてしまっている。」「あ、そう言えば、先輩、命令型のプログラミングのコードは、
とても単純に、上から下に順序良く順番に実行されていく、
つまり、上から下の方向に流れていく、という『フロー』でしたけど、
これも上と下では命令前と後なので『時間』が違うことになりますね。」「そう、全くそのとおりね。
n = n + 1
と命令してみる。その下の行で、
n = 9
と命令してみる。
上で命令した後、下で命令するので、もちろん時間が異なるわ。」「命令型プログラミングでそういうのはいつも無意識に普通にやります。」「n
と言う同じ変数なのに、
コードの左右で時間が異なる、
コードの上下で時間が異なる、
コードの上下左右で時間が異なる、
そしてその上下左右の時間それぞれで値が異なる。命令型のコードの上下左右で、同じ変数が異なる時間をもって
異なる値をもって存在しているという混乱。」セキヤは思い当たることがあったので、
特訓の復習内容からフレーズをひっぱりだした。
「先輩、このことって
フローがバグの元凶であるのと同様に、状態変数もバグの元凶
っていうやつのことですね?」「ああそうそう、今それを言おうと思ったのよ。
命令型のコードで、変数の破壊的代入をしていくのが状態変数ということ。
そもそも、『状態』っていうのはなんのことか?というと、
時間変化しながらその時々の値が違うっていう意味だから。」「先輩、状態変数がバグの元凶になる、
っていう理由についてもうちょっと知りたいです。」「そうね、命令型のコードで時間変化する状態変数の問題は、
そのものずばり、命令型のコードの上下左右の位置によって、
時間が違う、値が違うってことなのね。だってね、パット見て、n = n + 1
この左辺と右辺の同じi
の『時間』が違うってことがわかる?」「うーん、これだけならなんとなくわかるかもしれません。」「なんとなくとか無意識には理解しながらやってるでは全然ダメなのよ。」「多分そうなんでしょうね。」「だって、このi
はこの式の部分だけには留まらず、
コードのあっちへ行ったり、こっちへ行ったり、そのあちこちで、
あらゆる場所で破壊的代入が繰り返される運命なんでしょ?」「そうですね。」「命令型のコードのありとあらゆる場所で、
この同じi
が所属する時間が異なり、値が異なる。
おまけに、他のs
っていう破壊的代入が繰り返される状態変数があって、
そのs
の時間もまったくi
とは無関係に独立して存在する。
こういうi
とかs
みたいにそれぞれバラバラに
お互い共有のしようもない時間をもって変化し続ける
状態変数が無数に存在することになる。
セキヤ君、あなたはこの状況をコントロールしていると言えるかしら?」「先輩、そんなのは絶対無理です。」「命令型のコードで時間変化する状態変数っていうのは、
コントロールなんてできない存在だ、
ってもう最初の最初で認識しておいたほうがいいわね。」
「n = n + 1 は論理破綻」か?
さて、「宣言型」の話が長くなってしまいましたから、次は軽く済ませましょう。
なるほど先輩。これは確かに論理ではないです。方程式の左辺と右辺の値が異なります。(……)宣言型のコードは問題の論理のみを扱い、計算結果を扱わないの。 (p. 144)
既にAmazonのレビューで指摘されている通り、命令型プログラミング言語でのn = n + 1というステートメントは、等式・方程式ではありません。そもそも=は等価性ではなくassignmentを表しており、また左辺のnは場所・記憶域を、右辺のnはそこに格納された値を指しています4。つまるところ、命令型プログラミング言語でのn = n + 1は端から方程式でもなんでもないので、登場人物セキヤによって「論理ではない」と言われるいわれもないのです。記号が←でありさえすれば、n ← n + 1となって、このような誤解を産まなかったのかもしれません。
こうしてみると、登場人物サクラが力説する
命令型のコードでの問題は、『物質世界』の時間要素がコードの中に紛れ込んじゃうことよ。n = n + 1という方程式の右辺にあるnは命令前の値。左辺にあるnは、命令後の値。命令前と命令後、つまり『時間』が違うの。方程式という論理に『時間』が違う『同じ変数』があり、=とされてしまっている(p. 145)
という主張がまったくの的外れであることも明らかになります。まずそもそもこのコードは方程式ではありません。しかも、左右でnの指示するものが異なっているのであり5、左辺はあくまで「場所」であって「命令後の値」なのではありません。むしろ両辺のnは同じ時間に属しています。ある時点でのある領域と同時にそこに収納されている値が取り扱われているのですから6。
なお、関数型のコードとして見た場合にも、これが「方程式」ではなく項書換えシステムの書き換え規則n → n + 1であるという点はDay2のレビューに述べたとおりです。
こういう論理を破壊するような代入のやり方を特に破壊的代入って呼んだりするわね。(p. 144)
……そういうことじゃないと思います。
「これは、数学の方程式というよりも、
命令型プログラミングのn
にn+1
を代入する、という命令になっています。
だから、方程式の左辺と右辺は釣り合っていないのだと思います。」
We can go further in structuring computational models to match our perception of the physical world. Objects in the world do not change one at a time in sequence. Rather we perceive them as acting concurrently – all at once. So it is often natural to model systems as collections of computational processes that execute concurrently. Just as we can make our programs modular by organizing models in terms of objects with separate local state, it is often appropriate to divide computational models into parts that evolve separately and concurrently. Even if the programs are to be executed on a sequential computer, the practice of writing programs as if they were to be executed concurrently forces the programmer to avoid inessential timing constraints and thus makes programs more modular.われわれは更に, 計算モデルを, われわれの物理世界の概念に一致させる構造化に進むことが出来る. 世界にあるオブジェクトは, 一時に一個ずつ順々に変るわけではない. それらはむしろ, 並列的に(concurrently)—一斉に起きると思っている. 従ってシステムを, 並列的に動く計算プロセスの集りとしてモデル化するのが自然なことが多い. モデルを, 別々の局所状態を持つオブジェクトを使って組織化することで, プログラムを部品化出来たのと同様に, 計算オブジェクトを別々に, しかも並列的に進化する部分に分割するのも適切であることが多い. プログラムは逐次型計算機で実行することになるにしても, プログラムを並列的に実行されるものとして書く習慣は, プログラマに非本質的な時の制約を避けさせ, プログラムをより部品化的にさせる.
『物質世界』全部まるごとひとつの『まとまり』にしてバージョンナンバーをつけたら?それは『時刻』になる
「セキヤ君、この私たちが暮らす、『物質世界』には、
バージョンナンバーがあるのは知ってる?」「え?どういうことですか?
OSやアプリのバージョンとかあるのは知ってますけど、
『物質世界』のバージョンですか?」「『時刻』よ。」
「あ。」「『物質世界』全部まるごとひとつの『まとまり』にして
バージョンナンバーをつけたものが『時刻』よ。」
World@2015/07/12-14:32:00
World@2015/07/12-14:32:01
World@2015/07/12-14:32:02
World@2015/07/12-14:32:03
World@2015/07/12-14:32:04
表計算アプリのA1…..B1…..は、すべて同じ『時刻』という世界のバージョンナンバーを共有しているイミュータブルなデータ
関数型プログラミングで、
動的でミュータブルなGUIという『物質世界』を取り扱うためには、
この『物質世界』のイミュータブルなバージョンナンバーである、
『時刻』という考え方に着目する、
というより、論理的に、道理として、着目することになる。」「なるほど、大変興味深いです。」「表計算アプリのA1…..B1…..というUIは、
その『物質世界』全部まるごとひとつの『まとまり』のうちの
ごく一部の部品である、ということになるわよね?」「ああそうなるのかあ。」「つまり、表計算アプリのA1…..B1…..は、
すべて同じ『時刻』という世界のバージョンナンバーを共有している
イミュータブルなデータね。表計算アプリのA1…..B1…..は、すべての『時刻』において、
同じ『時刻』という世界のバージョンナンバーを共有している。
あたりまえのように聞こえちゃうけれども、
宇宙の構造として原理的にそうなっているわけ。」
A1@14:32:00 B1@14:32:00
A1@14:32:01 B1@14:32:01
A1@14:32:02 B1@14:32:02
A1@14:32:03 B1@14:32:03
A1@14:32:04 B1@14:32:04
「UIは、『物質世界』全部まるごとひとつの
『まとまり』のうちのごく一部の部品で、
『時刻』という『まとまり』のバージョンナンバーを共有している
のですか。なるほどなあ。」
残念ながら, 代入で取り込んだ複雑性は, 並列性の前には, 更に問題になる. 並列実行は, 世界が並列に動いているからか, 計算機がそうだからかで, われわれの時の理解を更に複雑にしている.
3.5 Streams
We’ve gained a good understanding of assignment as a tool in modeling, as well as an appreciation of the complex problems that assignment raises. It is time to ask whether we could have gone about things in a different way, so as to avoid some of these problems. In this section, we explore an alternative approach to modeling state, based on data structures called streams. As we shall see, streams can mitigate some of the complexity of modeling state.
3.5 ストリーム
モデル化の道具としての代入について十分理解し, 代入が惹き起す複雑な問題も認識した. これらの問題の幾分かを回避するため, 別の方向へいった方がよかったか考えてみよう. 本節では, 状態をモデル化する, ストリーム (streams)というデータ構造に基づいた, もう一つの解決法を調べてみる. すぐ分るように, ストリームは状態のモデル化の複雑さの幾分かを軽減する.
Let’s step back and review where this complexity comes from. In an attempt to model real-world phenomena, we made some apparently reasonable decisions: We modeled real-world objects with local state by computational objects with local variables. We identified time variation in the real world with time variation in the computer. We implemented the time variation of the states of the model objects in the computer with assignments to the local variables of the model objects.
少し後戻りして, この複雑さがどこから来たか反省しよう. 実世界の現象をモデル化しようとして, 明らかに合理的な決定をいくつかした: 局所状態を持つ実世界のオブジェクトを, 局所変数を持つ計算オブジェクトでモデル化した. 実世界の時間変化を計算機内の時間変化と同一視した. モデルオブジェクトの状態の時間変化を, 計算機内では, モデルオブジェクトの局所変数への代入で実装した.
実世界の時間変化を計算機内の時間変化と同一視した
モデルオブジェクトの状態の時間変化を, 計算機内では, モデルオブジェクトの局所変数への代入で実装した.
Is there another approach? Can we avoid identifying time in the computer with time in the modeled world? Must we make the model change with time in order to model phenomena in a changing world? Think about the issue in terms of mathematical functions. We can describe the time-varying behavior of a quantity x as a function of time x(t). If we concentrate on x instant by instant, we think of it as a changing quantity. Yet if we concentrate on the entire time history of values, we do not emphasize change – the function itself does not change.52
(52 Physicists sometimes adopt this view by introducing the “world lines” of particles as a device for reasoning about motion. We’ve also already mentioned (section 2.2.3) that this is the natural way to think about signal-processing systems. We will explore applications of streams to signal processing in section 3.5.3.)
これ以外の解決法があるだろうか. 計算機内の時をモデル世界の時と同一視するのを避けることは出来るだろうか. 変化する世界の現象をモデル化するのに, モデルを時と共に変化させなければならないか. これらの論点を数学関数を使って考えてみよう. 量xの時間変化する振舞いを, 時の関数x(t)と書くことが出来る. xを時刻時刻に注目すれば, それを変化する量だと思う. しかし値の全時間の歴史に注目すれば, 変化を強調しない—関数それ自身は変らない.52
(52 物理学者は運動に関する推論の道具として, 粒子の 「世界線」を導入することでこの視点を採用する時がある. われわれは(2.2.3 節で)これは信号処理システムを考える自然な方法であると述べた. 3.5.3節でストリームの信号処理への応用を述べる.)
物理学者は運動に関する推論の道具として, 粒子の 「世界線」を導入することでこの視点を採用する時がある.
これらの論点を数学関数を使って考えてみよう.
量x
の時間変化する振舞いを,
時の関数x(t)
と書くことが出来る.
x
を時刻時刻に注目すれば, それを変化する量だと思う.
しかし値の全時間の歴史に注目すれば, 変化を強調しない—関数それ自身は変らない.52
関数それ自身は変らない.
If time is measured in discrete steps, then we can model a time function as a (possibly infinite) sequence. In this section, we will see how to model change in terms of sequences that represent the time histories of the systems being modeled. To accomplish this, we introduce new data structures called streams. From an abstract point of view, a stream is simply a sequence. However, we will find that the straightforward implementation of streams as lists (as in section 2.2.1) doesn’t fully reveal the power of stream processing. As an alternative, we introduce the technique of delayed evaluation, which enables us to represent very large (even infinite) sequences as streams.
時を離散ステップで測るなら, 時間関数を(無限かも知れぬ)並びとしてモデル化出来る. 本節ではモデル化しようとするシステムの時間史を表現する並びを使い, 変化をモデル化する方法を見よう. そのためにストリーム (streams)という新しいデータ構造を取り入れる. 抽象の視点からはストリームは単なる並びである. しかしストリームを(2.2.1節のように)リストとして簡明直截に実装しても, ストリーム処理の力を十分に発現出来ない. その代り 遅延評価(delayed evaluation)の技法を取り入れよう. それを使えば非常に長い(無限でさえある)並びでもストリームとして表現出来る.
In general, we can think of delayed evaluation asdemand-driven'' programming, whereby each stage in the stream process is activated only enough to satisfy the next stage. What we have done is to decouple the actual order of events in the computation from the apparent structure of our procedures. We write procedures as if the streams existed
all at once” when, in reality, the computation is performed incrementally, as in traditional programming styles.
一般に遅延評価は 「要求駆動」プログラミングと考えることが出来る. ストリーム処理の各段階は次の段階を満足させるのに十分なだけ起動される. これまでやったのは計算における事象の実際の順を, 手続きの見かけの構造と 切り離すことである. われわれは伝統的なプログラミングスタイルでのように, ストリームがあたかも「みんな一緒に」存在したかのように手続きを書くが, 実際は計算が漸進的に実行される.
60 Eratosthenesは紀元前三世紀のアレキサンドリアギリシャの哲学者で, 地球の周囲の長さを初めて正確に測ったので有名である. 夏至の日の正午の影を観測して計算した. Eratosthenesの篩は, 古典的ではあるが, 特別目的のハードウェア「篩」の基礎を作った. それは最近まで大きな素数を探す, 存在する最も強力な道具であった. 70年代からはしかし, 1.2.6節で論じた 統計的技法の発展で置き換えられている.
A functional-programming view of time
Let us now return to the issues of objects and state that were raised at the beginning of this chapter and examine them in a new light. We introduced assignment and mutable objects to provide a mechanism for modular construction of programs that model systems with state. We constructed computational objects with local state variables and used assignment to modify these variables. We modeled the temporal behavior of the objects in the world by the temporal behavior of the corresponding computational objects.
Now we have seen that streams provide an alternative way to model objects with local state. We can model a changing quantity, such as the local state of some object, using a stream that represents the time history of successive states. In essence, we represent time explicitly, using streams, so that we decouple time in our simulated world from the sequence of events that take place during evaluation. Indeed, because of the presence of delay there may be little relation between simulated time in the model and the order of events during the evaluation.
時の関数型プログラミング的視点
本章の初めで持ち上がったオブジェクトと状態の論点に戻り, 新しい光でそれらを調べて見よう. 状態を持つシステムをモデル化するプログラムの部品化的構成の機構を提供するものとして, 代入と可変オブジェクトを取り入れた. 局所状態変数を持つ計算オブジェクトを構成し, これらの変数を修正するのに代入を使った. 世の中のオブジェクトの時間的振舞いを, 対応する計算オブジェクトの時間的振舞いでモデル化した.
ストリームが局所状態を持つオブジェクトをモデル化するもう一つの方法を提供することを見てきた. あるオブジェクトの局所状態のような変りゆく量を, 順次の状態の時間的歴史を表現するストリームを使ってモデル化する. 要するにストリームを使って時を明確に表現し, シミュレート中の時を評価中に起きる事象の並びから切り離す. 実際delayが存在するので, モデルのシミュレートされた時と評価中の事象の順の間にはあまり関係がない.
Stream-withdraw implements a well-defined mathematical function whose output is fully determined by its input. Suppose, however, that the input amount-stream is the stream of successive values typed by the user and that the resulting stream of balances is displayed. Then, from the perspective of the user who is typing values and watching results, the stream process has the same behavior as the object created by make-simplified-withdraw. However, with the stream version, there is no assignment, no local state variable, and consequently none of the theoretical difficulties that we encountered in section 3.1.3. Yet the system has state!
This is really remarkable. Even though stream-withdraw implements a well-defined mathematical function whose behavior does not change, the user’s perception here is one of interacting with a system that has a changing state. One way to resolve this paradox is to realize that it is the user’s temporal existence that imposes state on the system. If the user could step back from the interaction and think in terms of streams of balances rather than individual transactions, the system would appear stateless.73
stream-withdrawは出力が入力によって完全に決定される, 明確に定義された数学的関数を実装する. しかし入力\linebreakamount-streamが, 利用者が入力した順次の値のストリームであり, 結果としての残高のストリームが表示されているとしよう. すると値を入力し, 結果を眺めている利用者の見え方からは, ストリーム処理はmake-simplified-withdrawで作り出されたオブジェクトと同じ振舞いをする. ところがストリーム版には代入も局所状態変数もない. 従って3.1.3節で直面した理論的困難は一つもない. しかもシステムには状態が存在する!
これは実に注目すべきことだ. stream-withdrawが, その振舞いが変化しない, 明確に定義された数学的関数を実装したとしても, ここでの利用者の認識は, 変化する状態を持つシステムと対話しているという認識である. この矛盾を解く一つの方法は, システムに状態を持たせるのは, 利用者の時間的存在であると認めることである. 利用者が対話から一歩下って個々の取引きではなく, 残高のストリームを使って考えるとすれば, システムは状態なしに見えてくる.73
from the perspective of the user
利用者の見え方からは
Yet the system has state! This is really remarkable.
しかもシステムには状態が存在する! これは実に注目すべきことだ
Similarly in physics, when we observe a moving particle, we say that the position (state) of the particle is changing. However, from the perspective of the particle’s world line in space-time there is no change involved.
物理学でも同様で, 動いている粒子を観測する時, われわれは粒子の位置(状態)は変化しているという. しかし, 粒子の時間空間の 世界線の視点からは, 変化はない.
ここでの利用者の認識は, 変化する状態を持つシステムと対話しているという認識である. この矛盾を解く一つの方法は, システムに状態を持たせるのは, 利用者の時間的存在であると認めることである.
システムに状態を持たせるのは, 利用者の時間的存在であると認める
Our traffic with the subject matter of this book involves us with three foci of phenomena: the human mind, collections of computer programs, and the computer. Every computer program is a model, hatched in the mind, of a real or mental process. These processes, arising from human experience and thought, are huge in number, intricate in detail, and at any time only partially understood. They are modeled to our permanent satisfaction rarely by our computer programs. Thus even though our programs are carefully handcrafted discrete collections of symbols, mosaics of interlocking functions, they continually evolve: we change them as our perception of the model deepens, enlarges, generalizes until the model ultimately attains a metastable place within still another model with which we struggle. The source of the exhilaration associated with computer programming is the continual unfolding within the mind and on the computer of mechanisms expressed as programs and the explosion of perception they generate. If art interprets our dreams, the computer executes them in the guise of programs!
本書の主題との関係でわれわれは三つの現象: ひとの心, 計算機プログラムの集積と計算機に関る. 計算機プログラムは心に生れた物理的, 心理的プロセスのモデルである. ひとの経験と思考から生じたこれらのプロセスは数において巨大であり, 細部において複雑であり, 一時には部分的にしか理解されない. それらは計算機プログラムによって永遠に満足出来るようにモデル化されることは殆んどない. 従ってプログラムが注意深く細工した離散的な記号の集積, 相互作用する関数の組合せであっても, 絶えず進化する. われわれはモデルの認知が深まり, 広まり, 一般化するにつれ, まだ苦闘中の他のモデルの間で, モデルが究極的に準安定な場所を得るまで変化を続ける. 計算機プログラミング対応した陽気な気分の源泉は, プログラムとして表現した機構の心の中と計算機の上での絶えまなき解明と, それらが生成する認知の拡大である. 技術が夢を解釈するなら, 計算機はプログラムを装って夢を実行するであろう!
(https://github.com/minghai/sicp-pdf による翻訳)
この本の主題は 3 つの事象に焦点を当てます。人の心、コンピュータプロ
グラムの集合、そしてコンピュータです。全てのコンピュータプログラムは人
の心の中で生まれる現実の、または精神的な過程のモデルです。これらの過程
は人の経験と思考から浮かび上がり、数はとても多く、詳細は入り組んで、い
つでも部分的にしか理解されません。それらはコンピュータプログラムにより
稀にしか永遠の充足としてモデル化されることはありません。従って、例え私
達のプログラムが注意深く手作りされた別個の記号の集合だとしても、連動す
る機能の寄せ集めだとしても、それらは絶えず発展します。私達のモデルの知
覚がより深まるにつれ、増えるにつれ、一般化されるにつれ、モデルが究極的
に準安定な位置に逹っするまで変更を行い、その中には依然として私達が格闘
xivするモデルが存在します。コンピュータプログラミングに関連する歓喜の源は
プログラムとして表現された仕組みの心の中とコンピュータ上で絶え間無く続
く発展であり、それにより生まれる知力の爆発です。もし技巧が私達の夢を解
釈するならば、コンピュータはプログラムとして現わされるそれらを実行する
のです!
three foci of phenomena
三つの現象