LoginSignup
0

More than 5 years have passed since last update.

CTM読書メモ (WIP)

Last updated at Posted at 2014-09-20

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

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) endperson(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 endproc {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 = 2525 = X は同値
    • 内含/反駁 ==/\=

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

3.4.2. リスト

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

3.4.4. 差分リスト

  • Prolog由来
  • 内部に2つのリストを持ち、それらの差分でリストを表現
  • 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)

  • 仕事をするのに最小の権利を与えろというルール
  • 厳密に最小特権を求める方法はない -> 大体でおk

資格と明示的状態

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

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.

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
0