2.4.可变数据

发表于 更新于 分类于 ， 阅读次数： 本文字数： 5.5k 阅读时长 ≈ 20 分钟

\(2.4\)可变数据

  在模块化程序设计中的一个重要技术是合并随时间变化的数据，这样，合并后的数据就可以表示一个独立的对象、不被程序的其他部分限制。将状态加入数据中是“面向对象编程”的核心要素。

一、对象(\(objection\))及其相关概念

  对象包含数据的值(\(value\))与数据行为(\(behaviour\))。

  以\(python\)库中的date为例： 

1
from datetime import date
  在这里，date函数与class被绑定在一起。class是一类数值的总称，单独的date是class中的一个例子。

  我们可以如下对date赋值与对date进行运算，像普通数据一样： 

1
2
3
4
>>> tues = date(2014, 5, 13)

>>> print(date(2014, 5, 19) - tues)
6 days, 0:00:00

  同时，对象具有属性(attribute)，属性即是对象不同部分的数值。可以通过如下方式访问其属性： 

1
2
3
4
<expression>.<name>

>>> tues.year
2014

  对象还具有方法(method)，方法就是一个内置的函数，当调用方法时，对象会自己执行、输出对应的结果： 

1
2
>>> tues.strftime('%A, %B %d')
'Tuesday, May 13'

  不仅data，\(python\)中的其他值(如string,numbers...)都是对象，因为他们都有属性和对应的行为。

三、序列对象

1.可改变对象

  \(a.\)概念与性质

  可改变对象(\(mutable\;objects\))用于表示随时间变化的量。例如，我们可以改变\(list\)内的内容，利用\(list\)自带的方法。而\(number\)是不可改变对象。

  下面这个例子展示了\(list\)的可改变性： 

1
2
3
4
5
6
7
8
9
10
11
chinese = ['coin', 'string', 'myriad']
suits = chinese
suits.pop()
suits.remove('string')
suits.append('cup')
suits.extend(['sword', 'club'])
suits[2] = 'spade'
suits[0:2] = ['heart', 'diamond']

>>> chinese  # This name co-refers with "suits" to the same changing list
['heart', 'diamond', 'spade', 'club']
  由于我们一直在改变一个\(list\)而非创造一个新\(list\)，与原\(list\)绑定的chinese也随之改变，因为它们是同一个对象。因此，对于可改变对象，对某个名字(\(name\))使用的方法不改变另一个名字的值，当且仅当它们不共享同一个对象。

  \(p.s.\)这里的“共享”并不仅仅是相同，当一个变量的某一部分用可改变对象赋值时，改变可改变对象也会导致这一变量改变： 

1
2
3
4
5
>>> nest = list(suits)  # Bind "nest" to a second list with the same elements
>>> nest[0] = suits     # Create a nested list
>>> suits.insert(2, 'Joker')  # Insert an element at index 2, shifting the rest
>>> nest
[['heart', 'diamond', 'Joker', 'spade', 'club'], 'diamond', 'spade', 'club']

  需要注意，经过序列解析后得到的新序列不与先前序列共享一个对象。

  \(b.\)\(is\)运算

  由上述论证，我们定义表达式\(is\)为两个名字是否同属一个对象，如下例： 

1
2
3
4
5
6
7
8
9
10
11
12
suits = ['heart', 'diamond', 'spade', 'club']
nest = list(suits)
nest[0] = suits
suits.insert(2, 'Joker')
joke = nest[0].pop(2)

>>> suits is nest[0]
True
>>> suits is ['heart', 'diamond', 'spade', 'club']
False
>>> suits == ['heart', 'diamond', 'spade', 'club']
True
  此处的\(list\)是新创建的\(list\),因此是新的对象。

2.元组与字典

  \(a.\)元组(\(Tuple\))

  下面的几种序列形式都属于元组： 

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

  元组的查询操作如下： 

1
2
3
4
5
6
7
8
9
>>> code = ("up", "up", "down", "down") + ("left", "right") * 2
>>> len(code)
8
>>> code[3]
'down'
>>> code.count("down")
2
>>> code.index("left")
4
  由于元组是不可改变对象，因此\(list\)诸如pop,insert等方法对元组都不适用。

  虽然元组是不可改变对象，但当调用元组内部的可改变对象时，它依然是可改变的： 

