日拱一卒，伯克利教你用Lisp写递归，写完后我感觉代码更溜了

TechFlow-承志

发布于 2022-09-21 11:50:29

6020

发布于 2022-09-21 11:50:29

文章被收录于专栏：TechFlowTechFlow

作者 | 梁唐

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

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

我们继续伯克利CS61A公开课之旅，这一次是它的第九次实验课。昨天的期中测试过后，这门课关于Python的编程基础以及面向对象的部分就算是讲完了，接下来就到了Scheme和数据处理的部分。

Scheme是Lisp语言的一个分支，老师在课上没有解释为什么要引入Scheme的相关内容。我个人理解除了让大家多学一门语言，拓展大家的知识面之外，也是给之后的用Python实现Lisp解释器的project打基础。Lisp解释器这个Project也是我个人觉得这门课最有含金量，最能学到东西的project，当然难度也是最大的。

另外Lisp语言的特性使得它的词法语法分析很好做，可能也是为后面的编译原理打基础，并且整个语言的代码是以链表的形式存储的，也能更好地帮助大家理解递归和链表等数据结构。

大家看到Scheme肯定不像看到Python这么感兴趣，但伯克利这门课当中没有废话，每一个知识点都是有用的，踏实学完，收获一定是不菲的。

公开课视频链接：https://www.bilibili.com/video/BV16W411W76H

实验课资料：https://inst.eecs.berkeley.edu//~cs61a/sp18/lab/lab09/

整个实验课的完整代码我也放在了GitHub上。

首先，我们需要先去实验课的网站下载实验文件：

我们主要编写的代码在lab09.scm和lab09_extra.scm当中，其余的都是测试文件。scheme是老师提供的一个编译好的scheme解释器，我们可以在当中测试我们的Scheme代码。因为这个解释器是Python编写的，所以测试命令为：python3 scheme -i

老师还提供了在线的Scheme解释器，也可以直接在网站上进行编码和调试，地址为：https://code.cs61a.org/

好了，相关的背景就介绍到这里，下面我们来看实验内容。

Expressions

Primitives

和Python一样，primitive和atomic表达式在Scheme中也可以直接运行。这些包括数字、bool、变量名和symbol。

这些当中symbol类型是Python当中我们没有遇到过的。符号的行为很像是Python中的字符串，但不完全一致。现在，你可以把一串有效的Scheme字符表示成一个symbol。

在Scheme中，除了表示False的#f之外所有的变量都会被当做True。我们提供的特别版的Scheme解释器能够允许你使用Python中的True False来代替#t和#f，不过这并不是标准。

例子：

Call expressions

除了atomic表达式，其他表达式都是call表达式或者特殊格式。这两种都写成Scheme list。一个call表达式语法如下：

和Python一样，操作符先于所有操作数。和Python不同的是，操作符包括在了小括号里面，并且操作数之间以空格分隔，而非逗号。然而，Scheme call表达式的evaluate规则和Python一样：

首先evaluate操作符，这应该得到一个过程（procedure）
从左到右evaluate操作数
将得到的过程应用在操作数evaluate之后的结果上

下面是使用数学运算符的一些例子：

Special forms

特殊形式。

Scheme中的特殊形式严格拥有如下的表达式：

其中比较特殊的是，它们不遵守刚才所说的evaluate三规则。相反，每一个特殊形式都有自己的执行规则，比如短路掉操作数的evaluate。

我们今天将会学习特殊形式当中的一些案例，比如if, cond, define和lambda。阅读下面对应的章节来了解它们的evaluate规则。

Control Structures

控制结构

if Expressions

if 表达式

在Scheme中，if表达式是一个遵循以下规则的特殊形式。

注意和call表达式相似的语法，if关键字先于3个空格分隔的操作数。它的evaluate规则如下：

evaluate <condition>
如果<condition>的结果是true，if表达式将会以<true-result>作为结果，否则将以<false-result>

你能发现为什么这是一个特殊格式吗？将它和常规的call表达式的evaluate规则比较，它们的区别是什么？

下列代码块中以Python和Scheme实现的逻辑大致等价：

它们不完全等价的原因是Scheme中的if表达式是evaluate对应的值，而Python中的if表达式只是切换了执行的代码。在这个例子当中，Scheme是evaluate了1和2的值，而Python只是打印。

并且，Python中我们可以给分支添加更多的代码，然而Scheme中的if表达式对于true-result和false-result只能执行单个表达式。

另外一个区别是，在Scheme当中，我们不能实现elif逻辑。如果拥有多种情况需要判断，只能使用多个if表达式：

