やろーじだい

ブログです

Aizu SICP 第12回

 やりました。範囲は P99 練習問題 2.6 ~ P101 練習問題 2.10 です。ここから読書会参加者で scheme のテストを利用するようにしました。(gauche 利用者は gauche.test を、 racket 利用者は rackunit を利用しています。) 今後は利用したテストケース (ただし gauche の方だけ) も記述しておきます。

練習問題 2.6

 しっかりチャーチ数について調べていないが、 id 関数に対して何回関数 f を適用するかによって数字というものを表現しているようだ。zero というものは f を受けとるが適用せずに捨てていることに注意したい。

(define zero
  (lambda (f) (lambda (x) x)))

(define (add-1 n)
  (lambda (f) (lambda (x) (f ((n f) x)))))

(add-1 zero)
;; ↓
(add-1 (lambda (f) (lambda (x) x)))
;; ↓
(lambda (f) (lambda (x) (f (((lambda (f) (lambda (x) x)) f) x))))
                             ---------------------------
                                  ;; ここが n
;; ↓
(lambda (f) (lambda (x) (f (((lambda (f) (lambda (x) x)) f) x))))
                            -------------------------------
                            ;; f を適用するが f は使われずに内側の (lambda (x) x) だけが残る
;; ↓
(lambda (f) (lambda (x) (f ((lambda (x) x) x))))
                           ------------------
                           ;; (lambda (x) x) に x を渡すと x になる
;; ↓
(lambda (f) (lambda (x) (f x)))
;; これが one

(define one
  (lambda (f) (lambda (x) (f x))))

;; 同様に one に add-1 を適用すれば two ができる
(define two
  (lambda (f) (lambda (x) (f (f x)))))

これはつまり、ある x に対して Haskellsucc 関数のようなものを適用することで次のものにするということを表現していると考えられるので、f として (+1) を、x として 0 を渡せば整数に変換できる。

 ちなみに hoogle:succ にあるように succHaskellEnum 型が持つ method の一つで、『後継 (successor)』を意味する関数になる。(数字だけではなく、順序が定義されていれば渡された値の次の値を返す)

 Scheme では (+1) として inc を定義する。

(define (inc x)
  (+ 1 x))

よって以下のように、zerotwo、またはそれらに add-1 したものに inc0 を渡すことによって整数に変換できる。

((zero inc) 0)
;=> 0
((two inc) 0)
;=> 2
(((add-1 (add-1 two)) inc) 0)
;=> 4

 また、例えば zero として #\afnext-char という手続きを定義して渡せば文字にも変換できる。

(define (next-char x)
  (integer->char (+ 1 (char->integer x))))

