演習問題

Scheme SICP

25ページで止まっとる。全然読めてないな。今のところプログラムの勉強というか英語の長文読解のような感じ。とりあえず、演習問題の回答でも書いとこう。

Exercise 1.1

次の式を順にインタプリタで評価する場合、評価結果がどうなるかしらべなさい。

gosh> 10
10
gosh> (+ 5 3 4)
12
gosh> (- 9 1)
8
gosh> (/ 6 2)
3
gosh> (+ (* 2 4) (- 4 6))
6
gosh> (define a 3)
a
gosh> (define b (+ a 1))
b
gosh> (+ a b (* a b))
19
gosh> (= a b)
#f
gosh> (if (and (> b a) (< b (* a b)))
          a
          b)
3
gosh> (cond
       ((= a 4) 6)
       ((= b 4) (+ 6 7 a))
       (else 25))
16
gosh> (+ 2 (if (> b a) b a))
6
gosh> (* (cond ((> a b) a)
               ((< a b) b)
               (else -1))
         (+ a 1))
16

Exercise 1.2

次の式を中置記法に翻訳しなさい。
\frac{5+4+(2-(3-(6+\frac{4}{5})))}{3(6-2)(2-7)}

(/ (+ 5
      4
      (- 2
         (- 3
            (+ 6
               (/ 4 5)))))
   (* 3
      (- 6 2)
      (- 2 7)))

インデントやりすぎだろ常考...

Exercise 1.3

3個の数値を引数に取って、大きい2個の数値の二乗和を求める手続きを定義しなさい。

(define (f a b c)
  (define (g . lis)
    (fold (lambda (kar acc) (+ acc (* kar kar))) 0 lis))
  (apply g (cond ((and (< a b) (< a c)) `(,b ,c))
                 ((and (< b c) (< b a)) `(,c ,a))
                 (else `(,a ,b)))))

gosh> (f 1 2 3)
13
gosh> (f 2 3 1)
13
gosh> (f 3 1 2)
13

この演習問題の時点では

  • 手続き内手続き
  • 可変長引数
  • fold
  • lambda式
  • apply
  • 準クオート

はまだ出てきてないけど。

Exercise 1.4

評価的順序は、演算子（operators）が複合式（compound expressions）になっているような組合わせ（combinations）にも有効であることを、次の手続きで確認しなさい。

(define (a-plus-abs-b a b)
  ((if (> b 0) + -) a b))

(a-plus-abs-b 5 -2)

の評価過程を観察してみる。

  1. 引数である5と-2を評価し、それぞれ整数オブジェクトの5と-2を得る
  2. 仮引数を実引数で置き換えつつ、手続きの本体を取り出す => ((if (> -2 0) + -) 5 -2)
  3. if式を評価する => (- 5 -2)
  4. (ﾟдﾟ)ｳﾏｰ

Exercise 1.5

Ben Bitdiddle氏は、彼のインタプリタが評価的順序と正規順序のどちらを用いているか調べる以下のようなテストを考案した。

(define (p) (p))
(define (test x y)
  (if (= x 0) 0 y))

上記のような手続きを定義し、

(test 0 (p))

を評価するとき、評価的順序を採用したインタプリタの場合はどうなるか？また、正規順序の場合はどうなるか？（ただし、特殊形式ifの評価の順序は評価的順序でも正規順序でも同じとする）

評価的順序の場合
  1. まず引数を評価する
    1. 0を評価 => 整数0
    2. (p)を評価 => 計算が停止しない
正規順序の場合
  1. 仮引数を実引数で置き換えつつ、testを本体で置き換え => (if (= x 0) 0 (p))
  2. ifの評価順序に従い、0へと評価される。
結論

評価的順序では、関数適用に先立ち全ての引数を評価してしまうので、計算が停止しない。一方で、正規順序の場合は、(p)が一度も評価されないので、評価が停止し0が返る。