CS自学系列（一）CS61A_cover_001

相关学习的准备

小tip：

在google浏览器中按Ctrl+Shift+D，保存当前的所有标签页面到文件夹，下次学习的时候就可以直接右键文件夹打开所有标签页。

建议使用pycharm这个IDE，方便终端输入等。

Welcome_1pp

这篇pdf主要介绍课程的实现目标，规章制度和相关资源的使用，可以参考网页中pdf中的链接找到资源下载并学习。

Discussion 0：Getting Started

讨论课0：主要是了解一下函数。可以试着做下面的例题

Imagine you can call only the following three functions:

  • f(x): Subtracts one from an integer x
  • g(x): Doubles an integer x
  • h(x, y): Concatenates the digits of two different positive integers x and y. For example, h(789, 12) evaluates to 78912 and h(12, 789) evaluates to 12789.

Definition: A small expression is a call expression that contains only f, g, h, the number 5, and parentheses. All of these can be repeated. For example, h(g(5), f(f(5))) is a small expression that evaluates to 103.

What’s the shortest small expression you can find that evaluates to 2024?

我的答案如下：

h(g(g(5)) ,g(g(g(f(f(5))))))

Lab 0：Getting Started

Setup

教学生安装python并查看Python,以及终端的基础使用，讲得特别详细，而且紧跟Python版本，不像国内的ppt老20年起步，而且不会给如此详细的教学和文档资料.

目前我使用的是pycharm，也比较推荐使用这种集成的IDE，这样就不需要为了某个功能到处安装插件。

另外一个扩展阅读：https://cs61a.org/articles/unix/ 是有关unix和终端的

Assignment

网站链接

以后这些外文资料就用google打开并随时保存在浏览器中的"阅读清单"中

  1. 通过命令行打开老师发的zip文档。注意里面的代码不要用

重点部分

以后的作业基本上都是用ok这个平台，首先用1代码测试是否能使用ok，然后根据作业中的命令测试

  1. 用终端进入lab00文件夹，也就是ls时需要有ok这个文件，注意因为我使用的是window，所以老师命令行中的所有python3都改为python。
1
python ok

CS自学系列（一）CS61A_Assignment_image_001

退出可以用ctrl+z+enter 快捷键或者输入exit()

  1. 互动式运行py文件

-i 选项允许以Python命令行互动的形式。你会看到>>> 这样的提示符

1
python -i lab00.py
  1. 测试是否通过所有测试文档(doctests)
1
Python -m doctests lab00.py

其他的命令见链接

我保存了2024fall版本的课程：在/articles/using-ok.html路径下

lecture1：Function

老师讲解了**表达式树(**expression tree)——非常有用，可以解释许多的函数调用问题。

老师在讲解变量的时候，使用“赋值(assignment)”这个英语单词和bind绑定的英文。

Environment Diagrams

环境图：So environment diagrams are a way for us to keep track of what’s going on within the Python interpreter when it executes a program that we type in.they are the way in which an interpreter for a programming language keeps track of what names mean.So it’s sort of memory that keeps track of the bindings between names and values.

summary:An environment is a sequence of frames. A frame is a binding between names and values,one of the boxes in the environment diagram.涉及到局部变量和全局变量的使用。

可以打开此链接https://pythontutor.com/ 看到环境图，左边的就是代码(code),右边的就是框架(frame)

print的副作用(side effect)——推广

用表达式树的方式解释-函数调用的时候会返回值，无论是否显示在“屏幕”上。

1
2
3
4
5
6
7
print(print(1),print(2))
# 结果为
# 1
# 2
# None
# None
# 原因：先调用内部的两个print函数，输出为对应的参数，而其函数的side effect 是返回None值，然后作为外层print的参数，所以接连打印两个None

Textbook

推荐的书籍：Structure and Interpretation of Computer Programs (SICP) 计算机程序的结构与解释

ch1.1简单介绍了Python及其精神，旨在举一反三，将其思想运用到其他语言的编程中。然后开始教一些基础的Python语法

Interactive Sessions

