SICP in Python读书笔记

主要为SICP in Python的读书笔记，记录了书中的一些平时不是很熟悉的知识点。

第一章 用函数构建抽象

测试

doctest模块可以用于测试，python可以将测试写进函数的文档字符串内，例子如下：

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

调用如下，globals返回全局变量的表示，需要它来求解表达式，正常运行应该不返回结果：

from doctest import run_docstring_examples
run_docstring_examples(sum_naturals,globals())

在文件中编写python，可以用下面命令启动文档中所有doctest：

python3 -m doctest <python_source_file>

高阶函数

观察下列求和函数，可以看到相似的求和过程：

def sum_naturals(n):
    total, k = 0, 1
    while k <= n:
        total, k = total + k, k + 1
    return total

def sum_cubes(n):
    total, k = 0, 1
    while k<=n:
        total, k = total + pow(k,3), k+1
    return total

def pi_sum(n):
    total, k = 0,1
    while k<=n:
        total, k = total + 8/(k*(k+2)), k+4
    return total

对于相似的过程，我们可以将其抽象出来，如下：

def do_sum(n,term,next):
    total,k = 0,1
    while k<=n:
        total, k = total + term(k),next(k)
    return total

def cube(n):
    return n**3

def add_one(n):
    return n+1

def sum_cube_abstract(n):
    return do_sum(n,cube,add_one)

我们将方程作为参数，抽象出了中间过程，next表示下一项，term表示本项，对于三次方求和可以用如上过程求解。同样，对于pi_sum也可以通过类似方法求解，如下：

def add_four(n):
    return n+4

def pi_sum_term(n):
    return 8/(n*(n+2))

def pi_sum_abstract(n):
    return do_sum(n,pi_sum_term,add_four)

以同样的过程，我们可以用以下代码表示迭代逼近法：

def iter_improve(update,test,guess=1):
    while not test(guess):
        guess = update(guess)
    return guess

该函数代表当guess满足条件时候则返回，否则不断更新guess直到满足条件。我们可以定义以下函数，来计算黄金比例值：

def near(x,f,g):
    return approx_eq(f(x),g(x))

def approx_eq(x,y,eps=1e-5):
    return abs(x-y)<eps

def square(n):
    return n**2

def golden_update(guess):
    return 1/guess+1

def golden_test(guess):
    return near(guess,square,add_one)

def cal_golden():
    return iter_improve(golden_update,golden_test)

这是计算黄金比例的一种方法，当误差足够小的时候返回，否则继续迭代。

但上述存在一个问题，就是update只接受一个参数，我们可以重新修改我们的模型。

下面操作可以使得我们得到一个数的平方根：

def avg(x,y):
    return (x+y)/2

def sqrt_update(guess,x):
    return avg(guess,x/guess)

通过不断更新来获取平方根，但问题在于该update需要俩参数，我们可以通过以下方法来调用：

def get_sqrt(x):
    def update(guess):
        return sqrt_update(guess,x)

    def test(guess):
        return approx_eq(square(guess),x)
    
    return iter_improve(update,test)

可以看到，此处sqrt_update可以看到参数x，而无需改变iter_improve函数。这里局部函数的用法，他只影响函数内的东西，而不影响函数外的。局部定义的函数也通常称为闭包。

我们可以组合函数，得到一个新的函数，具体如下：

def compose(f,g):
    def h(x):
        return f(g(x))
    return h

我们通过局部函数的方法，得到了一个新的函数。我们也可以用lambda表达式代替上述示例，返回不是函数而是lambda表达式：

def compose_lambda(f,g):
    return lambda x:f(g(x))

我们可以通过函数嵌套的方法，实现牛顿法。首先，实现求导，这里采用近似法求导：

def approx_derivative(f,x,delta=1e-5):
    df = f(x+delta)-f(x)
    return df/delta

我们继续复用上面的迭代逼近法，这里包装一下，形成新的update函数，如下所示，注意函数类型：

def newton_update(f):
    def update(x):
        return x-f(x)/approx_derivative(f,x)
    return update

牛顿法写好后，我们就复用迭代逼近法，如下所示，注意函数类型：

