这是《计算机程序的构造与解释》中的一道习题,如何去判断一个scheme解释器是采用什么方式进行求值的?应用序 or 正则序。应用序是先对参数求值而后应用,而正则序则相反——完全展开而后归约求值。正则序相比于应用序,会部分存在重复求值的情况。习题是这样的:
Ben Bitdiddle发明了一种检测方法,能够确定解释器究竟采用的哪种序求值,是采用正则序,还是采用应用序,他定义了下面两个过程:
<!---->(define (p) (p))
(define (test x y)
(if (= x 0)
0
y))
而后他求值下列的表达式:
<!---->(test 0 (p))
如果解释器采用的是应用序求值,ben将会看到什么情况?如果是正则序呢?
分别分析下这两种情况下解释器的求值过程:
1.如果解释器是
应用序,将先对过程test的参数求值,0仍然是0,(p)返回的仍然是(p),并且将无穷递归下去直到栈溢出,显然,在这种情况下,解释器将进入假死状态没有输出。
2.如果解释器是
正则序,完全展开test过程:
<!---->(define (test 0 (p))
(if (= 0 0)
0
(p))
接下来再进行求值,显然0=0,结果将返回0。
一般lisp的解释器都是采用应用序进行求值。这个问题在习题1.6中再次出现。我们知道scheme已经有一个cond else的特殊形式,为什么还需要一个if else的特殊形式呢?那么我们改写一个new-if看看:
<!---->(define (new-if predicate then-clause else-clause)
(cond (predicate then-clause)
(else else-clause)))
写几个过程测试一下:
<!---->(new-if (< 1 0) 1 0)
结果一切正常,但是,当这3个参数是过程的时候会发生什么情况呢?在这3个参数如果存在递归调用等情况下,解释器也将陷入无限循环导致栈溢出!比如书中的求平方根过程用new-if改写:
<!---->(define (new-if predicate then-clause else-clause)
(cond (predicate then-clause)
(else else-clause)))
(define (average x y)(/ (+ x y) 2))
(define (square x) (* x x))
(define (improve guess x)(average guess (/ x guess)))
(define (good_enough? guess x)
(< (abs (- (square guess) x)) 0.000001))
(define (sqrt_iter guess x)
(new-if (good_enough? guess x)
guess
(sqrt_iter (improve guess x) x)))
(define (simple_sqrt x)(sqrt_iter 1 x))
因为解释器是应用序求值,将对new-if过程的3个参数求值,其中第三个参数也是一个过程(sqrt_iter (improve guess x) x)) 递归调用自身,导致无限循环直到栈溢出。
分享到:
相关推荐
正则表达式在程序开发中的应用比较广泛,通过对正则表达式的介绍,可以让你在程序开发中,规范又便捷!
Java正则表达式应用总结
C#正则表达式应用C#正则表达式应用C#正则表达式应用C#正则表达式应用
本文档结合多年使用正则表达式经验,总结正则表达式使用方式以及常见的正则表达式的表达。希望有助于您的学习!
正则表达式及其应用简介.txt正则表达式及其应用简介.txt正则表达式及其应用简介.txt正则表达式及其应用简介.txt正则表达式及其应用简介.txt正则表达式及其应用简介.txt
易语言正则表达式模块应用源码,正则表达式模块应用
易语言正则对象应用源码,正则对象应用,正则匹配,正则替换
正则表达式在Ext中,要加/^ $/,比如/^[0-9]{1,9}$/ 正则表达式在JAVA中应用 正则表达式在JAVA中应用 正则表达式在JAVA中应用 正则表达式在JAVA中应用
介绍了正则表达式的基本概念,以及在VBScript和javascript中如何使用正则表达式,同时,通过一些实例让大家有了感性的认识。正则表达式的应用范围很广,能为大家解决很多实际中的问题。
JavaScript应用实例-正则表达式学习.js
正则表达式的应用全集
正则表达式的高级应用 哈希表的应用 list 的 米索问题 map的再正则表达式的应用
讲述正则表达式的使用,不错的一份资料,常用的正则表达式应用基本上全都有。
JavaScript应用实例-正则匹配手机号.js
如何高效的处理文本?何谓是正则?何谓是表达式? PPT内容:概念介绍、应用实操、工具选择、总结答疑。
正则表达式到底是什么?正则表达式-常用元字符,正则表达式-常用元字符应用
非常齐全的asp.net的正则表达式应用
正则表达式,轻松理解正则表达式的应用。对正则表达式的应用和注意的事项都有很详细的说明
一刀屠文-在lisp中应用正则表达式 介绍正则表达式,及在cad二次开发软件lisp中的应用
正则表达式应用正则表达式正则表达式正则表达式正则表达式正则表达式