CG@CPPBLOG

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

我的SICP习题答案(1.1~1.5)

1.1

10,12,8,3,10 6,a,b,19,#f,4,16,6,16

1.2


(/(+ 5 4 (- 2 (- 3 (+ 6(/ 4 5)))))(* 3 (- 6 2)(- 2 7)))

or

(/(+ 5 4 (- 2 (- 3 (+ 6 4/5))))(* 3 (- 6 2)(- 2 7)))

1.3

这个问题中文版的翻译是错的,参看原文是求平方和而不是“和”。

(define (square(x)(* x x)))
(define (max x y)(if (< x y) y x))
(define (func x y z)
  (+ (square (max x y))
     (square (max (min x y) z))))

1.4

a+|b| 

<=>

1 # in python
2 def a_plus_abs_b(a,b):
3     if b>0 :
4         x = a + b
5     else:
6         x = a - b
7     return x

1.5

在网上看了很多答案,都认为“应用序”的实现会导致死循环,我非常困惑。反复看了中文版和英文版,觉得大家这样认为可能是书中说lisp的实现是“应用序”,而在scheme中跑这段代码会死循环,就先入为主的认为“应用序”的实现会死循环。其实对照正文,我们可以看到“正则序”停止展开的条件是“只包含基本运算符的表达式”,而对于

(define (p) (p))

是无论如何也没法完全展开的,因为它会不断递归,所以“正则序”才会死循环。

而对于“应用序”的实现,则会这样展开


(test 0 (p))
(if (= 0 0) 0 (p))
(if #t 0 (p))

; 0

解决这个问题主要是“正则序”(Normal order)以及“应用序”(Applicative order)展开一个组合式的规则,仔细研究了MIT 6.001课程讲义,网上的各种答案,以及中英文版。我认为,正则序以类似广度优先的方式进行展开。而应用序优先计算子表达式,类似与深度优先。那么对于这个问题,
正则序会展开为
=> (if (= 0 00 (p))
=> (if #t 0 (p))
接着,由于这是一个if的special form(特殊形式),就会被展开为
0
而应用序,由于(p)一直可以递归代换,从一开始就会进入一个无限递归中去。
简言之,由于应用序的原因,在 test 表达式 还没有展开为 if 特殊形式(special forms)时, (p)已经陷入了无限递归。

posted on 2007-12-26 00:19 cuigang 阅读(1974) 评论(13)  编辑 收藏 引用 所属分类: Lisp/Scheme我的SICP答案

评论

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

还有么..答案不太好找
一起讨论吧
2008-02-01 11:29 | 3fen

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

http://oss.timedia.co.jp/show/SICP/ex-1.5
1.5题的答案与你正好相反
2008-02-03 19:18 | 3fen

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

@3fen
我也很困惑,虽然网上很多答案都和我的不同,但是我没办法解释,只好认为我的是对的了。
2008-02-08 18:20 | cuigang

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

找到了一个不错的解释:http://panxz.blogbus.com/logs/8205960.html
感觉有点道理
2008-02-14 21:47 | 3fen

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

1.5题
normal-order evaluation是先替换参数,到最后才会计算操作数。
而applicative-order evaluation是开始就计算操作符和操作数,而后再替换参数。
所以题解应该是反的。
2008-02-26 10:02 | leo

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

@3fen
@leo
感谢两位关注,我最近仔细研究了这个问题,觉得以前理解是有问题,已经更新了答案
2008-03-04 23:30 | cuigang

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

(+ (* 2 4) (- 4 6))的答案应该为6吧.
2008-06-24 20:51 | paoapo

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

@paoapo
是的,我写错了,已经改过来了,谢谢。
2008-06-27 21:20 | cuigang

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

笨得可以,单步调试下就知道1.5的结果。
2009-11-08 20:47 | lwcore

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

@lwcore

当时还没有找到合适的解释器,另外,scheme解释器调试功能都不好用
2010-02-19 21:55 | cuigang

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

THX,那个1.5的练习我也找了好久才找到这里,每个人都说应用序的定义!!!可是我根本就看不懂!!!!
2011-03-03 13:33 | 咸鱼

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

其实对照正文,我们可以看到“正则序”停止展开的条件是“只包含基本运算符的表达式”,而对于

(define (p) (p))

是无论如何也没法完全展开的,因为它会不断递归,所以“正则序”才会死循环。

而对于“应用序”的实现,则会这样展开

(test 0 (p))
(if (= 0 0) 0 (p))
(if #t 0 (p))

; 0


大哥,你这段话完全是前后矛盾啊!!!!!不是说了是正则序=0,应用序陷入循环么?
2011-03-03 21:14 | 咸鱼

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

@咸鱼
灰色部分是我删掉的原来错误的部分,看来引起了误解。我把它删掉。
2011-07-12 09:31 | cuigang

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理