CTM読書メモ (WIP)

コンピュータプログラミングの概念・技法・モデル

2

2.4.2.

• 意味言明: (<s>, E) <s> = 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 宣言的スタック

• 関数型プログラミング風」の書き方

  {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つの操作しかない

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

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

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

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モジュールでデータをマーシャライズできるお

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

=======

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

{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 <s> 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の値は明らかではない

  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のアクターみたいに使える

• 生成方法

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の定義

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

任意のゲートつくるやつ

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

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

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を入力するクロック

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を使って実装できる

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したいじゃん？
  終了条件を監視するとできる

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

or

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するほうほう

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.