正则序和应用序


要点: 正则序:先展开过程,再求值。 应用序:先求值,再代入过程。

SICP习题1.5中答案所述,对于以下代码:

(define (p) (p))

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

如果解释器采用的是应用序,则程序会不断地执行,因为需要求值p函数,然而p函数返回自己,因此进入死循环。

(test 0 (p)) 
(test 0 (p)) 
(test 0 (p))
...

而对于采用正则序的解释器,程序则能成功输出0,因为,解释器先展开过程,再求值(如果表达式有用到,而这里因为x=0,并没有用到p函数),过程是这样的:

(test 0 (p)) 
 (if (= 0 0) 0 (p)) 
 (if #t 0 (p)) 
 0