1
2
nest = (10, 20, [30, 40])
nest[2].pop()

  \(b.\)字典(\(dictionary\))

  字典是一个储存键值对的容器。字典的作用是提供一种抽象，用于存储和检索那些不是通过连续整数而是通过描述性键进行索引的值。

  下面的几种序列形式都是字典： 

1
>>> numerals = {'I': 1.0, 'V': 5, 'X': 10}

  字典的查询等操作如下，由于字典是可改变对象，可以对字典进行插入、删改等操作： 

1
2
3
4
5
6
7
>>> numerals['X']
10

>>> numerals['I'] = 1
>>> numerals['L'] = 50
>>> numerals
{'I': 1, 'X': 10, 'L': 50, 'V': 5}
  需要注意，字典内元素有如下性质：

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

  字典中的元素都可通过可迭代的对象属性keys、values、items来访问，并可用\(sum\)等函数进行数据合并： 

1
2
>>> sum(numerals.values())
66

  一系列键值对可以直接转化为字典类型： 

1
2
>>> dict([(3, 9), (4, 16), (5, 25)])
{3: 9, 4: 16, 5: 25}
  字典也有类似列表解析的操作： 
1
2
>>> {x: x*x for x in range(3,6)}
{3: 9, 4: 16, 5: 25}

四、局部状态(\(local\;state\))

1.局部状态的概念

  列表与字典等可改变对象具有的这种性质被称为局部状态：在程序的执行过程中，它们的一些特定的内容会发生改变。“状态”一词说明对象的状态会在包含它的过程中发生改变。

  函数也具有局部状态。我们假设一个函数withdraw来模拟从银行取钱的过程。假设我们的银行账户有\(100\)元，我们希望通过引用withdraw得到下列序列： 

1
2
3
4
5
6
7
8
>>> withdraw(25)
75
>>> withdraw(25)
50
>>> withdraw(60)
'Insufficient funds'
>>> withdraw(15)
35
  表达式withdraw被调用两次，返回不同的结果，因此这个函数是非纯函数：引用该函数不仅返回一个值、还对函数本身有副作用。

  为了实现withdraw，它还需创建一个初始的银行账户，我们用高阶函数make_withdraw来实现这一功能，让withdraw作为返回的函数： 

1
2
3
4
5
6
7
8
9
10
11
12
def make_withdraw(balance):
    def withdraw(amount):
        nonlocal balance
        if(amount>balance):
            return 'Not enough'
        balance=balance-amount
        return balance
    return withdraw

wd=make_withdraw(20)
wd(5)
wd(3)
  对该函数的框架分析如下：

  • 第一个定义的函数将make_withdraw与全局框架绑定。
  • 第二个定义的函数是局部定义的，将withdraw与局部框架绑定。
  • 每次调用wd，都会创造出一个新的局部框架。

  而对于balance,在执行nonlocal语句后，任何balance在左侧的赋值语句都不会将balance与当前框架绑定。相反地，它会去寻找balance已经被定义的框架，并把balance与该框架绑定。而当balance还没被赋过一个值，nonlocal语句便会报错。

  在先前对嵌套函数的学习中，我们知道一个局部定义的函数可以调用局部框架以外的变量，并不需要nonlocal语句。但只有nonlocal可以让局部函数改变名称绑定的框架。

2.\(python\)的语言特性

  上面说到的nonlocal语句是\(python\)高阶函数与词法范围的特性。事实上，nonlocal语句经常是其它编程语言的默认行为。

  \(python\)语句还有一个限制：在函数体内部，所有名字(\(name\))的实例必须处于同一框架。因此，在\(python\)中，一个局部函数不能在非局部框架中查询一个名字的值、然后将其绑定到局部框架中，否则一个名字就属于两个不同的框架了。这个限制允许\(Python\)在执行函数体之前预先计算包含每个名称的框架。

  下面这个例子说明了\(python\)的这一特性： 

1
2
3
4
5
6
7
8
9
10
11
12
def make_withdraw(balance):
    def withdraw(amount):
        if amount > balance:
            return 'Insufficient funds'
            balance = balance - amount
            return balance
        return withdraw

wd = make_withdraw(20)
wd(5)

>>>UnboundLocalError: local variable 'balance' referenced before assignment

  在withdraw中，原本处于make_withdraw框架中的balance在局部框架中被赋值，违反了\(python\)的限制。

