【学習メモ】計算機プログラムの構造と解釈

1. 手続きを用いた抽象化の構築

プログラミングの要素

式

再帰方程式（recursion equation）
- 論理表現についての推論を定式化するもの
- 記号式の再帰方程式とそれらの機械による演算(McCarthy., 1960)
- 再帰的（recursive）
  - 手続きがそれ自身を使って定義されていること
プログラミング言語における3つのメカニズム
- 基本要素
  - 最も単純な要素
- 結合
  - 複合要素をより基本要素から構築する手段
- 抽象化
  - 複合要素に名前をつけ、要素として扱うための手段

組合の評価

評価規則
- 組合の評価 1. 組合の部分式を評価する 2. 部分式の左端（演算子）の値となっている手続きを、引数（被演算子）に適用する
- 本質的には再帰的となる
- 木構造で表現できる
  - 木の根に向かって値を伝えていく事を、木の集積（tree accumulation）と言う
  - 1を繰り返し適用することで、ある点で評価する対象が、組合ではなく数値や組み込み演算子、その他の名前といった基本要素となる
    - 基本要素を扱うための規定
      - 数字の値は、それを示す値である
      - 組み込み演算子の値は機械語の列で、それに対応する操作を実行する
      - その他の名前の値は、現在の環境でその名前に関連付けられたオブジェクトである
特殊形式（special form）
- 一般評価規則に対する例外
  - define など
複合手続き（compound procedure）
- 複合演算に名前を付け、1つの手続きとして参照できるようにする
- 手続き適用の置換モデル（substitution model）
  - 複合手続きを引数に適用するには、手続き本体に出てくる仮引数を、対応する引数で置き換えそれを評価する
評価戦略
- 正規順序評価（normal-order evaluation）
  - 被演算子の評価が必要になるまでは評価を行わない
  - 未評価の被演算子と遭遇してもその評価を後回しにできる（後続の処理を続行できる）場合、評価を後回しにする
  - 遅延評価（lazy evaluation）である
- 適用順序評価（applicative-order evaluation）
  - 先に全ての被演算子を評価してから手続きを行う
  - 未評価の被演算子に遭遇する度に、それを評価する
- 正規順序評価と適用順序評価は置換によってモデル化でき、かつ正当な値を返すなら必ず同じ値になる
関数と手続きの違い
- 関数
  - 宣言的（何であるか）記述
  - 物事の属性がどうであるかについて説明する
- 手続き
  - 命令的（どうやるか）記述
  - どのように物事を行うかについて説明する

ブラックボックス抽象化

手続き抽象（procedural abstraction）
- 特定のタスクをこなす手続きがどうやって計算するかという詳細をブラックボックス化する
- 手続き定義は詳細を隠せるようになっていなければならない
  - 局所名
    - 仮引数の名前に何を選んだかをブラックボックス化する
束縛変数（bound variable）
- 名前が何であっても構わない変数
- 束縛（bind）
  - 定義に対して名前がついた変数を割り当てること
- スコープ（scope）
  - 変数が束縛されている範囲
自由変数（free variable）
- 束縛されていない変数

ブロック構造（block structure）

局所的な定義を行うため、定義をネストすること

(define (sqrt x)
 (define (good-enough? guess x)
  (< (abs (- (square guess) x)) 0.001))
 (define (improve guess x)
  (average guess (/ x guess)))
 (define (sqrt-iter guess x)
  (if (good-enough? guess x)
   guess
   (sqrt-iter (improve guess x) x)))
 (sqrt-iter 1.0 x))

レキシカルスコーピング（lexical scoping）

補助手続きの定義を内部化する際、それを囲む手続きで使用している変数を使用できる

(define (sqrt x)
 (define (good-enough? guess)
  (< (abs (- (square guess) x)) 0.001))
 (define (improve guess)
  (average guess (/ x guess)))
 (define (sqrt-iter guess)
  (if (good-enough? guess)
   guess
   (sqrt-iter (improve guess))))
 (sqrt-iter 1.0))

手続きとそれが生成するプロセス

再帰プロセス（recursive process）
- 遅延演算（deferred operation）で特徴づけられる
  - 再帰構造を最後まで展開した後に演算を行う
  - 再帰構造は実際に演算が行われる際に縮約する
