Scheme演習 第5回

品川 嘉久, 浅井 健一, 萩谷 昌己, 西澤 弘毅, 原 謙治
[Table of Contents] [Index] [携帯版]

関数から返された関数
  • 下の関数 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

レポート課題5

問1
  • 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 で返された関数に対して、連続して3回、間違ったパスワードでアクセスすると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."

問2
  • 前回実装した環境モデルに、次のインターフェースを追加せよ
    • (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)


This page is generated by mtd2html.