关于正则序和应用序的问题,贯穿了全书,中间的习题和后面的惰性求值都会涉及到。
书上已经给出了明确的定义:正则序是:完全展开后规约,应用序是:先求值而后应用。
以练习1.5为例,
(define (p) (p)) (define (test x y) (if (= x 0) 0 y)) (test 0 (p))
使用正则序(直接将参数代入而不求值),会将这个过程展开为,因为满足if条件,于是直接返回0
(if (= 0 0) 0 (p))
使用应用序(先求参数(p)),于是,你懂的,它自废武功死了,一般我们使用的解释器环境就是应用序,所以,这段程序运行就挂了。
无独有偶,练习1.6同样考察了这个问题,
(define (sqrt-iter guess x) (new-if (good-enough? guess x) guess (sqrt-iter (improve guess x) x)))
由于我们的解释器就是应用序,所以这个new-if在展开前先会求解后面的参数,当求解到sqrt-iter时,悲剧又发生了,它又不断的递归展开参数,所以不能使用cond替代if
1.20再次提到这个问题
如果按照正则序展开,会变成如下的序列,展开时候if求值用了14次(a1 + a2 + a3 + a4 = a1 + (a1 + 1) + (a1 + a2 + 1) + (a2 + a3 + 1)),而归约时又用了4次,所以总共18次
gcd(206 40) if(= 40 0) gcd(40 (remainder 206 40));a1=(remainder 206 40) if(= a1 0) gcd(a1 (remainder 40 a1));a2=(remainder 40 a1) if(= a2 0) gcd(a2 (remainder a1 a2));a3=(remainder a1 a2) if(= a3 0) gcd(a3 (remainder a2 a3));a4=(remainder a2 a3) if(= a4 0);a4=0 归约过程 (remainder a1 a2) (remainder (remainder 206 40) (remainder 40 (remainder 206 40))) (remainder 6 (remainder 40 6)) (remainder 6 4) 2
gcd(40 6) gcd(6 4) gcd(4 2) gcd(2 0)所以一方面也可以明白为什么大多解释器用应用序而不是正则序 原文链接:https://www.f2er.com/regex/362835.html