置顶 |

阅读数: 次   

UC Berkeley CS61a自学历程和学习总结 (5)

Part 19: Decomposition

Modular Design –模块化设计

  • The goal of a modular design is to achieve separation of concerns

  • A desgin principle: Isolate different parts of a program that address different concerns

  • A modular component can be developed and tested independently

Part 20: Scheme

Scheme入门级别自学小书

Fundamentals

Scheme is a dialect of a language called Lisp

Scheme 是 Lisp 的一个变种，而 Lisp 是继 Fortran 之后仍然广受欢迎的第二古老的编程语言。Lisp 程序员社区几十年来持续蓬勃发展，Clojure 等 Lisp 的新方言拥有现代编程语言中增长最快的开发人员社区。

Scheme 程序主要是由各种表达式构成的，这些表达式可以是函数调用或一些特殊的结构。一个函数调用通常由一个操作符和其后面跟随的零个或多个操作数组成，这点和 Python 是相似的。不过在 Scheme 中，这些操作符和操作数都被放在一对括号里：

1
(quotient 10 2)

“quotient” names Scheme’s built-in integer division procedure(i.e, function)

Scheme 的语法一直采用前缀形式。也就是说，操作符像 + 和 * 都放在前面。函数调用可以互相嵌套，并且可能会写在多行上：

1
(+ (* 3 5) (- 10 6))
1
2
3
4
5
(+ (* 3
      (+ (* 2 4)
         (+ 3 5)))
   (+ (- 10 7)
      6))

我们可以用常见的比较操作符来比较数字，但在 Scheme 中，这些操作符仍然采用前缀的形式：

1
(>= 2 1)

我们还可以通过内置的一些过程来进行一些判断

1
2
3
4
5
6
7
8
9
10
11
12
> (number? 3)
#t
> (number? +)
#f
> (zero? 0)
#t
> (zero? (-2, 2))
#t
> (integer? 2.2)
#f
> (integer? 2)
#t

Scheme Interpreters

你可以下载Scheme解释器或者使用网页内嵌的Scheme解释器，但是在本课程第四个project将会使用python语言来构建一个Scheme解释器，只要运行一次，就能评估Scheme。

vscode配置Scheme方法

Scheme Forms

A combination that is not a call expression is a special form

  • If expression: (if <predicate> <consequent> <alternative>)

    1. Evaluate the predicate expression.
    2. Evaluate either the consequent or alternative

  • And and or: (and <e1>…<en>), (or <e1>…en)

  • Binding symbols: (define <symbol> <expression>)

    1
    2
    3
    > (define pi 3.14)
    > (*pi 2)
    6.28

  • New procedures: (define (<symbol> <formal parameters>)<body>)

    1
    2
    3
    4
    5
    6
    > (define (abs x)
        (if (< x 0)
            (-x)
            x))
    > abs (-3)
    3

ex:

1
(define (square x) (* x x))
1
2
3
4
(define (average x y)
  (/ (+ x y) 2))

(average 1 3)
1
2
3
4
5
6
7
8
9
10
11
(define (sqrt x)
  (define (good-enough? guess)
    (< (abs (- (square guess) x)) 0.001))
  (define (improve guess)
    (average guess (/ x guess)))
  (define (sqrt-iter guess)
    (if (good-enough? guess)
        guess
        (sqrt-iter (improve guess))))
  (sqrt-iter 1.0))
(sqrt 9)

这个代码是使用递归和牛顿法（Newton’s method）来计算一个数(x)的平方根。

Lambda Expressions

Lambda expressions evaluate to anonymous procedures.

  • (lambda (<formal-parameters>) <body>)

匿名函数是通过 lambda 特殊形式创建的。Lambda 用于创建过程，与 define 相似，但不需要为过程指定名称。

生成的过程与使用 define 创建的过程一样，唯一的区别是它没有在环境中关联任何名称。实际上，以下表达式是等效的：

1
2
(define (plus4 x) (+ x 4))
(define plus4 (lambda (x) (+ x 4)))

和任何返回过程的表达式一样，lambda 表达式可以在调用表达式中用作运算符：

1
((lambda (x y z) (+ x y (square z))) 1 2 3)

More Special Forms

Cond & Begin

通常来说，如果我们只是在两个选项之间做选择，那么我们用if，如果超过两个，还是建议使用cond