3.nonlocal的好处

  nonlocal语句是我们将程序视为相互交互而彼此独立的集合的重要步骤。

  特别地，nonlocal语句让我们能够维护那些属于某个函数的局部框架、但随着调用不断更新的状态。像上面的与withdraw联系的balance在对withdraw的多次调用中得到共享。但是，这个balance与withdraw的联系对函数的其它部分是不可访问的、仅对wd生效。当我们再次调用make_withdraw后，它会创建一个独立的框架，与一个跟新的balance的独特的联系。

  下面这个对原来例子的拓展很好地说明了这个问题： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def make_withdraw(balance):
    def withdraw(amount):
         nonlocal balance
         if amount > balance:
            return 'Insufficient funds'
        balance = balance - amount
        return balance
    return withdraw

wd = make_withdraw(20)
wd2 = make_withdraw(7)
wd2(6)
>>>1
wd(8)
>>>12
  通过这个方式，每个withdraw的实例(instance)都维护了自己独有的balance值，并且这个值对其它函数而言是不可访问的。这样，我们就创建了一个完全独立的\(bank\;account\)对象。

4.关于相等(\(same\))的思考

  对于一个函数，以上面的make_withdraw为例，wd与wd2绑定的都是同一个函数make_withdraw，但是两者是否相等呢？由上述讨论知两者并不相等。但对于以下例子，两者就变成完全相等的了： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def make_withdraw(balance):
    def withdraw(amount):
        nonlocal balance
        if amount > balance:
            return 'Insufficient funds'
        balance = balance - amount
        return balance
    return withdraw

wd = make_withdraw(12)
wd2 = wd
wd2(1)
>>>11
wd(1)
>>>10
  这时，make_withdraw的一个实例被两个不同的名字wd和wd2所表示，这是很不寻常的。而分析这个问题的关键在于只有调用函数才可以引入新的框架，并且赋值语句只会改变现有框架中的绑定关系。

  这引发了对“相等”的讨论。在先前对rational number的定义中，只要分子分母相等的数就是相等的；但如今，rational number又有了与其所在框架相关的属性——identity。而对于上面\(account\)的例子，wd2与wd的值并不相同，但它们是同一个\(account\)。这一差异让程序设计变得更为复杂。

五、对象的具体实现——以列表与字典为例

1.列表的实现

  我们将用一个以链表作为局部状态的函数代表可变列表，先考虑下面这些基本的设计：

  • 具有与框架相关的属性——identity，像普通的可变列表一样。
  • 不能用None表示空列表，因为两个不同的空列表不是相等的值，但None is None。而empty可以实现identity属性。

  既然是用函数实现，那么应该用什么作为函数的参数呢？该问题的答案揭示了编程中的一般模式：

  \(a.\)分派函数(\(dispatch\;function\))

  分派函数的第一个参数是message——一个字符串，用于指挥这个函数该调用哪个方法；其余参数是各个方法需要的参数。

  分派函数实际上是多个函数的集成体：message参数决定了函数的行为，其余参数则在这个行为中被调用: 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def mutable_link():
    contents=empty
    def dispatch(message,value=None):
        nonlocal contents
        if messages=='len':
            return len_link(contents)
        elif messages=='getitem':
            return getitem_link(contents,value)
        elif messages=='push_first':
            contents=link(value,contens)
        elif message=='pop_first':
            f=first(contents)
            contents=rest(contens)
            return f
        elif message=='str':
            return join_link(contents,",")
    return dispatch

  我们还可以创建一个将\(python\)内置的序列数据类型表示为mutable_list类型的函数： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def to_mutable_link(source):
    s=multible_link()
    for i in reverse(source):
        s('push_first',i)
    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
  这样，mutable list的封装就完成了。这种通过在一个函数内封装对某个数据值的所有操作的方法被称作信息传递原则(\(message\;passing\))。一个运用信息传递原则的函数会定义分派函数、并通过传递message来组织计算。

2.字典的实现

  利用上面的逻辑，我们也可以实现字典的封装： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
def dictionart():
    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

六、分派字典(\(dispatch\;dictionary\))

1.分派字典的概念

  分派函数是抽象数据传递接口的一种通用方法，而我们可以用字典这种数据类型来实现分派函数的分派功能。

2.分派字典的实现

  以先前的\(account\)为例，我们创建一个可变数据类型account，它由\(constructor\)account与\(selector\)check_balance组成： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
def account(initial_balance):
    def deposit(amount):
        dispatch['balance']+=amount
        return dispatch['balance']

    def withdraw(amount):
        if amount>dispatch['balance']:
            return 'Insufficient funds'
        dispatch['balance']-=amount
        return dispatch['balance']

    dispatch={'deposit':deposit,'withdraw':withdraw,'balance':initial_balance}
    return dispatch