交互式会话，Python的交互式会话会以>>> 为开头。开启Python会话的方法是：
Type python3 at a terminal prompt (Mac/Unix/Linux) or open the Python 3 application in Windows.
会话中会记录代码历史，按ctrl+p(previous)/n(next)查看历史，或者是键盘上下键，Ctrl+d退出会话。

ch1.2 重点介绍了函数，其中涉及到表达式树和Non-pure functions ，非纯函数可能产生副作用，从而改变解释器或计算机的状态。
比如print(print(1),print(2)) 输出结果为1 2 None None 就是因为print函数的返回值是None，在交互式会话中不会出现，但是在编程中容易出现，

ch1.3 同样重点介绍函数，其中A description of the formal parameters of a function is called the function's signature. 点明了函数签名的本质 Bind the arguments to the names of the function's formal parameters in a new local frame. 指明函数定义的细节，比如from math import sin 就是定义了一个全局“变量”sin，使得名字sin 与math库中的内置函数sin绑定(bind)在一起，所以sin可作为函数执行相关操作，但全局变量sin的任何改变都不影响内置函数的sin，同理，def add(a,b): return a+b是将名称(name)add与用户定义的函数add绑定。函数的形式参数也是这样，在函数调用的时候就定义了一个局部变量(比如x),然后将x名称(name)与值绑定，也就是x=2,一旦函数调用完，其本地框架(local frame)也不复存在，所以这就是局部变量不影响全局变量的原理。

函数的本质

The domain of a function is the set of arguments it can take. The range of a function is the set of values it can return. The intent of a function is the relationship it computes between inputs and output (as well as any side effects it might generate)

Lab 1：Function

这一部分的作业主要是用Python写一些相对简单的算法 只要学过数据结构应该不难做出来

Q1部分

  1. 函数调用顺序：print(welcome(), cal()) 会先调用 welcome() 和 cal() 函数。Python 会从左到右依次计算 welcome() 和 cal() 的返回值。调用 welcome() 时，先执行 print("Go")，输出 Go，然后返回字符串 'hello'。调用 cal() 时，先执行 print('Bears')，输出 Bears，然后返回字符串 'world'。
  2. print 函数的最终输出：welcome() 返回 'hello'，cal() 返回 'world'。print(welcome(), cal()) 会将 'hello' 和 'world' 作为参数传递给 print，默认用空格分隔，因此输出 hello world。注意用print不会直接打印出’',需要用转义字符才可以。
1
2
3
4
5
6
7
8
9
def welcome():
  print("Go")
  return 'hello'

def cal():
  print('Bears')
  return 'world'

print(welcome(),cal())

Q2部分

涉及到python的debug和相关编程规范，后续补上相关的问题与回答。

lecture2：control

Ch1.4

如何设计好的函数，以下是相关的一些建议和准则

  • Each function should have exactly one job：每一个函数都应该有一个确定的功能且=
  • Don’t repeat yourself is a central tenet of software engineering(DRY principle)：减少重复，一旦出现重复就要考虑函数或者是其他的抽象封装。
  • Functions should be defined generally： 定义函数的时候要笼统，或者说普适性 能写出pow这种能得到任意次幂的函数就不要用sqrt这种只能开方的函数。
  • Functions with many arguments can be awkward to call and difficult to read.：函数的参数不宜过多，对于很少改变的形式参数可以设置默认值(比如阿伏伽德罗常数、重力加速度等)

如何写一个好的文档(准确的说是函数的注释)

  • Docstrings are conventionally triple quoted：函数的注释要使用三引号
  • The first line describes the job of the function in one line. The following lines can describe arguments and clarify the behavior of the function.第一行描述函数的功能，后面几行介绍参数和明确函数的行为。示例代码如下
1
2
3
4
5
6
7
8
9
10
11
def pressure(v, t, n):
        """Compute the pressure in pascals of an ideal gas. 计算理想气体的帕斯卡压强 

        Applies the ideal gas law: http://en.wikipedia.org/wiki/Ideal_gas_law 应用理想气体定律： 网站链接

        v -- volume of gas, in cubic meters  v -- 气体体积，立方米
        t -- absolute temperature in degrees kelvin t -- 绝对温度，开尔文 
        n -- particles of gas  n -- 气体粒子
        """
        k = 1.38e-23  # Boltzmann's constant  玻耳兹曼常数
        return n * k * t / v
  • code is written only once, but often read many times:代码只会写一次，但是会被阅读成千上万次。可以参考Python的文档编写指导学习docstring guidelines

