CTM読書メモ (WIP)

[コンピュータプログラミングの概念・技法・モデル](http://www.amazon.co.jp/dp/4798113468)



# 2

### 2.4.2.
- 意味言明: (&lt;s&gt;, E)   &lt;s&gt; = statement
- 単一代入格納域σ  ヒープ領域？
- 環境E: {識別子 -> 変数} の写像
- 実行状態: (ST, σ) ;; (ST = 意味言明のスタック)
- 計算: (ST1, σ1) -> (ST2, σ2) -> ...
- 環境の限定: 元の環境のサブセット + ローカル変数

### 2.4.3.
- OzではProcでクロージャ作れる？？
- capture: closureから外部の変数を参照する事 (C++のラムダ記法みたい)
- 束縛された識別子出現と束縛された変数の違い
  - 「格納域の中の変数参照 = ポインタ」

## 2.5. メモリ管理
### 2.5.1.
末尾呼び出しでメモリ領域節約できる

### 2.5.2. メモリのライフサイクル
- 参照差されない領域は解放していい
- メモリ管理エラー: dangling reference, メモリリーク

## 2.5.3 GC
- 第一段階: 何がアクティブメモリかを判定
  - root set: ポインタの初期集合から到達可能なデータの集合 (=~ 意味スタック)
- 第二段階: アクティブ:イナクティブ領域のデフラグ、圧縮

### 2.5.4. GCでの注意事項
- メモリリークを避ける
- 外部資源の管理

### 2.5.5. GC in Mozart
- 双空間複写アルゴリズム
- 弱点
  - メモリ半分しか使えない
  - 長寿データも一々コピーしちゃう

## 2.6. 核言語から実用言語へ
### 2.6.1. 糖衣構文
- `local A in A="Taro" X=person(name: A) end`  は `person(name: "Taro")` の糖衣構文
- 暗黙の変数初期化
  - `{Browse 10}` は `local X = 10 in {Browse X} end`
  - `local person(name: A) = P in ... end` すると、自動で `A = P.name` の代入が行われる
- 入れ子マーカ

### 2.6.2. 関数
- `fun {F X} ... Foo end` は `proc {F X ?R} ... R = Foo end` の糖衣構文
- Mozartにはreturnは無い。最後の式がreturnされる

### 2.6.3. 対話的インタフェース
- declare
- Browse


## 2.7. 例外
- エラー局限原則 (error confinement principle)
- try/catch/finally, raise がある
- catch でエラーをパターンマッチできる

## 2.8. その他
### 2.8.1. 関数型言語
- Hudakのサーベイ
- 宣言型モデルに以下の制約を加えると純粋関数型言語になる
  - 変数の宣言と束縛は常に同時
  - `proc` ではなく `fun` 使う
- ↑こういう言語は正格関数型モデル(strict functional model)と呼ばれる

### 2.8.2. 単一化と内含
- 単一化は対象な操作
  - `X = 25` と `25 = X` は同値
  - 内含/反駁 `==`/`\=`



# 3 宣言的プログラミング技法

### 3.4.2. リスト
- 再帰的に処理できる
- 何も考えずに再帰書くと、スタックが深くなってメモリ食う
  - 適切に末尾再帰とかやると、状態変換でループ処理にできる
  - アキュムレータ: ループ間の状態を引数で渡すやつ
  - 状態不変表明(state invariant): ループ間で常に真となる式。漸化式に似てる
    - 帰納法で証明できたりする
- プログラムの構造は、扱う型の定義と似た構造になる
  - 例: リストを扱うコード

### 3.4.4. 差分リスト
- Prolog由来
- 内部に２つのリストを持ち、それらの差分でリストを表現
- concat, flatten, reverse が簡単にできる????

### 3.4.5. キュー
- リストではconsは簡単だが、popを一定時間でやるのは難しい
  - 正格関数型モデル -> できない
  - 正格関数型モデル + データフロー変数 -> できる
- 償却的一定時間単用的キュー (正格関数型モデル)
  - 単用的: 作ったキューは一度しか使えない
  - キューを q(F R) となるタプルで保持
    - F, R: リスト
  - `{Append F {Reverse R}}` でリストに変換できる
- 最悪時一定時間単用的キュー (正格関数型モデル + データフロー変数)
  - 差分リストを使う
  - キューを q(N S E) となるタプルで保持
    - N: 要素数
  - 挿入前に削除できる!!!???!??!?!?
  - 処理の例
     - `{NewQueue Q1}` 後の内部状態
         - Q1: q(0 _ _)
     - `Q2 = {Queue Q1 1}` 後の内部状態
         - Q1: q(0 1|_ 1|_)
         - Q2: q(1 1|_ _)   
     - `Q3 = {Queue Q2 2}` 後の内部状態
         - Q1: q(0 1|2|_ 1|2|_)
         - Q2: q(1 1|2|_ 2|_)
         - Q3: q(2 1|2|_ _)
     - `Q4 = {Dequeue Q3}` 後の内部状態
         - Q1: q(0 1|2|_ 1|2|_)
         - Q2: q(1 1|2|_ 2|_)
         - Q3: q(2 1|2|_ _)
         - Q4: q(1 2|_ _)

- 永続的キュー
  - 最悪時(ry を永続的にするには、キューを複製できれば良い

### 3.4.6. 木
- 2分木やろう
- 木はDeleteが面倒
- 深さ優先探索 w/ スタックのほうが、幅優先探索 w/ キューよりもメモリ節約できる
- 例で、Mozartで木を描画したりパーサ作ったりしてる

## 3.5. 時間効率と空間効率
### 3.5.1. 実行時間
- 再帰の計算量は漸化式で求められる

### 3.5.2. メモリ使用量
- 瞬間アクティブメモリ量: 同時に使用するメモリの最大量
  - 意味スタックが到達可能な、格納域の全ての値/部分値のサイズの合計
- 瞬間メモリ消費量: 単位時間あたりのメモリ使用総量
  - 実行される操作毎のメモリ消費の合計 + 意味スタックのメモリ消費量
  
- 償却的計算量が安ければ、瞬間メモリ消費量増えてもOKな場合も
- 「銀行家の方法と物理学者の方法」Okasakiの本よめ [157]

## 3.6. 高階プログラミング
- 引数中に手続きがない -> 1階 ある -> 2階

### 3.6.1. 基本操作
- 手続き抽象: 任意の文を手続きに
- 汎用性: 引数に手続きを渡せる
- 具体性: 返り値に手続きを使える
- 埋め込み: データ構造の中に手続きを入れられる
  - 明示的遅延計算: データ構造の各部分を遅延計算する
  - モジュール、コンポーネント

### 3.6.2. ループ抽象
- forループを高階関数として実装できる
  - FoldRは偉い
### 3.6.3.
- Mozartでは宣言的ループ使えるんじゃ
  - 命令的ループ: Cスタイルのループ
  - 宣言的ループ: 各ループが独立。並列処理できる
- Mozarのforは値を返す式

### 3.6.4. データ構造に対する後悔プログラミング技法
- リスト: map, filter, fold, ...
- 木: 上昇型の操作はFoldRに似てる

### 3.6.5. 明示的遅延計算
- 要求駆動実行 (<-> 供給駆動実行)
  - programmed trigger
    - データフロー変数
    - 高階プログラミング

### 3.6.6. カリー化
Mozartはカリー化機能無いよ


## 3.7 抽象データ型
### 3.7.1 宣言的スタック
- 関数型プログラミング風」の書き方

  ```Mozart
  {Pop S E}  % popした要素がEに入る
  ```

### 3.7.1 宣言的辞書
- リストを使った実装: O(n)
- 木を使った実装: O(log n)
- 状態を使う実装: 償却的一定時間

### 3.7.2 単語出現頻度アプリケーション
- リストを使った実装: 620sec
- 木を使った実装:     8sec
- 状態を使う実装:     2sec

### 3.7.4 安全な抽象データ型

抽象データ型の内部実装を外から操作できないようにしたい
  - 理由) 保守性, セキュリティ

データを保護する境界を設ける
- 停留値 (stationary value)
  境界内で全ての処理を行う
- 可動値 (mobile value)
  値は安全な手続きで境界の外へ出され、安全な手続きで境界内へ戻す

### 3.7.5 安全な型を備えた宣言的モデル

「名前生成」「読み出し専用ビュー」を核言語に追加し、可動値による安全なADTを実装する
  - `{NewName <x>}`: 値に対し、ユニークな名前を生成
  - `<y> = !!<x>`: `x` の読み出し専用ビュー `y` を作成

Name型は `{NewName}`, `N1==N2` の2つの操作しかない

このようなラッパーを作り、

```Mozart
proc {NewWrapper ?Wrap ?Unwrap}
  Key = {NewName} in
  fun {Wrap X}
    {Chunk.new w(Key:X)}      
  end
  fun {Unwrap W}
    try W.Key catch _ then raise error(unwrap(W)) end end
  end
end
```

安全なスタックを実装できる

```Mozart
local Wrap Unwrap in
  {NewWrapper Wrap Unwrap}
  fun {NewStack} {Wrap nil} end
  fun {Push S E} {Wrap E|{Unwrap S}} end
  fun {Pop S E}
    case {Unwrap S} of X|S1 then E=X {Wrap S1} end
  end
  fun {IsEmpty S} {Unwrap S} == nil end
end
```

安全な木、辞書も同様に実装できる

- 安全な前の生成
  - 中央管理方式: グローバルな名前サーバ作る
  - 脱中央管理方式: 乱数とかハッシュで擬似的に一意な名前を生成
  
### 3.7.7. 資格とセキュリティ
「敵 (adversary)」: 悪意があるかもしれない実体

#### 資格 (capability)
- 1960年代に生まれた概念
- E言語: 資格を用い安全を強化
  - 値への保護に暗号化/復号化をする (sealer/unsealer)
- データ型の全ての値は資格である
  - その型の操作を行う能力を与え、その他の能力を与えない
- 資格を与える簡単な方法: 内部を操作できる手続きを与える

#### 最小特権の原則 (POLA: principle of least authority) / 知る権利 (need to know)
- 仕事をするのに最小の権利を与えろというルール
- 厳密に最小特権を求める方法はない -> 大体でおｋ

#### 資格と明示的状態
- 宣言的資格は、途中で資格を変更できない
- 明示的状態が使えるとできる

## 3.8. 宣言的でない必要物
- 実用的なプログラムには、非宣言的な操作が必要
  - ファイルIO
  - GUI:
  - 独立コンパイル

### 3.8.1. ファイルIO
- 読み込めるファイルはファイルのパス or URL
- 文字コードはISO8859-1なので注意………
- pwdわからないのでパスは絶対指定
- 余談: 仮想文字列は常に文字列の代わりに使える

### 3.8.2. GUI
- QTkつかうお

### 3.8.3. ファイルとの状態なしデータIO
<<<<<<< HEAD
- Pickleモジュールでデータをマーシャライズできるお 

  ```Mozart
  {Picle.save X FN}
  {Picle.load FNURL ?X}
  ```

=======
- Pickleモジュールでデータをマーシャライズできるお 

```Mozart
{Picle.save X FN}
{Picle.load FNURL ?X}
```

>>>>>>> YOUR_EDITION
- 束縛されていない変数を含むデータは保存できない

## 3.9. 小規模プログラム設計
- 1人で設計するほうほう

### 3.9.1. 設計方法
- 形式張らない仕様、例、テストと推論、品質、。。。

### 3.9.2. casestudy
省略

### 3.9.3. ソフトウェアコンポーネント
#### モジュールとファンクタ
- ファンクタ: 必要とするモジュールを引数に取り、新しいモジュールを返す関数
  - import, export, defineの3部分からなる
  - Mozartのファンクタはコンパイル単位
  - MOGUL (Mozrt Global User Library) を使える
- コンポーネントベースプログラミングできる

### 3.9.4. スタンドアロンプログラム
- スタンドアロンプログラムは、`export` のないファンクタ
- `ozc -x hoge.oz` でコンパイル

#### ライブラリ
- 標準ライブラリは Base, System のみ
- System はREPLでのみ読み込まれる

# 4. 宣言的並列性
- この章、「並列」と「並行」ごっちゃになってるな？？

## 4.1. データ駆動並列モデル
核言語を2段階にわけて拡張する
- スレッド `thread 
 end` を追加 -> データ駆動並列モデル
- by-need trigger `{ByNeed P X}` を追加 -> 要求駆動計算,  要求駆動並列モデル/遅延並列モデル

### 4.1.1. 基本概念
- スレッドを追加

#### インタリーブ
- 「同時に動く」には2つの意味がある
  - 言語視点: どのように振る舞うのか。インタリーブ実行か、その他か
  - 実装視点: どのように実装されるか。シングルコアでマルチスレッド実装することもある
  
#### 因果順序
- 直列実行: 全計算ステップが全順序
- 並列実行: 全計算ステップが半順序 -> 並列スレッドの各ステップの実行順序は定まらない

#### 非決定性
- 宣言的並列モデルでは、非決定性はプログラムに見えない
  - スレッド or ステップの実行順序は、実行結果に影響しないはず

#### スケジューリング
- 「単調 (monotonic)」: 準備完了のスレッドはいつでも実行可能
- 未束縛の変数を使う処理はブロックする
- 「公平 (fair)」: どのスレッドも「飢え (starvation)」させないスケジューラ

### 4.1.2. スレッドの意味
- 抽象マシンの並行処理版
  - 計算は以下のような実行状態の列
    (MST_0, σ_0) -> (MST_1, σ_1)-> ....
  - MST: ST (意味スタック)のマルチセット
  - σ:単一代入格納域
- 格納域は全スレッドで共有される

### 4.1.3. 実行例
省略

### 4.1.4. 宣言的並列性とは
- ストリーム: 未束縛の変数を使う、遅延評価の無限リスト
- 部分停止: ストリームが終了すれば停止するプログラム
- 論理的同値: 制約 `x=foo(y w) && y=z` と制約 `x=foo(z w) && y=z` は論理的同値

#### 宣言的並列性
並列的プログラムが宣言的であるとは、任意の入力に対し、

  - 全て、停止しない
  - いずれ部分停止になり、論理的に同値な結果を出す

のどちらかになる事をいう
(「目に見える非決定性が存在しない」とも言える)

#### 失敗
- 並列的プログラム内で失敗があると、非決定性が生じる
- 以下のコードは単一化に失敗するが、そのときのXとYの値は明らかではない

  ```Mozart
  thread X=1 end
  thread Y=2 end
  thread X=Y end  
  ```

- 対処法: 失敗しうるコード、全部 `try ... catch` で囲む

## 4.2 スレッドプログラミングの基本的技法

### 4.2.1. スレッド生成
- Mozartではthreadは式 (値を返す)

### 4.2.2. スレッドとブラウザ
- `{Browse Foo}` は、`Foo` がストリームの場合、漸増的に表示してくれる

### 4.2.3. データフロー計算
- データフロー変数を使うと楽に並行処理できるお
- Mozartのスレッドは低コストなのでガンガン使える
  - 当然、シングルコアではシングルスレッドで全部やったほうが低コスト

### 4.2.4. スケジューリング
- タイムスライス: スレッドの実行に割り当てられる時間
- 各スレッドはラウンドロビン方式で実行される
- タイムスライスの割り当て方法は2つ
  - 計数法
    - スレッドの計算ステップに対応した時間を割り当てる
    - 計算コストが高いが、リアルタイムアプリケーションとかで使う
  - タイマー法
    - 全スレッドに同じ時間を与える
    - 大多数ののシステムはこっち
    
- スレッドに優先順位をつける
- 子スレッドの優先順位は親スレッドと同じ
  - 重要なスレッドをforkした時に優先度が低いと、致命的バグになりうる
  
- タイムスライスの長さ
  - 短すぎる -> スイッチングコスト大
  - 長すぎる -> 大量のスレッド捌けない
  - MozartはOSの割り込みタイマーつかう -> 60-100 Hz

### 4.2.5. 協調性並列性と競合的並列性
- 協調性並列性
  - 各ワーカの目的が同じ
  - スレッドがよく使われる  
-　競合的並列性
  - 各ワーカの目的が別々
  - プロセスがよく使われる

### 4.2.6. スレッド操作
- Thread
  - this, state, suspend, resume, preempt, terminate, injectException, setPriority, setThisPriority
- Property
  - get, put
- Threadの名前 (Name型) は、スレッド内で `{Thread.this}` しないと得られない


## 4.3. ストリーム
- ストリームは「能動的オブジェクト」
- ロックやmutexなしで並行処理できて便利
- 別名 "flow-based programming"

### 4.3.1. 基本的生産者 / 消費者
- 生産者: ストリーム生成
- 消費者: ストリーム読む
  - 決して破壊的操作するわけじゃない -> 複数の消費者が一つのストリームを読める

### 4.3.2. 変換器とパイプライン
- 変換器 (transducer): 入力ストリームを変換し出力する
- パイプライン
  - source: パイプラインの最初の生産者
  - sink: パイプラインの最後の消費者

### 4.3.3. 資源管理
- 生産者のスピードが早過ぎると、メモリ食いつくす！！
- フロー制御
  - 要求駆動並列性によるフロー制御
     - 消費するときに生産
     - 遅い
  - 有界バッファによるフロー制御
     - n個のデータをバッファする
     - m個消費されるたびに、m個の生産を要求する
     - n=0 -> 遅延実行, n=Inf -> 性急実行
  - スレッドの優先順位によるフロー制御
     - 生産者 / 消費者の優先順位を変えて制御
     - 最悪で危険なので使っちゃダメ！

### 4.3.4. ストリームオブジェクト
- オブジェクト: 値と操作をまとめた実体
- ストリームオブジェクト
  - 再帰的に実行され続けるスレッド
  - 他のストリームオブジェクトとストリームを通じて通信する
  - Erlangのアクターみたいに使える
  
- 生成方法

```Mozart
proc {StreamObject S1 X1 ?T1}
  case S1
  of M | S2 then N X2 T2 in
    {NextState M X1 N X2}
    T1 = N | T2
    {StreamObject S2 X2 T2}
  [] nil then T1 = nil end
end
declare S0 X0 T0 in
thread
  {StreamObject S0 X0 T0}
end
```
- S0: 入力ストリーム
- T0: 出力ストリーム
- X0: 初期状態

### 4.3.5 デジタル論理回路のシミュレーション
- 同期的プログラミング: ストリームオブジェクトの有向グラフを使うプログラミング
- 線形連鎖: 説明ない……？？？？？？
- ストリームオブジェクトで論理ゲートを表現できる

NOTゲートのオブジェクトを作るNotGの定義

```Mozart
local
  fun {NotLoop Xs}
    case Xs
    of X | Xr then
      (1 - X) | {NotLoop Xr}
    end
  end
in
  fun {NotG Xs}
    thread {NotLoop Xs} end
  end
end
```

任意のゲートつくるやつ

```Mozart
fun {GateMaker F}
  fun {$ Xs Ys}
    fun {GateLoop Xs}
      case Xs # Ys of (X | Xr) # (Y | Yr) then
        {F X Y} | {GateLoop Xr Yr}
      end
    end
  in
    thread {GateLoop Xs Ys} end
  end
end
```

↑使ってほかのゲートつくる

```Mozart
AndG  = {GateMaker fun {$ X Y} X * Y end}
OrG   = {GateMaker fun {$ X Y} X + Y - X * Y end}
NandG = {GateMaker fun {$ X Y} 1 - X * Y end}
NorG  = {GateMaker fun {$ X Y} 1 - X + Y - X * Y end}
XorG  = {GateMaker fun {$ X Y} X + Y - 2 * X * Y end}
```

フルアダーとか作れるねんで


#### 直列論理
- 組合せ回路では情報を保存できない
- フリップフロップとか作りたい
  - 単純にゲートつなげると、無限ループでデッドロックしちゃう
  - 遅延ゲート使う
    ```
    fun {DelayG Xs} 0 | Xs  end
    ```
  - これでラッチつくれる（省略

#### クロッキング
1Hzで1を入力するクロック

```Mozart
fun {Clock}
  fun {Loop B}
    {Delay 1000} B | {Loop B}
  end
in
  thread {Loop 1}
end
```

#### 言語抽象
- `gate` マクロみたいなの作れるといいのに
  - それMozartのパーサ生成ツール `gump` を使えばできるよ
  - Haskell, Prologは構文を拡張できるので同様のことができる



## 4.4. 宣言的並列モデルを直接使うこと
ストリーム以外でも宣言的並列モデルを実現できる

### 4.4.1. 順序決定並列性
宣言的プログラムでは、計算の内容を記述するが、順番を決めない事が多い
-> 計算順序がわからない

- プログラマが計算順序調べて頑張る
  - 効率いい
  - 間違えると動かない
- データフロー変数を使う
  - 簡単
  - ブロックしそうな処理はスレッドを生成して実行  

### 4.4.2. コルーチン
- `Spaws`, `Resume`によって、手動で制御できるスレッド的なもの
- 手動制御、ミスると「餓死」する
- Threadを使って実装できる

```Mozart
fun {Spawn P}
PId in
  thread
    PId = {Thread.this}
    {Thread.suspend PId}
    {P}
  end
  PId
end
proc {Resume Id}
  {Thread.resume Id}
  {Thread.suspend {Thread.this}}
end
```

### 4.4.3. 並列的合成
- thread, joinしたいじゃん？
終了条件を監視するとできる

```Mozart
local X1 X2 X in
  thread ...  X1 = unit end
  thread ...  X2 = X1 end
  thread ...  X = X2 end  
  {Wait X}
end
```

or

```Mozart
local X1 X2 X3 Done in
  thread ...  X1 = unit end
  thread ...  X2 = unit end
  thread ...  X3 = unit end
  thread
    {Wait X1} {Wait X2} {Wait X3}
    Done = unit
  end    
  {Wait Done}
end
```


#### 制御抽象
引数を持たない手続きのリストをjoninするほうほう

```Mozart
proc {Barrier Ps}
  fun {BarrierLoop Ps L}
    case Ps
    of P | Pr then M in
      thread {P} M = L end
      {BarrierLoop Pr M}
    [] nil then L
    end
  end
  S = {BarrierLoop Ps unit}
in
  {Wait S}
end
```

## 4.5 遅延実行

### 4.5.1. 要求駆動並列モデル
- データ駆動並列モデル + by-needトリガ
- by-needトリガ: 「必要とされる」をトリガ
- Mozartのfunctorはby-need実行

### 4.5.2. 宣言的計算モデル
- モデル
  - 正格 + 直列: 正格関数型 (Scheme, ML)
  - 正格 + 直列 + データフロー変数: 宣言的モデル (Prolog)
  - 正格 + 並列 + データフロー変数: データ駆動並列モデル
  - 遅延 + 直列: 遅延関数型 (Haskell)
  - 遅延 + 直列 + データフロー変数: 遅延関数型
  - 遅延 + 並列 + データフロー変数: 要求駆動並列モデル

### 4.5.3. 遅延ストリーム
遅延実行で無限リスト作れる

### 4.5.4. 有界バッファ
ストリーム、バッファあると要求時のレイテンシ減らせる

### 4.5.5. ファイルを遅延的に読む

### 4.6.6. ハミング問題
- 要求駆動並列性の古典的問題
- `2^a * 3^b * ...` で表される集合の、最初のn個を求める問題

### 4.5.7. 遅延リスト操作
- リストの基本操作は全部遅延化できる

### 4.5.8. 永続的キューとアルゴリズム設計
- 償却的永続的キュー
- 最悪時永続的キュー

## 4.6. 甘いリアルタイムプログラミング
- 一秒に一回増えるストリームでティッキング

## 4.7. Haskell
省略

## 4.8. 宣言的プログラミンの限界
### 4.8.1. 効率性
- 大きなデータを漸増的に処理するプログラム、効率的にコンパイルできない
- 宣言的プログラミングでは、メモ化するとインタフェースも変わる
- 表現力低いので辛い

### 4.8.2. モジュラ性
- プライベーーと変数とか無いし
- プログラムを計器化 (instrumenting) できない
  - 呼び出し回数測ったり

### 4.8.3. 非決定性
### 4.8.5. 正しいモデル選ぼう
最小表現力規則に従うとよい


### 4.8.7. 異なるモデルを一緒に使う
- インピーダンスマッチング、関心の分離

## 4.9 その他
- 並列処理で例外起きると決定性崩れる
- 遅延実行で投機的実行するとよさそう
- データフロー変数を通信チャネルとして使える



# 5. メッセージ伝達並列性

- ポートとストリーム使う
- ストリームでは多対一通信できない


# 6. OOP

# 7.