def withdraw(account,amount):
    return account['withdraw'](amount)

def deposit(account,amount):
    return account['deposit'](amount)

def check_balance(account):
    return account['balance']

a=account(20)
deposit(a,5)
withdraw(a,17)
check_balance(a)
>>>8

  在这里，我们通过把balance存储在字典中而非直接存储在account框架里，避免了使用nonlocal语句。

七、约束传递(\(propagating\;constraints\))

1.新的抽象系统——基于约束的系统(\(constraint-based\;system\))

  可改变数据允许我们模拟随时改变的系统，同时也为我们提供了新的抽象方法。下面介绍利用nonlocal赋值、\(list\)、字典搭建的基于约束器的系统。这是声明式编程(\(declarative\;programming\))的重要部分。

  在这个系统中，我们将程序表达为约束(\(constraint\))，确定待解决问题的结构，但将解决问题的细节进行抽象。

  这个系统的引入是基于计算机程序的特性——单向计算性(\(one-directional\;computations\))。在计算机程序中，我们将问题抽象为一个系统，模拟系统中各个数量的关系，在系统中传入给定的参数，然后计算出想要的答案。但很多事物，如下面的公式，并不是单向的：

\[pV=nRT\]

  在这个公式中，给出任意四个量，显然可以求出第五个量的值。但在计算机程序中，一个设计好用来求解\(p\)的程序由于参数被固定了，并不能用于求解\(T\)或其他量，即使我们已知其中四个量。

  于是我们构想一个模拟这种线性关系的模型。我们先定义一些初始的约束器，例如加法器adder(a,b,c)，它强制(\(enforce\))了数学的加法关系a+b=c。

  我们再定义一种合并的方法，使得初始的约束器能被合并以表达更复杂的关系。我们构建一个网络(\(network\))，在这个网络中，约束器被连接器(\(connector\))连接在一起。连接器是一个连接一个或多个限制的对象，它自身会携带一个值。例如摄氏度与华氏度的换算\(9\times c=5\times(f-32)\)可表示为如下网络：

  基于这个网络的计算流程如下：

  • 当一个连接器被赋值，它会唤醒所有与它相连的约束器，告诉它们自己获得了一个值。
  • 每个约束器检测(\(poll\))自己的连接器，看自己是否有足够多的信息来决定连接器的值。
  • 如果能决定，约束器就重设连接器的值，然后连接器接着执行唤醒操作。

  对于温度换算的例子，该网络执行如下操作：

  • 先在\(w\)、\(x\)、\(y\)这些放常数的盒子(\(constant\;box\))里放入常数。
  • 连接器唤醒加法器adder和乘法器multiplier
  • 由于\(celsius\)的输入，最左侧乘法器将连接器\(u\)的值重设，同时\(u\)唤醒右侧的乘法器；最右侧同理。

2.约束系统的使用

  \(a.\)连接器的创建与连接

  为创建两个表示温度的连接器，我们调用connector\(constructor\)： 

1
2
>>>celsius=connector('Celsius')
>>>fahrenheit=connector('Fahrenheit')

  然后我们把这些连接器组装到如上图的网络中。这里的converter函数用于组装该系统的诸多连接器与约束器： 

1
2
3
4
5
6
7
8
9
10
11
def converter(c,f):
    u,v,w,x,y=[connector()for _ in range(5)]
    #apply a new connector for each variables
    multiplier(c,w,u)
    multiplier(v,x,u)
    adder(v,y,f)
    constant(w,9)
    constant(x,5)
    constant(y,32)

converter(celsius,fahrenheit)
####   \(b.\)连接器与限制器的协调   我们用之前介绍的\(message\;passing\)系统来协调连接器与约束器。这里，约束器是不持有局部状态的字典，它们对message的回应是会改变连接器值的非纯函数。

  而连接器是持有当前值、并回应接收到的message从而改变当前值的字典。约束器不会立即改变连接器的值，而是发送信息，这样连接器就可以根据收到的信息来唤醒其他约束器。通过这一流程，连接器不仅表示当前值、而且还封装了一系列行为。

  向连接器发送信号，以set_val为例，的方法如下：(这里的user是我们，发送信号的人) 

