注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

分享,态度 ·~~

—— 十年太长,五年;如果可以回到五年前,你最想对那时候的自己说什么?

 
 
 

日志

 
 

应用序 or 正则序?  

2012-02-22 14:09:54|  分类: C/C++ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
 这是《计算机程序的构造与解释》中的一道习题,如何去判断一个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)) 递归调用自身,导致无限循环直到栈溢出。

【from http://www.blogjava.net/killme2008/archive/2007/05/08/115949.html

  评论这张
 
阅读(787)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017