cs61a

welcome

python ok -q python-basics -u --local没有ucb账号本地运行ok的方法
有用的命令行参数

• -i :直接进入交互模式，可以方便地查看各变量
• python -m doctest:不单独编写测试文件的情况下进行测试(Doctest 模块通过扫描你代码的文档字符串（docstrings），查找看起来像 Python 交互式会话的代码块，并执行这些代码块以验证它们的输出是否与文档中预期的输出相匹配。)还可以添加-v详细看到输出信息
  • e.g

def add(a, b):
    """
    This function adds two numbers.

    >>> add(2, 3)
    5
    >>> add(10, -5)
    5
    """
    return a + b

Functions

• 任何编程语言都具有的三种强大的机制:
  
• 中缀表示法（infix notation），运算符（例如 +、-、* 或 /）出现在操作数之间
• 调用表达式(operator:运算符,operand:操作数)
  • 
• 导入库函数: import operator导入常见的中缀运算符
• 名称与环境(name and environment):
  • 我们使用名称来引用对象name="tom"
  • 名称可以通过等号和import来与值绑定
  • 解释器必须要维护内存来保存名称的引用，这就叫环境(environment)
• 求解嵌套表达式
  • 
  • 求值本质上是递归的，我们规定,数字的值是其对应的数值,名称的值是环境中其对应的所关联的对象
• 非纯函数print
  • 纯函数：调用一个有输入的函数，然后仅仅返回一些值
  • 非纯函数:除了返回值外，调用一个非纯函数还会产生其他改变解释器和计算机的状态的副作用（side effect）
  • e.g: print:它实际上会返回一个none值，输出控制台相当于是副作用
• 环境
  • 求解表达式的环境由 帧 序列组成，它们可以被描述为一些盒子。每个帧都包含了一些 绑定，它们将名称与对应的值相关联。全局 帧（global frame）只有一个。赋值和导入语句会将条目添加到当前环境的第一帧。
  • 函数名称重复两次，一次在环境帧中，另一次是作为函数定义的一部分。函数定义中出现的名称叫做 内在名称（intrinsic name），帧中的名称叫做 绑定名称（bound name）。两者之间有一个区别：不同的名称可能指的是同一个函数，但该函数本身只有一个内在名称。求值使用的是绑定名称
  • 对函数形式参数的描述被称为函数的签名。
• 调用用户定义的函数
  • 这会产生局部帧(local frame):该局部中的实参会绑定到形参上
  • 名称求解（Name Evaluation）：在环境中寻找该名称，最早找到的含有该名称的帧，其里边绑定的值就是这个名称的计算结果。
• 抽象函数:
  • 域(domain):可以接收的参数集合
  • 范围(range):可返回的值的集合
  • 意图(intent):输入输出之间的关系，并且涉及任何副作用

hw01

注意:若add是一个函数

• f=add,这f是一个函数
• f=add(a,b),f是运算结果

lab01

python异或:^
阶乘:math.factorial()
交互式python环境中:任意定义完成一个函数之后要隔一个空行才算结束，并且调用函数会直接打印返回值

control

• 设计原则(函数就是抽象)：每个函数只执行一个任务、不要重复自己(don’t repeat yourself)、定义通用的函数(pow和平方函数)
• 文档字符串(docstring):以函数名的字符串为参数调用help就会看到(q以退出该状态)

>>> 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
        t -- absolute temperature in degrees kelvin
        n -- particles of gas
        """
        k = 1.38e-23  # Boltzmann's constant
        return n * k * t / v

• Python 代码是一系列语句。简单语句是不以冒号结尾的单行，而由其他语句（简单语句和复合语句）组成被称为复合语句。复合语句通常跨越多行，以单行头部（header）开始，并以冒号结尾，其中冒号标识语句的类型。头部和缩进的句体（suite）一起称为子句。
• 赋值语句:在更新左侧的绑定之前求出所有 = 右侧的内容
• 测试 assert fib(8) == 13, '第八个斐波那契数应该是 13'
  • 通常是在一个_test.py文件中执行的

#非命令行方法的测试
"""
This is the "example" module.

The example module supplies one function, factorial().  For example,