1
2
3
>>>celsius['set_val']('user',25)
celsius=25
fahrenheit=77.0

  在set_val被执行后，不仅\(celsius\)的值变成了\(25\)，它的值通过网络传递导致了\(fahrenheit\)的改变。这个改变被打印出来，因为\(constructor\)converter将两个名称绑定在同一网络里。

  那假如我们对其中一个名称输入一个与原结果相矛盾的值呢？ 

1
2
>>> fahrenheit['set_val']('user', 212)
Contradiction detected: 77.0 vs 212

  此时连接器报错了：它的值是\(77.0\)，但有人想把它变成\(212\)。如果我们想让这个网络采纳这个新值，就要让\(celsius\)忘记它的旧值： 

1
2
3
>>> celsius['forget']('user')
Celsius is forgotten
Fahrenheit is forgotten

  在接受到forget的指令后，不仅\(celsius\)撤回了原先的值，该指令通过网络传递给\(fahrenheit\)，\(fahrenheit\)也忘记了原先的值。此时再对\(fahrenheit\)进行赋值就可成立： 

1
2
3
>>> fahrenheit['set_val']('user', 212)
Fahrenheit=212
Celsius=100.0

  在这整个过程中体现出的系统的非方向性是约束系统的显著特征。

3.约束系统的实现

  我们想让连接器对如下message做出回应：

  • connector['set_val'](source, value)：为连接器赋值。
  • connector['has_val']()：返回是否有值。
  • connector['val']：输出连接器当前值。
  • connector['forget'](source)：告诉连接器source让它忘记当前值。
  • connector['connect'](source)：让连接器与source相连

  约束器也是字典，它接受连接器传来的两种信息：

  • constraint['new_val']()：表明与约束器相连的某个连接器有一个新值。
  • constraint['forget']()：表明与约束器相连的某个连接器忘记了它的值。

  当约束器收到message后，会将它们传给其他的连接器。

  下面展示一般三元约束(\(generic\;ternary\))的实现。在三元约束系统中，我们用三个连接器和三个从加法器adder创建的函数来创建约束： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def make_tenery_constraint(a,b,c,ab,ca,cb):
    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 bv and cv:
            a['set_val'](constraint,bc(b['val'],c['val']))
        elif av and cv:
            b['set_val'](constraint,ac(a['val'],c['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):
        connectot['connect'](constraint)
    return constraint

  这里的\(constraint\)既是分派字典、又是\(constraint\)对象本身，它负责回应连接器传来的信息。函数的实现逻辑如下：

  • \(constraint\)的new_value局部函数在约束器被告知它的连通器获得了一个新值时会被调用。当其检测到两个值时，它就会告知对应连接器：把值设置成两个值约束后的值。
  • 当约束器被告知它的连通器忘记了某个值时，它要求所有与它相连的连接器忘掉它们的值。

  乘法器的实现与加法器类似： 

1
2
3
from operator import mul,truediv
def muitiplier(a,b,c):
    return make_tenery_constraint(a,b,c,mul,truediv,truediv)

  常数也是一种约束器，但它不会发送任何信息，因为它只有一个刚创建时创建的连接器： 

1
2
3
4
def constant(connector,value):
    constraint={}
    connector['set_val'](constraint,value)
    return constraint

4.连接器的实现

  连接器是一个不仅包含自身值、还包含回应函数的字典。一个连接器需要跟踪给它赋予当前值的informant(source)与和它相连的constraint。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
def connector(name=None):
    informant=None
    constraint=[]
    def set_value(source,value):
        nonlocal informant
        val=connect['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 forger_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

  这里的\(connector\)同样既是分派字典又是\(connector\)对象本身，字典的其中四项代表方法函数，最后一项返回\(connector\)的值。函数的实现逻辑如下：

  • 当收到设置连接器当前值的请求时，set_value被调用。
  • 当此时的连接器没有值时，它会设置一个值，并将请求设置值的源约束器source作为informant。然后连接器就会告知除源约束器外的所有与它相连的约束器。
  • 当连接器被告知要忘记当前值时，它调用forget_value，接着告知除源约束器外的所有与它相连的约束器。

  告知函数可如下实现： 

1
2
3
4
def inform_all_except(source,message,constraints):
    for c in constraints:
        if c!=source:
            c[message]()

5.约束系统的性质

  约束系统中的约束器与连接器都是通过传递message来操作的对象。当某个连接器的值被改变时，传递的message不仅改变了连接器的值，还确认了值的正确性、将值的效果传递给其他对象。这使得程序更为完善