日拱一卒，伯克利CS61A大作业，scheme 解释器（四）

作者 | 梁唐

出品 | 公众号：Coder梁（ID：Coder_LT）

大家好，日拱一卒，我是梁唐。

我们来继续肝伯克利CS61A的scheme project，这是本project的第四篇，如果漏掉了之前的内容，可以去翻一下历史记录。

原始文档：https://inst.eecs.berkeley.edu/~cs61a/sp18/proj/scheme/#interpreter-details

在上一篇文章当中，我们完整实现了scheme解释器的功能，在这一篇文章中，我们用我们刚刚自己开发的解释器来做几个问题。

我们可以注意到，不仅scheme解释器本身是一个树递归的程序，并且它在处理其他递归问题上非常灵活。你将在questions.scm文件当中实现接下来的几个问题

虽然你已经完成了scheme解释器的开发，但由于可能存在潜在的bug。所以建议先使用通用的sheme解释器实现之后，再使用刚开发出的解释器进行测试，从而确保你的代码能够正常运行。

Problem 17

实现enumerate过程，它接收一个list，返回一个二元list。

这个二元list当中的每个元素是下标和值的组合，如：

开发完成之后，进行测试：

python3 ok -q 17

答案

lisp当中也有循环的语法，如果使用循环会简单很多。但老师讲课的内容当中没包括循环，所以我们还是只能使用递归来进行处理。

如果要递归处理，必然会发现一个问题，就是enumerate函数的入参只有一个list，而输出要带上下标。但问题是，我们在递归的时候拿不到当前下标这个变量。所以进而可以想到，只有一个参数递归肯定是解决不了的，我们至少需要两个参数。

在不改动原有函数签名的情况下，唯一的办法就是使用高阶函数。在函数内部再定义一个函数，然后我们再调用这个函数。

递归的逻辑其实不难，可以参考一下代码，就不过多赘述了。

(define (enumerate s)
  ; BEGIN PROBLEM 17
    (define (enum-iter n s)
        (if (null? s) 
          nil
          (cons
              (list n (car s))
              (enum-iter (+ n 1) (cdr s))
          )
        )
    )
    (enum-iter 0 s)
)

Problem 18

实现list-change过程，给定total和denominations，total表示总额，denominations表示我们有的面值，面值按照降序排序。我们要返回能够组成总面值total的所有方式。

比如total是10，denominations是(25, 10, 5, 1)，那么答案是：

再比如total是5，denominations是(4, 3, 2, 1)，答案是：

在实现的过程当中，你需要用到一个辅助函数：cons-all。要实现cons-all函数，需要用到内置的map过程。cons-all接收一个元素和一个list，将这个元素插入到list中的每个元素作为开头。

比如：

开发完成之后测试：

python3 ok -q 18

答案

我们先来实现cons-all，这个函数逻辑并不复杂。

遍历rests中的每一个元素，然后将first元素拼接上去即可。题目提示了我们，可以使用内置的map。map这个过程会将某一个过程应用在一个list的所有元素上。

那么显然，我们只需要实现一个函数能够将first拼接在元素上，然后再调用map即可，也不需要递归了。

(define (cons-all first rests)
    (define (concat s)
        (cons first s)
    )
    (map concat rests)
)

这道题我们之前在作业4当中用Python写过类似的，不知道大家还有没有印象。

不过当时求的是所有可能的数量，并且面额的限制也稍有区别，不是固定的几种，而是给定了一个整数m，所有小于等于m的面值都有，当时的代码：

def count_partitions(n, m):
    """Count the ways to partition n using parts up to m."""
    if n == 0:
      return 1
    elif n < 0:
      return 0
    elif m == 0:
      return 0
    else:
      return count_partitions(n-m, m) + count_partitions(n, m-1)

我们对它稍作改动，写成Python的版本：

def concat(v):
    return lambda x: [v] + x

def count_partitions(n, m):
    """Count the ways to partition n using parts up to m."""
    if n == 0:
      return [[]]
    if m == 0 or n < 0:
        return [] # invalid result
    if n >= m:
        ret = list(map(concat(m), count_partitions(n-m, m)))
        return ret + count_partitions(n, m-1)
    else:
        return count_partitions(n, m-1)

接下来要做的就是把上面这段Python代码转换成Lisp来实现，其实只要Python写得出来，Lisp也一样可以，语法虽然不同，但是核心原理是一样的。

这里由于Lisp递归的时候还涉及到参数的计算，写在一起会显得非常非常冗长。所以这里我们使用了define语句，简化了代码的书写。

(define (list-change total denoms)
  ; BEGIN PROBLEM 18
    (define (use-denom total denoms) (list-change (- total (car denoms)) denoms))
    (define (not-use-denom total denoms) (list-change total (cdr denoms)))
    (cond 
        ((null? denoms) nil)
        ((eq? total 0) (cons nil nil))
        ((< total (car denoms)) (list-change total (cdr denoms)))
        (else 
            (append (cons-all (car denoms) (use-denom total denoms)) (not-use-denom total denoms))
        )
    )
)