(((add-1 two) next-char) #\a)
;=> #\d

 次に加算手続き (plusとする) だが、考え方としては、まず最終的には inc0 を受けとれるような形である必要があるので以下のような形になる (... は未定義な場所とする)。

(define (plus a b)
  (lambda (f) (lambda (x) ...)))

次に、ab に入ってくるのは上で定義した onetwo であるので、例えば (plus one two) と呼ばれた場合の結果を考えると以下のようになる。

(lambda (f) (lambda (x) (f (f (f x)))))

これを踏まえると x に対して onetwo によって plus が受けとる f を適用すれば良いことがわかったので、結果は以下のようになる。

(define (plus a b)
  (lambda (f) (lambda (x) ((a f) ((b f) x)))))
;; Test
(test-section "practice 2.6")

(test "zero" 0
      (^[] ((zero inc) 0)))

(test "one" 1
      (^[] ((one inc) 0)))

(test "two" 2
      (^[] ((two inc) 0)))

(test "add-1" 3
      (^[] (((add-1 (add-1 one)) inc) 0)))

(test "plus" 3
      (^[] (((plus two one) inc) 0)))

(test "plus" 5
      (^[] (((plus two three) inc) 0)))

(test "character-church" #\d
      (^[] (((add-1 two) next-char) #\a)))

2.1.4 発展問題: 区間演算

二つ区間の割り算は、⼀つ⽬に⼆つ⽬の逆数をかけることにします。区間の逆数の下限と上限は、上限の逆数と下限の逆数という順番になることに気をつけてください。

(Page 100).

これに関しては、以下の練習問題 2.7 で気にしなくて良いようにした。

練習問題 2.7

 区間のオブジェクトは端点を二つ持ち、upper-bound (lower-bound) によって大きい方 (小さい方) を返すようにした。

(define (upper-bound interval)
  (max (car interval) (cdr interval)))

(define (lower-bound interval)
  (min (car interval) (cdr interval)))

計算量的な問題で以下のように make-intervalcar 部を小さい方、cdr 部を大きい方とするべきだろうと思う。と言うのも upper-boundlower-boundmul-interval などで同じオブジェクトに対して複数回呼ばれるため無駄な計算が増えてしまう。

(define (make-interval a b)
 (if (< a b)
     (cons a b)
     (cons b a)))
(test-section "practice 2.7")

(test "upper-bound" 3
      (^[] (upper-bound (make-interval 3 0))))

(test "lower-bound" 0
      (^[] (lower-bound (make-interval 3 0))))

練習問題 2.8

 差の場合は、引かれる方の最大値から引く方の最小値が、新しい区間の最大に、引かれる方の最小値から引く方の最大値が新しい区間の最小値になる。よって定義は以下のようになる。

(define (sub-interval x y)
  (make-interval (- (upper-bound x) (lower-bound y))
                 (- (lower-bound x) (upper-bound y))))
(test-section "practice 2.8")

(test "sub-interval"
      (cons 8 -2)
      (^[] (sub-interval (make-interval 10 3)
                         (make-interval 5 2))))

(test "sub-interval"
      '(100 . 0)
      (^[] (sub-interval (make-interval 100 25)
                         (make-interval 25 0))))

練習問題 2.9

区間の幅 (width) は、上限と下限の差の半分である。 幅は、区間によって規定される数値の不確かさの程度である。

(Page 101).

幅という単語からは上限と下限の差であることはイメージできるが、半分ということなので精度に近いものだろうということで理解した。

 まず具体例から考えてみる。以下では width という幅を求める関数には区間が渡され、区間[2,5] のように表現することにする。

// 加算
width([2, 5]) = 3.0/2 = 1.5
width([3, 8]) = 5.0/2 = 2.5
width([2, 5]) + width([3, 8]) = 1.5 + 2.5 = 4.0

add-interval([2,5], [3,8]) = [5, 13]
width([5, 13]) = 8.0/2 = 4.0

//減算
width([3, 8]) = 5.0/2 = 2.5
width([2, 5]) = 3.0/2 = 1.5
width([3, 8]) + width([2, 5]) = 2.5 + 1.5 = 4.0

sub-interval([3,8], [2,5]) = [-2, 6]
width([-2, 6]) = 8.0/2 = 4.0

よって、加算と減算に関しては width の結果の関数として表現可能できそうである。関数であるので width の結果の演算になっていれば良く、。これを示すと。

// 加算
// a < b, c < d とする
width([a, b]) = (b-a)/2 = t
width([c, d]) = (d-c)/2 = s
width([a+c, b+d]) = {b+d-(a+c)}/2 = {(b-a)/2} + {(d-c)/2} = t + s

// 減算
// 同じく a < b, c < d とする
width([a, b]) = (b-a)/2 = t
width([c, d]) =  (d-c)/2 = s
width([a-d, b-c]) = {b-c-(a-d)}/2 = {(b-a)/2} + {(d-c)/2} = t + s

よって関数となることを示せた。

 次に積算と除算については具体例で考えてみる。

//積算1
width([3,8]) = (8-3)/2 = 2.5 = t1
width([2,5]) = (5-2)/2 = 1.5 = s1
// それぞれの要素間の積は 3*2 = 6, 3*5 = 15, 8\*2 = 16, 8\*5 = 40 であるので
width([6,40]) = (40-6)/2 = 17 

//積算2
width([4,10]) = (10-4)/2 = 3.0 = t2
width([0,5]) = (5-0)/2 = 2.5 = s2
// それぞれの要素間の積は 0, 20, 0, 50 となるので
width([0,50]) = (50-0)/0 = 25

// 以上の二つを同じ関数では表現できないので、関数化不可能である。除算も同様だと思う。

練習問題 2.10

 ゼロを跨ぐ区間で除算を行うと問題となる理由は y=1/x のグラフを見てみるとわかりやすい (グラフ:wolframalpha)。

 0 での除算は未定義である上、 0 付近での除算が大きい数字になるにも関わらず、現在の div-interval では区間の両端でのみ考えているため誤った結果を返してしまう。

(define (div-interval x y)
  (mul-interval
   x
   (make-interval (/ 1.0 (upper-bound y))
                   (/ 1.0 (lower-bound y)))))

gosh> (div-interval (make-interval 10 20) (make-interval 5 -5))
(-4.0 . 4.0)

分母となる区間の両端の積の符号が負である場合はエラーを返すようにする。

(define (div-interval x y)
  (mul-interval
   x
   (if (>= (* (upper-bound y) (lower-bound y)) 0)
       (make-interval (/ 1.0 (upper-bound y))
                      (/ 1.0 (lower-bound y)))
       (error "ゼロを跨ぐ区間です"))))

gosh> (div-interval (make-interval 10 20) (make-interval 5 -5))
*** ERROR: ゼロを跨ぐ区間です