def find_root(f,initial_guess=10):
    def test(x):
        return approx_eq(f(x),0)
    return iter_improve(newton_update(f),test,guess=initial_guess)

find_root是一个通用方法，根据传进来的方程找到方程值为0的情况，下面是一些应用，分别是找到x**2==a的情况和x**0.5==a的情况：

def square_root(a):
    def f(x):
        return square(x)-a
    return find_root(f)

def sqrt_root(a):
    return find_root(lambda x:x**0.5-a)

高阶函数也可以用装饰器语法糖，这里不过多赘述。

第二章 使用对象构建抽象

数据抽象

我们可以用以下方法实现二元组：

def make_pair(x,y):
    def get_item(m):
        if m == 0:
            return x
        elif m == 1:
            return y
    return get_item

二元组并非传统意义上的二元组，而是实现了了一个函数，可以起到二元组的功能，调用方法如下：

p = make_pair(1,100)
print(p(0))
print(p(1))

我们可以用这样的元组，来实现一个有理数。这里将有理数定义为a/b的形式，可以为假分数。

def make_rat(x,y):
    tmp = gcd(x,y)
    return make_pair(x//tmp,y//tmp)

def print_rat(r):
    if(r(1)!=1):
        print(r(0),"/",r(1))
    else:
        print(r(0))

def add_rat(a,b):
    a0,a1 = a(0),a(1)
    b0,b1 = b(0),b(1)
    return make_rat(b0*a1+a0*b1,a1*b1)

这里只实现了加法操作和现实操作，其他的操作也类似。这是一种抽象的方法。

实现类与对象

首先明确思路：类包含成员函数，对象有着自己的属性。当调用成员函数的时候，需要将函数与对象相绑定。

我们可以用字典来模拟属性与方法。在类中的字典存放方法，调用的时候绑定到对象。在对象的字典中存放属性。

首先可以写出make_instance函数来创造一个对象，如下所示：

def make_instance(cls):
    def get_value(name):
        if name in attributes:
            return attributes[name]
        else:
            value = cls["get"](name)
            return bind_method(value,instance)

    def set_value(name,value):
        attributes[name] = value
    
    attributes = {}
    instance = {"get":get_value,"set":set_value}
    return instance

其中get_value用于获取属性，或者调用成员函数。set_value用于更改成员。当调用get_value时候，我们先找是否存在属性，如果找不到，则在类中找到对应方法并绑定。

bind_method用于绑定，实现如下所示：

def bind_method(value,instance):
    if callable(value):
        def method(*args):
            return value(instance,*args)
        return method
    else:
        return value

如果入参为可调用的，则绑定到instance，如果不是，则返回对应值。

注意这里的instance本质还是一个字典，在后续的成员函数的使用上会看到这一点。

在关注完创建对象之后我们再来关注创建类，如下所示：

def make_class(attributes,base_class=None):
    def get_value(name):
        if name in attributes:
            return attributes[name]
        elif base_class is not None:
            return base_class["get"](name)

    def set_value(name,value):
        attributes[name] = value

    def new(*args):
        return init_instance(cls, *args)

    cls = {"get":get_value,"set":set_value,"new":new}
    return cls

类的本质也是一个绑定了get,set,new三个基本方法的字典。这里实现了继承功能。在get的时候，会找到成员，如果找不到则在父类中寻找。set则逻辑相同。new的时候接收各种类型的参数，创建实例，然后找到用户定义的__init__函数，将参数输入进去进行对象的初始化，具体如下：

def init_instance(cls,*args):
    instance = make_instance(cls)
    init = cls["get"]("__init__")
    if init:
        init(instance, *args)

    return instance

接下来我们可以具体实现一个类，来观察这个系统是怎么执行的。创建类的函数实现如下：

def make_account_class():
    def __init__(self_instance,account_holder):
        print(self_instance)
        self_instance["set"]("holder",account_holder)
        self_instance["set"]("balance",0)

    def deposit(self_instance, amount):
        """Increase the account balance by amount and return the new balance."""
        new_balance = self_instance['get']('balance') + amount
        self_instance['set']('balance', new_balance)
        return self_instance['get']('balance')

    def withdraw(self_instance, amount):
        """Decrease the account balance by amount and return the new balance."""
        balance = self_instance['get']('balance')
        if amount > balance:
            return 'Insufficient funds'
        self_instance['set']('balance', balance - amount)
        return self_instance['get']('balance')
    return make_class({'__init__': __init__,
                        'deposit':  deposit,
                        'withdraw': withdraw,
                        'interest': 0.02})

这里实现了一个账户类以及一些方法。首先关注创建时候的流程。当调用该函数的时候，函数会创建一个class字典，其attributes为return里面的东西，而attritubes需要通过get_value函数，set_value函数来访问。调用方法如下：

Account = make_account_class()
print(Account["get"]("interest"))

该调用过程：makeclass.get_value("interest") => makeclass.attributes["interest"]

在完成类的创建后，我们需要通过访问class字典的new成员，将其当作函数来调用，如下所示：

jim_acc = Account["new"]("Jim")

调用过程:makeclass.new("Jim") => init_instance(makeclass.cls,"Jim") => make_account_class.__init__(make_instance(cls),"Jim")

在调用方法的时候，以以下形式调用：

print(jim_acc["get"]("deposit")(20))

他会先从对象的字典中寻找deposit，找不到则在类中找到deposit方法，并且调用类的deposit方法，参数为该对象与调用时候输入的参数。

接下来我们使用继承，看看继承是如何实现的：

def make_different_account_class():
    def withdraw(selfinstance, amount):
        return Account['get']("withdraw")(selfinstance,amount+1)
    return make_class({"withdraw":withdraw,"interest":0.01},Account)

我们实现了一个Account子类，复用了里面的所有方法，改写了withdraw方法使得扣钱会多一块钱。

这就是实现类与对象的基本思路。

泛用方法

接口：我们可以通过统一的接口来实现抽象。负数在表示时候可以用角度表示也可以用实数表示，以下加法可以协调两种不同表示法：

def add_complex(z1,z2):
    return ComplexRI(z1.real+z2.real,z1.img+z2.img)

def mul_complex(z1,z2):
    return ComplexMA(z1.mag * z2.mag, z1.ang + z2.ang)

只要两个类都定义了对应属性，就可以相加。这里引入@property装饰器，使用该装饰器可以当属性直接调用，而不用打括号。也减少了重复存储的麻烦。两个类定义如下：

class ComplexRI():

    def __init__(self,real,img) -> None:
        self.real = real
        self.img = img

    @property
    def mag(self):
        return (self.real ** 2 + self.img ** 2) ** 0.5

    @property
    def ang(self):
        return atan2(self.img,self.real)

    def __repr__(self) -> str:
        return "ComlexRI ({0},{1})".format(self.real,self.img)
    
class ComplexMA():

    def __init__(self,mag,ang):
        self.mag = mag
        self.ang = ang

    @property
    def real(self):
        return self.mag*cos(self.ang)

    @property
    def img(self):
        return self.mag*sin(self.ang)

    def __repr__(self) -> str:
        return "ComplexMA({0},{1})".format(self.mag,self.ang)

这样就简单地实现了复用。我们还可以用python的特殊方法，来实现运算符的使用，只要分别定义如下几行：

ComplexRI.__add__ = lambda self, other: add_complex(self, other)
ComplexMA.__add__ = lambda self, other: add_complex(self, other)
ComplexRI.__mul__ = lambda self, other: mul_complex(self, other)
ComplexMA.__mul__ = lambda self, other: mul_complex(self, other)

这样我们就可以使用加法运算符和乘法运算符。

我们可以通过判断type来实现跨类型的加法运算定制。也可以将其封装起来，实现一个字典，按照字典查找对应的加法运算。

第三章 计算机程序的构造和解释

递归

递归往往会因为重复计算而产生额外的开销。可以用以下装饰器来让递归记忆化：

def memo(f):
    cache = {}
    def memorized(n):
        if n not in cache:
            cache[n] = f(n)
        return cache[n] 
    return memorized