Week6-Lecture13-15

2026-09-162026-09-16

Lecture 13 Data Abstraction¶

Reading 2.2 Data Abstraction¶

Compound Date的使用能让我们提高程序的模块化程度。
The general technique of isolating the parts of a program that deal with how data are represented from the parts that deal with how data are manipulated is a powerful design methodology called data abstraction.
将数据的表示和计算方法分离开，这种方法被称之为数据抽象。

2.2.1 Example: Rational Numbers¶

Python
def add_rationals(x, y):
    nx, dx = numer(x), denom(x)
    ny, dy = numer(x), denom(y)
    return rational(nx * dy + ny * dx, dx *dy)
# ...其它分数计算性质
# 我们在还没有定义rational的时候就大胆地编写它的计算了

2.2.2 Pairs¶

列表中元素的获取可以通过

a, b = [1, 2]
operator.getitem
some_list[i]

Python
# 表示有理数
def rational(n, d):
    return [n, d]

def numer(x):
    return x[0]

def denom(x):
    return x[1]

# 约分
from fractions import gcd
def rational(n, d):
    g = gcd(n, d)
    return [n//g, d//g]

2.2.3 Abstraction Barriers¶

当程序的一部分本可以使用更高层次的函数，却使用了较低层次的函数时，就会发生 barrier violation
抽象屏障使程序更易于维护和修改。

2.2.4 The Properties of Data¶

一般来说，我们可以使用selectors和constructors以及一些behavior来表达数据抽象。

Python
def pari(x, y):
    def get(index):
        if index == 0:
            return x
        elif index == 1:
            return y
    return get

def select(p, i):
    return p(i)

# Functions are sufficient to represent compound data.

Lab04 Tree Recursion, Data Abstraction¶

Python
# 1. Divide
def divide(quotients: list[int], divisors: list[int]) -> dict[int, list[int]]:
    return {i: [j for j in divisors if j % i == 0] for i in quotients}

# 2. buy
def buy(fruits_to_buy: list[str], prices: dict[str, int], total_amount: int) -> None:
    def add(fruits: list[str], amount: int, cart: str) -> None:
        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, '')


def display(fruit: str, count: int) -> str:
    assert count >= 1 and fruit[-1] == 's'
    if count == 1:
        fruit = fruit[:-1]  # get rid of the plural s
    return '[' + str(count) + ' ' + fruit + ']'

# 4. Distance
def distance(city_a, city_b):
    return sqrt((get_lat(city_a) - get_lat(city_b)) ** 2 + (get_lon(city_a) - get_lon(city_b)) ** 2)

# 5. Closer City
def closer_city(lat, lon, city_a, city_b):
    city_c = make_city('c', lat, lon)
    closest_city = city_a
    if distance(city_a, city_c) > distance(city_b, city_c):
        closest_city = city_b
    return get_name(closest_city)

Lecture 14 Trees¶

Disc 05 Trees¶

Python
from tree import *

def has_path(t, p):
    if p == [label(t)]:  # when len(p) is 1
        return True
    elif label(t) != p[0]:
        return False
    else:
        return any([has_path(b, p[1:]) for b in branches(t)])

def find_path(t, x):
    if label(t) == x:
        return [x]
    for b in branches(t):
        path = find_path(b, x)
        if path:
            return [label(t)] + path
    return None

def only_paths(t, n):
    if label(t) == n and is_leaf(t):
        return t
    new_branches = [only_paths(b, n-label(t)) for b in branches(t)]
    if any(new_branches):
        return tree(label(t), [b for b in new_branches if b is not None])

Lecture 15 Mutability¶

Reading 2.4 Mutable Data¶

创建模块化程序的一种强大技术是引入可变数据。
In this way , a single data object can represent something that evolves independently of the rest of the program.
Adding state to data is a central ingredient

2.4.1 The Object Metaphor¶

Objects combine data values with behavior.
对象表示信息，同时也有与他们所表示的事物一样的行为。

对象的属性：<expression>.<name>
对象的方法：methods are functions that compute their results from both their arguments and their object.

数字、字符串、列表、range都是对象，都可以调用属性和方法。

Python
>>> '1234'.isnumeric()
True
>>> 'rOBERT dE nIRO'.swapcase()
'Robert De Niro'
>>> 'eyes'.upper().endwith('YES')
True

Python中的所有值都是对象，都可以调用属性和方法。

2.4.2 Sequence Objects¶