cond Expressions

使用嵌套的if表达式看起来不是一个非常优雅的方式，所以我们可以使用cond，它也是一个特殊格式。是一个处理多种条件分支的语句。

cond接收任意多个参数，表示逻辑上的分支（clause）。一个分支写成一个拥有两个表达式的list（<p> <e>）

每个分支中的第一个表达式叫做断言（predicate），它的值会被解释成True或False。分支中的第二个表达式是对应的返回表达式，最后的else选项没有断言。

它的evaluate规则如下：

按顺序evaluate断言中的<p1>, <p2>, ..., <pn>，直到遇见返回True的为止
cond表达式将会evaluate断言为True的对应的<ei>
如果没有断言结果为True，那么进入else分支，返回<else-expression>

正如你所见，cond是一个特殊形式，因为它不会evaluate它所有的操作数。断言和对应的返回表达式是分开的。另外，表达式遇到了第一个返回True的断言之后，将会短路其他的分支，不再去evaluate剩下的断言。

下面两个代码块逻辑大致等价：

Lists

当你阅读本章节，如果觉得Scheme中各种容器理解起来很困难，可以使用老师提供的在线Scheme解释器，它可以将lists和pairs以box-and-pointer的形式展现

Pairs

pair是Scheme中自带的数据类型，它可以容纳两个值。使用cons过程创建pair，它接收两个参数：

pair中的元素展示的时候中间会以点分隔。我们可以使用car和cdr过程来分别获取pair中的第一和第二个元素：

我们也可以嵌套cons来让一个pair中的元素是另外一个pair

你可能会好奇，为什么第一个例子中((1 . 2) . 3)的第一个点在第二个例子中消失了？这是因为当Scheme在点之后遇见了左括号，会去掉点和括号。

继续阅读，看看怎样可以让输出结果当中不包括点。

Well-formed lists

Scheme list和链表非常相似，链表是通过多个Link对象串联的，而Scheme list是以多个pair结合的。

一个well-formed（格式良好）的Scheme list，它调用cdr得到的是另外一个well-formd list或者是一个nil（空串）。well-formed list在展示的时候中间没有点。为了更好的理解，首先观察下面这个pair构造：

这被称为malformed list（畸形），因为它调用cdr得到的不是一个well-formed list或者是nil，因为你依然可以看到点。再来看看这个pair的结构：

这里我们创建了一个well-formed list，因为我们cons过程的第二个参数是另外一个cons表达式或者是nil。

我们可以使用car和cdr从这个list当中获取值，有些类似于Python链表中的first和rest属性。

list Procedure

我们还有一些其他创建list的方法，list过程接收任意数量的参数，并且创建一个well-formed list。

注意到操作数会在过程执行之前被evaluate

Quote Form

我们也可以使用引号形式来创建list，它也会根据我们的输入创建一个一模一样的list。和list过程不同的是，'操作数没有被evaluate

Built-In Procedures for Lists

Scheme中也有一些自带的list相关的过程：

Defining procedures

我们可以使用define来创建一个过程，语法如下：

这个表达式根据我们给定的参数以及运行的逻辑（body）创建了一个函数，并将它赋值给了name。

我们创建的过程可以接收的参数数量是不受限的，<body>当中可能包含多个表达式。这和python中return只能返回单个语句不同。函数可以返回body中的最后一个表达式。

这个表达式也是特殊形式，因为它的操作数没有被evaluate。比如<body>在过程定义的时候并没有被执行，而是在被调用的时候才会执行。并且在创建过程的时候，<name>和参数名也不应该被evaluate。

Lambdas

我们也可以在Scheme当中编写lambda表达式，它拥有如下语法：

注意，这个表达式和define表达式最大的区别就是它少了过程的名称。这个表达式将会创建以及返回一个函数，但这不会修改当前运行的环境。这和Python中def和lambda表达的区别非常相似。

Required Questions

What Would Scheme Display?

Q1: WWSD: Lists

填空题，阅读Scheme代码，填写返回结果。

使用ok命令进行答题：python3 ok -q wwsd-lists -u

scm> (cons 1 2)
______

scm> (cons 1 (cons 2 nil))
______

scm> (car (cons 1 (cons 2 nil)))
______

scm> (cdr (cons 1 (cons 2 nil)))
______

scm> (list 1 2 3)
______

scm> (list 1 (cons 2 3))
______

scm> '(1 2 3)
______

scm> '(2 . 3)
______

scm> '(2 . (3))  ; Recall dot rule for pairs
______

