阅读SICP的过程中，我尝试着用python将SICP的习题实现一遍。在对Exercise 2.36的实现中，遇到了些问题。Exercise 2.36是实现一个accumulate_n的累积函数，与先前的accumulate函数类似，accumulate_n函数的第三个参数seqs接受元素为列表的列表，并且所含元素的数目应该相同。
理想的输出如下：
1
2
3
4
| >>> accumulate_n(cons_of_list,[],[[1,2,3],[4,5,6]])
[[1, 4], [2, 5], [3, 6]]
>>> accumulate_n(lambda x,y:x + y,0,[[1,2,3],[4,5,6]])
[5, 7, 9]
|
实现
按照书中的提示，与scheme中accumulate-n函数类似，我实现了python中的accumulate_n函数，
1
2
3
4
5
6
7
8
9
10
11
12
|
from sicp import *
def accumulate_n(op,init,seqs):
if seqs[0]:
return cons_of_list(accumulate(op,init,map(car,seqs)),\
accumulate_n(op,init,map(cdr,seqs)))
else:
return []
|
测试：
1
2
| >>> accumulate_n(lambda x,y:x + y,0,[[1,2,3],[4,5,6]])
[5, 7, 9]
|
用accumulate_n函数求和显示正常，
1
2
| >>> accumulate_n(cons_of_list,[],[[1,2,3],[4,5,6]])
[[3, 6, 2, 5, 1, 4], [3, 6, 2, 5, 1, 4], [3, 6, 2, 5, 1, 4]]
|
用cons_of_list代替加法进行累积，得到结果不对，看来是碰到bug了…
调试
是时候使出print大法了，看看accumulate_n函数内部在调用过程中发生了什么。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
from sicp import *
def accumulate_n(op,init,seqs):
if car(seqs):
print seqs
print init
print "-----------------------"
current = accumulate(op,init,map(car,seqs))
print map(car,seqs)
print current
print "----****----"
rest = accumulate_n(op,init,map(cdr,seqs))
print map(cdr,seqs)
print rest
print "-----------------------"
print
return cons_of_list(current,rest)
else:
return []
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| >>> accumulate_n(cons_of_list,[],[[1,2],[4,5]])
[[1, 2], [4, 5]]
[]
-----------------------
[1, 4]
[1, 4]
----****----
[[2], [5]]
[1, 4]
-----------------------
[2, 5]
[2, 5, 1, 4]
----****----
[[], []]
[]
-----------------------
[[2], [5]]
[[2, 5, 1, 4]]
-----------------------
[[2, 5, 1, 4], [2, 5, 1, 4]]
|
函数一开始打印seqs,init的初始值[[1, 2], [4, 5]]，[]；对seqs列表的每个列表元素的第一个元素使用accumulate函数，打印结果没有错；接着对seqs中剩下的元素递归调用accumulate_n函数，打印新的accumulate_n函数中seqs，init的初始值，seqs值为[[2],[5]]，init的值为[1, 4]，显然init的理想值应该是[]，看来这就是bug所在了。在print init后加上id(init)，能更加直观地观察运行结果。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| >>> accumulate_n(cons_of_list,[],[[1,2],[4,5]])
[[1, 2], [4, 5]]
[] 67248816
-----------------------
[1, 4]
[1, 4]
----****----
[[2], [5]]
[1, 4] 67248816
-----------------------
[2, 5]
[2, 5, 1, 4]
----****----
[[], []]
[]
-----------------------
[[2], [5]]
[[2, 5, 1, 4]]
-----------------------
[[2, 5, 1, 4], [2, 5, 1, 4]]
|
在新的accumulate_n函数中，我们希望的是使用一个新的init变量，但从结果上看，两个init变量的id相同，执行过程中一直是对一个init变量操作。
原因
查阅资料发现，这与python的参数传递有关。python函数中，参数的传递本质上是一种赋值操作。accumulate_n函数定义好之后，使用空列表作为init的值，参数init就会指向（绑定）到一个空列表对象，每次调用函数时，都是对同一个对象进行操作，这样就造成了上示的bug。
python中，对于不可变对象作为函数参数，相当于C系语言的值传递；对于可变对象作为函数参数，相当于C系语言的引用传递。这也解释了当使用0作为init的初始值时为什么没有出现bug。
可以在accumulate_n函数中添加一个判断解决bug，如果init的值不是空列表，就将其初始化。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
from sicp import *
def accumulate_n(op,init,seqs):
if init:
init = []
if seqs[0]:
return cons_of_list(accumulate(op,init,map(car,seqs)),\
accumulate_n(op,init,map(cdr,seqs)))
else:
return []
|
1
2
| >>> accumulate_n(cons_of_list,[],[[1,2],[4,5]])
[[1, 4], [2, 5]]
|
参考:
1.Python 函数中，参数是传值，还是传引用？
2.python中参数传递方式