Problem 19

在Scheme语言当中，源代码也是一种数据。每一个非原生表达式都可以被写成一个Scheme list。所以我们可以实现一个过程，它可以像是生成一个scheme list一样生成另外一段程序。

重写代码是非常有用的，比如我们可以只实现解释器的核心功能，然后将其他的功能通过转写的方式转化成解释器支持的核心部件来进行运行。这样可以简化解释器的开发，我不太清楚这是否是Lisp语言设计逻辑的一部分，但它的确惊艳到了我，这样的设计思路实在是太巧妙了。

比如let语句等价于lambda表达式，它们都会基于当前环境创建新的frame。你可以回顾一下Problem 15当中对于let语法的定义。

这两个表达式可以用下图来表示：

使用这个规则来实现let-to-lambda过程，它会将let特殊类型转化成lambda表达式。

如果我们quote一个let表达式，将它传入这个过程，那么我们会得到一个等价的lambda表达式，例如：

要想实现功能，let-to-lambda必须能够感知scheme语法。因为scheme表达式是递归嵌套的，所以let-to-lambda也必须是递归的。

实际上，let-to-lambda的结构和scheme_eval函数是相似的，不过是用scheme语言实现的。提示：单元素包括数字、bool、nil和符号。

提示：你需要先实现zip过程，map过程很有帮助

在编码之前，先答题确保题目理解正确

python3 ok -q 19 -u

编码之后，进行测试：

python3 ok -q 19

答案

我们先来看zip过程，zip方法的输入是n x 2的二维list，我们返回的结果是一个2 x n的二维list。相当于对数据做了一个行列变换。

那么我们要做的就是将每一行中分别取出第一个和第二个元素来构成两个list，再把这两个list串在一起。

如果不使用循环，有种无从下手的感觉。好在题目中提示了我们，可以使用map。

代码如下：

(define (zip pairs)
    (list (map car pairs) (map cadr pairs))
)

然后是let-to-lambda

这道题老师已经替我们搭好了框架，把所有要考虑的情况都替我们列好了，我们只需要依次实现每一种情况的处理方法即可，算是为我们降低了一些难度。

我们分别来看一下这几种情况：

(atom? expr)

表达式是一个atom，即数字、symbol、nil或者bool，已经是不能再evaluate的结果了，直接返回即可。

(quoted? expr)

表达式是一个quote语句，和本题没有关系，不需要做任何处理，直接返回。

(or (lambda? expr) (define? expr))

表达式是lambda或define语句，不能直接确定是否有关系。因为define和lambda语句都还可以进一步嵌套，嵌套的语句可能会包含let语句，所以我们要递归一下嵌套的部分。

老师使用let语句替我们提取出了form,params和body。form是类型，params是参数，body是主体。只有body当中可能嵌套，所以我们要递归调用body。

(let? expr)

我们要处理的核心关键，let语句有两个部分，一个是values一个是body。我们看一下let语句的语法，它是先定义一些symbol和值的映射，再定义symbol的计算方式。我们要做的是把映射当中的symbol和value分别提取出来作为lambda过程的formal和params，body作为lambda过程的body。

不过比较麻烦的是这三者中间都有可能存在嵌套，所以我们需要使用递归。

else

即其它情况，由于我们只判断了car expr，所以我们还需要继续递归调用，判断后面的内容。这里我直接使用了map过程

更多细节参考代码：

(define (let-to-lambda expr)
  (cond ((atom? expr)
         ; BEGIN PROBLEM 19
          expr
         ; END PROBLEM 19
         )
        ((quoted? expr)
         ; BEGIN PROBLEM 19
          expr
         ; END PROBLEM 19
         )
        ((or (lambda? expr)
             (define? expr))
         (let ((form   (car expr))
               (params (cadr expr))
               (body   (cddr expr)))
           ; BEGIN PROBLEM 19
            (cons form (cons params (let-to-lambda body)))
           ; END PROBLEM 19
           ))
        ((let? expr)
         (let ((values (cadr expr))
               (body   (cddr expr)))
           ; BEGIN PROBLEM 19
            (define combine (zip values))
            (cons (cons 'lambda (cons (let-to-lambda (car combine)) (cons (let-to-lambda (car body)) nil))) (map let-to-lambda (cadr combine)))
           ; END PROBLEM 19
           ))
        (else
         ; BEGIN PROBLEM 19
            (cons (car expr) (map let-to-lambda (cdr expr)))
         ; END PROBLEM 19
         )))

到这里，这三题就算是讲完了。

虽然只有三道题，但是完整做下来感觉收获还是非常大的。不仅对于Scheme这一门语言，而且对解释器这个项目也进一步加深了印象，可以说是收获满满，这一次的大作业的的确确非同凡响，因此非常非常推荐大家亲自试试。

喜欢本文的话不要忘记三连~