1
2
3
4
(cond ((> x 10) (print 'big))
      ((> x 5)  (print 'medium))
      (else     (print 'small))
)

或者可以这样写：

1
2
3
4
5
(print
(cond ((> x 10) 'big)
      ((> x 5)  'medium)
      (else     'small)
))

begin特殊形式将多个表达式合并为一个表达式

1
2
(cond ((> x 10) (begin (print 'big)   (print 'guy)))
      (else     (begin (print 'small) (print 'fry))))

Let

  • The let special form binds symbols to values temporarily; just for one expression

Let有点像define,但不同之处在于它只是临时将符号绑定到一个表达式的值里。

1
2
3
(define c (let (a 3)
                (b (+ 2 2)))
            (sqrt (+ (*a a) (* b b))))
  • a and b are not bound down here

通常在Scheme中，define用于那些真正永久的事物，而let则是短暂跟踪或者调用某些值。

Sierpinski’s Triangle

在这篇文章的 Scheme 版本中，加入了一个称为 Turtle 的图形功能（通常叫海龟），它源自 Logo 语言（Lisp 的另一种方言）中的一部分。这个“海龟”从一个画布的中心出发，根据特定的程序命令来移动和转向，并在它移动的过程中留下轨迹。尽管海龟图形最初是设计来吸引孩子学习编程的，但实际上，它对于高级程序员来说也是一个非常有趣的图形化编程工具。

当 Scheme 程序运行时，这只“海龟”会在画布上有一个特定的位置和方向。例如，使用 forward 和 right 这样的命令，可以改变“海龟”的位置和方向。为了方便，一些常用的程序命令有缩写形式，比如 forward 可以简写为 fd。在 Scheme 中，begin 这个特殊结构允许我们在一个表达式中串联多个子命令，这在执行多个操作时非常有用：

1
2
3
4
5
6
7
8
9
> (define (repeat k fn) (if (> k 0)
                            (begin (fn) (repeat (- k 1) fn))
                            nil))
> (repeat 5
          (lambda () (fd 100)
                     (repeat 5
                             (lambda () (fd 20) (rt 144)))
                     (rt 144)))
nil

Python 也内置了完整的 Turtle 功能，作为一个 turtle 库模块。

再举一个例子，Scheme 可以用其 Turtle 图形功能以非常简洁的方式来展现递归的图形。谢尔宾斯基三角形是一种分形结构，它将大的三角形分解成三个小的三角形，小三角形的顶点位于大三角形边的中点。我们可以用下面的 Scheme 程序来实现这个到一定递归深度的绘制：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
> (define (repeat k fn)
    (if (> k 0)
        (begin (fn) (repeat (- k 1) fn))
        nil))

> (define (tri fn)
    (repeat 3 (lambda () (fn) (lt 120))))

> (define (sier d k)
    (tri (lambda ()
           (if (= k 1) (fd d) (leg d k)))))

> (define (leg d k)
    (sier (/ d 2) (- k 1))
    (penup)
    (fd d)
    (pendown))

riangle 函数是一个通用方法，它可以将某个绘图操作重复三次，每次操作后，都会让乌龟左转。sier 函数接受两个参数：一是长度 d，另一个是递归的深度 k。如果深度为 1，它就画一个简单的三角形；否则，它会调用 leg 函数来构建一个由三个小三角形组成的大三角形。leg 函数的功能是画一个谢尔宾斯基三角形的边，它首先递归调用 sier 函数来画出边的上半部分，然后移动乌龟到下一个顶点。而 penup 和 pendown 函数的作用是控制乌龟的画笔，使其在移动时可以选择是否画线。通过 sier 和 leg 的相互递归调用，我们可以得到不错的效果。

1
> (sier 400 6)

Scheme Lists

  • cons: Two-argument procedure that creates a linked list
  • car: Procedure that returns the first element of a list
  • cdr: Procedure that returns the rest of a list
  • nil: The emptu list

Important! Scheme lists are written in parentheses with elements separated by spaces

1
2
3
4
5
6
7
8
9
10
11
> (cons 1 (cons 2 nil))
(1 2)
> (define x (cons 1 (cons 2 nil)))
> x
(1 2)
> (car x)
1
> (cdr x)
(2)
> (cons 1 (cons 2 (cons 3 (cons 4 nil))))
(1 2 3 4)

Symbolic Programming

Symbols normally refer to values; how do we refer to symbols?

1
2
3
4
> (define a 1)
> (define b 2)
> (list a b)
(1 2)

No sign of “a” and “b” in the resulting value

Quotation is used to refer to symbols directly in Lisp.

1
2
3
4
> (list 'a 'b)
(a, b)
> (list 'a b)
(a, 2)

Short for (quote a), (quote b):Special form to indicate that the expression itself is the value.

Quotation can also be applied to combinations to form lists

1
2
3
4
5
6
> '(a b c)
(a b c)
> (car '(a b c))
a
> (cdr '(a b c))
(b c)

List Processing

  • (append s t)
  • (map f s)
  • (filter f s)
  • (apply f s)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
scm> (define s (cons 1 (cons 2 nil)))
s
scm> s
(1 2)
scm> (append s s)
(1 2 1 2)
scm> (append s s s s)
(1 2 1 2 1 2 1 2)
scm> (list s s s s)
((1 2) (1 2) (1 2) (1 2))
scm> (map even? s)
(#f #t)
scm> (map (lambda (x) (* 2 x)) s)
(2 4)
scm> (filter even? s)
(2)
scm> (filter even? '(5 6 7 8 9))
(6 8)
scm> (filter list? '(5 (6 7) 8 (9)))
((6 7) (9))
scm>  (map (lambda (s) (cons 5 s)) (filter list? '(5 (6 7) 8 (9))))
((5 6 7) (5 9))
scm> (apply quotient '(10 5))
2
scm> (apply + '(1 2 3 4))
10


-------------本文结束感谢您的阅读-------------



本文作者： Arua
本文链接： https://blog.visionary-5.top/2024/09/14/CS61A%E7%BC%96%E7%A8%8B%E8%AF%AD%E8%A8%80%E8%AF%BE%E8%87%AA%E5%AD%A6%E5%8E%86%E7%A8%8B(5)/
版权声明： 本作品采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可。转载请注明出处！
知识共享许可协议
赏

如果给你带来一点启发，可以请我喝一杯下午茶吗？

支付宝
置顶

扫一扫，分享到微信

微信分享二维码
本站总访问量次 本站访客数人次

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

A mediocrity CSer in HIT,but eager to do something.