SICP 読書ノート#27 - 3.1 代入と局所状態 (pp.127-137)
いよいよ3章。キーワードは、
- モジュール化
- オブジェクトによるプログラムの組織化
- 代入(assignment)と局所状態(local state)
- 環境モデル(enviroment model)
- ストリーム(streams)と遅延評価(delayed evaluation)
あたりのようです。
代入と局所状態
これまではdefine、lambda、letによる束縛(bind)ではなく、代入(assignment)が初めて登場。
前にも紹介したけど、束縛と代入の違いのわかりやすい解説はこちら。
それにしても、代入なしで130ページもプログラミングするなんて、SICPくらいだよなぁ。
局所状態変数
make-withdraw、make-accountの例、局所状態とセレクタを持つ手続きオブジェクトの コンストラクタだけど、JavaScriptの典型的なプラクティスである プロパティをメソッドを持つ関数オブジェクトを持つコンストラクタとまさに同じだ。
そこまでいうと、make-accountをJavaScriptで書きたくなってきた。
元々のコードは、
(define (make-account balance) (define (withdraw amount) (if (>= balance amount) (begin (set! balance (- balance amount)) balance) "Insufficient funds")) (define (deposit amount) (set! balance (+ balance amount)) balance) (define (dispatch m) (cond ((eq? m 'withdraw) withdraw) ((eq? m 'deposit) deposit) (else (error "Unknown request -- MAKE-ACCOUNT" m)))) dispatch)
JavaScriptで書くとこんな感じ。
var Account = function(balance) { this.withdraw = function(amount) { if (balance >= amount) { balance = balance - amount; return balance; } else { return 'Insufficient funds'; } }; this.deposit = function(amount) { balance = balance + amount; return balance; }; };
JavaScriptはWebで動くScheme。さすがに似てますね。
全てのJavaScripterにSICPをおすすめしたいなぁ、個人的には。
JavaSript版のnodeでの実行結果は以下の通り。
> acc = new Account(100); { withdraw: [Function], deposit: [Function] } > acc.withdraw(50); 50 > acc.withdraw(60); 'Insufficient funds' > acc.deposit(40); 90 > acc.withdraw(60); 30
問題 3.1
(define (make-accumulator amount) (lambda (value) (begin (set! amount (+ amount value)) amount)))
テスト。
racket@> (define A (make-accumulator 5)) racket@> (A 10) 15 racket@> (A 10) 25
問題 3.2
counterをdispatchの外部環境に置くのがポイント。
counterはletでも定義できます。let、lambda、defineはsyntax sugarなので当たり前だけど。
なので、特にdefineにしている理由はないです、すみません…
(define (make-monitored proc) (define counter 0) (define (dispatch m) (cond ((eq? m 'how-many-calls?) counter) (else (begin (set! counter (+ counter 1)) (proc m))))) dispatch)
テスト。
racket@> (define s (make-monitored sqrt)) racket@> (s 100) 10 racket@> (s 'how-many-calls?) 1
問題 3.3
前述のmake-accountを直接修正する方法もあると思うけど、面倒そうだったので、 make-accountはそのままにパスワードをかけたmake-secure-accountを書いてみた。
(define (make-secure-account balance password) (let ((account (make-account balance))) (lambda (pw method) (if (eq? pw password) (account method) "Incorrect password"))))
テスト。
racket@> (define acc (make-secure-account 100 'secret-password)) racket@> ((acc 'secret-password 'withdraw) 40) 60 racket@> (acc 'other-password 'deposit) "Incorrect password"
問題 3.4
7回でexpireは面倒だったので、3回とした。
(define (make-secure-account balance password call-the-cops) (let ((account (make-account balance)) (mistake-counter 0)) (lambda (pw method) (if (eq? pw password) (begin (set! mistake-counter 0) (account method)) (begin (set! mistake-counter (+ mistake-counter 1)) (if (< mistake-counter 3) "Incorrect password" (call-the-cops)))))))
テスト。
racket@> (define acc (make-secure-account 100 'secret-password (lambda() "Oops!"))) racket@> ((acc 'secret-password 'withdraw) 40) 60 racket@> (acc 'foo 'withdraw) "Incorrect password" racket@> (acc 'foo 'withdraw) "Incorrect password" racket@> (acc 'foo 'withdraw) "Oops!"
このレベルの問題なら何の迷いもなくさらさらと書けるようになった。 少しはScheme力が身についてきたのかもしれない。
代入を取り入れた利点
時間の経過とともに変化する局所状態を変数で、状態の変化を変数への代入でモデル化する。こういう時に代入の利点が存在する。
逆に言えば、むやみやたらと代入を使うのではなく、代入にも使いどころ・そうでないところがあるということ。このあたりは始めから代入が登場する関数型言語以外のプログラミング言語では得られなかった観点だ。
乱数の生成手続き
脚注によると、適切な\( a, b, m \) を設定すれば \( modulo(a * x + b, m) \) で乱数の生成ができるとのこと。
何が適切かはよく解らないが、適当に二桁の素数を設定してみた。
(define (rand-update x) (modulo (+ (* 13 x) 47) 97)) (define random-init 7) (define rand (let ((x random-init)) (lambda () (set! x (rand-update x)) x)))
テスト。それっぽい値は取れていると思う。
racket@> (map (lambda (i) (rand)) (enumerate-interval 0 20)) => '(41 95 21 29 36 30 49 5 15 48 89 40 82 46 63 90 53 57 12 9 67)
問題 3.5
モンテカルロ積分について。これ大学のCの授業でやったなあ。乱数はRacketの組み込み関数のrandomを転用。
(define (random-in-range low high) (let ((seed (+ (- high low) 1))) (+ low (random seed)))) (define (estimate-integral predicate x1 y1 x2 y2 trials) (define (iter remain passed) (let ((x (random-in-range x1 x2)) (y (random-in-range y1 y2))) (cond ((= remain 0) (/ (* (- x2 x1) (- y2 y1) passed 1.0) trials)) ((predicate x y) (iter (- remain 1) (+ passed 1))) (else (iter (- remain 1) passed))))) (iter trials 0))
テスト。
racket@> (estimate-integral (lambda (x y) (<= (+ (square (- x 5)) (square (- y 7))) (square 3))) 2 4 8 10 1000000) => 21.288636
実際の答えはこう。
racket@> (* (square 3) pi) => 28.274333882308138
精度がいまいちなのは整数しか扱ってないからだと思う。
(2015/02/22追記)
最初のやり方ではmonte-carloを使うという題意が満たせていないし、それぞれの処理のモジュール化もできておらず、後日問題3.82を解く際に困ったので解き直した。
まずmonte-carloは反復的にexperiment手続きを評価し成功率を返す手続き。テキストそのままだが、戻り値は小数としたいので1.0を掛けて返すようにした。
(define (monte-carlo trials experiment) (define (iter trials-remaining trials-passed) (cond ((= trials-remaining 0) (/ (* trials-passed 1.0) trials)) ;;小数で返すように1.0を掛ける ((experiment) (iter (- trials-remaining 1) (+ trials-passed 1))) (else (iter (- trials-remaining 1) trials-passed)))) (iter trials 0))
特定の範囲内の乱数を返すrandom-in-rangeの実装。
(define (range low high x) (+ low (modulo x (+ 1 (- high low))))) (define (random-in-range low high) (range low high (rand)))
テスト。
racket@> (map (lambda (i) (random-in-range 2 8))
(enumerate-interval 0 20))
=> '(3 6 5 2 2 5 6 6 8 3 2 7 8 4 7 5 4 3 6 4 5)
モンテカルロ積分は全体の面積とモンテカルロテストの成功率を掛ければよいので、次のように実装できる。それぞれの部品を組み合わせる形が採れたので、前よりかなり進歩したと思う。
(define (estimate-integral predicate x1 y1 x2 y2 trials) (let ((area (* (- x2 x1) (- y2 y1))) (passed-ratio (monte-carlo trials (lambda () (let ((x (random-in-range x1 x2)) (y (random-in-range y1 y2))) (predicate x y)))))) (* area passed-ratio)))
テスト。もちろん精度はやり直す前とほぼ同じ。
racket@> (estimate-integral (lambda (x y) (<= (+ (square (- x 5)) (square (- y 7))) (square 3))) 2 4 8 10 1000000) => 21.750012
問題 3.6
(2015/02/22追記)
乱数の生成に加えてリセットも行えるようにrandを拡張する。
(define rand-ex (let ((x random-init)) (define (generate) (set! x (rand-update x)) x) (define (reset) (set! x random-init) x) (define (dispatch m) (cond ((eq? m 'generate) generate) ((eq? m 'reset) reset) (else (error "Unknown request -- RAND" m)))) dispatch))
テスト。
racket@> ((rand-ex 'reset)) => 7 racket@> ((rand-ex 'generate)) => 41 racket@> ((rand-ex 'generate)) => 95 racket@> ((rand-ex 'generate)) => 21 racket@> ((rand-ex 'reset)) => 7 racket@> ((rand-ex 'generate)) => 41 racket@> ((rand-ex 'generate)) => 95 racket@> ((rand-ex 'generate)) => 21
代入を取り入れた代価
原文では「代価」とあるけど「代償」じゃないかな。
- 参照透過性が失われて置き換えモデルが成立しなくなる話
- 代入の順序に注意が必要
後者の方は、
for (...) {
product *= counter;
count += 1
}
と
for (...) {
count += 1
product *= counter;
}
では結果が異なるよねという話。代入がなければこうした落とし穴はない。
また、代入を必要としないプログラミングを関数型プログラミング(functional programming)、 反対に代入を多用するプログラミングを命令型プログラミング(imperative programming) というらしい。
問題 3.7
make-accountの修正なしで実装してみた。
(define (make-joint another-account another-password password) (lambda (pw method) (if (eq? pw password) (another-account another-password method) "Incorrect password")))
テスト。
racket@> (define peter-acc (make-secure-account 100 'open-sesame)) racket@> ((peter-acc 'open-sesame 'withdraw) 0) 100 racket@> (define paul-acc (make-joint peter-acc 'open-sesame 'rosebud)) racket@> ((paul-acc 'rosebud 'withdraw) 40) 60 racket@> ((peter-acc 'open-sesame 'withdraw) 0) 60
こんな口座嫌だ(笑)
問題 3.8
(+ (f 0) (f 1))
があるときに、引数の式は左から評価されるか右から評価されるかをチェックする。
まさか右からなんてないよなぁ。
(define *zero-evaluated* false) (define (f x) (cond ((= x 0) (begin (set! *zero-evaluated* true) 0)) ((= x 1) (if (eq? *zero-evaluated* true) 1 0)) (else "Unexpected argument -- " x)))
テスト。
racket@> (set! *zero-evaluated* false) racket@> (+ (f 0) (f 1)) 1
(f 0)と(f 1)を入れ替えてみると結果が変わる。
racket@> (set! *zero-evaluated* false) racket@> (+ (f 1) (f 0)) 0
左からだ。良かった。
しかし、fが大域変数を変更するような手続きだと、 その呼び出し順にも配慮をしなければならないという良い例。
Schemeに限らず、大域変数を持つということはオブジェクトの状態を増やしているということ。 その代償が大きいことをここでは肝に銘じましょう。
次は「§3.2 評価の環境モデル」から。
