[SICP] 問題 1.06 : ifが特殊形式である理由

Alyssa P. Hackerはifが特殊形式である理由が分らない. 「cond を利用し, 普通の手続きとして定義してはいけないの?」と聞いた. Alyssaの友人のEva Lu Atorはそうすることはもちろん出来るといって, ifの新版を定義した:

(define (new-if predicate then-clause else-clause)
  (cond (predicate then-clause)
        (else else-clause)))

EvaはAlyssaにプログラムを見せた:

(new-if (= 2 3) 0 5)
5

(new-if (= 1 1) 0 5)
0

Alyssaは喜び, 平方根のプログラムを書き直すのにnew-ifを使った:

(define (sqrt-iter guess x)
  (new-if (good-enough? guess x)
          guess
          (sqrt-iter (improve guess x)
                     x)))

Alyssaが平方根を計算するのにこれを使おうとすると, 何が起きるか, 説明せよ.

new-ifを使って平方根を求める手続きを定義します. 手続き名sqrtは解釈系で定義済みであるため, my-sqrtとしています.

(define (new-if predicate then-clause else-clause)
  (cond (predicate then-clause)
        (else else-clause)))

(define (square x)
  (* x x))

(define (average x y)
  (/ (+ x y) 2))

(define (good-enough? guess x)
  (< (abs (- (square guess) x)) 0.001))

(define (improve guess x)
  (average guess (/ x guess)))

(define (sqrt-iter guess x)
  (new-if (good-enough? guess x)
      guess
      (sqrt-iter (improve guess x)
                 x)))

(define (my-sqrt x)
  (sqrt-iter 1.0 x))

この手続を使って平方根を求めてみると, 解釈系は停止しません. その理由は, new-ifが特殊形式ではなく, 解釈系が作用的順序で評価しているためです.

new-ifは特殊形式ではないため, new-ifを評価するために三つの引数を評価します. ３つ目の引数でsqrt-iterを呼び出しているため無限ループに入り, 解釈系は停止しません.

ifは特殊形式であるため, まずguessの値が「十分よい」か判定します. 「十分よい」を場合は, sqrt-iterを評価せずguessを返すので解釈系は停止します.

[SICP] 問題 1.05 : 作用的順序と正規順序

Ben Bitdiddleは, 彼の対面している解釈系が, 作用的順序の評価を使っているか, 正規順序の評価を使っているか決定するテストを発明した. 次の二つの手続きを定義した:

(define (p) (p))

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

彼は次に式

(test 0 (p))

を評価してみた. 作用的順序の評価を使う解釈系で, Benはどういう振舞いを見るか. 正規順序の評価を使う解釈系で, 彼はどういう振舞いを見るか. 説明せよ. (特殊形式ifの評価規則は, 解釈系が正規順序と作用的順序のどちらを使うかに無関係に同じとする: 述語式を最初に評価し, その結果が帰結式と代替式のいずれを評価するかを決める.)

問題文の手続きを定義します.

(define (p) (p))

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

式(test 0 (p))を評価すると, 解釈系は停止しません. その理由を考えます.

まず, この問題を理解するためには, 手続きpが無限ループを表していることに気づかなくてはなりません. 手続きpの本体で式(p)を呼び出しているので, 式(p)を評価すると式(p)を評価し続けるため, 解釈系は停止しません.

作用的順序で評価すると次のようになります.

1. 式(test 0 (p))を評価します.
2. 引数である0と(p)を評価します.
3. 式(p)を評価すると無限ループに入ります.
4. その結果, 解釈系は停止しません.

正規順序で評価すると次のようになります.

1. 式(test 0 (p))を評価します.
2. 手続きの定義に従いif式に展開します.
   (if (= 0 0) 0 (p))
3. if式は特殊形式であるため, まず述語部分を評価します.
4. 述語部は(= 0 0)であるためtrueとなります.
5. 述語部がtrueであるため, 帰結部のみが評価されます.
6. 帰結部は0であるため, 0を返します.

引数yの値は式(p)ですがif式の代替部に相当し, 述語部がtureとなるため評価されません. そのため、解釈系が正規順序で評価するのであれば, 無限ループに入らず評価結果として0を返します.

[SICP] 問題 1.04 : 合成式を演算子として使う

われわれの評価モデルは, 演算子が合成式である組合せでも使えることを観察せよ. それに従って, 次の手続きの振舞いを述べよ.

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

問題文の手続きをエディタに入力します.

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

「+」などの演算子が入る箇所にif式が入っているので、奇妙な感じがします. この手続を評価してみます.

ようこそ DrRacket, バージョン 6.1 [3m].
言語: Pretty Big; memory limit: 2048 MB.
> (a-plus-abs-b 4 3)
7
> (a-plus-abs-b 4 -3)
7
> 

評価結果から, aにbの絶対値を加えていることが分かります. こういう事ができるからといって, 何が嬉しいのかは今の時点ではよくわかりませんが, テキストを読み進めると, こういうことができないと苦労する例が出てきます＼(^o^)／

[SICP] 問題 1.03 : 三つの数を引数として取り、大きい二つの数の二乗の和を返す手続き

三つの数を引数としてとり, 大きい二つの数の二乗の和を返す手続きを定義せよ.

問題文を計算する手続きを定義します.

1. 手続きは, 三つの引数x, y, zを取ることとします.
2. xが最小であればyとzをそれぞれ二乗し,その和を返します.
3. 同様に, yが最小である場合, zが最小である場合もそれぞれ計算します.

これを手続きとして定義します.

(define (square x)
  (* x x))

