SICP読書女子会 3.1.3 (#41)

3.1.3 代⼊を導⼊することのコスト

; setを使ったwithdraw(簡易版)
(define (make-simplified-withdraw balance)
  (lambda (amount)
    (set! balance (- balance amount))
    balance))

 make-simplified-withdraw

(define W (make-simplified-withdraw 25))

 W

(W 20)
(W 10)

 5
 -5

set! を使わない次の make-decrementer ⼿続き

続けて呼び出しても、make-simplified-withdraw のような
集積効果はない

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

 make-decrementer

(define D (make-decrementer 25))

 D

(D 20)
(D 10)

 5
 15

同⼀性と変化

(define D1 (make-decrementer 25))

 D1

(define D2 (make-decrementer 25))

 D2

(D1 20)
(D1 20)
(D2 20)

 5
 5
 5

上の２つは同じだが、下の２つは異なる

(define W1 (make-simplified-withdraw 25))

 W1

(define W2 (make-simplified-withdraw 25))

 W2

(W1 20)
(W1 20)
(W2 20)

 5
 -15
 5

式の値を変化させることなく、式の中で “等しいものは等しいものによって置き換えることができる

という概念をサポートしている⾔語は、参照透明(referentially transparent) であると⾔わる。

set! を含めたときに、参照透明性はられる。

命令型プログラミングの落とし⽳

関数型プログラミングとは対照的に、

代⼊を多⽤するプログラミングは*命令型プログラミング *という。

階乗を例に

; 例: 関数型的に
(define (factorial n)
  (define (iter product counter)
    (if (> counter n)
        product
        (iter (* counter product) (+ counter 1))))
  (iter 1 1))
(factorial 3)

 factorial
 6

; 命令形スタイルでの階乗
(define (factorial n)
  (let 
    (
        (product 1)
        (counter 1)
    )
    (define (iter)
      (if (> counter n)
          product
          (begin 
           (set! product (* counter product))
           (set! counter (+ counter 1))
           (iter))))
    (iter)))
(factorial 3)

 factorial
 6

これは動くけれど

(set! counter (+ counter 1))
(set! product (* counter product)

の順番を間違えたら動かなくなる

当たり前・・・と思うけれど、この問題は、関数型プログラミングでは最初から起こらない。

Ex 3.7

: 練習問題 3.3で述べた、パスワード機能を追加したmake-account で作った銀⾏⼝座オブジェクトについて考える。

私たちの銀⾏システムでは、共同⼝座を作る能⼒が必要だとする。
これを実現する⼿続き make-joint を定義せよ。

make-joint は三つの引数を取る。

• ⼀つ⽬はパスワード保護された⼝座である。
• ⼆つ⽬の引数は⼝座を定義したときのパスワードと⼀致している必要があり、そうでなければ make-joint 演算を進めることはできな い。
• 三番⽬の引数は新しいパスワードである。make-joint は、元の⼝座に新しいパスワードでもアクセスできるようにする。例えば、peter-acc が open-sesame というパスワードを持つ銀⾏⼝座だとすると、 (define paul-acc (make-joint peter-acc 'open-sesame 'rosebud)) このようにすることで、paul-acc という名前と rosebud というパスワードによって peter-acc に対する取引ができるようにする。

3.3での実装からコピー

; 3.3より
(define (make-account password balance)
  (define correct-password (list password))
  ;; 引き出し
  (define (withdraw amount)
    (if (>= balance amount)
      (begin 
        (set! balance (- balance amount))
        balance)
    "Insufficient funds"))

  ;; 預金
  (define (deposit amount)
    (set! balance (+ balance amount))　balance)

  ;; パスワード設定
  (define (add-password new-password)
    (begin
        (set! correct-password (cons new-password correct-password))
    dispatch))

  ;; password check
  (define (is-correct-password? password)
    (define (itr corrects password)
      (cond
       ((null? corrects) #f)
       ((eq? (car corrects) password) #t)
       (else (itr (cdr corrects) password))))
    (itr correct-password password)
  )

  ;;
  (define (dispatch password m)
    (if 
      (is-correct-password? password)
      (cond 
        ((eq? m 'withdraw) withdraw)
        ((eq? m 'deposit) deposit)
        ((eq? m 'new-password) add-password)
        (else (error "Unknown request: MAKE-ACCOUNT" m)))
      (lambda (args) "Incorrect password"))
    )
dispatch)

 make-account

;; 共有口座
(define (make-joint account password new-password)
  ((account password 'new-password) new-password))

 make-joint

; 口座1
(define account (make-account 'nyan 0))

 account

; 口座2
(define new-account (make-joint account 'nyan 'nyanko))

 new-account

((account 'nyan 'withdraw) 10)
((account 'nyan 'deposit) 10)
((account 'nyan 'withdraw) 10)
((new-account 'nyan 'deposit) 10)
((new-account 'nyanko 'deposit) 10)

 "Insufficient funds"
 10
 0
 10
 20

((new-account 'nyan 'deposit) 10)
((new-account 'nyanko 'withdraw) 10)
((account 'nyanko 'withdraw) 10)

 30
 20
 10

だめだ、accountの方でもnew-accountのパスワード使えるようになっちゃった。

そういうことじゃないっぽい(⌒(´-ω-`)_

パスワード部分だっけwrapしてみる

(define (make-joint account password new-password)
  (define (wrap pass arg)
    (if 
     (eq? pass new-password)
     (account password arg)
     (lambda (_) "invalid password")
     ))
wrap)

 make-joint

(define account (make-account 'nyan 0))

 account

(define wrap-account (make-joint account 'nyan 'nyanko))

 wrap-account

((wrap-account 'nyan 'deposit) 10)
((wrap-account 'nyanko 'deposit) 10)
((account 'nyan 'withdraw) 10)

 "invalid password"
 10
 0

Ex 3.8

1.1.3 節で評価モデルを定義したときに、
式を評価する最初のステップはその部分式を評価することだと述べた。
しかし、部分式を評価する順番 (例えば、左から右、または右から左)については規定しなかった。
代⼊を導⼊すると、⼿続きの引数を評価する順番によって結果が変わるということが起こりえる。

単純な⼿続き f を定義して、次の式

(+ (f 0) (f 1))

を評価する際に、+ の引数の評価順が左から右であれば 0 を返し、右から左であれば 1 を返すようにせよ。

ひたすら一個分評価を遅延して返す関数作った

(define (queue-1)
  (define queue 0)
  (lambda (x) 
    (let ((top queue))
    (begin
      (set! queue x)
      top
    )))
)

 queue-1

(define f (queue-1))
(+ (f 0) (f 1))

 f
 0

(define g (queue-1))
(+ (g 1) (g 0))

 g
 1