- インタプリタは後で実行する演算について記録しておく必要がある
- 線形再帰プロセス（linear recursive process）
  - 遅延演算の連鎖の長さ、それを記録するための情報の量、ステップ数が$n$に対して線形に増加する再帰プロセス
反復プロセス（iterative process）
- 状態が、限られた数の状態変数（state variable）に集約されるプロセス
- ステップ数や各ステップで記録しておく必要がある情報の量は増えない
- 線形反復プロセス（linear iterative process）
  - 必要なステップ数が$n$に対して線形に増加する反復プロセス
末尾再帰（tail-recursive）
- たとえ構文上は再帰的に呼び出していたとしても、各プロセスにおいて必要な情報は引数として受け取った状態変数のみであり、再帰プロセスのように呼び出し前の情報を保持しておく必要が無い再帰プロセス
  - 再帰手続きで反復プロセスである場合はこれを満たす
木の再帰（tree recursion）
- ステップ数は木のノード数に比例する
- 空間は木の最大の深さに比例する
確率的アルゴリズム（probabilistic algorithm）
- ほとんどの場合正しいものの、反例が存在するアルゴリズム

高階手続きによる抽象の定式化

高階手続き（higher-order procedure）
- 手続きを引数として受け取る、手続きを返り値として返す、手続きを作成するなど、手続きを操作する手続き
不動点（fixed point）
- $f(x) = x$を満たす$x$
- 関数$f$に対して、値が変わらなくなるまで$f$を繰り返し適用していく方法で求めることができる
```
    $f(x), f(f(x)), f(f(f(x))), ...$
```
平均緩和法（average damping）
- 不動点探索において、振動をコントロールするため、平均を取ることでどちらからもあまり遠くない値を推測値とする手法
  - 次の予測値は$\frac{1}{2}(y+x/y)$となる
    - 平均の計算方法と同じ
ファーストクラス（first-class）計算要素
- 制約が最も少ない計算要素
- 変数によって名前を付けることができる
- 手続きに引数として渡すことができる
- 手続きの返り値になることができる
- データ構造に組み込むことができる

2. データを用いた抽象化の構築

複合データ（compound data）
- 複数のデータオブジェクトを組み合わせて構築されたデータ
データ抽象化（data abstraction）
- データをどうやって表すかを扱う部分と、データをどうやって使うかを扱う部分を分離する設計手法

データ抽象化

基本的な考え方は、複合データオブジェクトを扱う際、抽象データを扱うようにすること
- プログラムでデータを扱うときに、手元のタスクを実行するのに確実に必要とは言えないことについて想定をしないようにする
具体的なデータ表現は、そのデータを使うプログラムとは独立して定義する
- プログラムとデータ表現をつなぐインターフェース
  - セレクタ（selector）
    - 複合データの各構成要素について選択・操作するための手続き
  - コンストラクタ（constructor）
    - 複合データを生成するための手続き
ペア（pair）
- 2つのデータを持つ複合構造
- cons 手続きによって構築できる
  - 2つの引数を取り、それら2つを部品として含む複合データオブジェクトを返す
- carとcdr という手続きによって、それぞれを参照できる
  - car → カー。1つ目の要素を取り出せる
  - cdr → クダー。2つ目の要素を取り出せる
- ペアによって構築されるデータオブジェクトはリスト構造（list-structured）データと呼ばれる

抽象化の壁（abstraction barrier）

抽象化のレベルによって分離される境界
- それぞれのレベルの手続きは、抽象化の壁を定義し、異なるレベルをつなぐインターフェースとなる
データ抽象化の基礎となる考え方は、それぞれのデータオブジェクトの型に対して、それさえあればその型に対するどんな演算も行えるような基本演算セットを特定し、その後はデータを操作するのにそれらの演算しか使用しないというもの

データ

データとは、何らかのセレクタとコンストラクタの集合に加え、それらが有効な表現となるために満たさなければならない規定された条件によって定義されると考えることができる

階層データと閉包性