(define (sum-square-large-2 x y z)
  (cond ((and (<= x y) (<= x z)) (+ (square y) (square z)))
        ((and (<= y z) (<= y x)) (+ (square z) (square x)))
        ((and (<= z x) (<= z y)) (+ (square x) (square y)))))

計算してみます.

ようこそ DrRacket, バージョン 6.1 [3m].
言語: Pretty Big; memory limit: 2048 MB.
> (sum-square-large-2 1 2 3)
13
> (sum-square-large-2 4 2 3)
25
> (sum-square-large-2 1 5 3)
34
> (sum-square-large-2 1 3 3)
18
> (sum-square-large-2 2 2 2)
8
> 

計算結果から, 手続きはうまく定義できているようです.

手続きの定義をよく眺めると, 同じような構造が繰り返されており, 引数が循環していることが分かります. この構造に着目することで, 手続きの定義をもっと簡潔にできます. 手続名をsum-square-large-2-rとして定義します.

(define (square x)
  (* x x))

(define (sum-square-large-2-r x y z)
  (if (and (<= x y) (<= x z))
      (+ (square y) (square z))
      (sum-square-large-2-r y z x)))

この手続定義で何をしているかを説明します.

1. 引数xの値が最も小さい場合は, yの2乗とzの2乗の和を求めます.
2. それ以外の場合は, 引数の順序を入替えて自分自身を呼び出します.
3. 引数x, y, zのどれかが最小になるので, 残りの引数のそれぞれを2乗し, その和を返します.

手続きのテストをするため, 同じ条件で計算してみます.

ようこそ DrRacket, バージョン 6.1 [3m].
言語: Pretty Big; memory limit: 2048 MB.
(13 25 34 18 8)
> (sum-square-large-2-r 1 2 3)
13
> (sum-square-large-2-r 4 2 3)
25
> (sum-square-large-2-r 1 5 3)
34
> (sum-square-large-2-r 1 3 3)
18
> (sum-square-large-2-r 2 2 2)
8
> 

結果は一致しています.

[SICP] 問題 1.02 : 前置記法

次の式を前置記法に翻訳せよ.

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

Lispでは前置記法を採用しているため, 前置記法に慣れるための問題です. p.5の図のように数式の構造を把握できれば, 前置記法に書き表せます.

Racketのエディタは, カッコを閉じた時に対応する開きカッコを調べてくれます. また, タブキーを押すとインデント量を適切に設定してくれます. これらの機能をうまく使えば, 入力した式の構造を理解しやすくなります.

前置記法に翻訳した式は次のとおりです.

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

式を評価した結果は次のとおりです.

ようこそ DrRacket, バージョン 6.1 [3m].
言語: Pretty Big; memory limit: 2048 MB.
> (/ (+ 5 4 (- 2 (- 3 (+ 6 (/ 4 5)))))
     (* 3 (- 6 2) (- 2 7)))
-37/150
> 

結果が有理数の場合, 分数のまま返してくれるので驚きです.

手で計算した結果と合っていました(^o^)

[SICP] 問題 1.01 : 解釈系を使う

式の列がある. それぞれの式で解釈系が印字する結果は何か. 列は示した順に評価するものとする.

10

(+ 5 3 4)

(- 9 1)

(/ 6 2)

(+ (* 2 4) (- 4 6))

(define a 3)

(define b (+ a 1))

(+ a b (* a b))

(= a b)

(if (and (> b a) (< b (* a b)))
    b
    a)

(cond ((= a 4) 6)
      ((= b 4) (+ 6 7 a))
      (else 25))

(+ 2 (if (> b a) b a))

(* (cond ((> a b) a)
         ((< a b) b)
         (else -1))
   (+ a 1))

DrRacketに式を入力し, その応答を観察します. Racketを起動し, 画面の下側に式を入力した結果は次の通りです.

ようこそ DrRacket, バージョン 6.1 [3m].
言語: Pretty Big; memory limit: 2048 MB.
> 10
10
> (+ 5 3 4)
12
> (- 9 1)
8
> (/ 6 2)
3
> (+ (* 2 4) (- 4 6))
6
> (define a 3)
> (define b (+ a 1))
> (+ a b (* a b))
19
> (= a b)
#f
> (if (and (> b a) (< b (* a b)))
      b
      a)
4
> (cond ((= a 4) 6)
        ((= b 4) (+ 6 7 a))
        (else 25))
16
> (+ 2 (if (> b a) b a))
6
> (* (cond ((> a b) a)
           ((< a b) b)
           (else -1))
     (+ a 1))
16
> 

最後の２つの式で, ifやcondの結果をそのまま式の値として使用しています. Schemeでは, 式と文の区別がありません.

カラマーゾフの妹（高野 文緒 著、講談社文庫）

カラマーゾフの妹 (高野 文緒 著、講談社文庫)

ドストエフスキーの「カラマーゾフの兄弟」の続編として書かれています。もともと、「カラマーゾフの兄弟」は2部構成の第1部にあたり、第2部の伏線と思われる記述があります。結局、ドストエフスキーは第2部を書かずに死んだため、中途半端な状態のままになっています。

著者は、第2部に相当する「カラマーゾフの妹」を書くことで、第1部の伏線や矛盾点を解決しようと試みています。こういう見方があるのかと感心しましたが、第1部の詳細は忘れました＼(^o^)／

この本を読む前に、「カラマーゾフの兄弟」を一通り読むことをオススメします。



何が言いたいかというと、

私はカラマーゾフの兄弟を読んだ＼(^o^)／

と、いうことです。