Ch1.5

主要讲解：控制语句的语法和函数的写法

控制语句的目的是决定解释器应该要执行哪一条语句

函数中的expression用于evaluate value，而return用于将value 返回.大部分函数一般都需要返回值，当然可以没有，比如print

Python中由header+冒号，并且跟着有缩进的语句就是复合语句，比如 def等

1
2
3
4
5
<header>:
    <statement>
    <statement>
    
<separating header>

递归本质的揭示

This definition exposes the essential structure of a recursively defined sequence: a sequence can be decomposed into its first element and the rest of its elements. 用中文的话说就是：一棵树上有多少片叶子，答案是一片叶子，以及剩下的叶子。当你重复这样做的时候，叶子数量也就被你数出来了。

return语句的作用

是沟通局部和全局环境的关键语句，通过return语句将其值通过赋值语句存储到全局变量中(或者是某一个局部变量)

and的短路作用

如果and左边的值为false,那么and整个的表达式结果就是false，无需判断后面的表达式

断言assert的作用

When the expression being asserted evaluates to a true value, executing an assert statement has no effect. When it is a false value, assert causes an error that halts execution

如果断言为真，对语句没有什么影响；如果断言为假，抛出异常，程序终止，常用于测试。

测试(Doctests)要用专门的文件，在Java中是test.java 在Python中一般建议名字后缀为_test

测试的书写

  1. 第一行描述函数的功能

  2. 紧跟空行

  3. 再给几个具体的参数以及期望的结果

  4. 对于部分函数可以给出交互会话示例，以及如何调用函数

示例

1
2
3
4
5
6
7
8
9
10
11
12
def sum_naturals(n):
        """Return the sum of the first n natural numbers.

        >>> sum_naturals(10)
        55
        >>> sum_naturals(100)
        5050
        """
        total, k = 0, 1
        while k <= n:
            total, k = total + k, k + 1
        return total

python中有专门的测试库，可以调用 参考链接

示例如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
from doctest import run_docstring_examples

# 定义一个自定义函数
def sum_naturals(n):
    """返回从1到n的自然数之和

    >>> sum_naturals(10)
    55
    >>> sum_naturals(100)
    5050
    """
    total, k = 0, 1
    while k <= n:
        total, k = total + k, k + 1
    return total

# 开始测试函数
run_docstring_examples(sum_naturals,globals(),True)

得到的结果，这个库函数会根据你在函数中写的测试用例测试，如果函数执行结果和你在测试用例下写的的一样，就返回OK，否则返回错误。所以在写测试用例的时候要写对！！

以后都需要这样测试，而不是自己随便写一个测试用例。

1
2
3
4
5
6
7
8
9
10
11
Finding tests in NoName
Trying:
    sum_naturals(10)
Expecting:
    55
ok
Trying:
    sum_naturals(100)
Expecting:
    5050
ok

在应用函数之前建议先写一些测试用例保证函数的正确性，其中用于测试一个函数的测试被称为unit test(单元测试)

Disc01

Q1：Race

answer：核心就是让tortoise - hare!=0 也就是说，函数循环判断逻辑是有问题的。如果要修改应当是

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def race(x, y):
    """The tortoise always walks x feet per minute, while the hare repeatedly
    runs y feet per minute for 5 minutes, then rests for 5 minutes. Return how
    many minutes pass until the tortoise first catches up to the hare.

    >>> race(5, 7)  # After 7 minutes, both have gone 35 steps
    7
    >>> race(2, 4) # After 10 minutes, both have gone 20 steps
    10
    """
    assert y > x and y <= 2 * x, 'the hare must be fast but not too fast'
    tortoise, hare, minutes = 0, 0, 0
    while minutes == 0 or tortoise > =hare: # 修改的地方
        tortoise += x
        if minutes % 10 < 5:
            hare += y
        minutes += 1
    return minutes