箱とポインタ記法（box-and-pointer notation）
閉包性（closure property）
- 集合の要素に演算を適用して得られるものがまたその集合の要素である場合、閉包されている
- 階層（hierarchical）構造を作ることが可能になる
標準インターフェース（conventional interface）
- 列挙（enumerator）
- フィルタ（filter）
- マップ（map）
- 集積（accumulator）
階層化設計（stratified design）
- 複雑なシステムは一連の言語によって記述される一連のレベルとして構造化されるべきだという概念
  - それぞれのレベルは、そのレベルで基本とされている部品を組み合わせて構築され、それぞれのレベルで構築された部品は次のレベルで基本部品として使用される
頑健（robust）なプログラム
- 仕様の小さな変更が、プログラム上でも相応に小さな変更で済むようなプログラム

抽象データの多重表現

ジェネリック手続き（generic procedure）
- 2種類以上の方法で表現されるデータを扱う手続き
- タイプタグ（type tag）
  - どのように処理されるべきかという情報を明示的に持っているデータオブジェクト
  - 型によるディスパッチ（dispatching on type）
    - データの型をチェックし、適切な手続きを呼ぶ戦略
    - 呼び出し側が全ての異なる表現について知っている必要がある
- データ主導（data-directed）プログラミング
  - データオブジェクト側に操作の責務を持たせ、呼び出し側は操作をデータオブジェクトに依頼する
- メッセージパッシング（message passing）
  - データオブジェクトが要求された演算の名前をメッセージとして受け取る

型の階層（hierarchy of types）

サブタイプ（subtype）
- 型Aに適用できる任意の演算は自動的に型Bに適用できる場合、型Bは型Aのサブタイプである
- 型における子要素
スーパータイプ（supertype）
- 型Aに適用できる任意の演算が自動的に型Bに適用できる場合、型Aは型Bのスーパータイプである
- 型における親要素

3. モジュール性、オブジェクト、状態

モジュール（module）
- システムのまとまりのある単位
- モジュール化戦略
  - オブジェクト（object）に集中する
    - システムを独立した要素の集合として捉える
  - ストリーム（stream）に集中する
    - システムを情報の流れとして捉える

状態と代入

オブジェクト（object）
- モデル化対象のシステムの各要素に対応する計算要素
- 相互作用によって他のオブジェクトに影響を与える
- 時間とともに振る舞いが変化する
  - オブジェクトの振る舞いがその過去に影響されるとき、そのオブジェクトは状態を持つと言える
- 状態変数（state variable）
  - オブジェクトの現在の振る舞いを決定するのに十分な履歴情報を持つ
- オブジェクトは局所的な状態変数を持つ環境が備わった関数であると言える
参照透過（referentially transparent）
- 式の値を変化させることなく、式の中で等しいものは等しいものによって置き換える事ができることをサポートしている言語
- 参照透過性を諦める場合、同一性を確認するには片方のオブジェクトを変更した際に、もう一方のオブジェクトが変化したかどうか（副作用）を確認する必要がある
  - 変化を測定することは、同じということについてのprioriな概念なしにはできない
  - ただし、値を変化させることが出来ない場合は、同一性についての確認は意味を成さなくなる
    - 値が同じかつそれが変化しない場合、どの時間でもそれは同じであるため
関数型プログラミング（functional programming）
- 局所状態変数とその代入を行わない、手続きを数学関数の計算とみなすことができるモデル
  - 置換モデルが適用できる
- 同じ引数による同じ手続きの呼び出しを二回評価しても結果は変わらない
  - 参照透過性を持つ
命令形プログラミング（imperative programming）
- 代入を多用する（局所状態とその変更を許可する）モデル
代入は相対的な順序がプログラムの実行に影響するので、注意する必要がある
- 並列実行時に非常に悪い影響を与える

評価の環境モデル

環境（environment）
- 現在の状態を表す変数群を保存する構造
- フレーム（frame）として表現され、それらの並びによって構成される
  - フレームの要素
    - 変数の名前とそれに対応する値を結びつける束縛（binding）のテーブル
      - 任意の変数に対して最大1つの束縛を持つ
      - 空であることもある
    - 外側の環境フレーム（enclosing environment）へのポインタ
      - グローバル（global）な環境は外側へのポインタを持たない
- ある環境についての変数の値（value of variable）とは、環境の中でその変数に対する束縛を持つ最初のフレームの中の、その変数に対して束縛されている値のこと
  - もし環境の中に、その変数に対する束縛を規定するフレームが無ければ、その変数は環境の中で未束縛（unbound）であるといえる