scm> (equal? '(1 . (2 . 3)) (cons 1 (cons 2 (cons 3 nil)))) ; Recall how boolean values are displayed
______

scm> (equal? '(1 . (2 . 3)) (cons 1 (cons 2 3)))
______

scm> (equal? '(1 . (2 . 3)) (list 1 (cons 2 3)))
______

scm> (cons 1 '(list 2 3))  ; Recall quoting
______

scm> (cons (list 2 (cons 3 4)) nil)
______

scm> (car (cdr '(127 . ((131 . (137))))))
______

scm> (equal? '(1 . ((2 . 3))) (cons 1 (cons (cons 2 3) nil)))
______

scm> '(cons 4 (cons (cons 6 8) ()))
______

这里面有几道题有一点点绕，如果想不清楚可以打开Scheme解释器运行一下。

Coding Questions

Q2: Over or Under

创建过程over-or-under，接收一个x和y，返回：

如果x < y返回-1
如果x = y返回0
如果x > y返回1

(define (over-or-under x y)
  'YOUR-CODE-HERE
)

;;; Tests
(over-or-under 1 2)
; expect -1
(over-or-under 2 1)
; expect 1
(over-or-under 1 1)
; expect 0

使用ok命令进行解锁和测试：

python3 ok -q over-or-under -u
python3 ok -q over-or-under

答案

cond语法小试牛刀

(define (over-or-under x y)
  (cond
    ((> x y) 1)
    ((< x y) -1)
    (else 0)
  )
)

Q3: Filter

编写过程filter，接收一个断言f，和一个list lst。返回一个新的list，仅仅包含满足断言f的元素。输出时，元素需要保持之前的相对顺序。

(define (filter f lst)
  'YOUR-CODE-HERE
)

;;; Tests
(define (even? x)
  (= (modulo x 2) 0))
(filter even? '(0 1 1 2 3 5 8))
; expect (0 2 8)

使用ok命令解锁测试样例以及进行测试：

python3 ok -q filter -u
python3 ok -q filter

答案

这也是递归题，我们每次判断lst第一个元素在断言下是否为true，如果是的话，那么将它拼接到答案当中，如果不是，返回递归(cdr lst)的结果。

递归的逻辑不复杂，只不过用Scheme来写，可能需要熟悉一下

(define (filter f lst)
    (
      if (null? lst) nil
      (if (f (car lst)) (cons (car lst) (filter f (cdr lst)))
          (filter f (cdr lst))
      )
    )
)

Q4: Make Adder

实现make_adder过程，接收一个初始值num，返回一个过程。返回的过程接收一个数x返回x + num。

(define (make-adder num)
  'YOUR-CODE-HERE
)

;;; Tests
(define adder (make-adder 5))
(adder 8)
; expect 13

使用ok命令解锁和测试：

python3 ok -q make-adder -u
python3 ok -q make-adder

答案

很显然，题意是让我们返回一个lambda函数。我们只需要根据lambda的语法返回即可。

(define (make-adder num)
    (lambda (x) (+ x num))
)

Optional Questions

接下来的题目可以在lab09_extra.scm中找到

Q6: Make a List

根据下图创建list：

使用ok命令解锁和测试：

python3 ok -q make-list -u
python3 ok -q make-list

答案

这题网站上图挂了，我用19年的图做出来不对，正确答案是：

(define lst
    (cons (list 1) (cons 2 (cons (cons 3 4) (list 5))))
)

这个代码用老师给的在线作图工具得到的结果是这样的：

和题目中的图并不相符，如果是题目中的图，答案应该是：

(define lst
    (cons (list 1) (cons 2 (cons (list 3 4) (list 5))))
)

Q6: Compose

实现coposed过程，它接收两个过程f和g，返回一个新的过程。这个返回的过程接收一个数x，返回调用f和g的结果。

(define (composed f g)
  'YOUR-CODE-HERE
)

使用ok命令来解锁和测试：

python3 ok -q composed -u
python3 ok -q composed

答案

同样是返回lambda函数，读懂题意之后没有难度。

(define (composed f g)
    (lambda (x) (f (g x)))
)

Q7: Remove

实现过程remove，接收一个list，返回一个新的list。返回的list中所有等于item的元素被删除。你可以假设list当中只包含数字，没有嵌套的list。

提示：你可能会觉得filter函数很好用

(define (remove item lst)
  'YOUR-CODE-HERE
)


;;; Tests
(remove 3 nil)
; expect ()
(remove 3 '(1 3 5))
; expect (1 5)
(remove 5 '(5 3 5 5 1 4 5 4))
; expect (3 1 4 4)

使用ok命令来进行解锁和测试

python3 ok -q remove -u
python3 ok -q remove

答案

题目已经提示我们了，可以使用filter函数，过滤的条件为不等于num

(define (remove item lst)
    (filter (lambda (x) (not (equal? x item))) lst)
)

Q8: Greatest Common Divisor

让我们复习一下最大公约数。

编写一个过程实现gcd，它返回两个数a和b的最大公约数。我们可以使用欧几里得算法：

如果较大值能够被较小数整除，答案为较小数
否则为较大数关于较小数的余数和较小数的最大公约数

用代码表示，如果a大于b那么：

你可能会觉得min和max过程很有用：

(define (max a b) (if (> a b) a b))
(define (min a b) (if (> a b) b a))
(define (gcd a b)
  'YOUR-CODE-HERE
)

;;; Tests
(gcd 24 60)
; expect 12
(gcd 1071 462)
; expect 21

使用ok命令来解锁和测试：

python3 ok -q gcd -u
python3 ok -q gcd

答案

辗转相除法我们做过很多次了，注意一下a和b中可能存在0，需要特判。

(define (max a b) (if (> a b) a b))
(define (min a b) (if (> a b) b a))
(define (gcd a b)
    (if (equal? (min a b) 0) (max a b)
        (if (equal? (remainder a b) 0) b
            (gcd b (remainder a b))
        )
    )
)

Q9: No Repeats

实现no-repeats过程，接收一个list返回一个list，包含输入当中所有各不相同的数字。比如(no-repeats (list 5 4 5 4 2 2))结果是(5 4 2)。

提示：可以使用=判断两个数字是否相等，如果要判断不等，可以在前面再加上一个not操作。你可以使用filter过程

(define (no-repeats s)
  'YOUR-CODE-HERE
)

使用ok命令来进行解锁和测试：

python3 ok -q no-repeats -u
python3 ok -q no-repeats

答案

这一题有一点难想，需要我们反向思考。常规的想法是我们想办法判断一个元素是否在list中出现了超过一次，如果是的话，进行去重。

但这样一来实现会非常麻烦，因为我们没有办法很方便地遍历list。

由于Scheme list是一个接近链表的结构，我们是从头开始遍历的。我们可以每次拿到元素之后，对剩下的list进行去重。这样可以保证每次从list中拿到的都是和之前所有元素都不重复的元素。这样也就可以把filter函数用上了。

(define (no-repeats s)
    (if (null? s) nil
        (cons (car s)
            (no-repeats (filter (lambda (x) (not (= x (car s)))) (cdr s)))
        )
    )
)

Q10: Substitute

实现substitute函数，它接收三个参数：一个list s，一个old单词和一个new单词。它返回一个list，将s中所有old替换成new，即便在子链表中也一样。

(define (substitute s old new)
  'YOUR-CODE-HERE
)

提示：使用pair?判断元素类型是否是pair

=只能判断数字，equal?还能判断symbol。

使用ok命令来进行解锁和测试：

python3 ok -q substitute -u
python3 ok -q substitute

答案

题意本身不难，递归的逻辑比较直观，只不过使用lisp来实现稍稍有些麻烦。我们可以使用cond语句将原本嵌套的if语句展开，会稍稍好写一点……

(define (substitute s old new)
    (cond 
        ((null? s)  nil)
        ((pair? (car s)) (cons (substitute (car s) old new) (substitute (cdr s) old new)))
        ((equal? (car s) old) (cons new (substitute (cdr s) old new)))
        (else (cons (car s) (substitute (cdr s) old new)))
    )
)

Q11: Sub All

实现sub-all过程，接收一个list s，一个包含若干old单词的list，一个包含若干new单词的list。返回一个新的list，将s中所有出现在old中的单词替换成对应的new单词。确保old和new的list长度一样。

你可以使用substitute来实现

(define (sub-all s olds news)
  'YOUR-CODE-HERE
)

使用ok命令进行解锁和测试：

python3 ok -q sub-all -u
python3 ok -q sub-all

答案

我们每次从olds和news当中提取一个单词，使用substitute进行替换。

替换之后得到的结果作为递归参数传入下一次递归当中，直到最后olds为nil时，返回。

(define (sub-all s olds news)
    (if (null? olds) s 
        (sub-all (substitute s (car olds) (car news)) (cdr olds) (cdr news))
    )
)

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

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2022-05-13，如有侵权请联系 cloudcommunity@tencent.com 删除

python

腾讯云测试服务

编程算法

serverless

本文分享自 Coder梁微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！