2024-08-31

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

有用的一些网址

cs61课程网站2022-spring

概述

CS61a的python编程课强调抽象，让学生掌握用程序来解决实际问题，而不关注底层的硬件细节。不仅仅是一门编程语言课，而是会深入到程序构造与运行的原理。最后你将在第 4 个 Project 中用 Python 实现一个 Scheme 的解释器。此外，抽象将是这门课的一大主题，你将学习到函数式编程、数据抽象、面向对象等等知识来让你的代码更易读，更模块化。当然，学习编程语言也是这门课的一大内容，你将会掌握 Python、Scheme 和 SQL 这三种编程语言，在它们的学习和比较中，相信你会拥有快速掌握一门新的编程语言的能力。

注意：如果此前完全没有编程基础，直接上手 CS61A 需要一定的学习能力和自律要求。为避免课程难度过高而导致的信心挫折，可以选择一个更为友好的入门编程课程。例如伯克利的 CS10 或者哈佛大学的 CS50。(这部分转自与csdiy.wiki)

就我个人的学习经验而言，如果这是你第一次接触到外国高校的系统编程课，那你需要适应他们区别于国内大多数高校的授课方式和思维模式，国外的课程讲得特别特别细，区别于三小时速成课，UCB这系列课程算不上拿来的实用主义，相反他更希望你了解到python这门语言的内核和本质，会用很多的例子，看上去可能比较啰嗦，但是其实你听进去的话，你会发现短短半小时的视频里，信息容量巨大

对国内的学生来说这并不轻松，我们需要的就是耐心，反复体会授课老师语言的内涵，最终把握到他思维最为核心的部分，那么就不成问题了。我会总结一些比较核心和关键的内容，很多的内容还是会用英文去表达，这样更契合实际课程的讲法一点，(如果很复杂的英文表述我会添加中文翻译)，当然总体来说内容还是很多，后面还会单独出一篇有关于这门课程project的文章。

ps: 文章较长，右下角有目录（好像只有电脑客户端才有）

写在前面：交互式解释器

交互式解释器是这套课程授课的工具之一，也是很好地锻炼思维的一种方式。

交互式，体现在你可以即时的获取代码执行的反馈，如果是在pycharm这样的编辑器里，你写完一段代码后，先要知道代码的执行效果必须执行代码，稍作修改后，还得再执行一次代码才能知道效果。

而在交互式解释器里，就如同一个始终在运行着程序，你随时可以修改，随时可以获得反馈。

#在交互式的python解释器中：
python -m doctest Python_Features.py
#输入这行代码的话如果文本无误就没有输出，如果我们想得到更为详细的参数信息，那么我们可以添加一个参数-v,来更详细地展现文本检测的内容和过程
python -m doctest -v Python_Features.py
Trying:
    q, r = divide_exact(2013,10)
Expecting nothing
ok
Trying:
    q
Expecting:
    201
ok
Trying:
    r
Expecting:
    3
ok
1 items had no tests:
    Python_Features
1 items passed all tests:
   3 tests in Python_Features.divide_exact
3 tests in 2 items.
3 passed and 0 failed.
Test passed.

Part1: Expression–表达式

Definition:An expression describes a computation and evaluates to a value.

usages:

1.Calculator

