Scheme演習第５回

品川嘉久, 浅井健一, 萩谷昌己, 西澤弘毅, 原謙治

関数から返された関数

下の関数 make-adder は、引数 n を受け取り、新しく関数を作って返す
ここでは add1 と add2 という二つの関数が作られている
これらはそれぞれ、引数 m に1加える関数と、2加える関数である。
このように関数の中で作られて返された関数というのは、作られたときの状態(この場合は関数 make-adder の引数 n が何であったかなど)を、いつまでも覚えていなければならない。

> (define (make-adder n)
    (lambda (m) (+ m n)))
> (define add1 (make-adder 1))
> (define add2 (make-adder 2))
> (add1 10)  ; add1 は (lambda (m) (+ m n)) という式と、n=1 だったことを覚えている
11
> (add2 10)  ; add2 は (lambda (m) (+ m n)) という式と、n=2 だったことを覚えている
12

解説

この例を実現するだけなら、(lambda (m) (+ m 1)) という式や (lambda (m) (+ m 2)) という式を直接覚えておけばよいと考えるかもしれない
しかし、実はadd1やadd2に対し、n を後で変更できる仕組みが用意されており（3節、4節）そのためにはそれでは不十分である
前回で解説したようなλ-closureは「引数、本体、環境」から成っており、その中の環境が状態を覚えておくのに役に立つ。

環境モデルの続き

let

(let ((v1 e1) (v2 e2) ... (vn en)) <body> ...)

は

((lambda (v1 v2 ... vn) <body> ...)
 e1 e2 ... en)

と同じことである。

ここで、ei は拡張された環境で評価されるのではないことに注意。

実行例

> ((lambda (a b c) (+ a b c))
   3 7 2)
12
> (let ((a 3) (b 7) (c 2)) (+ a b c))
12
> (let ((a 3) (b a) (c 2)) (+ a b c))
*** ERROR IN (stdin)@10.16 -&minus; Unbound variable: a
1>

局所変数（局所関数）

define は、現在の最外フレームに変数や関数を作る
（すでに、作られていれば書き換える）
局所的に関数が作られた場合、その λ-closureが覚えている環境は、作られたときの環境
局所関数が実行されると、その記録してある環境がさらに新しいフレームで拡張されることになる。

1 > (define (fac n)
      (define (iter-fac product counter)
        (if (> counter n)     ;  iter-fac が作られたときのフレームの n を参照
            product
            (iter-fac (* product counter) (+ counter 1))))
      (iter-fac 1 1))
2 > (fac 1)           ; (fac 1) の実行中に iter-fac が定義されている
  1

環境モデルの実装による再現

  > (define init-env (make-env))
1 > (define-value! 'fac
      (list '*lambda* '(n)
        '(begin (define (iter-fac product counter)
                  (if (> counter n)
                      product
                      (iter-fac (* product counter) (+ counter 1))))
                (iter-fac 1 1))
        init-env)
      init-env)
2 > (define fac-env (extend init-env '(n) '(1)))
2 > (define-value! 'iter-fac
      (list '*lambda* '(product counter)
        '(if (> counter n)
             product
             (iter-fac (* product counter) (+ counter 1)))
        fac-env)
      fac-env)