>>> factorial(5)
120
"""

def factorial(n):
    """Return the factorial of n, an exact integer >= 0.

    >>> [factorial(n) for n in range(6)]
    [1, 1, 2, 6, 24, 120]
    >>> factorial(30)
    265252859812191058636308480000000
    >>> factorial(-1)
    Traceback (most recent call last):
        ...
    ValueError: n must be >= 0

    Factorials of floats are OK, but the float must be an exact integer:
    >>> factorial(30.1)
    Traceback (most recent call last):
        ...
    ValueError: n must be exact integer
    >>> factorial(30.0)
    265252859812191058636308480000000

    It must also not be ridiculously large:
    >>> factorial(1e100)
    Traceback (most recent call last):
        ...
    OverflowError: n too large
    """

    import math
    if not n >= 0:
        raise ValueError("n must be >= 0")
    if math.floor(n) != n:
        raise ValueError("n must be exact integer")
    if n+1 == n:  # catch a value like 1e300
        raise OverflowError("n too large")
    result = 1
    factor = 2
    while factor <= n:
        result *= factor
        factor += 1
    return result


if __name__ == "__main__":
    import doctest
    doctest.testmod()

• globals()函数，返回全局变量字典

Higher OrderFunctions && Environment

• 作通用方法的函数

>>> def improve(update, close, guess=1):
        while not close(guess):
            guess = update(guess)
        return guess

• 嵌套定义函数

#为了解决improve函数签名不一致的问题
>>> def sqrt(a):
        def sqrt_update(x):
            return average(x, a/x)
        def sqrt_close(x):
            return approx_eq(x * x, a)
        return improve(sqrt_update, sqrt_close)

• 继承环境（Extended Environments）：一个环境可以由任意长的帧链构成，并且总是以全局帧结束。在举 sqrt 这个例子之前，环境最多只包含两种帧：局部帧和全局帧。通过使用嵌套的 def 语句来调用在其他函数中定义的函数，我们可以创建更长的（帧）链。
• 局部定义的函数通常被称为闭包（closures）

牛顿法

#沿着切线近似到0
>>> def newton_update(f, df):
        def update(x):
            return x - f(x) / df(x)
        return update

>>> def find_zero(f, df):
        def near_zero(x):
            return approx_eq(f(x), 0)
        return improve(newton_update(f, df), near_zero)

柯里化(Currying)

通过函数链把多参数转化为单参数

>>> def curried_pow(x):
        def h(y):
            return pow(x, y)
        return h
>>> curried_pow(2)(3)
8
>>> def curry2(f):
        """返回给定的双参数函数的柯里化版本"""
        def g(x):
            def h(y):
                return f(x, y)
            return h
        return g
>>> def uncurry2(g):
        """返回给定的柯里化函数的双参数版本"""
        def f(x, y):
            return g(x)(y)
        return f

lambda函数

lambda              x         :              f(g(x))
"A function that    takes x   and returns    f(g(x))"

装饰器(decorator)

>>> def trace(fn):
        def wrapped(x):
            print('-> ', fn, '(', x, ')')
            return fn(x)
        return wrapped

>>> @trace
    def triple(x):
        return 3 * x

>>> triple(12)
->  <function triple at 0x102a39848> ( 12 )
36

#这个装饰器等价于
>>> def triple(x):
        return 3 * x
>>> triple = trace(triple)

hw02

#递归调用要有累积+柯里化
def make_repeater(f, n):
    """Returns the function that computes the nth application of f.

    >>> add_three = make_repeater(increment, 3)
    >>> add_three(5)
    8
    >>> make_repeater(triple, 5)(1) # 3 * (3 * (3 * (3 * (3 * 1))))
    243
    >>> make_repeater(square, 2)(5) # square(square(5))
    625
    >>> make_repeater(square, 3)(5) # square(square(square(5)))
    390625
    """
    "*** YOUR CODE HERE ***"
    def all(start):
        return recur_fuc(start,f,n)
    return all

    
def recur_fuc(m,f,i):
    if i==1:
        return f(m)
    else:
        return f(recur_fuc(m,f,i-1))

hog

# *args的用法
def make_averaged(original_function, times_called=1000):
    """Return a function that returns the average value of ORIGINAL_FUNCTION
    called TIMES_CALLED times.

    To implement this function, you will have to use *args syntax.

    >>> dice = make_test_dice(4, 2, 5, 1)
    >>> averaged_dice = make_averaged(roll_dice, 40)
    >>> averaged_dice(1, dice)  # The avg of 10 4's, 10 2's, 10 5's, and 10 1's
    3.0
    """
    # BEGIN PROBLEM 8
    def ret_func(*args):
        total=0
        for i in range(times_called):
            total+=original_function(*args)
        return total/times_called
    return ret_func

lab2

>>> def cake():
...    print('beets')
...    def pie():
...        print('sweets')
...        return 'cake'
...    return pie
>>> chocolate = cake()
#beets

>>> chocolate
#<Function>

>>> chocolate()
#(line 1)? sweets
#(line 2)? "cake"

>>> more_chocolate, more_cake = chocolate(), cake
#? sweets

>>> more_chocolate
#? "cake"

>>> def snake(x, y):
...    if cake == more_cake:
...        return chocolate
...    else:
...        return x + y
>>> snake(10, 20)
#? Function

>>> snake(10, 20)()
#(line 1)? sweets
#(line 2)? "cake"

>>> cake = 'cake'
>>> snake(10, 20)
#? 30

>>> b = lambda x, y: lambda: x + y  # Lambdas can return other lambdas!
>>> c = b(8, 4)
>>> c#是个函数

>>> higher_order_lambda = lambda f: lambda x: f(x)
>>> g = lambda x: x * x
>>> higher_order_lambda(2)(g)  # Which argument belongs to which function call?
#error：参数位置不对

functional abstraction

error and traceback

three types:语法错误(syntax error)、运行时错误(runtime error)、逻辑行为错误
none是无类型的：none-none也是错的

recurssion function

• 将递归调用看作一种函数抽象这一思想，就是所谓“递归的信仰之跃（recursive leap of faith）”。我们根据函数自身来定义一个函数，但在验证函数的正确性时，我们只需相信在更简单的情况下，函数同样能正确工作。

互递归

• 两个函数互相调用

def is_even(n):
        if n == 0:
            return True
        else:
            return is_odd(n-1)
    
def is_odd(n):
    if n == 0:
        return False
    else:
        return is_even(n-1)
    
result = is_even(4)

树递归

e.g:分割树(n被最大为m的整数分割的分法总数)

>>> def count_partitions(n, m):
        """计算使用最大数 m 的整数分割 n 的方式的数量"""
        if n == 0:
            return 1
        elif n < 0:
            return 0
        elif m == 0:
            return 0
        else:
            return count_partitions(n-m, m) + count_partitions(n, m-1)
            # 含m的和不含m的分法

disc3

def swipe(n):
    """Print the digits of n, one per line, first backward then forward.

    >>> swipe(2837)
    7
    3
    8
    2
    8
    3
    7
    """
    if n < 10:
        print(n)
    else:
        print(n%10)
        temp=n//10
        swipe(temp)
        print(n%10)
        "*** YOUR CODE HERE ***"
#递归中的help method
def is_prime(n):
    """Returns True if n is a prime number and False otherwise.
    >>> is_prime(2)
    True
    >>> is_prime(16)
    False
    >>> is_prime(521)
    True
    """
    "*** YOUR CODE HERE ***"
    def check(i):
        if n==i or n==2:
            return True 
        elif n%i==0:
            return False
        else:
            return check(i+1)
    return check(2)

数据抽象

• 原始数据类型：int、float、complex
  • 有一些可以求解为原始数据类型的表达式，被称为字面量（literals）、有用于操作原始类型值的内置函数和操作符.
• 将“数据表示”与“数据处理”的程序隔离的通用技术是一种强大的设计方法，称为数据抽象。
• e.g:有理数(内置的float有很大的精度问题，所以可用有理数来精确表示)
  • 
  • 抽象屏障：当程序中有一部分本可以使用更高级别函数但却使用了低级函数时，就会违反抽象屏障，这会增大维护的难度

hw03

#分割+特殊情况
def digit_distance(n):
    """Determines the digit distance of n.

   
    """
    "*** YOUR CODE HERE ***"
    if n<10:
        return 0
    elif n>=10 and n<100:
        return abs(n//10-n%10)
    else:
        if n%100<10:
            return digit_distance(n//10)+n%100
        else:
            return digit_distance(n//10)+digit_distance(n%100)
#级联elif注意顺序！！！
def count_dollars(total):
    """Return the number of ways to make change."""


    "*** YOUR CODE HERE ***"
    def count(val,max_b):
        if val==0:
            return 0
        elif max_b==1:
            return 1
        elif val<max_b:
            return count(val,next_smaller_dollar(max_b))
        elif val==max_b:
            return 1+count(val,next_smaller_dollar(max_b))
        else:
            return count(val-max_b,max_b)+count(val,next_smaller_dollar(max_b))
    return count(total,100)

序列

• 序列（sequence）是一组有顺序的值的集合，是计算机科学中的一个强大且基本的抽象概念
• 列表间的相加和相乘(就是元素附上去)
• 序列解包（Sequence unpacking）:for x,y in pairs
• 列表推导式（List Comprehensions）[<map expression> for <name> in <sequence expression> if <filter expression>]
• 聚合（Aggregation）:sum、min、max等都算聚合函数

高阶函数

>>> def apply_to_all(map_fn, s):
        return [map_fn(x) for x in s]
>>> def keep_if(filter_fn, s):
        return [x for x in s if filter_fn(x)]
#聚合的一般形式
>>> def reduce(reduce_fn, s, initial):
        reduced = initial
        for x in s:
            reduced = reduce_fn(reduced, x)
        return reduced

序列抽象

• 成员资格（Membership）in\not in
• 切片（Slicing)
• 字符串中的成员资格是查找子字符串

lab3

• 列表乘2:变长为2倍
• range生成的是可迭代对象:只是不是数组，甚至可以直接用下标取值
• 判断整数:%1==0

disc4

def max_product(s):
    """Return the maximum product of non-consecutive elements of s.

    >>> max_product([10, 3, 1, 9, 2])   # 10 * 9
    90
    >>> max_product([5, 10, 5, 10, 5])  # 5 * 5 * 5
    125
    >>> max_product([])                 # The product of no numbers is 1
    1
    """
    if s == []:
        return 1
    if len(s) == 1:
        return s[0]
    else:
        return max(s[0] * max_product(s[2:]), max_product(s[1:]))
        # OR
        return max(s[0] * max_product(s[2:]), s[1] * max_product(s[3:]))

def sums(n, m):
    """Return lists that sum to n containing positive numbers up to m that
    have no adjacent repeats.

    >>> sums(5, 1)
    []
    >>> sums(5, 2)
    [[2, 1, 2]]
    >>> sums(5, 3)
    [[1, 3, 1], [2, 1, 2], [2, 3], [3, 2]]
    >>> sums(5, 5)
    [[1, 3, 1], [1, 4], [2, 1, 2], [2, 3], [3, 2], [4, 1], [5]]
    >>> sums(6, 3)
    [[1, 2, 1, 2], [1, 2, 3], [1, 3, 2], [2, 1, 2, 1], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
    """
    if n < 0:
        return []
    if n == 0:
        sums_to_zero = []     # The only way to sum to zero using positives
        return [sums_to_zero] # Return a list of all the ways to sum to zero
    result = []
    for k in range(1, m + 1):
        result = result + [[k] + rest for rest in sums(n-k, m) if rest == [] or rest[0] != k]
    return result
#The recursive case is that each list that sums to n is an integer k (up to m)
#followed by the elements of a list that sums to n-k and does not start with k.

cats

• 对函数的递归调用:每一帧传进去的参数不一样！！！
• 负无穷float('-inf')

#文本处理
def about(subject):
    """Return a function that takes in a paragraph and returns whether
    that paragraph contains one of the words in SUBJECT.

    Arguments:
        subject: a list of words related to a subject
    assert all([lower(x) == x for x in subject]), "subjects should be lowercase."
    """
    # BEGIN PROBLEM 2
    def sel(paragraph):
        for word in split(lower(remove_punctuation(paragraph))):
            for key in subject:
                if key == word:
                    return True
        return False
    return sel
    "*** YOUR CODE HERE ***"
    # END PROBLEM 2
#思路:分各种情况全递归算出来加一起比较

def minimum_mewtations(typed, source, limit):
    """A diff function for autocorrect that computes the edit distance from TYPED to SOURCE.
    This function takes in a string TYPED, a string SOURCE, and a number LIMIT.

    Arguments:
        typed: a starting word
        source: a string representing a desired goal word
        limit: a number representing an upper bound on the number of edits


    """
    if typed==source: # Base cases should go here, you may add more base cases as needed.
        # BEGIN
        "*** YOUR CODE HERE ***"
        return 0
        # END
    elif abs(len(typed)-len(source))>limit:
        return limit+1
    elif limit<0:
        return 0
    elif len(typed)==0 or len(source)==0:
        return abs(len(typed)-len(source))
    # Recursive cases should go below here
    if typed[0]==source[0]: # Feel free to remove or add additional cases
        # BEGIN
        "*** YOUR CODE HERE ***"
        return minimum_mewtations(typed[1:],source[1:],limit)
        # END
    else:
        add = 1+minimum_mewtations(source[0]+typed,source,limit-1) # Fill in these lines
        remove = 1+minimum_mewtations(typed[1:],source,limit-1)
        temp=source[0]+typed[1:]
        substitute = 1+minimum_mewtations(temp,source,limit-1)
        return min(add,remove,substitute)
        # BEGIN
        "*** YOUR CODE HERE ***"
        # END

可变数据

• 基本数据类型是不可变的，复杂对象是可变的
• 区分:身份验证和相等验证(前者是验证是否同一个对象)
• 元组是不可变对象
• 字典:可用dict()方法加列表构成，其key不能是可变数据，一个key对应一个val
  • get,返回key对应val或者默认值
  • 也有字典推导式
• 局部状态：声明变量非局部nonlocal balance
  • 只有函数调用才会返回新的帧，否则就是在这里面自己变

#如果不使用nonlocal声明变量会导致python默认它是局部变量(有赋值加减的操作)
#这个时候第三句的判断会出错
def make_withdraw(balance):
    def withdraw(amount):
        nonlocal balance
        if amount > balance:
            return 'Insufficient funds'
        balance = balance - amount
        return balance
    return withdraw

• 使用函数来实现链表：需要一个调度函数，其参数首先是一个期望的指令，代表期望这个函数做什么；然后是该方法的需要用到的参数。
  • 也可以使用一个调度字典(包含各种各样的操作情况和非局部变量(还可以避免使用nonlocal))

约束传递

• 计算机程序传统上是被定义为单向的计算(数学上无法利用一个方程进行双向计算)
• 将程序表示为约束(声明式编程)
  • 

>>> connector ['set_val'](source, value)  """表示 source 在请求连接器将当前值设为 value"""
>>> connector ['has_val']()  """返回连接器是否已经具有值"""
>>> connector ['val']  """是连接器的当前值"""
>>> connector ['forget'](source)  """告诉连接器 source 请求遗忘它的值"""
>>> connector ['connect'](source)  """告诉连接器参与新的约束，即 source"""

>>> constraint['new_val']()  """表示与约束相连的某个连接器具有新的值。"""
>>> constraint['forget']()  """表示与约束相连的某个连接器遗忘了值。"""

>>> def converter(c, f):
        """用约束条件连接 c 到 f ，将摄氏度转换为华氏度."""
        u, v, w, x, y = [connector() for _ in range(5)]
        multiplier(c, w, u)
        multiplier(v, x, u)
        adder(v, y, f)
        constant(w, 9)
        constant(x, 5)
        constant(y, 32)

>>> from operator import add, sub
>>> def adder(a, b, c):
        """约束a+b=c"""
        return make_ternary_constraint(a, b, c, add, sub, sub)

>>> def constant(connector, value):
        """常量赋值."""
        constraint = {}
        connector['set_val'](constraint, value)
        return constraint

>>> def make_ternary_constraint(a, b, c, ab, ca, cb):       #不存储连接的连接器，只提供功能
        """约束ab(a,b)=c，ca(c,a)=b，cb(c,b)=a。"""
        def new_value():
            av, bv, cv = [connector['has_val']() for connector in (a, b, c)]
            if av and bv:
                c['set_val'](constraint, ab(a['val'], b['val']))
            elif av and cv:
                b['set_val'](constraint, ca(c['val'], a['val']))
            elif bv and cv:
                a['set_val'](constraint, cb(c['val'], b['val']))
        def forget_value():
            for connector in (a, b, c):
                connector['forget'](constraint)
        constraint = {'new_val': new_value, 'forget': forget_value}
        for connector in (a, b, c):
            connector['connect'](constraint)
        return constraint

>>> def connector(name=None):
        """限制条件之间的连接器."""
        informant = None	#记录谁给它赋值
        constraints = []	#记录其参与的所有约束
        def set_value(source, value):
            nonlocal informant
            val = connector['val']
            if val is None:
                informant, connector['val'] = source, value
                if name is not None:
                    print(name, '=', value)
                inform_all_except(source, 'new_val', constraints)
            else:
                if val != value:
                    print('Contradiction detected:', val, 'vs', value)
        def forget_value(source):
            nonlocal informant
            # 如果是source提供的值就清空并通知
            if informant == source:
                informant, connector['val'] = None, None
                if name is not None:
                    print(name, 'is forgotten')
                inform_all_except(source, 'forget', constraints)
        connector = {'val': None,
                     'set_val': set_value,
                     'forget': forget_value,
                     'has_val': lambda: connector['val'] is not None,
                     'connect': lambda source: constraints.append(source)}
        return connector

>>> def inform_all_except(source, message, constraints):
        """告知信息除了source外的所有约束条件，。"""
        for c in constraints:
            if c != source:
                c[message]()

lab4

• in对字典只检测键，不检测值
  检测值: x in dic.values()
  迭代键值对for key,val in dic.items()

def buy(fruits_to_buy, prices, total_amount):
    """Print ways to buy some of each fruit so that the sum of prices is amount.
    """
    for item in fruits_to_buy:
        total_amount-=prices[item]
    def add(fruits, amount, cart,count):
        if amount==0:
            print(cart)
        elif fruits==[]:
            return
        elif amount<0:
            return
        else:
            new_cart=""
            for item,i in count.items():
                new_cart+=display(item,i)
            add(fruits[1:],amount,new_cart,count)
            count[fruits[0]]+=1
            new_cart=""
            for item,i in count.items():
                new_cart+=display(item,i)
            add(fruits,amount-prices[fruits[0]],new_cart,count)
            count[fruits[0]]-=1
            
    add(fruits_to_buy, total_amount, '',{key:1 for key in fruits_to_buy})
#回溯：字典是共享的，我必须保证每个递归分支中的字典保持不变
#否则走a的修改会应用到下一次走b上
#不用回溯的方法:传字典的副本new_count = count.copy()

    def add(fruits, amount, cart):
        if fruits == [] and amount == 0:
            print(cart)
        elif fruits and amount > 0:
            fruit = fruits[0]
            price = prices[fruit]
            for k in range(1, amount // price + 1):
                # Hint: The display function will help you add fruit to the cart.
                add(fruits[1:], amount - price * k, cart + display(fruit, k))
    add(fruits_to_buy, total_amount, '')

disc5

any:内置函数，判断可迭代对象里是否至少有一个为True
注意区分:一个元素的列表和单个元素的处理方法也不一样

#nonlocal只对嵌套函数有效
#注意只有列表之间才能互相拼接
def find_path(t, x):
    if label(t) == x:              # 找到目标
        return [x]
    for b in branches(t):          # 遍历子树
        subpath = find_path(b, x)
        if subpath:                 # 找到路径就拼接
            return [label(t)] + subpath
    return None                     # 没找到

隐式序列

• 惰性计算（Lazy computation）:直到程序需要它的值才去计算

迭代器

• 两个组件：检查下一个元素是否存在、到达序列末尾发出信号的机制
• 对任何容器都可以调用iter函数获取迭代器，并对iter使用next来获取下一个元素，若没有下一个元素，python处理方法是抛出异常

try:
    next iter_list
except StopIteration:
    print("no more element")

• 同一对象可以有多个互不影响的迭代器，但是直接赋值迭代器是会相互影响的
• 在迭代器上调用iter会返回其本身
• 可迭代对象：序列、容器、迭代器本身(如果对象具有返回迭代器的 iter 方法（method），则表示对象是可迭代的。)要在 for 循环中使用迭代器，迭代器还必须具有 iter 方法
• 内置迭代器：map\filter\zip\reversed. map应用之后，其对应操作会推迟到对返回的对象调用next的时候，对迭代器使用list函数后会一次性next完。

生成器

• 生成器是由一种特殊类型的函数 生成器函数 返回的迭代器。 生成器函数与常规函数不同之处在于，它们在其主体内不包含 return 语句，而是使用 yield 语句来返回一系列元素
• 生成器不使用对象的属性来跟踪它们在序列中的进度。 相反，它们控制生成器函数的执行，在每次调用生成器的 next 方法时执行，直到下一个 yield 语句被执行为止

# 可迭代接口
>>> class LettersWithYield:
        def __init__(self, start='a', end='e'):
            self.start = start
            self.end = end
        def __iter__(self):
            next_letter = self.start
            while next_letter < self.end:
                yield next_letter
                next_letter = chr(ord(next_letter) + 1)
# 迭代器接口
>>> class LetterIter:
        """依照 ASCII 码值顺序迭代字符的迭代器。"""
        def __init__(self, start='a', end='e'):
            self.next_letter = start
            self.end = end
        def __next__(self):
            if self.next_letter == self.end:
                raise StopIteration
            letter = self.next_letter
            self.next_letter = chr(ord(letter)+1)
            return letter

python 流

• 流（Streams）提供了另一种隐式表示连续数据的方法。 Stream 是一个惰性计算的链表（linked-list）。

>>> class Stream:
        """惰性计算的链表"""
        class empty:	#empty类：表示链表末尾
            def __repr__(self):
                return 'Stream.empty'
        empty = empty()
        
        def __init__(self, first, compute_rest=lambda: empty):
            assert callable(compute_rest), 'compute_rest 必须为可调用'
            self.first = first
            self._compute_rest = compute_rest
        @property	#标记为属性，可以使用 S.rest来访问
        def rest(self):
            """返回 Stream 的其他部分（缓存部分），如果需要计算，则计算"""
            if self._compute_rest is not None:
                self._rest = self._compute_rest()
                self._compute_rest = None	#下次调用就直接返回值而不再调用函数
            return self._rest
        def __repr__(self):	#魔术方法，无需显示调用
            return 'Stream({0}, <...>)'.format(repr(self.first))

#以上实现只能调用一次rest，实际可以结合递归方法实现无限序列

hw04

/：就算是整数也会得到浮点数

def deep_map(f, s):
    """Replace all non-list elements x with f(x) in the nested list s.
    """
    "*** YOUR CODE HERE ***"
    for i in range(len(s)):
        temp=s[i]
        if type(temp)!=list:
            s[i]=f(temp)
        else:
            deep_map(f,s[i])
            #原位改动


def berry_finder(t):
    """Returns True if t contains a node with the value 'berry' and 
    False otherwise.
    """
    "*** YOUR CODE HERE ***"
    if label(t)=='berry':
        return True
    elif is_tree(t):
        for b in branches(t):
            '''
            如果直接写成berry_finder(b),最外层这个没返回啊
            '''
            if berry_finder(b):
                return True
    return False

面向对象编程

• 当通过点表达式调用方法时，对象本身（在本例中绑定为 spock_account ）扮演双重角色。首先，它确定名称 withdraw 的含义; withdraw 不是环境中的名称，而是 Account 类的本地名称。其次，当调用 withdraw 方法时，它绑定到第一个参数 self
• 点表达式
  • <expression>.<name>等价于getattr(expression,name)
  • hasattr()判断是否有
• 方法和函数

#参数为self,num
>>> type(Account.deposit)
<class 'Function'>
#参数仅有num
>>> type(spock_account.deposit)
<class 'method'>

• Python 的约定规定，如果属性名称以下划线开头，则只能在类本身的方法中访问它，而不是用户访问。
• 命名约定：类名通常使用 CapWords 约定（也称为 CamelCase，因为名称中间的大写字母看起来像驼峰）编写。方法名称遵循使用下划线分隔的小写单词命名函数的标准约定。

类属性(类变量，静态变量)

• 属性赋值
  • 所有左侧包含点表达式的赋值语句都会影响该点表达式对象的属性。如果对象是实例，则赋值将设置实例属性。如果对象是类，则赋值将设置类属性。(对实例的属性赋值不会影响同类的其他实例)

继承

>>> class CheckingAccount(Account):
        """从账号取钱会扣出手续费的账号"""
        withdraw_charge = 1
        interest = 0.01
        def withdraw(self, amount):
            return Account.withdraw(self, amount + self.withdraw_charge)
            #调用父类方法

菱形继承问题:

lab05

>>> a, b = s, s[:]  
>>> a is s
True   # a 和 s 是同一个对象

>>> b == s
True   # b 的值和 s 相同

>>> b is s
False  # b 是拷贝，不是同一个对象

s.append()#改变了s后返回值是none


def sprout_leaves(t, leaves):
    """Sprout new leaves containing the labels in leaves at each leaf of
    the original tree t and return the resulting tree.
    """
    "*** YOUR CODE HERE ***"
    ret = copy_tree(t)
    helper(ret,leaves)
    return ret

def helper(node,leaves):
    if is_leaf(node):
        node[1:]=[tree(x)for x in leaves]
    else:
        for b in branches(node):
            helper(b,leaves)
#直接对node对象里面进行修改才改的到

局部赋值问题

• 变量 = 新对象 → 只是变量绑定变了（局部赋值，不会影响外部）
• 对象内部修改（如 list.append, list[:] = …, dict[…] = …）→ 会影响外部
• 避免局部赋值的方法：直接修改传入对象的内部结构，而不是给形参重新赋值

disc06

filter(function, iterable),过滤所有应用function的值为true的

def gen_fib():
    n, add = 0, 1
    while True:
        yield n
        n, add = n + add, n

next(filter(lambda n: n > 2024, gen_fib()))

def differences(t):
    """Yield the differences between adjacent values from iterator t."""
    "*** YOUR CODE HERE ***"
    begin=next(t)
    while True:
        try:
            temp=next(t)
            yield temp-begin
            begin=temp
        except(StopIteration):
            break

def partition_gen(n, m):
    """Yield the partitions of n using parts up to size m.
    """
    assert n > 0 and m > 0
    if n == m:
        yield str(m)
    if n - m > 0:
        "*** YOUR CODE HERE ***"
        for p in partition_gen(n-m,m):
            yield p +" + "+str(m)
    if m > 1:
        "*** YOUR CODE HERE ***"
        yield from partition_gen(n,m-1)

hw05

• yield：产出一个值，暂停执行，等下一次 next() 继续。
  yield from：把另一个可迭代对象的值逐个 yield 出来（简化写法）。
  还能处理 生成器返回值 和 方法转发，功能更强。

def hailstone(n):
    yield n
    while n != 1:
        if n % 2 == 0:
            n //= 2
        else:
            n = 3 * n + 1
        yield n
    while True:
        yield 1

#yield from 的用法
def stair_ways(n):
    """
    Yield all the ways to climb a set of n stairs taking
    1 or 2 steps at a time.

    >>> list(stair_ways(0))
    [[]]
    >>> s_w = stair_ways(4)
    >>> sorted([next(s_w) for _ in range(5)])
    [[1, 1, 1, 1], [1, 1, 2], [1, 2, 1], [2, 1, 1], [2, 2]]
    >>> list(s_w) # Ensure you're not yielding extra
    []
    """
    "*** YOUR CODE HERE ***"
    if  n==0:
        yield []
    elif n>0:
        temp_1=stair_ways(n-1)
        yield from([1]+way for way in temp_1)
        temp_2=stair_ways(n-2)
        yield from([2]+way for way in temp_2)

def yield_paths(t, value):
    if label(t) == value:
        yield [value]
    elif is_leaf(t):
        return#实际上这个判断是多余的，叶子节点直接for不了会退出
    for b in branches(t):
        for p in yield_paths(b,value):
            yield [label(t)]+p

实现类和对象

• 在本节中，我们将看到类和对象本身可以使用函数和字典来表示。通过以这种方式实现对象系统的目的是为了说明使用对象的隐喻并不需要特定的编程语言。即使在没有内置对象系统的编程语言中，程序也可以是面向对象的。

实例

#当当前实例没有name属性时在该类中寻找方法，并将其绑定到实例上
>>> def make_instance(cls):
        """Return a new object instance, which is a dispatch dictionary."""
        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

>>> def bind_method(value, instance):
        """Return a bound method if value is callable, or value otherwise."""
        if callable(value):
            def method(*args):
                return value(instance, *args)
            return method
        else:
            return value

类

>>> def make_class(attributes, base_class=None):
        """Return a new class, which is a dispatch dictionary."""
        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

>>> def init_instance(cls, *args):
    """Return a new object with type cls, initialized with args."""
    instance = make_instance(cls)
    init = cls['get']('__init__')
    if init:
        init(instance, *args)
    return instance

使用自定义的对象

>>> def make_account_class():
        """Return the Account class, which has deposit and withdraw methods."""
        interest = 0.02
        def __init__(self, account_holder):
            self['set']('holder', account_holder)
            self['set']('balance', 0)
        def deposit(self, amount):
            """Increase the account balance by amount and return the new balance."""
            new_balance = self['get']('balance') + amount
            self['set']('balance', new_balance)
            return self['get']('balance')
        def withdraw(self, amount):
            """Decrease the account balance by amount and return the new balance."""
            balance = self['get']('balance')
            if amount > balance:
                return 'Insufficient funds'
            self['set']('balance', balance - amount)
            return self['get']('balance')
        return make_class(locals())
        #最后对 locals 的调用返回一个以字符串为 key 的字典
        #其中包含了当前局部帧的名称 - 值的绑定。

>>> Account = make_account_class()
>>> kirk_account = Account['new']('kirk')
>>> kirk_account['get']('holder')
'kirk'
>>> kirk_account['get']('interest')
0.02
>>> kirk_account['get']('deposit')(20)
20
>>> kirk_account['get']('withdraw')(5)
15

#inheritance
>>> def make_checking_account_class():
        """Return the CheckingAccount class, which imposes a $1 withdrawal fee."""
        interest = 0.01
        withdraw_fee = 1
        def withdraw(self, amount):
            fee = self['get']('withdraw_fee')
            return Account['get']('withdraw')(self, amount + fee)
        return make_class(locals(), Account)

lab06

类内调用类内方法:加个self
邮件系统

class Email:
    """An email has the following instance attributes:

        msg (str): the contents of the message
        sender (Client): the client that sent the email
        recipient_name (str): the name of the recipient (another client)
    """
    def __init__(self, msg, sender, recipient_name):
        self.msg = msg
        self.sender = sender
        self.recipient_name = recipient_name

class Server:
    """Each Server has one instance attribute called clients that is a
    dictionary from client names to client objects.
    """
    def __init__(self):
        self.clients = {}

    def send(self, email):
        """Append the email to the inbox of the client it is addressed to.
            email is an instance of the Email class.
        """
        self.clients[email.recipient_name].inbox.append(email)

    def register_client(self, client):
        """Add a client to the clients mapping (which is a 
        dictionary from client names to client instances).
            client is an instance of the Client class.
        """
        self.clients[client.name] = client

class Client:
    """A client has a server, a name (str), and an inbox (list).
    """
    def __init__(self, server, name):
        self.inbox = []
        self.server = server
        self.name = name
        server.register_client(self)

    def compose(self, message, recipient_name):
        """Send an email with the given message to the recipient."""
        email = Email(message, self, recipient_name)
        self.server.send(email)

对象抽象

• 对象抽象的一个核心概念就是泛型函数，这种函数能够接受多种不同类型的值。我们将思考三种不同的用于实现泛型函数的技术：共享接口，类型派发和类型强制转换。

字符串转换

• Python 规定所有的对象都应该生成两个不同的字符串表示：一种是人类可读的文本，另一种是 Python 可解释的表示式。字符串的构造函数，即 str，返回一个人类可读的字符串。如果可能，repr 函数返回一个 Python 可解释的表达式，该表达式的求值结果与原对象相同(eval(repr(object))==object)
• 如repr这样能作用于各种甚至自定义的数据类型，实现方法是在每个类里面有不同定义的共享属性名称(_str_())

专用方法

• 某些特殊名称会在特殊情况下自动调用
• eg.1 boolean
  • Account.__bool__ = lambda self: self.balance != 0
  • 可以使用bool(account_name)来调用该方法
• eg.other:__len__ __getitem__

>>> class Adder(object):
        def __init__(self, n):
            self.n = n
        #call,实现类似高阶函数的可调用的类对象
        def __call__(self, k):
            return self.n + k
>>> add_three_obj = Adder(3)
>>> add_three_obj(4)
7

多重表示

• 如复数有几乎相同的两种表示方式(直角坐标和极坐标)，有时需要支持同一个对象的两种表示

>>> class Number:
        def __add__(self, other):
            return self.add(other)
        def __mul__(self, other):
            return self.mul(other)
>>> class Complex(Number):
        def add(self, other):
            return ComplexRI(self.real + other.real, self.imag + other.imag)
        def mul(self, other):
            magnitude = self.magnitude * other.magnitude
            return ComplexMA(magnitude, self.angle + other.angle)
>>> from math import atan2
>>> class ComplexRI(Complex):
        def __init__(self, real, imag):
            self.real = real
            self.imag = imag
        @property
        def magnitude(self):
            return (self.real ** 2 + self.imag ** 2) ** 0.5
        @property
        def angle(self):
            return atan2(self.imag, self.real)
        def __repr__(self):
            return 'ComplexRI({0:g}, {1:g})'.format(self.real, self.imag)

>>> from math import sin, cos, pi
>>> class ComplexMA(Complex):
        def __init__(self, magnitude, angle):
            self.magnitude = magnitude
            self.angle = angle
            @property
        def real(self):
            return self.magnitude * cos(self.angle)
        @property
        def imag(self):
            return self.magnitude * sin(self.angle)
        def __repr__(self):
            return 'ComplexMA({0:g}, {1:g} * pi)'.format(self.magnitude, self.angle/pi)

泛型函数

• 类型派发:根据函数或方法的参数类型进行选择(isinstance,type_tag)

>>> class Number:
        def __add__(self, other):
            if self.type_tag == other.type_tag:
                return self.add(other)
            #若两者类型不同则在adders字典中找是否有相应的跨类型实现并应用
            elif (self.type_tag, other.type_tag) in self.adders:
                return self.cross_apply(other, self.adders)
        def __mul__(self, other):
            if self.type_tag == other.type_tag:
                return self.mul(other)
            elif (self.type_tag, other.type_tag) in self.multipliers:
                return self.cross_apply(other, self.multipliers)
        def cross_apply(self, other, cross_fns):
            cross_fn = cross_fns[(self.type_tag, other.type_tag)]
            return cross_fn(self, other)
        adders = {("com", "rat"): add_complex_and_rational,
                    ("rat", "com"): add_rational_and_complex}
        multipliers = {("com", "rat"): mul_complex_and_rational,
                        ("rat", "com"): mul_rational_and_complex}

• 强制转换(自己写，如实数转换成虚部为零的复数)

>>> class Number:
        def __add__(self, other):
            x, y = self.coerce(other)
            return x.add(y)
        def __mul__(self, other):
            x, y = self.coerce(other)
            return x.mul(y)
        def coerce(self, other):
            if self.type_tag == other.type_tag:
                return self, other
            elif (self.type_tag, other.type_tag) in self.coercions:
                return (self.coerce_to(other.type_tag), other)
            elif (other.type_tag, self.type_tag) in self.coercions:
                return (self, other.coerce_to(self.type_tag))
        def coerce_to(self, other_tag):
            coercion_fn = self.coercions[(self.type_tag, other_tag)]
            return coercion_fn(self)
        coercions = {('rat', 'com'): rational_to_complex}

disc 07

super().__init()

def draw(hand, positions):
    """Remove and return the items at positions from hand.
        tip1:the pop would change the index,
        so you need to ensure a way that do no change
    """
    return list(reversed( [hand.pop(i) for i in reversed(sorted(positions))] ))


class CapsLock:
    """表示键盘的 CapsLock 键。"""
    def __init__(self):
        self.pressed = 0

    def press(self):
        """按下 CapsLock 键，切换状态。"""
        self.pressed += 1


class Button:
    """一个键盘上的按键。
    """
    # 类属性，全局唯一的 CapsLock
    caps_lock = CapsLock()

    def __init__(self, letter, output=None):
        assert letter in LOWERCASE_LETTERS
        self.letter = letter
        self.output = output
        self.pressed = 0
        self.caps_lock = Button.caps_lock

    def press(self):
        """按下当前按键。输出大写或小写字母，并返回自己。"""
        self.pressed += 1
        # 临时决定输出字符，不改变 self.letter
        to_output = self.letter.upper() if self.caps_lock.pressed % 2 == 1 else self.letter
        if self.output is not None:
            self.output(to_output)
        return self


class Keyboard:
    """一个由 Button 组成的键盘。
    """
    def __init__(self):
        self.typed = []
        # Button 的 output 指向 self.typed.append，保证记录按键
        self.keys = {chr(i+97): Button(chr(i+97), self.typed.append) for i in range(26)}

    def type(self, word):
        """按下 word 中的每个字母。"""
        assert all([w in LOWERCASE_LETTERS for w in word]), 'word must be all lowercase'
        for l in word:
            self.typed.append(self.keys[l].press())

hw06

def store_digits(n):
    """Stores the digits of a positive number n in a linked list.
    """
    "*** YOUR CODE HERE ***"
    ret=None
    store=[]
    length=0
    while n>0:
        store.append(n%10)
        n=n//10
        length+=1
    for i in range(length-1,-1,-1):
        if ret==None:
            ret=Link(store[i])
        else:
            node=ret
            while node.rest!=Link.empty:
                node=node.rest
            node.rest=Link(store[i])
    return ret
'''区分:
node=ret.rest
node=new
这就丢失了,没连接上
cur.rest=new
cur=cur.rest
'''

#python风格的嵌套链表
def deep_map_mut(func, s):
    """Mutates a deep link s by replacing each item found with the
    result of calling func on the item. Does NOT create new Links (so
    no use of Link's constructor).
    """
    "*** YOUR CODE HERE ***"
    temp=s
    while temp!=Link.empty:
        if not isinstance(temp.first,Link):
            temp.first=func(temp.first)
        else:
            deep_map_mut(func,temp.first)
        temp=temp.rest

效率

• 这种树递归是非常冗余低效的
• 空间效率:要了解函数的空间需求，我们通常必须指定在计算的环境模型中如何使用、保留和回收内存。在计算表达式时，解释器会保存所有活动的环境，以及这些环境引用的所有值和帧。我们称一个环境是活动的，如果它为正在计算的某个表达式提供了评估上下文。每当为其创建第一个帧的函数调用最终返回时，环境将变为非活动状态。

记忆化(memoization)

#函数本身也是对象，可以挂载属性
>>> def count_frames(f):
        def counted(n):
            counted.open_count += 1
            counted.max_count = max(counted.max_count, counted.open_count)
            result = f(n)
            counted.open_count -= 1
            return result
        counted.open_count = 0
        counted.max_count = 0
        return counted
>>> fib = count_frames(fib)
>>> fib(19)
4181
>>> fib.open_count
0
>>> fib.max_count
19
>>> fib(24)
46368
>>> fib.max_count
24

• 记忆化自然的可以使用高阶函数的方式进行记录(使用字典作为缓存的数据结构要求被记忆化的函数的参数是不可变的。)

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

增长类别

lab07

class Link:
    """A linked list.
    """
    empty = ()

    def __init__(self, first, rest=empty):
        assert rest is Link.empty or isinstance(rest, Link)
        self.first = first
        self.rest = rest

    def __repr__(self):
        if self.rest is not Link.empty:
            rest_repr = ', ' + repr(self.rest)
        else:
            rest_repr = ''
        return 'Link(' + repr(self.first) + rest_repr + ')'

    def __str__(self):
        string = '<'
        while self.rest is not Link.empty:
            string += str(self.first) + ' '
            self = self.rest
        return string + str(self.first) + '>'

disc08

def display(s, k=10):
    """Print the first k digits of infinite linked list s as a decimal.

    """
    assert s.first == 0, f'{s.first} is not 0'
    digits = f'{s.first}.'
    s = s.rest
    for _ in range(k):
        assert s.first >= 0 and s.first < 10, f'{s.first} is not a digit'
        digits += str(s.first)
        s = s.rest
    print(digits + '...')
def divide(n, d):
    """Return a linked list with a cycle containing the digits of n/d.

    >>> display(divide(5, 6))
    0.8333333333...
    >>> display(divide(2, 7))
    0.2857142857...
    >>> display(divide(1, 2500))
    0.0004000000...
    >>> display(divide(3, 11))
    0.2727272727...
    >>> display(divide(3, 99))
    0.0303030303...
    >>> display(divide(2, 31), 50)
    0.06451612903225806451612903225806451612903225806451...
    """
    assert n > 0 and n < d
    result = Link(0)  # The zero before the decimal point
    "*** YOUR CODE HERE ***"
    cur=result
    stored={}
    while True:
        if n in stored:
            cur.rest=stored[n]#从循环开始的地方变，所以用字典存起来
            break
        temp=n*10
        digit=temp//d
        cur.rest=Link(digit)
        cur=cur.rest
        stored[n]=cur
        n=temp%d
    return result

函数式编程

表达式

• scheme 程序主要是由各种表达式构成的，这些表达式可以是函数调用或一些特殊的结构。
  (quotient 10 2)调用函数
(+ (* 3 5) (- 10 6))前缀操作符

(define (<name> <formal parameters>) <body>)定义一个函数(过程)
  (lambda (<formal-parameters>) <body>)

复合类型

• pair 是内置的数据结构。出于历史原因，pair 是通过内置函数 cons 创建的，而元素则可以通过 car 和 cdr 进行访问
• Scheme 语言中也内置了递归列表，它们使用 pair 来构建。特殊的值 nil 或 '() 表示空列表。递归列表的值是通过将其元素放在括号内，用空格分隔开来表示的(define one-through-four (list 1 2 3 4))

(define (length items)
  (if (null? items)
      0
      (+ 1 (length (cdr items)))))
(define (getitem items n)
  (if (= n 0)
      (car items)
      (getitem (cdr items) (- n 1))))
(define squares (list 1 4 9 16 25))

(length squares)

(getitem squares 3)


(define (repeat k fn)
  (if (> k 0)
      (begin;;begin表示顺序执行多个表达式并返回最后一个的值
        (fn)
        (repeat (- k 1) fn))
      nil))

• 为了操作符号，我们需要语言中的一个新元素：引用数据对象的能力。假设我们想构建列表 (a b)。我们不能通过 (list a b) 来实现这一目标，因为这个表达式构建的是 a 和 b 的值，而不是它们自身的符号。在 Scheme 中，我们通过在它们前面加上一个单引号来引用符号 a 和 b 而不是它们的值

lab08

#max+lambda函数
def prune_small(t, n):
    """Prune the tree mutatively, keeping only the n branches
    of each node with the smallest labels.
    """
    while len(t.branches)>n:
        largest = max(t.branches, key=lambda x:x.label)
        t.branches.remove(largest)
    for b in t.branches:
        if not b.is_leaf():
            prune_small(b,n)

#删除节点
def delete(t, x):
    """Remove all nodes labeled x below the root within Tree t. When a non-leaf
    node is deleted, the deleted node's children become children of its parent.

    The root node will never be removed.
    """
    new_branches = []
    for b in t.branches:
        if b.label == x and not b.is_leaf():
            delete(b,x)
            for sub in b.branches:
                new_branches.append(sub)
        elif b.label!=x:
            delete(b,x)
            new_branches.append(b)
    t.branches = new_branches

lab09

• scheme中的if:必须要真假都写上

;;cond的用法，本身就是一个表达式所以不需要再加括号
(define (over-or-under num1 num2)
  (cond ((> num1 num2) 1)
    ((< num1 num2) -1)
    ((= num1 num2) 0))
)

(define (make-adder num) 
  (lambda (inc) (+ inc num) )
)

(define (composed f g) 
  (lambda (x) (f (g x)))
   )

(define (repeat f n)
  (if (= n 1) f (composed f (repeat f (- n 1))))
  
)

(define (max a b)
  (if (> a b)
      a
      b))

(define (min a b)
  (if (> a b)
      b
      a))

(define (gcd a b)
  (let ((ma (max a b)))
    (let ((mi (min a b)))
      (let ((ret (remainder ma mi)))
        (if (= ret 0)
            mi
            (gcd mi ret))))))
;;define不能用在函数内部

• A Scheme symbol is equivalent to a Python name. A symbol evaluates to the value bound to that symbol in the current environment. (They are called symbols rather than names because they include + and other arithmetic symbols.)
• Just like in Python, to evaluate a call expression:
  • Evaluate the operator. It should evaluate to a procedure.
  • Evaluate the operands, left to right.
  • Apply the procedure to the evaluated operands.

(define <symbol> <expression>)分配值
(if <predicate> <if-true> <if-false>)

函数式编程思想	解释
一切皆函数	函数可以当数据用
无副作用	函数不修改外部状态
不可变性	数据一旦创建不可更改
递归代替循环	不依赖变量状态
函数组合	把小函数组合成复杂逻辑

hw07

(define (square n) (* n n))

(define (pow base exp) 
  (if (= exp 0) 1 
  (if (= exp 1) base 
  (if (even? exp) (square (pow base (/ exp 2))) 
  (* base (square (pow base (/ (- exp 1) 2)))))))
)

(define (repeatedly-cube n x)
  (if (zero? n)
      x
      (let ((y (repeatedly-cube (- n 1) x)))
        (* y y y))))

(define (cddr s) (cdr (cdr s)))

(define (cadr s) (car (cdr s)))

(define (caddr s) (car (cdr (cdr s))))

disc 09

三种嵌套列表的方式

    (define with-list
        (list
            (list 'a 'b) 'c 'd (list 'e)
        )
    )
    ; (draw with-list)  ; Uncomment this line to draw with-list

        (define with-quote
        '(
            (a b) c d (e)
        )

    )
    ; (draw with-quote)  ; Uncomment this line to draw with-quote
        (define with-cons
        (cons
            first (cons 'c (cons 'd (cons (cons 'e nil) nil)))
        )
    )
    ; (draw with-cons)  ; Uncomment this line to draw with-cons

;;; Return a list of pairs containing the elements of s.
    ;;;
    ;;; scm> (pair-up '(3 4 5 6 7 8))
    ;;; ((3 4) (5 6) (7 8))
    ;;; scm> (pair-up '(3 4 5 6 7 8 9))
    ;;; ((3 4) (5 6) (7 8 9))
    (define (pair-up s)
        (if (<= (length s) 3)
           (list s) (cons (list (car s) (car (cdr s))) (pair-up (cdr (cdr s))))
        ))

    (expect (pair-up '(3 4 5 6 7 8)) ((3 4) (5 6) (7 8)) )
    (expect (pair-up '(3 4 5 6 7 8 9)) ((3 4) (5 6) (7 8 9)) )

异常

try:
    print(1 / 0)
except Exception as exc:
    raise RuntimeError("Something bad happened") from exc
'''
Traceback (most recent call last):
  File "<stdin>", line 2, in <module>
    print(1 / 0)
          ~~^~~
ZeroDivisionError: division by zero

The above exception was the direct cause of the following exception:

Traceback (most recent call last):
  File "<stdin>", line 4, in <module>
    raise RuntimeError("Something bad happened") from exc
RuntimeError: Something bad happened
'''

• 当抛出异常时，当前代码块中的后续语句将不会执行。除非异常被处理（如下所述），否则解释器将直接返回到交互式的读取 - 求值 - 打印（read-eval-print-loop）循环，或者在 Python 是通过文件参数启动时会完全终止。此外，解释器将打印一个堆栈回溯（stack backtrace），它是一个结构化的文本块，描述了在异常被抛出的执行分支中活动的嵌套函数调用集合。

异常对象

>>> class IterImproveError(Exception):
        def __init__(self, last_guess):
            self.last_guess = last_guess
>>> def improve(update, done, guess=1, max_updates=1000):
        k = 0
        try:
            while not done(guess) and k < max_updates:
                guess = update(guess)
                k = k + 1
            return guess
        except ValueError:
            raise IterImproveError(guess)#抛出异常
>>> def find_zero(f, guess=1):
        def done(x):
            return f(x) == 0
        try:
            return improve(newton_update(f), done, guess)
        except IterImproveError as e:
            return e.last_guess#这里才是处理异常

组合语言的解释器

hw08

(define (no-repeats s) 
    (cond ((null? s) '())
    (else (cons (car s) 
                (no-repeats 
                    (my-filter 
                        ((lambda (temp) (lambda (q) (not (equal? temp q)))) (car s))
                        (cdr s)
                    )
                )
          ))
    )
)

lab10

#计算
def floor_div(args):
    """
    """
    "*** YOUR CODE HERE ***"
    first= args.first if isinstance(args.first,int) else calc_eval(args.first)
    if args.rest==nil:
        return first
    else:
        second=calc_eval(args.rest.first) if isinstance(args.rest.first,Pair) else args.rest.first
        return floor_div(Pair(first//second,args.rest.rest))

def calc_eval(exp):
    """
    """
    if isinstance(exp, Pair):
        operator = exp.first # UPDATE THIS FOR Q2, e.g (+ 1 2), + is the operator
        operands = exp.rest # UPDATE THIS FOR Q2, e.g (+ 1 2), 1 and 2 are operands
        if operator == 'and': # and expressions
            return eval_and(operands)
        elif operator == 'define': # define expressions
            return eval_define(operands)
        else: # Call expressions
            return calc_apply(OPERATORS[operator],operands) if not operator in bindings else calc_apply(bindings[operator],operands) # UPDATE THIS FOR Q2, what is type(operator)?
    elif exp in OPERATORS:   # Looking up procedures
        return OPERATORS[exp]
    elif isinstance(exp, int) or isinstance(exp, bool):   # Numbers and booleans
        return exp
    elif exp in bindings: # CHANGE THIS CONDITION FOR Q4 where are variables stored?
        return bindings[exp] # UPDATE THIS FOR Q4, how do you access a variable?

def eval_and(expressions):
    """
    """
    "*** YOUR CODE HERE ***"
    if expressions==nil:
        return scheme_t
    elif expressions.first is scheme_f:
        return scheme_f
    elif expressions.rest ==nil:
        return calc_eval(expressions.first) if isinstance(expressions.first,Pair) else expressions.first
    else:
        second=calc_eval(expressions.rest.first) if isinstance(expressions.rest.first,Pair) else expressions.rest.first
        return eval_and(Pair(second,expressions.rest.rest))

抽象语言的解释器

• 计算器语言不支持任何方式的抽象。因此，它不是一种特别强大或通用的编程语言。现在，我们的任务是定义一种通用编程语言，通过将名称绑定到数值和定义新操作来支持抽象。

结构

• 解析器解析得到表达式，对表达式调用求值函数。
• 求值（Evaluation）。Scheme 一次计算一个表达式。scheme_read 返回的每个表达式都传递给 scheme_eval 函数，该函数计算当前环境 env 中的表达式 expr。
• 函数应用(procedure application)。两种参数
  • primitiveprocedure:python实现，直接绑定
  • lambdaprocedure:scheme实现,调用就是对body 部分求值，为了求值会在环境中新建一个帧
• 求值流程的本质就是求值函数和应用函数的互相递归

环境

• 就是各个frame(有个绑定以及parent,global没有prarent)
• 绑定不能直接访问，而是通过两种 Frame 方法：lookup 和 define。第一个方法:符号与当前帧的绑定相匹配。如果找到它，则返回它绑定到的值。如果没有找到，则继续在父帧中查找。另一方面，define 方法用来将符号绑定到当前帧中的值。

disc10

def print_evals(expr):
    #实际上也是一种evaluate的过程
        """Print the expressions that are evaluated while evaluating expr.

        expr: a Scheme expression containing only (, ), +, *, and numbers.
        """
        if not isinstance(expr, Pair):
            if expr!=nil:
                print(expr)
        else:
            print(expr)
            expr.map(print_evals)

scheme

• User-defined procedures open a new frame; builtins do not
• Builtins simply execute a predefined Python function; user-defined procedures must evaluate additional expressions in the body
• 注意当前帧找不到的到父帧去找
• scheme中的(+)结果为0
• para.append()返回值是none

#why:scheme中nil也是一个有效参数值
def get_args(args):
    p = []
    while args is not nil:
        p.append(args.first)   # ✅ 不要判断真值
        args = args.rest
    return p

• 求值的关键pair(2,nil)<=>(2),解决办法就是map

#递归思路:两个就直接用，多个操作数先map全部求值再递归
def scheme_eval(expr, env, _=None): # Optional third argument is ignored
    """Evaluate Scheme expression EXPR in Frame ENV.
    """
    # Evaluate atoms
    if scheme_symbolp(expr):
        return env.lookup(expr)
    elif self_evaluating(expr):
        return expr

    # All non-atomic expressions are lists (combinations)
    if not scheme_listp(expr):
        raise SchemeError('malformed list: {0}'.format(repl_str(expr)))
    first, rest = expr.first, expr.rest
    if scheme_symbolp(first) and first in scheme_forms.SPECIAL_FORMS:
        return scheme_forms.SPECIAL_FORMS[first](rest, env)
    else:
        # BEGIN PROBLEM 3
        "*** YOUR CODE HERE ***"
        opera=scheme_eval(first,env)
        return scheme_apply(opera,rest.map(lambda x:scheme_eval(x,env)),env)
        # END PROBLEM 3

• begin

#为什么这么写，在求值过后，还有pair就是直接quote的
#(理解输入在该条件的结构)
def get_last(expressions):
    if not isinstance(expressions,Pair):
        return expressions
    if expressions.rest==nil:
        return expressions.first
    if isinstance(expressions.rest,Pair):
        return get_last(expressions.rest)

Pair(3,nil)(3)
Pair(2,Pair(3,nil))(2,3)
Pair(2,3)(2.3);;不算列表

• lambda函数

child_frame=procedure.env.make_child_frame(procedure.formals,args)
return eval_all(procedure.body,child_frame)
#对于嵌套的lambda函数，相当于begin求所有之后返回最后一个

• 嵌套lambda函数示意

(define outer 
  (lambda (x y)
    (define inner 
      (lambda (z x)
        (+ x (* y 2) (* z 3))))
    (inner x 10)))
;;outer有两条表达式(一个inner一个调用inner)

• 一般的function就可以看作其去掉函数名的lambda绑定在这上面

• lexical scope(词法作用域):the parent of the new call frame is the environment in which the procedure was defined.(主流，决定于其定义的上下文)

• dynamic scope(动态作用域):the parent of the new call frame is the environment in which the call expression was evaluated.

• do_and_form

#attention :when judging by if statement,the first is already evaled
def do_and_form(expressions, env):
    """Evaluate a (short-circuited) and form.
    """
    # BEGIN PROBLEM 12
    "*** YOUR CODE HERE ***"
    
    if expressions==nil:
        return True 
    if not isinstance(expressions,Pair):
        return expressions
    if expressions.rest==nil:
        return scheme_eval(expressions.first,env)
    if is_scheme_false(scheme_eval(expressions.first,env)):
        return False
    else:
        return do_and_form(expressions.rest,env)

• 判断是否多个语句:len(pair)==1
• scheme函数嵌套

(define (enumerate s)
  ; BEGIN PROBLEM 15
  (define (helper l idx)
  (if (null? l) nil (cons (list idx (car l)) (helper (cdr l) (+ idx 1)))))
  (helper s 0)
  )

program as data、macro(宏)

• scheme expression is just the scheme list(这使得编写产生程序的程序尤其直接)
• quosiquotation:部分引用
  
• 
  • 宏实际上相当有用(新代码生成，控制抽象)

hw09

;(car formals)=>`a 则,(car formals)出来的是a,没有对其求值
(define (curry-cook formals body) 
    (if (null? (cdr formals)) `(lambda (,(car formals)) ,body) `(lambda (,(car formals)) ,(curry-cook (cdr formals) body))
    )
)


(define (switch-to-cond switch-expr)
  (cons `cond
        (map (lambda (option)
               (cons `(equal? ,(car (cdr switch-expr)) ,(car option)) (cdr option)))
             (car (cdr (cdr switch-expr))))));取出map遍历的目标

SQL

• structured query language(SQL):
  • declarative programming language(声明式)
  • 仅仅只需要描述你期望的结果,解释器会自动翻译过来
  • 区别于python 等命令式编程(imperative)(描述执行的过程)

• project (从一个表生成另一个表)

• .mode column设置模式为列
• select * from ints查看整个列表(union生成的列表无法保证顺序，这取决于解释器的实现)

disc 11

;宏的一个特点:在调用宏的帧当中求值，可以直接交换x,y=y,x这种
(define-macro (assign sym1 sym2 expr1 expr2)
  `(begin
     (define ,sym1 ,expr1)
     (define ,sym2 ,(eval expr2))))

Tables

hw10

• 降序:DESC记号
• sql 不允许嵌套创建table
• 最好建立表的时候对相同名的列进行重命名

CREATE TABLE by_parent_height AS
SELECT p.child
FROM dogs AS d
JOIN parents AS p
  ON p.parent = d.name
ORDER BY d.height DESC;

-- 条件过滤
CREATE TABLE size_of_dogs AS
  SELECT d.name,s.size from dogs as d,sizes as s where d.height>s.min and d.height<=s.max;

-- 字符串
CREATE TABLE sentences AS
  SELECT "The two siblings, "||si.child1||" and "||si.child2||", have the same size: "||s.size 
    from siblings as si,size_of_dogs as s,size_of_dogs as s1 
      where s1.size=s.size and si.child1=s1.name and si.child2=s.name;


-- 分组求均值
create table avg as
  select d.fur,AVG(height) from dogs as d group by d.fur;


CREATE TABLE low_variance AS
SELECT 
    fur,
    MAX(height) - MIN(height) AS height_range
FROM dogs
GROUP BY fur
HAVING MIN(height) >= 0.7 * AVG(height) --having是分组后过滤
										--而where是分组前
   AND MAX(height) <= 1.3 * AVG(height);

aggregation(聚合)

• 通过group by 进行聚合
  
  

database

• DDL(数据库定义语言):create\drop
  
  • drop table 是直接把表给删了(这和清空表不一样)
• DML(修改表格数据)
  • insert
  • udpate
  • delete:delete没指定，就是全删，但是此时的列表还是存在的

designing functions

--remember to use and
-- Pizza places that are open for late-night-snack time and when they close
  SELECT p.name || " closes at " || p.close AS status
  FROM pizzas as p,meals as m
  WHERE m.meal='snack' and p.close>=m.time;
--alias can't be used directly in where clause
-- Two meals at the same place
SELECT f.meal AS first, s.meal AS second, p.name
FROM meals AS f, meals AS s, pizzas AS p
WHERE p.open <= f.time
  AND p.close >= s.time
  AND s.time - f.time > 6;