読者です 読者をやめる 読者になる 読者になる

mrasu’s blog

読んだ物の内容など

算機プログラムの構造と解釈(3章)

「計算機プログラムの構造と解釈(SICP)」の3章です

関数型プログラミングとストリーム、遅延評価についてです。

計算機プログラムの構造と解釈 第2版

計算機プログラムの構造と解釈 第2版


3章 標準部品化力、オブジェクトおよび状態

3.1 代入と局所状態

3.1.1 局所状態変数

銀行口座を考える

  1. 高設定
  2. 引出

これらを隠蔽して、以下を公開する

  1. 金額の設定
  2. 預金機能

3.1.2 代入を取り入れた利点

rand関数のシードがあるとすると、シードをユーザーが覚えておく意味がないので、関数内に隠蔽とすると楽

3.1.3 代入を取り入れた代価

代入を使わないのが関数型プログラミング(functional programming)

代入があることによる難しさを見ると、

再代入あり

(define (make-simplified-withdraw balance)  
    (lambda (amount)  
        (set! balance (- balance amount)  
            balance  
        )  
    )  
)  

再代入無し

(define (make-decrementer balance)  
    (lambda (amount)  
        (- balance amount)  
    )  
)  

この二つを比べると、make-decrementerは置き換えが簡単にできるが、
make-simplified-withdrawはbalanceの初期状態と代入後の値を区別する必要があるが、置換えモデルではできない
つまり、変数の値が変化するために、置き換えが出来ない。(今まで変数は値の「名前」だったが、代入では値の「格納場所」になった)

参照透明(referentially transparent[参照透過性])があるかないか。
参照透明がないと「同じ」である時の「置き換え」が出来ない、ともいえる

命令型プログラミングと関数型プログラミングを比べると

関数型

(define (factorial n)  
    (define (iter product counter)  
        (if (> counter n)  
            product  
            (iter (* product counter) (+ counter 1))  
        )  
    )  
    (iter 1 n)  
)  

命令型

(define (factorial n)  
    (let ((product 1)  
            (counter 1))  
        (define (iter)  
            (if (> counter n)  
                product  
                (begin (set! product (* product counter))  
                    (set! counter (+ counter 1))  
                    (iter)  
                )  
            )  
        )  
    )  
    (iter)  
)  

関数型では、実行順序を気にする必要はないが、命令型では代入の順序を変えるとバグになる。

3.2 評価の環境モデル

代入が存在することにより、既存のモデルが使えないので、新しいモデルを作成する

環境 : フレームの並び
フレーム: 変数名と値を持つ束縛(bindings)の集まり。外側の環境(外部スコープ)へのポインタを持つ
未束縛: フレームをたどっても変数が束縛されていない状態

このモデルでは、
手続きはlambda式の評価のみから得られ、lambda式を評価した場所が「環境」で、
また、defineはlambdaのシンタックスシュガーである。

3.3 可変データのモデル化

キューの実装は

  1. 追加
  2. 取り出し

表の実装

  1. キーに対応する値の取り出し
  2. キーの存否
  3. 追加
  4. 初期化

インターフェースは作成できるが、Lispではlistしかないのでハッシュ化できない
二次元の表にすることはできる

デジタル回路のシミュレータ

デジタル回路を実装する

  1. 半加算器
  2. 全加算器
  3. 順次呼び出し

wireを実装する

  1. 値を取得する
  2. 値を設定する
  3. 回路につなげる

さらに、
0. シミュレータの経路を作る
0. 接続する

3.4 並列性

3.4.1 並列システムでの時

並列プログラムにおける正しいふるまいとは、「結果」が「正しい」ことであり、「結果」が複数あることもあり得る
つまり、順序が決定していない環境で割合計算が発生すると、どの時点で計算したかにより結果が変わる

例えば、

初期値100のものに以下の並列計算を実行すると、

  1. 20引く
  2. 2で割る

(100 - 20) / 2
(100 / 2) - 20

結果は違うが、どちらも正しいといえる。本質的に並列計算は非決定的である

3.4.2 並列性の制御機構

直列変換器

  1. 積算→加算(101)
  2. 加算→積算(121)
  3. (* x x)のx評価中に加算が発生(110)
  4. (+ x x)のx評価中に積算が発生(110)
  5. 両者の引数の評価が終わった後に、両者の代入が実行される(100, 11)

順序を確定する必要があるのなら、資源をロックすればいい、両方同時にロックするmutexを実装する
ただし、デッドロックは気を付ける必要がある

3.5 ストリーム

3.5.1 ストリームは遅延リスト

リストを使用すると、メモリや時間の消費が大きいので、ストリームを使って逐次処理ができるようにする
計算が終わっていなくても、必要な要素を取得していれば次の処理へ行くことができるのだから、評価を遅延させてもよい

3.5.2 無限ストリーム

遅延評価ができるということは、無限ストリームもできる
素数がほしいのなら、数の連続をエラトステネスのふるいにかけ続ければいい
ストリームを暗黙に使うこともできる

3.5.3 ストリームパラダイムの開発

再帰などはストリームであらわせる

例えば、

  1. 平方根
  2. 交項級数によるπの近似
  3. オイラーの並び加速[sequence accelerator]による改良
  4. 2要素の対の無限ストリーム(両方のストリームの内容を対としてもつ無限ストリーム、i <= j となる(i,j)の無限ストリーム)

3.5.4 ストリームと遅延評価

delayを採用することにより定義前の名前が使用可能になる

3.5.5 関数的プログラムの部品化度とオブジェクトの部品化度

ストリームで状態を表す

手続き型では

(define (make-simplified-withdraw balance)  
    (lambda (amount)  
        (set! balance (- balance amount)  
            balance  
        )  
    )  
)  

ストリームにすると

(define (stream-withdraw balance amount-stream)  
    (cons-stream  
        balance  
        (stream-withdraw (- balance (stream-car amount-stream) (stream-cdr amount-stream)))  
    )  
)  

これによって、変数の状態を持つことなく、状態を表現できるようになり、