[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を返します.