咱们好，日拱一卒，我是梁唐。

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

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

别的Lisp言语的特性使得它的词法语法分析很好做，或许也是为后边的编译原理打基础，而且整个言语的代码是以链表的方式存储的，也能更好地协助咱们了解递归和链表等数据结构。

咱们看到Scheme必定不像看到Python这么感兴趣，但伯克利这门课傍边没有废话，每一个知识点都是有用的，踏实学完，收成一定是不菲的。

课程链接

试验原始文档

我的Github

首要，咱们需求先去试验课的网站下载试验文件：

咱们主要编写的代码在lab09.scm和lab09_extra.scm傍边，其余的都是测验文件。scheme是教师提供的一个编译好的scheme解说器，咱们能够在傍边测验咱们的Scheme代码。因为这个解说器是Python编写的，所以测验指令为：python3 scheme -i

教师还提供了在线的Scheme解说器，也能够直接在网站上进行编码和调试，地址为：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。