- 隠蔽（shadow）
  - 外側のフレームで束縛されている変数を、現在のフレームで新たに束縛することで、外側の変数を覆い隠すこと

評価規則

手続きの作成
- 手続きは与えられた環境について、λ式を評価することによって作成する
  - 作成される手続きオブジェクトは、λ式のコード（手続きの本体）と、手続きが作成された環境へのポインタからなるペアである
記号の定義
- 現在の環境フレームの中に束縛を作成し、その記号に指定の値を割り当てる
引数セットへの手続きオブジェクトの適用
- 適用順序 1. フレームを構築 2. 手続きの仮引数を呼び出しの引数に束縛 3. 新しく構築された環境という文脈の中で手続きの本体を評価
- 新しいフレームは、適用する手続きオブジェクトの環境を外側の環境として持つ

可変データによるモデル化

ミューテータ（mutator）
- データオブジェクトを変更する手続き
可変データオブジェクト（mutable data object）
- ミューテータが定義されているデータオブジェクト

制約システムの実装

基本制約（primitive constraint）
- 量と量の間に成り立つ関係の記述
コネクタ（connector）
- 制約を接続する
制約ネットワーク（constraint network）
- 接続された制約のネットワーク

並行性

直列変換器（serializer）
- 互いに区別される複数の手続きの集合を作り、それぞれの直列化された集合の中では同時に1つのプロセスしか実行されないようにする
デッドロック（deadlock）
- お互いにロックが必要なリソースを待ち合って、処理が続行できなくなる
- 対策
  - それぞれのリソースにID番号を振り、ロックを獲得する際に番号が若い順から獲得するようにする
    - 必ず同じ順序でのロック獲得を試行する
    - 交換問題の対策のみ可能

ストリーム（stream）

表面的には列として見える、必要なリソースを要求される毎に計算し送信するデータ構造
- 遅延評価（delayed evaluation）テクニックを用いる
  - 要求駆動プログラミングと考えることができる
    - 次の段階を満たせるのに十分な計算のみを行う
- 基本的な考え方
  - ストリームを部分的に構築し、構築した一部をそのストリームを消費するプログラムに渡す
  - 消費プログラムがストリームの未構築な部分を要求した場合、必要な部分だけを構築し渡す
遅延オブジェクト（delayed object）
- (delay <exp>) によって得られる
  - 実際は(lambda () <exp>) のシンタックスシュガー
- ある将来の時点で<exp> を評価するという約束
- (force <delayed object>) によって評価を実行する
  - 定義は(define (force delayed-object) (delayed-object)) である
列加速（sequence accelerator）
- ストリームを変形して、近似値の列をより速く収束するように変換する手法
タブロー（tableau）
- ストリームのストリーム
状態を持つことをシステムに求めているのはユーザの時間的な存在である

4. メタ言語抽象化

評価器（emulator）
- その言語の式に適用された時、その式を評価するのに必要なアクションを実行する手続き
- プログラミング言語の式の意味を決める評価器もまたただのプログラムに過ぎない
派生式（derived expression）
- 既存の構文の変形によって実装した式
- マクロ（macro）
  - ユーザが定義できる派生式
厳密（strict）
- ある引数が手続きの本体に入る前に評価される
非厳密（non-strict）
- 引数を評価し終える前に手続きの本体に入る
サンク（thunk）
- 評価が遅延された引数を表現するオブジェクト
- 引数の値が必要になった時に、あたかも適用時に評価されていたかのようにその値を返す
  - 引数の式と、手続き適用が評価された環境を持っている必要がある
- 強制（forcing）
  - サンクの式を評価するプロセス
- メモ化（memoize）
  - サンクの値を記録しておき、計算回数を減らす手法
非決定性選択点（nondeterministic choice point）
- 時間の分岐が発生した点
- それぞれの分岐ではその式の可能な値の1つが選択された状態で計算が進む
依存主導バックトラック（dependency-directed backtracking）
- 事実と事実を繋いだ論理的依存性を追跡することで、非時間的なバックトラックを行う手法
- 真理維持（truth maintenance）
  - 依存主導バックトラックをより一般化したもの
