正規順序と作用的順序による評価

SICP問題1.5
手続き

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

を定義した後で、

(test 0 (p))

を評価する。

正規順序の場合

展開の様子をトレースしてみる。正規順序は完全に展開する。そのため引数はそのままに、評価対象の式の手続き部分を展開していく。

(test 0 (p))

(if (= 0 0)
  0
  (p)))

pは自分自身を呼び出す関数なのでこれ以上は展開できない。if文が評価されて、述語が真なので0が返る。

作用的順序の場合

作用的順序の評価は、評価対象の式の引数部分から評価していく。

(test 0 (p))

の段階で、まず0を評価し、次に(p)を評価しようとする。pは自分自身を呼び出す関数なので無限ループに入る。

gaucheで実験したところ無限ループに入った。Lispでは作用的順序の評価を使っている。