可变对象用于表示随时间变化的值。
An object may have changing properties due to mutating operations.

Python
# Example
>>> chinese = ['coin', 'string', 'myriad']
>>> suits = chinese
>>> suits.pop()
'myriad'
>>> suits.remove('string')
>>> suits.append('cup')
>>> suits.extend(['sword', 'club'])
>>> suits[2] = 'spade'
>>> suits
['heart', 'diamond', 'spade', 'club']
>>> chinese
['heart', 'diamond', 'spade', 'club'] # 绑定的是同一个对象

>>> nest = list(suits) # 使用list复制列表，一个列表的变更不会改变另一个列表
>>> nest[0] = suits
>>> suits.inser(2, 'Joker)
>>> nest
[['heart', 'diamond', 'Joker', 'spade', 'club'], 'diamond', 'spade', 'club'] # 如果有共享结构，还是会改变

# 求值相等与是同一个东西是两个概念
>>> suits is nest[0]
True
>>> suits is ['heart', 'diamond', 'spade', 'club']
False
>>> suits == ['heart', 'diamond', 'spade', 'club']
True

Tuples. 元组是一种不可变对象。

Python
>>> 1, 2 + 3
(1, 5)
>>> ("the", 1, ("and", "only"))
('the', 1, ('and', 'only'))
>>> type( (10, 20) )
<class 'tuple'>

>>> ()    # 0 elements
()
>>> (10,) # 1 element
(10,)

>>> code = ("up", "up", "down", "down") + ("left", "right") * 2
>>> len(code)
8
>>> code[3]
'down'
>>> code.count("down")
2
>>> code.index("left")
4

2.4.3 Dictionaries¶

Dictionaries are Python's built-in data type for storing and manipulating correspondence relationships.
字典用于存储和操作对应关系。字典的键和值都是对象。字典的目的是提供一种抽象：由描述性键索引的值

字典的键不能是可变值，也不能包含可变值
对于给定的键，最多只能有一个值

2.4.4 Local State¶

Lists and dictionaries have local state: they are changing values that have some particular contents at any point in the execution of a program.

Python
>>> def make_withdraw(balance):
        """Return a withdraw function that draws down balance with each call."""
        def withdraw(amount):
            nonlocal balance                 # Declare the name "balance" nonlocal
            if amount > balance:
                return 'Insufficient funds'
            balance = balance - amount       # Re-bind the existing balance name
            return balance
        return withdraw

# Tracing the effect of evaluating withdraw illustrates the effect of a nonlocal statement in Python: a name outside of the first local frame can be changed by an assignment statement.

Only after a nonlocal statement can a function change the binding of names in these frames.

assignment statements already had a dual role: they either created new bindings or re-bound existing names

这种非局部赋值模式是具有高阶函数和词法作用域的编程语言的普遍特征。在解释器中，执行函数体之前预先计算有关函数体的事实是相当常见的。Python的预处理限制了局部变量可以出现的帧。

2.4.5 The Benefits of Non-local Assignment¶

非局部赋值是我们把程序视为独立自主对象的重要一步，这些对象彼此交互，但又各自管理自己的内部状态。
非局部赋值允许我们维护某种局部状态。

2.4.6 The Cost of Non-Local Assignment¶

我们需要思考两个名字是值相同，绑定的instance不同，还是本身就是相同的东西。
非局部赋值引入了复杂性，但仍是创建模块化程序的强大工具。利用具有局部状态的函数，我们能够实现可变数据类型。

2.4.7 Implementing Lists and Dictionaries¶

Python
>>> def mutable_link():
        """Return a functional implementation of a mutable linked list."""
        contents = empty
        def dispatch(message, value=None):
            nonlocal contents
            if message == 'len':
                return len_link(contents)
            elif message == 'getitem':
                return getitem_link(contents, value)
            elif message == 'push_first':
                contents = link(value, contents)
            elif message == 'pop_first':
                f = first(contents)
                contents = rest(contents)
                return f
            elif message == 'str':
                return join_link(contents, ", ")
        return dispatch

>>> def to_mutable_link(source):
        """Return a functional list with the same contents as source."""
        s = mutable_link()
        for element in reversed(source):
            s('push_first', element)
        return s

>>> s = to_mutable_link(suits)
>>> type(s)
<class 'function'>
>>> print(s('str'))
heart, diamond, spade, club

>>> s('pop_first')
'heart'
>>> print(s('str'))
diamond, spade, club

Python
>>> def dictionary():
        """Return a functional implementation of a dictionary."""
        records = []
        def getitem(key):
            matches = [r for r in records if r[0] == key]
            if len(matches) == 1:
                key, value = matches[0]
                return value
        def setitem(key, value):
            nonlocal records
            non_matches = [r for r in records if r[0] != key]
            records = non_matches + [[key, value]]
        def dispatch(message, key=None, value=None):
            if message == 'getitem':
                return getitem(key)
            elif message == 'setitem':
                setitem(key, value)
        return dispatch
        
>>> d = dictionary()
>>> d('setitem', 3, 9)
>>> d('setitem', 4, 16)
>>> d('getitem', 3)
9
>>> d('getitem', 4)
16

2.4.8 Dispatch Dictionaries¶

分发函数是实现抽象数据消息传递接口的通用方法。

2.4.9 Propagating Constraints 传播约束¶

Expressing programs as constraints is a type of declarative programming, in which a programmer declares the structure of a problem to be solved, but abstracts away the details of exactly how the solution to the problem is computed.
将程序表达为约束是一种声明式编程，在这种编程方式中，程序员声明待解决问题的结构，但抽象掉了问题解决方案具体如何计算的细节。

一旦某个连接器被赋值，它就唤醒所有与它相连、但不是刚刚给它赋值的那个约束；
每个被唤醒的约束检查自己关联的几个连接器，看是否已经有足够信息能推算出还缺值的那个连接器；
如果能推出来，就把值设给那个连接器，从而继续唤醒下一圈约束……
直到网络稳定、没有新信息可以传播为止。

Python
celsius['set_val']('user', 25)
# 输出: Celsius = 25 / Fahrenheit = 77.0

fahrenheit['set_val']('user', 212)
# 输出: Contradiction detected: 77.0 vs 212   —— 因为网络里已经有一个确定值，新值冲突

celsius['forget']('user')
# 输出: Celsius is forgotten / Fahrenheit is forgotten  —— 撤回赋值，网络里的推导值也随之撤销

fahrenheit['set_val']('user', 212)
# 输出: Fahrenheit = 212 / Celsius = 100.0   —— 现在可以反向推算了

谁赋的值就由谁来撤销：每个连接器会记住是谁（哪个约束或用户）给它赋的值（即 "informant"），只有这个来源才能让它"忘记"这个值；
矛盾检测：如果连接器已有值，又收到一个不同的值，就报告矛盾，而不是简单覆盖。

Python
"""
约束传播系统 (Propagating Constraints)
来源: claude 梳理

整体结构:
    connector(name)      —— 构造一个"连接器"，持有一个值，可参与多个约束
    make_ternary_constraint(a, b, c, ab, ca, cb) —— 构造通用三元约束
    adder(a, b, c)        —— 约束: a + b = c
    multiplier(a, b, c)   —— 约束: a * b = c
    constant(connector, value) —— 约束: connector 恒等于 value
    converter(c, f)       —— 把摄氏度连接器 c 和华氏度连接器 f 组网

连接器支持的消息:
    connector['set_val'](source, value)  设置值（source 表示是谁要求设置的）
    connector['has_val']()               是否已有值
    connector['val']                     当前值（数据本身，不是函数）
    connector['forget'](source)          撤销值
    connector['connect'](source)         把某个约束加入自己的关联列表

约束支持的消息:
    constraint['new_val']()   有相邻连接器被赋了新值
    constraint['forget']()    有相邻连接器的值被撤销
"""

from operator import add, sub, mul, truediv


# ---------------------------------------------------------------------------
# 1. 连接器 (Connector)
# ---------------------------------------------------------------------------

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)
            # 通知除 source 之外的所有关联约束：我有新值了
            inform_all_except(source, 'new_val', constraints)
        else:
            # 已经有值 —— 检查是否冲突
            if val != value:
                print('Contradiction detected:', val, 'vs', value)

    def forget_value(source):
        nonlocal informant
        # 只有原来设值的那个来源才有权撤销
        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):
    """把 message 发给 constraints 中除 source 之外的所有约束。"""
    for c in constraints:
        if c != source:
            c[message]()


