9
10
2012
8

正则序和应用序

练习1.5

Ben 发明了一种检测方法来确定Lisp的解释器采用应用序(Applicative Order)还是正则序(Normal Order)来求值。

他定义了下面两个过程并进行检测:

;过程定义
(define (p) (p))
(define (test x y)
        (if (= x 0) 0 y))
;检测
(test 0 (p))

问解释器使用应用序和正则序时分别输出什么结果?


解释器怎么解释这段程序呢?

如果是按正则序的话,解释器会“完全展开而后规约”,所以求值流程如下:

(test 0 (p))
;展开test 得到以下程序
(if (= 0 (p)) 0 (p))
;对谓词(= )进行求值
(if (#t) 0 (p))
;谓词等于真 返回0
0

这个if语句的行为很重要,实际上if发现(p)并没有被求值的必要。

如果是按应用序的话,解释器会“先对参数求值而后应用”,所以流程如下:

(test 0 (p))
;对参数(p)求值,根据(p)的定义,解释器又得到了(p)
(test 0 (p))
;程序将不会产生有意义的输出

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com