> For the complete documentation index, see [llms.txt](https://zlt-shadow.gitbook.io/sicp-in-python-cn/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://zlt-shadow.gitbook.io/sicp-in-python-cn/di-2-zhang-shu-ju-gou-jian-chou-xiang/2.4-ke-bian-shu-ju.md). # 2.4 可变数据 我们已经看到了抽象在帮助我们应对大型系统的复杂性方面是如何至关重要的。 有效的程序设计还需要有组织的原则来指导我们制定程序的总体设计。 特别是，我们需要一些策略来帮助我们将大型系统结构成模块化的，这意味着它们自然地划分为可以单独开发和维护的连贯部分。 创建模块化程序的一种强大技术是合并可能随时间改变状态的数据。 通过这种方式，单个数据对象可以表示独立于程序其余部分发展的东西。 一个不断变化的对象的行为可能会受到它的历史的影响，就像世界上的一个实体一样。 向数据添加状态是称为面向对象编程的范式的核心组成部分。 ### 2.4.1 对象隐喻 在本文的开头，我们区分了函数和数据：函数执行操作，数据被操作。 当我们在数据中包含函数值时，我们承认数据也可以有行为。 函数可以作为数据进行操作，但也可以被调用来执行计算。 对象将数据值与行为结合起来。 对象代表信息，但也表现得像它们所代表的事物。 对象如何与其他对象交互的逻辑与编码对象值的信息捆绑在一起。 当一个对象被打印出来时，它知道如何在文本中拼写出来。 如果一个对象是由部件组成的，它知道如何根据需要显示这些部件。 对象既是信息又是过程，捆绑在一起表示复杂事物的属性、交互和行为。 在Python中，对象行为是通过专门的对象语法和相关术语来实现的，我们可以通过示例介绍这些术语。 日期是一种对象。 ``` >>> from datetime import date ``` 名称date被绑定到一个类。正如我们所看到的，类代表一种值。单独的日期被称为该类的实例。实例可以通过对实例的特征参数调用类来构造。 ``` >>> tues = date(2014, 5, 13) ``` 虽然tues是由原始数字构造的，但它的行为与日期类似。例如，从另一个日期减去它将得到一个我们可以打印的时差。 ``` >>> print(date(2014, 5, 19) - tues) 6 days, 0:00:00 ``` 对象具有属性，这些属性是命名值，是对象的一部分。在Python中，像许多其他编程语言一样，我们使用点表示法来指定对象的属性。 ``` >>> tues.year 2014 ``` 对象也有方法，这些方法是函数值属性。打个比方，我们说对象“知道”如何执行这些方法。通过实现，方法是根据其参数和对象计算结果的函数。例如，tues的strftime方法(一个经典的函数名称，意思是唤起“字符串格式的时间”)只有一个参数，用来指定如何显示日期(例如，% a表示应该完整地说出星期几)。 ``` >>> tues.strftime('%A, %B %d') 'Tuesday, May 13' ``` 计算strftime的返回值需要两个输入：描述输出格式的字符串和绑定成tues的日期信息。在此方法中应用特定日期的逻辑来产生此结果。 我们从未说过2014年5月13日是星期二，但知道相应的工作日是日期的一部分。 通过将行为和信息捆绑在一起，这个Python对象为我们提供了一个令人信服的、自包含的日期抽象。 日期是对象，但是数字、字符串、列表和范围也是对象。 它们表示值，但也以适合它们所表示的值的方式行事。 它们还具有属性和方法。 例如，字符串有一个有助于文本处理的方法数组。 ``` >>> '1234'.isnumeric() True >>> 'rOBERT dE nIRO'.swapcase() 'Robert De Niro' >>> 'eyes'.upper().endswith('YES') True ``` 事实上，Python中的所有值都是对象。也就是说，所有的值都有行为和属性。他们表现得像他们所代表的价值。 ### 2.4.2 序列对象 原始内置值(比如number)的实例是不可变的。 这些值本身不能在程序执行过程中改变。 另一方面，列表是可变的。 可变对象用于表示随时间变化的值。 一个人每天都是同一个人，尽管他变老了，剪了发，或者以其他方式改变了。 类似地，由于操作的变化，对象的属性也可能发生变化。 例如，可以更改列表的内容。 大多数更改是通过调用列表对象的方法来执行的。 我们可以通过一个示例来介绍许多列表修改操作，该示例演示了扑克牌的历史(大大简化了)。 示例中的注释描述了每次方法调用的效果。 扑克牌是在中国发明的，大约是在9世纪左右。 早期的一副牌有三套，分别对应不同面额的货币。 ``` >>> chinese = ['coin', 'string', 'myriad'] # A list literal >>> suits = chinese # Two names refer to the same list ``` 随着纸牌迁移到欧洲(也许是通过埃及)，西班牙的牌组(oro)中只剩下一套硬币。 ``` >>> suits.pop() # Remove and return the final element 'myriad' >>> suits.remove('string') # Remove the first element that equals the argument ``` 后来又增加了三套西装(随着时间的推移，它们的名字和设计都有所变化)， ``` >>> suits.append('cup') # Add an element to the end >>> suits.extend(['sword', 'club']) # Add all elements of a sequence to the end ``` 意大利人把剑叫做铲子。 ``` >>> suits[2] = 'spade' # Replace an element ``` 给一副传统的意大利牌的套装 ``` >>> suits ['coin', 'cup', 'spade', 'club'] ``` 如今在美国使用的法语变体改变了前两种套装： ``` >>> suits[0:2] = ['heart', 'diamond'] # Replace a slice >>> suits ['heart', 'diamond', 'spade', 'club'] ``` 也存在插入、排序和反转列表的方法。所有这些突变操作都会改变列表的值;它们不创建新的列表对象。 **共享和身份。**因为我们一直在更改单个列表而不是创建新的列表，绑定到名称chinese的对象也发生了变化，因为它是绑定到suits的同一个列表对象！ ``` >>> chinese # This name co-refers with "suits" to the same changing list ['heart', 'diamond', 'spade', 'club'] ``` 这种行为是新的。以前，如果一个名称没有出现在语句中，那么它的值不会受到该语句的影响。对于可变数据，在一个名称上调用的方法可以同时影响另一个名称。 [这个例子的环境图](http://composingprograms.com/tutor.html#code=chinese+%3D+%5B'coin',+'string',+'myriad'%5D%0Asuits+%3D+chinese%0Asuits.pop\(\)%0Asuits.remove\('string'\)%0Asuits.append\('cup'\)%0Asuits.extend\(%5B'sword',+'club'%5D\)%0Asuits%5B2%5D+%3D+'spade'%0Asuits%5B0%3A2%5D+%3D+%5B'heart',+'diamond'%5D)显示了绑定到chinese的值是如何被只涉及suits的语句更改的。通过下面示例中的每一行来观察这些变化。 ![](/files/-MXR2_p8ejlhQ_LU_mg9) 可以使用list构造函数复制列表。对一个列表的更改不会影响另一个列表，除非它们共享结构。 ``` >>> nest = list(suits) # Bind "nest" to a second list with the same elements >>> nest[0] = suits # Create a nested list ``` 根据这个环境，更改suits引用的列表将影响nest的第一个元素的嵌套列表，而不会影响其他元素。 ``` >>> suits.insert(2, 'Joker') # Insert an element at index 2, shifting the rest >>> nest [['heart', 'diamond', 'Joker', 'spade', 'club'], 'diamond', 'spade', 'club'] ``` 同样，撤消在nest的第一个元素中的更改也会更改suit。 ``` >>> nest[0].pop(2) 'Joker' >>> suits ['heart', 'diamond', 'spade', 'club'] ``` [逐行执行此示例](http://composingprograms.com/tutor.html#code=suits+%3D+%5B'heart',+'diamond',+'spade',+'club'%5D%0Anest+%3D+list\(suits\)%0Anest%5B0%5D+%3D+suits%0Asuits.insert\(2,+'Joker'\)%0Ajoke+%3D+nest%5B0%5D.pop\(2\))将显示嵌套列表的表示方式。 ![](/files/-MXR2uPxEXWmDLIFZBzi) 因为两个列表可能有相同的内容，但实际上是不同的列表，所以我们需要一种方法来测试两个对象是否相同。Python包含两个名为is和is not的比较操作符，用于测试两个表达式是否实际计算为相同的对象。如果两个对象的当前值相等，则它们是相同的，对其中一个对象的任何更改都会在另一个对象中反映出来。身份是比平等更强的条件。 ``` >>> suits is nest[0] True >>> suits is ['heart', 'diamond', 'spade', 'club'] False >>> suits == ['heart', 'diamond', 'spade', 'club'] True ``` 最后两个比较说明了is和==之间的区别。前者检查身份，而后者检查内容的相等性。 **列表推导式。**列表推导式总是创建一个新列表。例如，unicodedata模块跟踪Unicode字母表中每个字符的正式名称。我们可以查找与名字对应的字符，包括纸牌套对应的字符。 ``` >>> from unicodedata import lookup >>> [lookup('WHITE ' + s.upper() + ' SUIT') for s in suits] ['♡', '♢', '♤', '♧'] ``` 这个结果列表不会与suits共享任何内容，并且对列表的推导式求值也不会修改suits列表。 你可以在《深入Python 3》的Unicode部分阅读更多关于表示文本的Unicode标准的内容。 **元组。**一个元组，一个内置元组类型的实例，是一个不可变序列。元组是用一个元组字面值创建的，该元组字面值用逗号分隔元素表达式。括号是可选的，但在实践中经常使用。任何对象都可以放在元组中。 ``` >>> 1, 2 + 3 (1, 5) >>> ("the", 1, ("and", "only")) ('the', 1, ('and', 'only')) >>> type( (10, 20) ) ``` 空元组和单元素元组具有特殊的文字语法。 ``` >>> () # 0 elements () >>> (10,) # 1 element (10,) ``` 与列表一样，元组具有有限的长度并支持元素选择。它们还有一些用于列表的方法，如count和index。 ``` >>> code = ("up", "up", "down", "down") + ("left", "right") * 2 >>> len(code) 8 >>> code[3] 'down' >>> code.count("down") 2 >>> code.index("left") 4 ``` 然而，用于操作列表内容的方法对于元组是不可变的，所以是不可用的。 虽然不可能更改元组中的哪些元素，但可以更改元组中包含的可变元素的值。 ![](/files/-MXR5HeVi-CCr0Tq61Cm) 元组在多次赋值中被隐式使用。将两个值赋给两个名称将创建一个包含两个元素的元组，然后将其解包。 ### 2.4.3 字典 字典是Python用于存储和操作对应关系的内置数据类型。字典包含键-值对，其中键和值都是对象。字典的目的是提供一种存储和检索值的抽象，这些值不是按连续整数索引的，而是按描述性键索引的。 字符串通常用作键，因为字符串是我们对事物名称的常规表示。本词典逐字给出各种罗马数字的值。 ``` >>> numerals = {'I': 1.0, 'V': 5, 'X': 10} ``` 通过键查找值，使用前面应用于序列的元素选择操作符。 ``` >>> numerals['X'] 10 ``` 字典中每个键最多只能有一个值。添加新的键-值对和更改键的现有值都可以通过赋值语句实现。 ``` >>> numerals['I'] = 1 >>> numerals['L'] = 50 >>> numerals {'I': 1, 'X': 10, 'L': 50, 'V': 5} ``` 注意，'L'并没有添加到上述输出的末尾。字典是键值对的无序集合。当我们打印字典时，键和值会按某种顺序呈现，但是作为语言的用户，我们无法预测这个顺序。当程序多次运行时，顺序可能会改变。 字典也可以出现在[环境图](http://composingprograms.com/tutor.html#code=numerals+%3D+%7B'I'%3A+1,+'V'%3A+5,+'X'%3A+10%7D%0Anumerals%5B'L'%5D+%3D+50)中。 ![](/files/-MXUY68OZ-BDumhxvJ_A) 字典类型还支持将字典的内容作为一个整体遍历的各种方法。方法键、值和项都返回可迭代值。 ``` >>> sum(numerals.values()) 66 ``` 字典也有一些限制： * 字典的键不能是或包含可变值。 * 一个给定的键最多只能有一个值。 第一个限制与Python中字典的底层实现有关。 这个实现的细节不是本文的主题。 直观地看，这个键告诉Python在内存中哪里可以找到键-值对; 如果密钥发生变化，则可能丢失密钥对的位置。 元组通常用于字典中的键，因为不能使用列表。 第二个限制是字典抽象的结果，它被设计用来存储和检索键的值。 只有当字典中最多存在一个键值时，我们才能检索该键的值。 get是字典实现的一个有用的方法，它返回键的值(如果键存在的话)或默认值。 获取的参数是键和默认值。 ``` >>> numerals.get('A', 0) 0 >>> numerals.get('V', 0) 5 ``` 字典也有类似于列表的理解语法。键表达式和值表达式用冒号分隔。计算一个字典的理解会创建一个新的字典对象。 ``` >>> {x: x*x for x in range(3,6)} {3: 9, 4: 16, 5: 25} ``` ### 2.4.4 本地状态 列表和字典具有局部状态：在程序执行的任何时刻，它们都在改变具有特定内容的值。“状态”一词意味着状态可能改变的一个演进过程。 函数也可以有局部状态。例如，让我们定义一个函数来模拟从银行账户取款的过程。我们将创建一个名为withdraw的函数，该函数以要提取的金额作为参数。如果帐户中有足够的钱来容纳提款，那么提款将返回提款后剩余的余额。否则，取款将返回“资金不足”信息。例如，如果我们以帐户中的$100开始，我们希望通过调用withdraw来获得以下返回值序列： ``` >>> withdraw(25) 75 >>> withdraw(25) 50 >>> withdraw(60) 'Insufficient funds' >>> withdraw(15) 35 ``` 上面的表达式withdraw(25)计算了两次，得到了不同的值。 因此，这个用户定义的函数是非纯的。 调用这个函数不仅会返回一个值，而且还会以某种方式改变这个函数，以便下次使用相同参数的调用会返回不同的结果。 这个副作用是withdraw在当前框架之外更改名称-值绑定的结果。 为了使取款有意义，它必须创建一个初始账户余额。 函数make\_withdraw是一个高阶函数，它以初始余额作为参数。 函数withdraw是它的返回值。 ``` >>> withdraw = make_withdraw(100) ``` make\_withdraw的实现需要一种新的语句：非局部语句。调用make\_withdraw时，将名称余额绑定到初始金额。然后定义并返回一个局部函数withdraw，该函数在调用时更新并返回balance的值。 ``` >>> 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 ``` nonlocal语句声明，每当我们更改名称balance的绑定时，该绑定就会在已经绑定balance的第一个框架中更改。回想一下，如果没有nonlocal语句，赋值语句将始终在当前环境的第一个框架中绑定一个名称。nonlocal语句表示该名称出现在环境中的某处，而不是第一个(局部)框架或最后一个(全局)框架。 [下面的环境图](http://composingprograms.com/tutor.html#code=def+make_withdraw\(balance\)%3A%0A++++def+withdraw\(amount\)%3A%0A++++++++nonlocal+balance%0A++++++++if+amount+%3E+balance%3A%0A++++++++++++return+'Insufficient+funds'%0A++++++++balance+%3D+balance+-+amount%0A++++++++return+balance%0A++++return+withdraw%0A%0Awd+%3D+make_withdraw\(20\)%0Awd\(5\)%0Awd\(3\))演示了多次调用由make\_withdraw创建的函数的效果。 ![](/files/-MXUZpaGFH8YTVT1iLT9) 第一个def语句具有通常的效果：它创建一个新的用户定义函数，并在全局框架中将名称make\_withdraw绑定到该函数。 随后对make\_withdraw的调用创建并返回一个本地定义的函数withdraw。 balance名称绑定在这个函数的父框架中。 至关重要的是，在本示例的其余部分中，name balance只会有一个绑定。 接下来，计算一个调用这个函数的表达式，该函数绑定到名称wd，数量为5。 withdraw的主体在一个新环境中执行，该环境扩展了定义withdraw的环境。 跟踪求出withdraw的效果可以说明Python中非局部语句的效果：第一个局部框架之外的名称可以通过赋值语句更改。 ![](/files/-MXUZvF5qJbvOBGVoxBm) 非局部语句更改了withdraw定义中的所有剩余赋值语句。 在执行了非局部balance之后，任何位于=左边的balance赋值语句都不会在当前环境的第一框架中绑定balance。 相反，它将找到第一个已经定义了balance的框架，并在该框架中重新绑定名称。 如果balance以前没有绑定到某个值，那么non - local语句将给出一个错误。 通过为balance更改绑定，我们也更改了withdraw函数。 下次调用时，name balance将计算为15，而不是20。 因此，当我们第二次调用withdraw时，我们看到它的返回值是12而不是17。 从第一个调用到balance的更改将影响第二个调用的结果。 ![](/files/-MXUZySN6z5tiqwNQCYx) 第二次调用withdraw会像往常一样创建第二个本地框架。 然而，两个withdraw框架都有相同的父框架。 也就是说，它们都扩展了make\_withdraw的环境，其中包含了balance的绑定。 因此，它们共享特定的名称绑定。 调用withdraw有改变环境的副作用，该环境将被未来的withdraw调用所扩展。 nonlocal语句允许withdraw更改make\_withdraw框架中的名称绑定。 自从我们第一次遇到嵌套def语句以来，我们观察到局部定义的函数可以在其局部框架之外查找名称。 访问非本地名称不需要非本地语句。 相比之下，只有在非局部语句之后，函数才能更改这些框架中的名称绑定。 通过引入非局部语句，我们为赋值语句创建了一个双重角色。 它们要么更改本地绑定，要么更改非本地绑定。 事实上，赋值语句已经有了双重角色:它们要么创建新的绑定，要么重新绑定现有的名称。 赋值还可以更改列表和字典的内容。 Python赋值的许多角色可能会掩盖执行赋值语句的效果。 作为一名程序员，你应该清楚地记录你的代码，以便其他人能够理解赋值的效果。 **Python细节。** 这种非局部赋值模式是具有高阶函数和词法作用域的编程语言的一般特性。 大多数其他语言根本不需要非局部语句。 相反，非局部赋值通常是赋值语句的默认行为。 Python对于名称的查找还有一个不寻常的限制：在函数体中，名称的所有实例必须引用相同的框架。 因此，Python无法在非本地框架中查找名称的值，然后将相同的名称绑定到本地框架中，因为相同的名称将在同一个函数的两个不同框架中访问。 这个限制允许Python在执行函数体之前预先计算哪一框架包含每个名称。 当违反此限制时，就会产生令人困惑的错误消息。 为了演示，[下面](http://composingprograms.com/tutor.html#code=def+make_withdraw\(balance\)%3A%0A++++def+withdraw\(amount\)%3A%0A++++++++if+amount+%3E+balance%3A%0A++++++++++++return+'Insufficient+funds'%0A++++++++balance+%3D+balance+-+amount%0A++++++++return+balance%0A++++return+withdraw%0A%0Awd+%3D+make_withdraw\(20\)%0Awd\(5\))重复了make\_withdraw示例，并删除了非本地语句。 ![](/files/-MXUanieEogKA5hDMcHL) 出现这个UnboundLocalError是因为balance在第5行中被局部赋值，因此Python假设所有对balance的引用也必须出现在局部框架中。 这个错误发生在第5行执行之前，这意味着Python在执行第3行之前以某种方式考虑了第5行。 当我们学习解释器设计时，我们会看到在执行函数体之前对它进行预计算是很常见的。 在这种情况下，Python的预处理限制了balance可能出现的框架，从而阻止了名称被找到。 添加非局部语句可纠正此错误。 非局部语句在Python 2中不存在。 ### 2.4.5 非本地分配的好处 非局部赋值是将程序视为独立自主对象的集合的重要一步，这些对象彼此交互，但各自管理自己的内部状态。 特别是，非局部赋值使我们能够维护函数局部的一些状态，但会随着对该函数的连续调用而演变。 与特定提取函数关联的余额在对该函数的所有调用中共享。 但是，与withdraw实例关联的balance绑定对程序的其余部分是不可访问的。 只有wd与定义它的make\_withdraw帧相关联。 如果再次调用make\_withdraw，那么它将创建一个单独的框架，并为balance创建一个单独的绑定。 我们可以[扩展我们的示例](http://composingprograms.com/tutor.html#code=def+make_withdraw\(balance\)%3A%0A++++def+withdraw\(amount\)%3A%0A++++++++nonlocal+balance%0A++++++++if+amount+%3E+balance%3A%0A++++++++++++return+'Insufficient+funds'%0A++++++++balance+%3D+balance+-+amount%0A++++++++return+balance%0A++++return+withdraw%0A%0Awd+%3D+make_withdraw\(20\)%0Awd2+%3D+make_withdraw\(7\)%0Awd2\(6\)%0Awd\(8\))来说明这一点。 对make\_withdraw的第二个调用返回第二个withdraw函数，该函数具有不同的父函数。 我们将第二个函数绑定到全局框架中的名称wd2上。 ![](/files/-MXUcFGE1jMXWDoOr-sS) 现在，我们看到在两个不同的框架中实际上有两个name balance绑定，每个withdraw函数都有一个不同的父函数。名称wd被绑定到一个平衡值为20的函数上，而wd2被绑定到另一个平衡值为7的函数上。 调用wd2会更改其非本地balance名的绑定，但不会影响绑定到名称withdraw的函数。对wd的未来调用不受wd2 balance变化的影响，wd的balance仍然是20。 ![](/files/-MXUcIbsTuO8pUQ1UlQ9) 这样，每个withdraw实例都保持自己的balance状态，但是程序中的任何其他函数都无法访问该状态。从更高的层次来看这种情况，我们已经创建了一个银行帐户的抽象，该帐户管理自己的内部，但其行为方式是对世界上的帐户建模：它根据自己的提款请求历史随着时间而变化。 ### 2.4.6 非本地分配的代价 我们的计算环境模型干净地扩展，以解释非局部赋值的影响。 然而，非局部赋值在我们考虑名称和值的方式上引入了一些重要的细微差别。 以前，我们的值没有改变; 只有我们的名称和绑定更改了。 当两个名字a和b都绑定到值4时，它们绑定的是同一个4还是不同的4都没有关系。 据我们所知，只有一个4的物体从未改变。 但是，带有状态的函数却不是这样的。 当两个名称wd和wd2都绑定到一个withdraw函数时，它们是绑定到同一个函数还是该函数的不同实例都很重要。 考虑[下面的例子](http://composingprograms.com/tutor.html#code=def+make_withdraw\(balance\)%3A%0A++++def+withdraw\(amount\)%3A%0A++++++++nonlocal+balance%0A++++++++if+amount+%3E+balance%3A%0A++++++++++++return+'Insufficient+funds'%0A++++++++balance+%3D+balance+-+amount%0A++++++++return+balance%0A++++return+withdraw%0A%0Awd+%3D+make_withdraw\(12\)%0Awd2+%3D+wd%0Awd2\(1\)%0Awd\(1\))，它与我们刚刚分析的例子形成对比。 在本例中，调用由wd2命名的函数确实改变了由wd命名的函数的值，因为两个名称都指向同一个函数。 ![](/files/-MXUdd3j9kL-eqp_dOT-) 在世界上，两个名字共同指向同一个值是很常见的，在我们的程序中也是如此。 但是，由于值随时间变化，我们必须非常小心地理解更改对可能引用这些值的其他名称的影响。 正确分析带有非局部赋值的代码的关键是要记住，只有函数调用才能引入新的框架。 赋值语句总是会更改现有框架中的绑定。 在本例中，除非调用了两次make\_withdraw，否则balance只能有一个绑定。 **一致性和改变。** 之所以产生这些微妙之处，是因为通过引入改变非局部环境的非纯函数，我们改变了表达式的性质。 只包含纯函数调用的表达式是引用透明的；如果我们用它的子表达式的值替换它的子表达式，它的值不会改变。 重新绑定操作违反了引用透明的条件，因为它们做的不仅仅是返回一个值; 它们改变了环境。 当我们引入任意的重新绑定时，我们遇到了一个棘手的认识论问题：两个值相同意味着什么。 在我们的计算环境模型中，两个单独定义的函数是不相同的，因为对一个函数的更改可能不会反映在另一个函数中。 一般来说，只要我们从不修改数据对象，我们就可以将复合数据对象视为其各个部分的总和。 例如，一个有理数可以通过给出它的分子和分母来确定。 但是这个视图在发生更改时不再有效，因为复合数据对象具有不同于组成它的部分的“身份”。 即使我们通过提款来改变余额，银行账户仍然是“相同的”银行账户; 相反，我们可以有两个银行账户，碰巧有相同的余额，但是是不同的对象。 尽管它引入了复杂性，但非局部赋值是创建模块化程序的强大工具。 程序的不同部分对应于不同的环境框架，可以在整个程序执行过程中分别发展。 此外，使用具有局部状态的函数，我们能够实现可变数据类型。 事实上，我们可以实现与上面介绍的内置list和dict类型等价的抽象数据类型。 ### 2.4.7 实现列表和字典 Python语言不允许我们访问列表的实现，只允许我们访问内置在语言中的序列抽象和可变方法。 为了理解如何使用具有本地状态的函数来表示可变列表，我们现在将开发一个可变链表的实现。 我们将用一个将链表作为其局部状态的函数来表示可变链表。 列表需要有一个标识，就像任何可变值一样。 特别地，我们不能用None来表示空的可变列表，因为两个空列表不是相同的值(例如，在一个列表上追加就不会追加到另一个列表上)，但None就是None。 另一方面，两个本地状态为空的不同函数足以区分两个空列表。 如果一个可变链表是一个函数，它需要什么参数? 答案展示了编程中的一般模式：函数是一个分派函数，它的参数首先是一条消息，然后是用于参数化该方法的附加参数。 这条消息是一个字符串，命名函数应该做什么。 分派函数实际上是多个函数合二为一：消息确定函数的行为，并在该行为中使用附加参数。 我们的可变列表将响应5个不同的消息：len、getitem、push\_first、pop\_first和str，前两个实现序列抽象的行为。 接下来的两个函数添加或删除列表的第一个元素。 最后一条消息返回整个链表的字符串表示形式。 ``` >>> 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 ``` 在上面的定义中，reversed函数接受并返回一个可迭代值；这是处理序列的函数的另一个例子。 现在，我们可以构造一个函数实现的可变链表。注意，链表本身是一个函数。 ``` >>> s = to_mutable_link(suits) >>> type(s) >>> print(s('str')) heart, diamond, spade, club ``` 此外，我们还可以将消息传递给改变其内容的列表，例如删除第一个元素。 ``` >>> s('pop_first') 'heart' >>> print(s('str')) diamond, spade, club ``` 原则上，操作push\_first和pop\_first足以对列表进行任意更改。 我们总是可以完全清空列表，然后用想要的结果替换它的旧内容。 **消息传递。** 在一定的时间内，我们可以实现Python列表的许多有用的可变操作，例如extend和insert。 我们可以选择：我们可以将它们全部作为函数实现，函数使用现有消息pop\_first和push\_first来进行所有更改。 另外，我们可以在分派体中添加额外的elif子句，每个检查消息(例如，'extend')并直接对contents应用适当的更改。 第二种方法将对数据值的所有操作的逻辑封装在一个响应不同消息的函数中，这是一种称为消息传递的规则。 使用消息传递的程序定义了分派函数(每个函数都可能有本地状态)，并通过将“messages”作为第一个参数传递给这些函数来组织计算。 消息是对应于特定行为的字符串。 **实现字典。** 我们还可以实现一个行为类似于字典的值。 在本例中，我们使用一个键-值对列表来存储字典的内容。 每个pair都是一个包含两个元素的列表。 ``` >>> 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 ``` 同样，我们使用消息传递方法来组织我们的实现。我们支持两个消息：getitem和setitem。要为一个键插入一个值，我们过滤掉所有具有给定键的现有记录，然后添加一个。这样，我们就可以保证每个键在记录中只出现一次。为了查找一个键的值，我们筛选与给定键匹配的记录。现在，我们可以使用我们的实现来存储和检索值。 ``` >>> d = dictionary() >>> d('setitem', 3, 9) >>> d('setitem', 4, 16) >>> d('getitem', 3) 9 >>> d('getitem', 4) 16 ``` 字典的这种实现并没有针对快速记录查找进行优化，因为每个调用都必须过滤所有记录。内置字典类型的效率要高得多。它的实现方式超出了本文的范围。 ### 2.4.8 分派字典 分派函数是实现抽象数据的消息传递接口的通用方法。 为了实现消息分派，到目前为止，我们已经使用了条件语句来将消息字符串与一组固定的已知消息进行比较。 内置字典数据类型提供了为键查找值的一般方法。 我们可以使用带有字符串键的字典来代替使用条件来实现分派。 [下面的](http://composingprograms.com/tutor.html#code=def+account\(initial_balance\)%3A%0A++++def+deposit\(amount\)%3A%0A++++++++dispatch%5B'balance'%5D+%2B%3D+amount%0A++++++++return+dispatch%5B'balance'%5D%0A++++def+withdraw\(amount\)%3A%0A++++++++if+amount+%3E+dispatch%5B'balance'%5D%3A%0A++++++++++++return+'Insufficient+funds'%0A++++++++dispatch%5B'balance'%5D+-%3D+amount%0A++++++++return+dispatch%5B'balance'%5D%0A++++dispatch+%3D+%7B'deposit'%3A+++deposit,%0A++++++++++++++++'withdraw'%3A++withdraw,%0A++++++++++++++++'balance'%3A+++initial_balance%7D%0A++++return+dispatch%0A%0Adef+withdraw\(account,+amount\)%3A%0A++++return+account%5B'withdraw'%5D\(amount\)%0Adef+deposit\(account,+amount\)%3A%0A++++return+account%5B'deposit'%5D\(amount\)%0Adef+check_balance\(account\)%3A%0A++++return+account%5B'balance'%5D%0A%0Aa+%3D+account\(20\)%0Adeposit\(a,+5\)%0Awithdraw\(a,+17\)%0Acheck_balance\(a\))可变帐户数据类型是作为字典实现的。 它有一个构造函数帐户和选择器check\_balance，以及存入或提取资金的函数。 此外，帐户的本地状态与实现其行为的函数一起存储在字典中。 ``` 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) ``` ![](/files/-MXUh2FF-EXal3E8F4rI) account构造函数体中的名称分派被绑定到一个字典，该字典包含帐户作为键接受的消息。 余额是一个数字，而存款和取款消息被绑定到功能。 这些函数可以访问分派字典，因此它们可以读取和更改平衡。 通过将余额存储在分派字典中而不是直接存储在帐户框架中，我们避免了在存款和取款中需要非本地语句。 操作符+=和-=在Python(和许多其他语言)中是组合查找和重新赋值的简写。 下面的最后两行是等价的。 ``` >>> a = 2 >>> a = a + 1 >>> a += 1 ``` ### 2.4.9 传播约束 可变数据允许我们模拟带有变化的系统，但也允许我们构建新的抽象类型。 在这个扩展的例子中，我们结合了非局部赋值、列表和字典来建立一个支持多个方向计算的基于约束的系统。 将程序表示为约束是声明式编程的一种类型，在这种编程中，程序员声明要解决的问题的结构，但抽象出如何计算问题的解决方案的细节。 传统上，计算机程序被组织为单向计算，它对预先指定的参数执行操作以产生期望的输出。 另一方面，我们经常想用数量之间的关系来建模系统。 例如，我们以前考虑过理想气体定律，它通过玻尔兹曼常数(k)将理想气体的压力(p)、体积(v)、量(n)和温度(t)联系起来。 $$p \* v = n \* k \* t$$ 这样的方程不是单向的。 给定任意四个量，我们可以用这个方程来计算第五个量。 然而，如果把这个方程翻译成传统的计算机语言，我们将不得不从其他四个计算量中选择一个来计算。 因此，计算压力的函数不能用来计算温度，即使这两个量的计算来自同一个方程。 在本节中，我们概述线性关系一般模型的设计。 我们定义了存在于数量之间的原始约束，例如一个加法器(a, b, c)约束，它强制执行数学关系a + b = c。 我们还定义了一种组合的方法，以便原始约束可以组合起来表示更复杂的关系。 在这方面，我们的程序类似于一种编程语言。 我们通过构建一个由连接器连接约束的网络来组合约束。 连接器是“保存”值的对象，可以参与一个或多个约束。 例如，我们知道华氏温度和摄氏温度之间的关系是 $$9 \* c = 5 \* (f - 32)$$ 这个方程是c和f之间的一个复杂的约束。这个约束可以看作是一个由原始加法器、乘法器和常数约束组成的网络。 ![](/files/-MXUi_7QMFmnQgwnL77r) 在这个图中，我们看到在左边有一个三端乘法器，标记为a、b和c。这些端子将倍增器连接到网络的其余部分，如图所示：a端连接到一个连接器celsius，它将保持摄氏温度。 b端连接到连接器w，该连接器连接到常数9。 乘法器限定为a和b乘积的c端连接到另一个乘法器的c端，乘法器的b连接到常数5，a连接到求和约束中的一项。 该网络的计算过程如下：当一个连接器是给定一个值(由用户或通过它与约束框)，它唤醒所有相关的约束(只是唤醒了它的限制除外)通知他们它有了值。 然后，每个被唤醒的约束框轮询其连接器，看看是否有足够的信息来确定连接器的值。 如果是，则该框将设置该连接器，然后该连接器将唤醒它的所有相关约束，依此类推。 例如，在摄氏温度和华氏温度之间的转换中，w、x和y立即被常数方框分别设置为9、5和32。 连接器唤醒乘法器和加法器，确定它们是否没有足够的信息进行。 如果用户(或网络的其他部分)将celsius连接器设置为一个值(比如25)，最左边的乘数将被唤醒，它将u设置为25 \* 9 = 225。 然后u唤醒第二个乘法器，将v设置为45，v唤醒加法器，将华氏连接器设置为77。 使用约束系统。 为了使用约束系统来执行上面概述的温度计算，我们首先通过调用连接器构造函数创建两个命名连接器，celsius和fahrenheit。 ``` >>> celsius = connector('Celsius') >>> fahrenheit = connector('Fahrenheit') ``` 然后，我们将这些连接器连接到一个反映上面图的网络中。函数converter在网络中组装各种连接器和约束。 ``` >>> def converter(c, f): """Connect c to f with constraints to convert from Celsius to Fahrenheit.""" 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) ``` ``` >>> converter(celsius, fahrenheit) ``` 我们将使用消息传递系统来协调约束和连接器。 约束是本身不保存局部状态的字典。 它们对消息的响应是非纯函数，这些函数更改它们所约束的连接器。 连接器是保存当前值并响应操纵该值的消息的字典。 约束不会直接更改连接器的值，而是通过发送消息来更改，以便连接器可以通知其他约束以响应更改。 通过这种方式，连接器代表一个数字，但也封装连接器行为。 我们可以发送给连接器的一条消息是设置其值。 这里，我们(“用户”)将摄氏度的值设置为25。 ``` >>> celsius['set_val']('user', 25) Celsius = 25 Fahrenheit = 77.0 ``` 不仅celsius的值会变为25，而且它的值会通过网络传播，因此celsius也会发生变化。这些更改将被打印出来，因为我们在构造这两个连接器时对它们进行了命名。 现在我们可以尝试将华氏温度设置为一个新值，比如212。 ``` >>> fahrenheit['set_val']('user', 212) Contradiction detected: 77.0 vs 212 ``` 连接器抱怨它感觉到一个矛盾：它的值是77.0，有人试图将它设置为212。如果我们真的想用新的值重用网络，我们可以告诉摄氏度忘记它的旧值： ``` >>> celsius['forget']('user') Celsius is forgotten Fahrenheit is forgotten ``` 连接器celsius发现最初设置其值的用户现在正在收回该值，因此celsius同意丢失其值，并将此事实通知网络的其他部分。这个信息最终传播到华氏度，华氏度现在发现它没有理由继续相信自己的值是77。因此，它也放弃了它的价值。 现在fahrenheit没有值了，我们可以将其设置为212： ``` >>> fahrenheit['set_val']('user', 212) Fahrenheit = 212 Celsius = 100.0 ``` 当这个新值通过网络传播时，它将强制摄氏度的值为100。我们用同样的网络来计算给定华氏温度下的摄氏度和给定摄氏度下的华氏温度。这种计算的非方向性是基于约束的系统的显著特征。 实施约束系统。正如我们所看到的，连接器是将消息名称映射到函数和数据值的字典。我们将实现响应以下消息的连接器： * 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']\()表示某个连接到约束的连接器忘记了它的值。 当约束接收到这些消息时，它们会将它们适当地传播到其他连接器。 加法器函数构造一个加法器约束在三个连接器,在前两个必须添加第三：a + b = c。支持多向约束传播,加法器还必须指定它减去从c b得到和减去b c得到一样。 ``` >>> from operator import add, sub >>> def adder(a, b, c): """The constraint that a + b = c.""" return make_ternary_constraint(a, b, c, add, sub, sub) ``` 我们想实现一个通用的三元约束，它使用来自adder的三个连接器和三个函数来创建一个接受new\_val和forget消息的约束。对消息的响应是本地函数，它们被放置在一个称为约束的字典中。 ``` >>> def make_ternary_constraint(a, b, c, ab, ca, cb): """The constraint that ab(a,b)=c and ca(c,a)=b and 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 ``` 称为constraint的字典是一个分派字典，也是约束对象本身。 它响应约束接收的两条消息，但也在调用其连接器时作为源参数传递。 当约束被告知它的一个连接器有一个值时，就会调用约束的局部函数new\_value。 这个函数首先检查a和b是否都有值。 如果是，它告诉c将它的值设置为函数ab的返回值，在加法器的情况下，返回值是add。 约束将自身(constraint)作为连接器的源参数传递，连接器是加器对象。 如果a和b都没有值，那么约束将检查a和c，以此类推。 如果约束被告知它的一个连接器忘记了它的值，它会请求它的所有连接器现在忘记它们的值。 (只有那些由这个约束设置的值实际上会丢失。) 乘法器与加法器非常相似。 ``` >>> from operator import mul, truediv >>> def multiplier(a, b, c): """The constraint that a * b = c.""" return make_ternary_constraint(a, b, c, mul, truediv, truediv) ``` 常量也是一个约束，但它从不发送任何消息，因为它只涉及它在构造时设置的单个连接器。 ``` >>> def constant(connector, value): """The constraint that connector = value.""" constraint = {} connector['set_val'](constraint, value) return constraint ``` 这三个约束条件足以实现我们的温度转换网络。 **代表连接器。** 连接器表示为包含值的字典，但也具有具有本地状态的响应函数。 连接器必须跟踪为其提供当前值的信息提供者，以及它参与的约束列表。 构造函数连接器具有用于设置和遗忘值的本地函数，这些值是对来自约束的消息的响应。 ``` >>> def connector(name=None): """A connector between constraints.""" 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 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 ``` 连接器是约束用于与连接器通信的5条消息的分派字典。 四个响应是函数，最后一个响应是值本身。 当请求设置连接器的值时，将调用本地函数set\_value。 如果连接器目前并没有一个值，它会将其值设置并记住线人，源约束，要求要设置的值，然后连接器将通知所有的参与约束除了要求要设置的值的约束。这是使用下面的迭代函数来完成。 ``` >>> def inform_all_except(source, message, constraints): """Inform all constraints of the message, except source.""" for c in constraints: if c != source: c[message]() ``` 如果要求连接器忘记其值，它将调用本地函数forget-value，该函数首先检查以确保请求来自最初设置值的相同约束。 如果是，连接器将通知其关联约束值丢失的情况。 对消息has\_val的响应指示连接器是否有值。 对消息连接的响应将源约束添加到约束列表中。 我们所设计的约束程序引入了许多思想，这些思想将在面向对象编程中再次出现。 约束和连接器都是通过消息进行操作的抽象。 当更改连接器的值时，它将通过消息进行更改，该消息不仅更改了值，还验证了它(检查源)并传播其效果(通知其他约束)。 事实上，我们将在本章的后面部分使用一个类似的字典体系结构，包含字符串值键和函数值来实现一个面向对象的系统。