継続渡し（continuation passing）
- 手続きをリレー形式で実行していく手法
- 継続（continuation）
  - 次に実行される計算の全体
- 継続手続き（continuation procedure）
  - 式の評価が以下の2つの手続きのどちらかを呼んで終わる
  - 成功継続（success continuation）
    - 評価の結果が値になった場合、その値を受取り計算を続行する
    - 成功継続の手続きが失敗した場合のため、失敗継続も持つ
  - 失敗継続（failure continuation）
    - 評価の結果が失敗になった場合に呼ばれる

5. レジスタマシンによる計算

レジスタマシン（register machine）
- レジスタ（register）を操作する命令（instruction）を順に実行するマシン
  - 固定された記憶素子
- データパス（data path）
  - レジスタとその演算
- コントローラ（controller）
  - 演算を正しく並べる
  - 命令（instruction）とラベル（label）の列
    - ラベルの列はエントリポイント（entry point）を示す
オブアレイ（obarray）
- 出現した記号を管理するテーブル
- 閉じ込め（interning）
  - 出現した記号をテーブルに保存しておき、そのポインタを記号の代わりに扱うことで、記号比較をポインタ比較に置き換える
  - 既知の記号の場合、既にテーブルに存在する項目のポインタを返すことで、同じ記号が同じポインタを返すことを保証する
ガベージコレクション（garbage collection）
- データオブジェクトが必要でなくなった時に、それに割り当てられていたメモリを自動的にリサイクルする機構
- 戦略
  - ストップ＆コピー（stop-and-copy）
    - 手順
      - メモリをワーキングメモリとフリーメモリに分割する
      - データオブジェクトはワーキングメモリに割り付ける
      - ワーキングメモリがいっぱいになったらGCを行う
        現在の環境からアクセス可能なワーキングメモリ中のデータオブジェクトをフリーメモリにコピーする
        ワーキングメモリをリフレッシュする
        ワーキングメモリとフリーメモリを入れ替える
    - 圧縮（compacting）ガベージコレクタである
      - GC後にオブジェクトがメモリ上の連続した位置に集積されている
        余計なページング処理が無くなる
        キャッシュのパフォーマンスが良くなる
  - マーク＆スイープ（mark-sweep）
    - 手順
      - 現在の環境からアクセス可能なデータオブジェクトを全てたどり、到達できたものに印を付ける
      - メモリを全て走査し、印のついていないオブジェクトを全て解放する
末尾再帰（tail recursion）
- 再帰部分が部分式となっていないため、再帰前の情報を保存しておく必要がなく、単純な呼び出しの繰り返しに展開できる再帰
  - レジスタの値等をスタックに保存しておく必要がないため、逆説的に不要なスタックへの保存を行わない様なマシンの実装を行うと末尾再帰評価器となる
- エブリス末尾再帰（evlis tail recursion）
  - 最後の被演算子を評価した後には環境などを保存しておく必要がないため、保存処理を省略することで最適化する

1. 手続きを用いた抽象化の構築#

プログラミングの要素#

式#

組合の評価#

ブラックボックス抽象化#

手続きとそれが生成するプロセス#

高階手続きによる抽象の定式化#

2. データを用いた抽象化の構築#

データ抽象化#

抽象化の壁（abstraction barrier）#

データ#

階層データと閉包性#

抽象データの多重表現#

型の階層（hierarchy of types）#

3. モジュール性、オブジェクト、状態#

状態と代入#

評価の環境モデル#

評価規則#

可変データによるモデル化#

制約システムの実装#

並行性#

ストリーム（stream）#

4. メタ言語抽象化#

5. レジスタマシンによる計算#

1. 手続きを用いた抽象化の構築

プログラミングの要素

式

組合の評価

ブラックボックス抽象化

手続きとそれが生成するプロセス

高階手続きによる抽象の定式化

2. データを用いた抽象化の構築

データ抽象化

抽象化の壁（abstraction barrier）

データ

階層データと閉包性

抽象データの多重表現

型の階層（hierarchy of types）

3. モジュール性、オブジェクト、状態

状態と代入

評価の環境モデル

評価規則

可変データによるモデル化

制約システムの実装

並行性

ストリーム（stream）

4. メタ言語抽象化

5. レジスタマシンによる計算