Q2：Fizzbuzz

简单函数，注意判别的顺序即可

如何解决问题(算法的要求)

  1. 给定一个正确的输入和输出(示例)
  2. 用简单的语句描述如何一步步根据输入得到输出
  3. 弄清你所需要的参数
  4. 使用你所需要的参数
  5. 确定方法是否能适用于原始示例
  6. 确定方法能否适用于其他示例

Q3：判断是否为质数

Q4：找出数中只出现一次的数字

Q5-Q6 是关于Environment Diagrams，也就是局部和全局、return语句相关的知识。需要注意的是函数”赋值“，如下

1
2
3
4
5
def double(x):
    return x * 2
    
# double名称指向的是func double(x) [parent=Global]
hat = double #hat也指向的是func double(x) [parent=Global]

不是让hat指向double,而是让hat指向double所指向的函数，本质也就是C的函数指针。

需要注意的翻译

assignment statement：赋值语句

local：在这里要翻译成局部，与之相对的是全局global

Iteration：迭代

Ch1.6 Higher-Order Functions

概念：操纵函数的函数就叫高阶函数

新知识：term，类比C++传入函数指针作为参数

term(k) 表示调用函数 term 并传入参数 k，其返回值用于累加。这种设计使得 summation 函数非常通用，可以计算任意形式的累加和，只要传入相应的 term 函数即可

1
2
3
4
5
def summation(n, term):
    total,k = 0,1
    while k<=n:
        total,k = total+term(k),k+1
    return total

这种函数的设计非常优雅，将抽象的、重复的逻辑整合为一个高阶函数，在高阶函数中调用”定制“的函数，就可以扩展函数的功能。

Nested Functions

函数嵌套，顾名思义就是在函数里面定义函数并使用

嵌套函数的特点

  • 本地函数的名称不会与定义它的函数的外部名称发生冲突，因为本地函数名称将在定义它的当前本地环境中绑定，而不是在全局环境中绑定。
  • 局部函数可以访问外层函数的环境，因为局部函数的主体是在一个扩展了定义它的评估环境的环境中进行评估的。也就是说函数内部定义的函数可以使用外部函数中的环境，比如变量、参数等等

词法作用域(Lexical scope)：

核心定义是：一个变量或符号的可见性（它在哪儿能被访问到）是由它在源代码中的位置决定的，并且在编译时（compile time）就已经确定，而不是在运行时（run time）

比如将变量定义在函数内部，那么作用域就被定死了。表现为向内访问，向外遮蔽

利用这些特性，甚至可以返回函数的组合

1
2
3
4
def compose1(f, g):
    def h(x):
        return f(g(x))
    return h

curry: 柯里化

有些编程语言（如 Haskell）只允许函数接受一个参数，因此程序员必须对所有多参数过程进行 “卷曲”

示例如下

1
2
3
4
5
def curried_pow(x):
    def h(y):
        return pow(x, y)
    return h
curried_pow(2)(3)   # 先将carried_pow返回为h(3) 而x=2已经在pow(2,y)里面，再调入y=3 即可得到8

逆curry化

可以用逆函数去理解，一个简单的公式为uncurry2(curry2(f))=f

1
2
3
4
5
6
7
8
def uncurry2(g):
    """Return a two-argument version of the given curried function."""
    def f(x, y):
        return g(x)(y)
    return f

# 示例
uncurry2(curried_pow)(2, 5) # 将uncurry2返回为curried_pow(2)(5),后面的操作就同之前的

匿名函数Lambda(λ\lambda)

有趣的知识点：利用英语结构理解Lambda,对于其他编程语言的匿名函数也是一样

1
2
3
4
5
6
     lambda            x            :          f(g(x))
"A function that    takes x    and returns     f(g(x))"   

# 示例
f = composel(lambda x:x*x,lambda y:y+1)
result = f(12)

建议严格遵循IDE给出的弱警告，有助于养成编写良好代码的习惯。

装饰器decorator

和Java的注解有些类似，不过其起到的作用还是高阶函数的那种

Hw02

待续…

参考资料

  1. CS自学指南
  2. CS61A官网