SICP 3.1.3 The Costs of Introducing Assignment
面白い事に代入を導入すると同時に代入が存在しない関数プログラミングの説明がされる。むしろ代入を導入する事で代入の存在しない関数プログラミングを説明しているのかも知れない。
ノート
代入を導入する事による代償。
代入が存在すると置換モデル(substitution model:手続きを呼び出している部分に手続きの定義を展開する解釈)で実行を解釈する事は出来ない。
Programming without any use of assignments, as we did throughout the first two chapters of this book, is accordingly known as functional programming.
この本の最初の二章のように代入がないプログラミングを関数プログラミングと言う。
置換モデルでは手続きを呼び出している部分にその定義を展開した後、仮引数の部分を実引数(の値)で置き換える。しかし代入があると置き換えた値が途中で変わる事を意味しているので置換モデルでは説明出来ない。
これまで「名前」は「値」に付けた名前であったが、代入が存在すると値を保存する「場所」(C言語等で言う所の変数)の名前となる。
一応例を動かしておく。
> (define (make-simplified-withdraw balance) (lambda (amount) (set! balance (- balance amount)) balance)) > (define W (make-simplified-withdraw 25)) > (W 20) 5 > (W 10) -5 > (define (make-decrementer balance) (lambda (amount) (- balance amount))) > (define D (make-decrementer 25)) > (D 20) 5 > (D 10) 15 >
Sameness and change
samenessは同一性かな。
(define D1 (make-decrementer 25)) (define D2 (make-decrementer 25))
このD1、D2は同じか。それぞれ常に引数を25から引いた値を返す関数となる。実際D1を使っている所をD2で置き換えても結果に変わりはない。
(define W1 (make-simplified-withdraw 25)) (define W2 (make-simplified-withdraw 25))
一方、W1とW2は最初は同じだが実行を進めると同じではなくなってしまう。途中からは交換可能ではなくなるので。
A language that supports the concept that ``equals can be substituted for equals'' in an expresssion without changing the value of the expression is said to be referentially transparent.
式のある一部を別のものと置き換えても常にその式の値が変わらない事をその二つ(置き換えられたものと置き換えたもの)が等価である、と言う概念を参照透過と言う。
代入が存在すると式を置換によって単純化する事は出来ない。
Consequently, reasoning about programs that use assignment becomes drastically more difficult.
代入が存在するプログラムを解釈する(reasoning)のは難しくなる。
「同じ」と言う言葉が指す意味が代入のない世界とある世界では異なる。
代入のない世界では同じ初期値から作られた二つのオブジェクトは同じと言えるが、代入がある世界では別々に作られた二つのオブジェクトはたとえ初期値が同じでもその意味で同じとは言えない。
同じ値を意味するのか同じオブジェクトを意味するのかの違い。等値とか等価は別の話。
ポインタのない世界ではこの区別は難しいのかも知れない。例では片方に変更を加えて自動的にもう片方も変わったらそれは同じオブジェクトを参照していると言えると述べている。*1
Pitfalls of imperative programming
命令的プログラミングの落とし穴。
関数型プログラミングと対比して、代入を全面的に使ったプログラミングを命令的プログラミングと言う。
(関数型と比べて)計算モデル(substitution modelとか)がややこしくなるだけでなく、関数型では起こりえないバグを作り込みやすい。
時々刻々と変化する変数に対して、更新と参照の順番に気をつけないと間違った答えを出す。関数型ではこの落とし穴は存在しない。
命令型では並列処理に於いて更に複雑になる。
関数型と命令型で書いた階乗。counterの代入と参照の順番を間違えると正しい答えが得られない。
(define (factorial-f n) (define (iter product counter) (if (> counter n) product (iter (* counter product) (+ counter 1)))) (iter 1 1)) (define (factorial-i1 n) (let ((product 1) (counter 1)) (define (iter) (if (> counter n) product (begin (set! product (* counter product)) (set! counter (+ counter 1)) (iter)))) (iter))) (define (factorial-i2 n) (let ((product 1) (counter 1)) (define (iter) (if (> counter n) product (begin (set! counter (+ counter 1)) (set! product (* counter product)) (iter)))) (iter)))
実行結果。
> (factorial-f 6) 720 > (factorial-i1 6) 720 > (factorial-i2 6) 5040 >
確かにC言語とか習い始めはループカウンターの状態を一生懸命頭で考えるのがプログラミングだった気がする。
Exercise 3.7
make-accountはそのまま。Paulの方は自分の口座としてのパスワード認証を通った後、peter-accのパスワードも知っているので、そのパスワードを使ってpeterの口座にアクセスする。
(define (make-joint account password-for-account saved-password) (define (dispatch password m) (if (eq? password saved-password) (account password-for-account m) "Incorrect password")) dispatch)
動作確認
> (define peter-acc (make-account 100 'open-sesame)) > (define paul-acc (make-joint peter-acc 'open-sesame 'rosebud)) > ((peter-acc 'open-sesame 'withdraw) 10) 90 > ((paul-acc 'rosebud 'withdraw) 5) 85 > ((peter-acc 'open-sesame 'deposit) 10) 95 > ((paul-acc 'rosebud 'withdraw) 3) 92 >
確かにひとつの口座になっている。
Exercise 3.8
取り敢えずこのケースだけ成り立てば良いのであれば、
- 内部的に初期値0を持っていて
- 呼び出される度に保存されていた値を返し、保存している値を更新する
左から評価されると最初の(f 0)が0を返し、次の(f 1)も0を返すので足して0。右から評価されると最初の(f 1)で0を返し、次の(f 0)で1を返すので足して1。
(define f (let ((s 0)) (lambda (n) (let ((p s)) (set! s n) p))))
実行してみると
> (+ (f 0) (f 1)) 0 >
fの定義が正しければ左から評価されている事になる。引数の評価順の制御方法が分からないので引数の順番を入れ替えて実行してみる。
> (+ (f 1) (f 0)) 1 >
一応、fの定義はあっていそう。