作者 | 梁唐
出品 | 公众号：Coder梁（ID：Coder_LT）
大家好，日拱一卒，我是梁唐。
我们今天继续来肝伯克利CS61A这门公开课，这次我们一起来看的是作业10.
原始文档：https://inst.eecs.berkeley.edu//~cs61a/sp18/hw/hw10/
这次的作业一共有3题，难度不大，是scheme的拓展练习，主要让我们尝试使用scheme的几个重要特性，以及巩固一下对于尾递归的理解。
Q1: Accumulate
完善accumulate过程，它能够根据传入的参数将前n个自然数合并在一起：
combiner：一个接收两个参数的函数start: 最早用来合并的数n：表示自然数的个数term：一个接收一个参数的函数，我们需要绑定n个数的term后的结果
举个例子，比如我们可以通过accmulate过程来计算1到5的乘积，这需要我们传入乘法操作充当combiner，并且start需要设置成1：
我们也可以用来计算若干个数的平方和，这时候的combiner就是加法，term是平方操作：
完成之后，进行测试：
代码语言：javascript复制python3 ok -q accumulate
答案
这道题本身逻辑并不复杂，如果觉得理不清楚，可以先用Python实现：
代码语言：javascript复制def accmulate(combiner, start, n, term):
if n == 0:
return start
else:
return combiner(term(n), accmulate(combiner, start, n-1, term))
再用lisp实现同样的逻辑即可。
代码语言：javascript复制(define (accumulate combiner start n term)
(if (= n 0)
start
(combiner
(term n)
(accumulate combiner start (- n 1) term)
)
)
)
Q2: Tail Recursive Accumulate
更新你刚开发的accumulate，让它变成尾递归。保证更新之后依然能够通过测试样例。
你可以假设combiner和term过程本身都是尾递归。
提示：如果你在运行测试样例的过程中遇到递归深度越界的错误，这说明了你的实现不是一个合格的尾递归
开发完成之后进行测试：
代码语言：javascript复制python3 ok -q accumulate-tail
答案
首先我们来看一下我们刚才的实现代码为什么不是尾递归，原因很简单，因为当我们递归的结果返回了之后，仍然进行了操作，我们combiner了递归的结果和term(n)，它依然对环境有所依赖，这就导致了递归的时候环境变量的存储不能释放，因此不是尾递归。
想要将实现改变成尾递归，那么我们就不能在递归之后进行combiner，而需要在递归之前进行。
我们看下老师给的求阶乘的例子：
我们的做法本质上和这一样，将中间结果传递进递归当中，而不是递归结束之后进行计算。
整个代码的结构和刚才是一样的，只不过细节上有所变化，但就是这一点不起眼的小细节，优化了运行效率。
代码语言：javascript复制(define (accumulate-tail combiner start n term)
(if (= n 0)
start
(accumulate-tail combiner (combiner (term n) start) (- n 1) term)
)
)
Q3: List Comprehensions
在Python当中list comprehensions写成如下形式：
[<expression> for <element> in <sequence> if <conditional>]
通过macro创建一个scheme中的list comprehension。特别的，我们希望创建一个命名为list-of的宏，它接收如下参数：
(list-of <expression> for <element> in <sequence> if <conditional>)
比如，我们像这样使用list comprehension的宏
提示：你也许会需要用到map和filter过程
完成开发之后，进行测试：
代码语言：javascript复制python3 ok -q list-comp
答案
这题需要我们使用define-macro语法，这是一个宏定义的语法，它可以允许我们机械性地替换代码。
比如这个例子：
这里定义的是将一个表达式执行两次的宏，当我们调用的twice的时候，它会将我们传入的表达式执行两次：
但如果我们不是定义宏，而是直接通过define来操作，就无法实现这个效果：
虽然表面上看，(define (twice expr) (list 'begin expr expr))效果似乎是一样的。但我们看一下上面的运行结果就发现完全不同。
原因也很简单，当我们通过(twice (print 2))传入表达式的时候，解释器会先evaluate表达式。比如(print 2)，就是输出2，解释器就先执行掉了，传入的表达式就成了运行之后的结果也就是nil。
而使用宏的时候，可以保证我们传入的表达式不会被执行，而是会原封不动地替换。
另外我们观察一下define-macro表达式的返回结果，会发现它返回的其实是代码。比如(list 'begin expr expr)的执行结果是(begin expr expr)，这其实就是我们希望解释器执行的代码。
也就是说宏返回的是待执行的代码，当我们调用宏的时候，其实有两个步骤，一个步骤是调用define-macro拿到待执行的代码，还有一个执行代码拿到结果的步骤。
理解了这一点之后，代码就不难写了：
代码语言：javascript复制(define-macro (list-of expr for var in seq if filter-fn)
(list 'map (list 'lambda (list var) expr) (list 'filter (list 'lambda (list var) filter-fn) seq))
)
我们还可以利用quasi-quotation语法，来直接书写代码。它相当于Python当中的''.format语法，让我们可以直接生成想要的字符串，并且也可以填入变量或表达式的值。
我们使用一个```符号来表示之后的内容全部都是字符串，如果我们希望某个字符串表示的是对应名称的表达式的值，我们就在前面加上一个逗号。
通过quasi-quotation语法写出来的代码如下：
代码语言：javascript复制(define-macro (list-of expr for var in seq if filter-fn)
`(map (lambda (,var) ,expr) (filter (lambda (,var) ,filter-fn) ,seq))
)
虽然是同样的逻辑，但书写起来就简单了许多。
到这里，这次的作业10就算是做完了，虽然题目量不大，但还是挺有意思的，尤其是第三题。我当时没有看讲课视频就来做了，结果卡了很久，后来看了视频才豁然开朗，直呼学到了。
好了，这次的作业就聊到这里，感谢大家的阅读
喜欢本文的话不要忘记三连~