1
2
3
4
>>> 2000 + 15
2015
>>> 1 * 2 * ((3 * 4 * 5 // 6) ** 3) + 7 + 8
2015

2.Call expressions

1
2
3
4
5
6
7
8
9
10
11
12
13
14
>>> max(2, 4)
4
>>> min(-2, 50000)
-2
>>> from operator import add, mul
>>> add(2, 3)
5
>>> mul(2, 3)
6
>>> max(1, 2, 3, 4, 5)
5
>>> mul(add(2, mul(4, 6)), add(3, 5))
208
# In call expressions, you don't need to memorize the order of operations.

3.Anatomy of a Call Expression

1
2
3
add(2, 3)
add -- operator
(2, 3) -- operands -- separated by commas within parentheses

Now, you understand programming languages work is that they interpret your expressions by applying evaluation procedures.

Evaluate the operator and then the operand subexpressions
Apply the function that is the value of the oprator subexpressions to the arguments that are the values of the operand subexpressions
(将作为运算符子表达式的函数应用于作为操作数子表达式的参数)

Assignment Statements：
以下再补充一些赋值的原则：

Evaluate all expressions to the rigt of = from left to right.
Bind all names to the left of = to the resulting values in the current frame.

Part2:enviroments–环境

原课程是将环境的内容放在函数当中讲的，但是为了帮助大家更好地理解函数的内容，我选择把环境这一内容放在第二部分，因为所谓编程的”环境”,本质上是一种抽象的思想，但是对我们理解函数，剖析代码的核心框架有显著的作用，这也是CS61a课程所区别于国内一些编程语言课的核心所在，这一部分主要传递的是一种思想，但这种思想贯穿于课程始终。

在执行函数时，每个函数都会分配一个独立的栈帧，用于存储该函数的参数、局部变量、返回地址等信息。栈帧的作用在于保存函数的运行环境，使得函数执行时可以随时访问其所需的参数和局部变量。当函数被调用时，其栈帧被推入栈中，成为当前活动的栈帧。

如果要深入了解栈帧的知识，还要深入学习数据结构这些内容，在此先不进行深入。但是对于此课程，我们还是需要了解一些基本概念：frame(通常翻译成框架或者帧)，还有父框架、全局框架、环境……

以下是概念之间的一些关系：

Every user-defined function has a parent frame(often global)
每一个自定义函数都有一个父框架,经常是全局框架
The parent of a function is the frame in which it was defined
函数的父级是其定义或者创建时的框架
Every local frame has a parent frame
每个本地框架都有一个父框架
An environment is a sequence of frames
一个环境是一系列帧的序列

我们可以通过python tutor这些软件来进行环境图的绘制，帮助我们理解函数的逻辑，这个是可用的链接:https://pythontutor.com/python-compiler.html#mode=edit

在这个软件中定义和调用函数，观察环境图的生成，你会慢慢理解到一级一级框架所构建的环境，也会慢慢理解变量在各个环境中发生的作用，最终读懂代码的最终逻辑，如果目前你对环境、帧这些概念还是不够了解，也没关系，因为在之后的课程中你还会一次又一次深化这个概念。

Part3:function–函数

当然这一部分的函数章节应该加个基本二字，因为后面还有高阶函数，更为抽象和复杂

We’ll just write down everything using function call notaton

Assignment is a simple means of abstractions:

赋值是一种简单的抽象方法：将名称绑定到值。

Function definition is a more powerful means of abstractions:binds name to expression

函数定义是一种更强大的抽象方法：绑定名称到表达式或者一系列语句.

Name, Assignment,and User-Defined Functions

1.built in functions and built-in names:

>>> from math import pi
>>> pi
3.141592653589793
>>> pi * 71 / 223
1.0002380197528042
>>> from math import sin
>>> sin(pi/2)
1.0

2.assignment statement:

>>> radius = 10
>>> radius
10
>>> 2 * radius
20
>>> area, circ = pi * radius * radius, 2 * pi *radius
>>> area
314.1592653589793
>>> circ
62.83185307179586
>>> radius = 20
>>> area
314.1592653589793

These things are out of sync.And that’s how assignment works.

我们来看一些例子，照应上面的两个性质

ex: to understand functions and parameters

max and f:
>>> max(1,2,3)
3
>>> f = max
>>> f
<built-in function max>
>>> max
<built-in function max>
>>> f(1,2,3)
3
>>> max = 7
>>> f(1,2,3)
3
>>> f(1,2,max)
7
>>> max = f
>>> f
<built-in function max>
>>> max
<built-in function max>
>>> max(1,2,3)

>>> square           
<function square at 0x0000028D0B12CE00>
>>> square(11)       
121
>>> square(add(3,4))
49
>>> square(square(3))
81

Create Function

1 2	>>> def <name>(<formal parameters>): return <return expressions>

Calling / Applying User-Defined Functions:

Add a local frame,forming a new environment
添加一个局部帧，形成一个新的环境
Bind the function’s formal parameters to its arguments in that frame
将该帧中函数的形式绑定到参数
Execute the body of the function in that new environment
我们在这个新环境中执行函数的主体

Life Cycle of a User-Defined Function

1.Def statement
        def square(x):
            return mul(x, x)    
2.call expression
        square(2+2)
3.Calling/Applying

首先定义一个函数，调用表达式，调用或者应用自定义函数（创建一个新的帧）

Pure Function and Non-Pure Function

ex: to figure out the relationship between parameters,return values,and output

>>> print(print(1), print(2)) 
1
2
None None

>>> def does_not_square(x):
...     x * x
...
>>> does_not_square(4)
>>> sixteen = does_not_square(4)
>>> sixteen + 4
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: unsupported operand type(s) for +: 'NoneType' and 'int'

学到这里我们可以补充一下python语言的两个特性：

可以使用一个赋值语句为多个名称赋值，可以从函数中返回许多个值
在定义函数时，可以给出一个默认值，即占位符

Part 4：Control–控制语句

“if” Syntax tips:

Always start with “if” clause.
Zero or more “elif” clauses.
Zero or one “else” clause,alwatys at the end.

ex: 来看一个最基本的例子，返回一个数的绝对值

if x < 0:
        return -x
    elif x == 0:
        return 0
    else:
        return x

Difference between using an if statement and using an if call expression

def if_(c, t, f):
    if c:
        t
    else:
        f

def if_(c, t, f):
    if c:
        t
    else:
        f

from math import sqrt

def real_sqrt():
    """Return the real part of the square root of x."""
    if x >= 0:
        return sqrt(x)
    else:
        return 0

def real_sqrt1():
    """Return the real part of the square root of x."""
    return if_(x >= 0, sqrt(x), 0)

real__sqrt1(-16)这样会报错,调用表达式不允许你跳过对调用表达式的部分进行评估，而控制语句会跳过一些内容,按照顺序流来执行逻辑，调用表达式则反之。

and 和 or 的使用

def has_big_sqrt(x):
    return x > 0 and sqrt(x) > 10

def reasonable(n):
    return n == 0 or 1/n !=0

while and iteration

ex: The Fibonacci Sequence

def fib(n):
    """Compute the nth Fibonacci number, for N >= 1."""
    pred,curr = 0,1
    idex = 1
    while idex < n:
        pred, curr = curr,curr + pred
        idex = idex + 1
    return curr
"""设计迭代函数的时候，要考虑的最重要的事情之一是你需要跟踪的信息，为了进行迭代"""


def fib_improve(n):
    """Compute the nth Fibonacci number, for N >= 1."""
    在之前定义的函数中，fib(0)=1,这个显然是有问题的，我们对这个问题进行改进
    索引设置为0，多进行一次循环"""
    pred,curr = 1,0
    idex = 0
    while idex < n:
        pred, curr = curr,curr + pred
        idex = idex + 1
    return curr

Part 5:Higher-Order Functions

如果前面的内容都还比较简单的话，那这一部分难度提升可能就比较大了，因为这一部分比较抽象，建议多看几遍老师的授课~讲述这一部分主要可能还是通过例子的形式来理解

Generalizing Patterns with Arguments 用参数泛化模式

在这里我解释一下什么叫泛化，在我们写代码的过程中，很多时候都需要重复进行某项工作，比如我计算一个图形的面积，包括正方形，我的面积公式为 a * a,计算圆，我们用到 pi * a * a,如果我们不泛化a这个参量，但我们需要写正方形和圆形的面积公式的时候，我们不可避免的重复自己的代码，即repeat，一个好的程序员是不会重复自己的代码的。下面这个例子就是泛化的一个简单应用。

from math import pi, sqrt

def area_square(r):
   return area(r, 1)

def area_circle(r):
   return area(r, pi)

def area_hexagon(r):
   return area(r, 3 * sqrt(3) / 2)

def area(r,shape_constant):
    assert r > 0, 'A length must be positive'
    return r * r * shape_constant

这其实就是高阶函数的一种

通过这个例子我们引入了高阶函数(higher-order function)

高阶函数是至少满足下列一个条件的函数：

接受一个或多个函数作为输入
返回一个函数

from operator import mul
def  identity(k):
    return k

def cube(k):
    return pow(k, 3)

def pi_term(k):
    return 8 / mul (4 * k - 3, 4 * k - 1)

def summation(n, term):
    """Sum the first N terms of a sequence
    >>> summation(5,cube)
    225
    """
    total, k = 0, 1
    while k <= n:
        total, k = total + term(k), k + 1
    return total
    
def sum_naturals(n):
    """Sum the first N natural number
    >>> sum_naturals(5)
    15
    """
    return summation(n, identity)

def sum_cubes(n):
    """Sum the first N cubes of natural numberss.
    >>> sum_cubes(5)
    225
    """
    total, k = 0, 1
    while k <= n :
        total, k = total + pow(k, 3), k + 1
    return total

"""构建一个函数，返回一个函数"""
def make_adder(n):
    """Return a function that takes one argument K and return K + N
    >>> add_three = make_adder(3)
    >>> add_three(4)
    7
    """
    def adder(k):
        return k + n
    return adder
"""make_adder returns a function, and adder returns a value"""

"""首先，我们表面函数是第一类值，意味着它们可以作为参数传递，可以作为返回值返回，就像编程语言中的任何其他值一样"""

lambda_expression

lambda是除了def之外另外一种定义函数的方式，通常只接收单一参数

"""
square = lambda x: x * x



def square(x):
    return x * x
    
    
1.Both create a function with the same domain, range, and behavior
两者都创建了一个具有相同域、范围和行为的函数
2.Both functions have as their parent the frame in which they were defined
两个函数的父级都是定义他们的框架
3.Both bind that function to the name square
4.Only the def statement gives the function an intrinsic name
只有def语句赋予函数一个内在的名称，会影响环境图的绘制
"""

Currying – 函数柯里化

柯里化是将多参数函数转换为一个单参数高阶函数的行为，该函数返回一个接受其余参数的函数

通俗易懂的解释：用闭包把参数保存起来，当参数的数量足够执行函数了，就开始执行函数。

from operator import add

def make_adder(n):
    return lambda k: n + k

def curry2(f):
    def g(x):
        def h(y):
            return f(x,y)
        return h
    return g

m = curry2(add)
add_three = m(3)
a = add_three(2)
print(a)

curry2 = lambda f: lambda x: lambda y: f(x, y)

回到环境图

一般讲到这里，环境的重要性就不言而喻了。
再repeat一下：

Every user-defined function has a parent frame(often global)
每一个自定义函数都有一个父框架,经常是全局框架
The parent of a function is the frame in which it was defined
函数的父级是其定义或者创建时的框架
Every local frame has a parent frame
每个本地框架都有一个父框架

Part 6: Sounds_ex

这是CS61a中带着大家完成的一个小项目，是一个声音的项目，只有短短2秒钟，是一个Mario的主题曲，也算是以例子的形式加深各位对高阶函数的理解吧！

from wave import open
from struct import Struct
from math import floor

frame_rate = 11025

def encode(x):
    """Encode float x between -1 and 1 as two bytes
    (See https://docs.python.org/3/library/struct.html)
    """
    i = int(16384 * x)
    return Struct('h').pack(i)
    """根据如何根据wav文件要求编码值的方法"""

def play(sampler, name = 'song.wav', seconds = 2):
    """Write the output of a sampler function as a wave file.
    (See https://docs.python.org/3/library/wave.html)
    """
    out = open(name, 'wb')
    out.setnchannels(1)
    out.setsampwidth(2)
    out.setframerate(frame_rate)
    t = 0
    while t < seconds * frame_rate:
        sample = sampler(t)
        out.writeframes(encode(sample))
        t = t + 1
    out.close()
    
    
def tri(frequency, amplitude = 0.3):
    """A continuous triangle wave"""
    period = frame_rate // frequency
    def sampler(t):
        saw_wave = t / period - floor(t / period + 0.5)
        tri_wave = 2 * abs(2 * saw_wave) - 1
        return amplitude * tri_wave
    return sampler


c_freq, e_freq, g_freq = 261.63, 329.63, 392.00

def both(f, g):
    return lambda t: f(t) + g(t)

def note(f, start, end,fade = 0.01):
    def sampler(t):
        seconds = t / frame_rate
        if seconds < start:
            return 0
        elif seconds > end:
            return 0
        elif seconds < start + fade:
            return (seconds - start) / fade * f(t)
        elif seconds >  end - fade:
            return (end - seconds) / fade * f(t)
        else:
            return f(t)
    return sampler

def mario_at(octave):
    c, e = tri(octave * c_freq), tri(octave * e_freq)
    g, low_g = tri(octave * g_freq), tri(octave * g_freq / 2)
    return mario(c, e, g, low_g)

c, e = tri(c_freq), tri(e_freq)
g, low_g = tri(g_freq), tri(g_freq / 2)

def mario(c, e, g, low_g):
    z = 0
    song = note(e, z, z + 1/8)
    z += 1/8
    song = both(song, note(e, z , z + 1/8))
    z += 1/4
    song = both(song, note(e, z, z + 1/8))
    z += 1/4
    song = both(song, note(c, z, z + 1/8))
    z += 1/8
    song = both(song, note(e, z, z + 1/8))
    z += 1/4
    song = both(song, note(g, z, z + 1/4))
    z += 1/2
    song = both(song, note(low_g, z, z + 1/4))
    z += 1/2
    return song

play(both(mario_at(1), mario_at(1/2)))

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

本文作者： Arua
本文链接： https://blog.visionary-5.top/2024/08/31/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(1)/
版权声明： 本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。转载请注明出处！