Lisp 语言求值过程的Normal Order与Applicative Order

在对Lisp的复合表达式求值时,可以有两种不同的方式:Normal OrderApplicative Order
我们先来定义一些函数:

(define (bar v)
    (* v 4))
(define (foo x)
    (+ x 5 (bar x)))

当我们对(foo 10)求值时,如果使用Normal Order,求值顺序将是这样的:

;Normal Order: full expand, then reduce.
(foo 10)
(+ 10 5 (bar 10))
(+ 10 5 (* 10 4))
(+ 10 5 40)
55

如果使用Applicative Order,则是这样的:

;Applicative Order: evaluate the arguments and then apply.
(foo 10)
(+ 10 5 (bar 10))

;开始对(bar 10)求值
(bar 10)
(* 10 4)
40

;将结果代入
(+ 10 5 40)
55

在特定情景下,结果是完全相同的

但是,结果并不总是这样:下面的代码段就可以区分两者

(define (boom) (boom))
(define (test a b)
    (if (= a 0) 0 b))

执行(test 0 (boom))
若为Normal Order:

(test 0 (boom))
(if (= 0 0) 0 (boom))
(if (= 0 0) 0 (boom))
(if (= 0 0) 0 (boom))
...
;不断尝试展开(boom),于是解释器boom!

若为Applicative Order:

(test 0 (boom))
(if (= 0 0) 0 (boom))

;开始对(= 0 0)求值
(= 0 0)
#t

;将结果代入
 (if      #t          0          (boom))
;(if <predicate> <consequent> <alternative>)

;if是scheme中的特殊形式(special form),进行惰性求值
;于是if的predicate部分满足,直接返回consequent:0
0

;解释器没有boom!

发表评论