CG@CPPBLOG

/*=========================================*/
随笔 - 76, 文章 - 39, 评论 - 137, 引用 - 0
数据加载中……

我的SICP习题答案(1.6)

会递归直到堆栈溢出。
原因是 在 new-if 还没有展开为 cond special forms 时,else-clause 子式已经陷入了无限递归。 做了以下实验,可以验证
(define (new-if pred thenc elsec)
  (cond (pred thenc)
        (else elsec)))

(define (iter x y)
  (new-if (
= x y)
          
0
          (iter (+ x 
1) y)))

(define (iter-if x y)
  (if (
= x y)
      
0
      (iter-if (+ x 
1) y)))

(define (iter-cond x y)
  (cond ((
= x y) 0)
        (else (iter-cond (+ x 
1) y))))

对于 (iter 1 10), (iter-if 1 10), (iter-cond 1 10)
其中 iter 会 导致堆栈溢出,而 iter-cond 和 iter-if 并不会。

此题同1.5
在1.5中,由于应用序的原因,在 test 表达式 还没有展开为 if 特殊形式(special forms)时, (p)已经陷入了无限递归。

posted on 2008-03-09 23:12 cuigang 阅读(1744) 评论(9)  编辑 收藏 引用 所属分类: Lisp/Scheme我的SICP答案

评论

# re: 我的SICP习题答案(1.6)[未登录]  回复  更多评论   

对于这一题,是不是应用序的解释器和正则序的解释器都会陷入无限递归?
2009-09-08 10:15 | Achilles

# re: 我的SICP习题答案(1.6)  回复  更多评论   

我认为正则序不会,因为正则序不会去解析else-clause里面的代码
@Achilles
2010-01-28 11:06 | jubincn

# re: 我的SICP习题答案(1.6)  回复  更多评论   

我使用的Berkeley的stk解释器,貌似使用new-if没有什么问题,难道stk使用的是正则序?
2010-01-28 11:08 | jubincn

# re: 我的SICP习题答案(1.6)  回复  更多评论   

前文有说到Lisp是采用应用序求值,请教为什么if是正则序的呢? 是因为它是built-in的吗?
2012-02-02 18:01 | atw

# re: 我的SICP习题答案(1.6)  回复  更多评论   

@jubincn
我很好奇一个正则序的解释器是如何对待递归调用的:无限展开??不可能;但展开到哪个程度呢?

@atw
不是说if是正则序,而是因为在new-if中,接下来的参数都会作为new-if调用的参数被求值,从而iter陷入了无限递归;而使用if的话,处理接下来的“参数”(之所以打引号是因为Lisp默认的if应该不算是函数调用,算是个语句),会先对第一个参数求值而后决定进入哪个过程分支。
2012-05-05 20:27 | alsotang

# re: 我的SICP习题答案(1.6)  回复  更多评论   

博主你好,我使用的是MIT的scheme的解释器
按照你的说法 我试了一下 new-if确实会递归到堆栈溢出

但是即使是使用if和cond的另外两种,也会导致堆栈溢出,这是为什么呢?
2012-08-22 12:58 | NWm

# re: 我的SICP习题答案(1.6)  回复  更多评论   

好吧,我现在又试了一下,cond情况是不会溢出,刚好返回10
但是使用if是确实会溢出的,不知道为何
2012-08-22 13:00 | NWm

# re: 我的SICP习题答案(1.6)  回复  更多评论   

好吧 我又试了一下 好像跟您的说法是一致的.也许是我刚才打错了吧
2012-08-22 13:14 | NWm

# re: 我的SICP习题答案(1.6)  回复  更多评论   

根据我调试的结果,显示,new-if 的 cond 段根本没有机会运行到,因为是应用序求值的规则,因此,(good-enough? guess x)及(sqrt-iter guess x)不断被解开运行直到溢出。
2013-01-30 00:36 | flyleoleo

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理