# ---------------------------------------------------------------------------
# 2. 通用三元约束 及 由它派生出的 adder / multiplier
# ---------------------------------------------------------------------------

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 adder(a, b, c):
    """约束: a + b = c。"""
    return make_ternary_constraint(a, b, c, add, sub, sub)


def multiplier(a, b, c):
    """约束: a * b = c。"""
    return make_ternary_constraint(a, b, c, mul, truediv, truediv)


def constant(connector, value):
    """约束: connector 恒等于 value（只在构造时设置一次，之后不再响应消息）。"""
    constraint = {}
    connector['set_val'](constraint, value)
    return constraint


# ---------------------------------------------------------------------------
# 3. 组网: 摄氏度 <-> 华氏度换算   9 * c = 5 * (f - 32)
# ---------------------------------------------------------------------------

def converter(c, f):
    """用约束网络连接 c(摄氏度) 与 f(华氏度)。"""
    u, v, w, x, y = [connector() for _ in range(5)]
    multiplier(c, w, u)   # c * w = u
    multiplier(v, x, u)   # v * x = u
    adder(v, y, f)        # v + y = f
    constant(w, 9)
    constant(x, 5)
    constant(y, 32)


# ---------------------------------------------------------------------------
# 4. 使用示例
# ---------------------------------------------------------------------------