2 > (define iter-fac-env (extend fac-env '(product counter) '(1 1)))
2 > (get 'counter iter-fac-env)  ; (> counter n) の計算のため
  (counter . 1)
2 > (get 'n iter-fac-env)        ; (> counter n) の計算のため
  (n . 1)
2 > (get 'product iter-fac-env)  ; (* product counter) の計算のため
  (product . 1)
2 > (get 'counter iter-fac-env)  ; (* product counter) の計算のため
  (counter . 1)
2 > (get 'counter iter-fac-env)  ; (+ counter 1) の計算のため
  (counter . 1)
2 > (define iter-fac2-env (extend fac-env '(product counter) '(1 2)))
2 > (get 'counter iter-fac2-env) ; (> counter n) の計算のため
  (counter . 2)
2 > (get 'n iter-fac2-env)       ; (> counter n) の計算のため
  (n . 1)
2 > (get 'product iter-fac2-env)
  (product . 1)

高階関数 (higher-order functions)

関数の実行時に拡張されたフレームは、その実行が終わると忘れられてしまう
それを覚えておくには、環境を覚えてくれるもの、すなわち関数を返して、大域環境で名前を付ければよい。
下の add1 は大域環境に定義されているが、作られたのは関数 make-adder の実行時である

したがって、そのときの環境（拡張されたフレームに n=1 が記録されている）を覚えている。

1 > (define (make-adder n)
      (lambda (m) (+ m n)))
2 > (define add1 (make-adder 1))
3 > (define add2 (make-adder 2))
4 > (add1 3)
  4

環境モデルの実装による再現

  > (define init-env (make-env))
1 > (define-value! 'make-adder
      (list '*lambda* '(n)
        '(lambda (m) (+ m n))
        init-env)
      init-env)
2 > (define make-adder-env (extend init-env '(n) '(1)))
2 > (define-value! 'add1
      (list '*lambda* '(m)
        '(+ m n)
        make-adder-env)
      init-env)
3 > (define make-adder2-env (extend init-env '(n) '(2)))
3 > (define-value! 'add2
      (list '*lambda* '(m)
        '(+ m n)
        make-adder2-env)
      init-env)
4 > (define add1-env (extend make-adder-env '(m) '(3)))
4 > (get 'm add1-env)
  (m . 3)
4 > (get 'n add1-env)
  (n . 1)

シンタックス形式set!

(set! <変数> <式>)

<変数> の値を <式> を評価した結果に書き換える
<変数> はあらかじめ宣言されていなくてはならない
（多くの実装では、<変数>が宣言されていない場合はdefineと同義）
返り値は不定
<変数> を評価せずに<変数> そのものとして扱うところがシンタックス形式
注意

今回の set!と前回の set-car!の間には重要な違いがある

set-car!やset-cdr!は第一引数をまず評価して、求まったペアに対してそこから延びるポインタの付け替えを行う
（引数が先に全て評価されるので、シンタックス形式ではなく、ただの関数）
一方、set!は引数を「変数そのもの」として受け取り、それが現在何を指しているかにかかわらず、その変数に別の値を指させる
（したがってシンタックス形式）
たとえば次の(set! y 'ccc) で変化するのは y のポインタのみで、x のポインタは変化しない。

> (define x (cons 'a 'b))
> (define y x)
> (set-car! y 'aaa)
> (set! y 'ccc)
> y
ccc
> x
(aaa . b)

状態を持つ関数の例：銀行口座

局所変数 (Local Variable) の書き換え

銀行口座（預金残高）を作るために、関数を返す関数 make-withdraw を用意している
make-withdrawは初期値を与えて実行するたびに、新しい口座を表す関数を返す
返された関数 w1 や w2 は、それぞれ自分が作られたときの環境（引数 balance を含む）を覚えている

(define (make-withdraw balance)
  (lambda (amount)
    (if (>= balance amount)
        (begin (set! balance (- balance amount))
               balance)
        "Insufficient funds")))

set! は define と違い、環境をさかのぼって最初に出会った変数を書き換える
この機能により、w1 や w2 は、実行時のフレームではなくbalance を含むフレームを変更できる

1 > (define w1 (make-withdraw 10000))
2 > (define w2 (make-withdraw 5000))
3 > (w1 1000)
  9000
4 > (w2 6000)
  "Insufficient funds"
5 > (w1 6000)
  3000

オブジェクト指向風

関数（λ-closure）は、変更可能な状態を持つことができるデータであり、オブジェクト指向のまさにオブジェクトとみなすこともできる
たとえば acc は、balanceという変数とwithdrawとdepositというメソッドを持つオブジェクトである

(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 amount)
    (cond ((eq? m 'withdraw) (withdraw amount))
          ((eq? m 'deposit) (deposit amount))
          (else "Unknown request")))
  dispatch)
(define acc (make-account 10000))
> (acc 'withdraw 5000)
5000
> (acc 'withdraw 6000)
"Insufficient funds"
> (acc 'deposit 4000)
9000
> (acc 'withdraw 6000)
3000

レポート課題５

問１

4.2 のオブジェクト指向プログラムを拡張し、Password を持つ銀行口座を作成せよ

仕様は次の様にするが、自由に拡張してかまわない

(make-account ) で残高がでパスワードがであるような関数を返す
パスワードは適当なシンボルとする
ここで (define nisizawa-acc (make-acount 10000 'hagiya)) としたとしよう

(nisizawa-acc 'hagiya 'withdraw amount)はパスワードが一致した時のみ預金を引き出す
(nisizawa-acc 'hagiya 'deposit amount)はパスワードが一致した時のみ入金する
パスワードが合わない時は、どのような金額を受けとっても次のようなメッセージを出す

> (nisizawa-acc 'hagya 'deposit 10000)
"incorrect password"

make-account で返された関数に対して、連続して３回、間違ったパスワードでアクセスするとcall-the-cops という関数を呼ぶようにする
（call-the-cops の内容は自由）

また、下のように動作することを確認せよ

> (define acc (make-account 10000 'password))
> (acc 'password 'withdraw 3000)
7000
> (acc 'password 'withdraw 10000)
"Insufficient funds"
> (acc 'password 'deposit 1000)
8000
> (acc 'wrong 'withdraw 5000)
"incorrect password"
> (acc 'password 'withdraw 5000)
3000
> (acc 'wrong 'withdraw 1000)
"incorrect password"
> (acc 'pass 'deposit 1000)
"incorrect password"
> (acc 'word 'withdraw 1000)
"You're under arrest."

問２

前回実装した環境モデルに、次のインターフェースを追加せよ

(set!-value! var value env):

env の中から（最外フレームから順に）var の指す値を探し、その値を value に書き換える
var が見つからない時には、define-value!と同様に最外フレームに定義を追加する
返り値は不定でよい
※ define-value!は最外フレームに値が定義されていた場合のみ書き換えたが、set-value!は環境に値が定義されていた場合に書き換える

また、下のように 4.1 の実行例で環境にアクセスしているところを再現せよ

入力プログラム

  > (define init-env (make-env))
  > (define-value! 'make-withdraw
      (list '*lambda* '(balance)
        '(lambda (amount)
           (if (>= balance amount)
               (begin (set! balance (- balance amount))
                      balance)
               "Insufficient funds"))
        init-env)
      init-env)
1 > (define make-withdraw-env (extend init-env '(balance) '(10000)))
1 > (define-value! 'w1
      (list '*lambda* '(amount)
        '(if (>= balance amount)
             (begin (set! balance (- balance amount))
                    balance)
             "Insufficient funds")
        make-withdraw-env)
      init-env)
2 > (define make-withdraw2-env (extend init-env '(balance) '(5000)))
2 > (define-value! 'w2
      (list '*lambda* '(amount)
        '(if (>= balance amount)
             (begin (set! balance (- balance amount))
                    balance)
             "Insufficient funds")
        make-withdraw2-env)
      init-env)

3 > (define w1-env (extend make-withdraw-env '(amount) '(1000)))
3 > (get 'balance w1-env)
  (balance . 10000)
3 > (get 'amount w1-env)
  (amount . 1000)
3 > (get 'balance w1-env)
  (balance . 10000)
3 > (get 'amount w1-env)
  (amount . 1000)
3 > (set!-value! 'balance 9000 w1-env)
3 > (get 'balance w1-env)
  (balance . 9000)
4 > (define w2-env (extend make-withdraw2-env '(amount) '(6000)))
4 > (get 'balance w2-env)
  (balance . 5000)
4 > (get 'amount w2-env)
  (amount . 6000)
5 > (define w12-env (extend make-withdraw-env '(amount) '(6000)))
5 > (get 'balance w12-env)
  (balance . 9000)
5 > (get 'amount w12-env)
  (amount . 6000)
5 > (get 'balance w12-env)
  (balance . 9000)
5 > (get 'amount w12-env)
  (amount . 6000)
5 > (set!-value! 'balance 3000 w12-env)
5 > (get 'balance w12-env)
  (balance . 3000)

Scheme演習 第５回

関数から返された関数

解説

環境モデルの続き

let

局所変数（局所関数）

環境モデルの実装による再現

高階関数 (higher-order functions)

環境モデルの実装による再現

シンタックス形式set!

状態を持つ関数の例：銀行口座

局所変数 (Local Variable) の書き換え

オブジェクト指向風

レポート課題５

問１

問２

Scheme演習第５回