学海注
0%

cs61a改:sicp 学习记录

发表于 更新于 分类于

来源

​ sicp，计算机程序构造与解释，经典编程入门教材，以Lisp方言为教学语言。在csdiy中知道有这么一门课程——cs61a,使用python作为教学语言。在搜索中发现有一个up爱扑bug的熊, 整理并上传了英文资料中文授课的cs61a改(课程主页)。

重要链接：

Composing Programs

pythontutor sicp特供版

2022.10.11 完成课程内容的一半

要点难点记录

​ 虽然已经不是初学的菜鸟，但是这门课程的内容和配套的labs，homework和projects总能给我带来新的东西。做完递归，发现此前有很多东西可以记录一下，以供后续使用。

抽象 Absraction

​ 没有什么问题是不能通过添加一层抽象解决的。

Name

​ 第一个抽象

​ 必须有具体的名字(name)才能被显示调用。

​ (匿名递归不需要暴露名字给外接，但是内部也需要一个具体的名字指称)

表达式计算顺序

image-20221010120612772

​ 操作符(operator) 和 操作数(operand) 都可能是 表达式，从左至右以此计算(evaluate)。

​ 表达式可以嵌套，计算到基本表达式(Primitive Expressions)为止, 如数字，字符，函数

​ 之后将操作符(operator) 应用到 操作数(operand(s)) 上

环境，特指frame

image-20221010121425962

一个函数在哪儿被定义，哪儿的frame就是它的父环境。

一个frame的父环境是 被调用函数的父环境。

An environment is a sequence of frames. 环境就是一个帧序列

Name 查找从local frame开始，向父环境依次往上查找，选择最接近的一个。

高阶函数

将函数作为参数，将函数作为返回值的函数，是函数式编程的根基

重点在于demo和pythontutor的演示

自引用

1
2
3
4
5
6
7
8
9
10
11
12
13
def print_sum(n):
    """
    >>>print_sum(1)(3)(5)
    1
    4
    9
    
    """
    print(n)
    def next_sum(k):
        return print_sum(n +k)
   	return next_sum

函数柯里化(currying)

将多个参数的函数转化为多个单参数函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
>>> add(1,2,3)
6

>>> make_adder_adder(1)(2)(3)
6

def add(x, y, z)
	return x + y + z

def make_adder_adder(x):
    def make_adder(y):
        def adder(z):
            return x + y + z
       	return adder
   	return make_adder

软工常识

​ TDD：先写测试，在写函数体

​ 代码清晰易懂 > 代码短效率高

递归

image-20221010122830607

函数签名需要考虑递归传递的信息；先定义 终止情形(base case)；再定义 递归情况

​ 递归的难点在于，寻找问题结构的相似之处 和 写代码时存在很多未知情况。

​ 前者可以通过迭代解法找循环不变式发现，也可以通过对比大规模和小规模情况下的输出发现。

​ 后者，我们可以抽象出一个函数，假设这个函数解决了这个部分的未知，使用这个函数继续描述问题解法，之后再完善抽象出的函数。

递归也可以多次调用自己，或者互相调用

几个经典问题：

汉诺塔、数字拆分

在homework2中，使用匿名函数完成递归

数据抽象

image-20221010232339204

数据抽象:将数据的表示与数据的操作分隔开来。

有点像ADT(抽象数据类型)，但是此时类型并未现身，仅仅是数据表示和操作。

关键点有两个, constructor 和selector （这两个词的中文翻译有点词不达意，直接用英文，之前做OS实验《一个操作系统的实现》导致对选择子过敏）

demo如下：

image-20221010233024211

constructor 构造一个存储数据的结构（list，structure，hof都可以）

selector 将存储数据的结构中各个部分取出

image-20221010232150240

上游和下游在不改变层际的接口时，互不影响。