if __name__ == '__main__':
    celsius = connector('Celsius')
    fahrenheit = connector('Fahrenheit')
    converter(celsius, fahrenheit)

    print('--- 设置 Celsius = 25 ---')
    celsius['set_val']('user', 25)          # Celsius = 25 / Fahrenheit = 77.0

    print('--- 尝试把 Fahrenheit 设为 212（应产生矛盾）---')
    fahrenheit['set_val']('user', 212)      # Contradiction detected: 77.0 vs 212

    print('--- 撤销 Celsius 的值 ---')
    celsius['forget']('user')               # Celsius is forgotten / Fahrenheit is forgotten

    print('--- 现在可以反向设置 Fahrenheit = 212 ---')
    fahrenheit['set_val']('user', 212)      # Fahrenheit = 212 / Celsius = 100.0

核心思想：把数据和行为捆绑在一起、通过"消息"来驱动交互、通过校验来源实现受控的状态改变。

Homework 04 Sequences, Data Abstraction, Trees¶

Python
def shuffle(s):
    """Return a shuffled list that interleaves the two halves of s."""
    assert len(s) % 2 == 0, 'len(seq) must be even'
    s_1 = s[0:len(s) // 2]
    s_2 = s[len(s) // 2:]
    result = []
    for i in range(len(s) // 2):
        result.append(s_1[i])
        result.append(s_2[i])
    return result



def deep_map(f, s):
    """Replace all non-list elements x with f(x) in the nested list s."""
    for i in range(len(s)):
        if type(s[i]) != list:
            s[i] = f(s[i])
        else:
            deep_map(f, s[i])


SOURCE_FILE = __file__


def planet(mass):
    """Construct a planet of some mass."""
    assert mass > 0
    return ['planet', mass]

def mass(p):
    """Select the mass of a planet."""
    assert is_planet(p), 'must call mass on a planet'
    return p[1]


def is_planet(p):
    """Whether p is a planet."""
    return type(p) == list and len(p) == 2 and p[0] == 'planet'

def examples():
    t = mobile(arm(1, planet(2)),
               arm(2, planet(1)))
    u = mobile(arm(5, planet(1)),
               arm(1, mobile(arm(2, planet(3)),
                             arm(3, planet(2)))))
    v = mobile(arm(4, t), arm(2, u))
    return t, u, v

def total_mass(m):

    if is_planet(m):
        return mass(m)
    else:
        assert is_mobile(m), "must get total mass of a mobile or a planet"
        return total_mass(end(left(m))) + total_mass(end(right(m)))

def balanced(m):
    if is_planet(m):
        return True
    if is_planet(end(left(m))) and is_planet(end(right(m))):
        return total_mass(end(left(m))) * length(left(m)) == total_mass(end(right(m))) * length(right(m))
    if total_mass(end(left(m))) * length(left(m)) != total_mass(end(right(m))) * length(right(m)):
        return False
    return balanced(end(left(m))) and balanced(end(right(m)))



def prune_leaves(t, vals):

    if is_leaf(t):
        if label(t) in vals:
            return None
        return tree(label(t))
    new_branch = [prune_leaves(b, vals) for b in branches(t)]
    return tree(label(t), [b for b in new_branch if b is not None])


SOURCE_FILE = __file__


def max_path_sum(t):
    if is_leaf(t):
        return label(t)
    sum_list = [label(t) + max_path_sum(b) for b in branches(t)]
    return max(sum_list)