Python如何實現SICP賦值與局部狀態
- WBOY轉載
- 2023-06-05 14:10:40674瀏覽
所謂模組化，也即使這些系統能夠「自然地」劃分為一些內聚（coherent）的部分，使這些部分可以分別進行開發和維護。
在哲學上，組織程序的方式與我們對被模擬系統的認識息息相關。接下來我們要研究兩個特色很鮮明的組織策略，它們源自於對於系統結構的兩種非常不同的「世界觀」（world views）。
第一種策略將注意力集中在物件（objects）上，將一個大型系統看成不同物件的集合，它們的狀態和行為可能隨著時間不斷變化。
另一種組織策略將注意力集中在流經系統的訊息流（streams of information）上，非常像EE工程師觀察一個訊號處理系統。
這兩種策略都對程式設計提出了具有重要意義的語言要求。對於物件途徑而言，我們必須專注於物件可以如何變化而又保持其標識（identity）。這將迫使我們拋棄前面說講過的計算的代換模型，轉向更機械式的，理論上也更不容易把握的計算的環境模型(environment model)。在處理物件、變化和標識時，各種困難的根源在於我們需要在這個計算模型中與時間搏鬥，如果引入並發後還會變得更糟。流方式將我們的模型中的模擬時間與求值過程中的事件發生順序進行解耦，我們將透過一種稱為延時求值(lazy evaluation)的技術做到這一點。
1 局部狀態變數
在物件世界觀裡，我們想要讓計算物件具有隨著時間變化的狀態，而這就需要讓每個計算物件有自己的一些局部狀態變數。現在讓我們來對一個銀行帳戶支取現金的情況做一個模擬。我們將用一個流程withdraw完成此事，它有一個參數amount表示支取的現金量。如果餘額足夠則withdraw傳回支取之後帳戶裡剩餘的款額，否則回傳訊息Insufficient funds(金額不足)。假設開始時帳戶有100元錢，在不斷使用withdraw的過程中我們可能得到下面的回應序列：
withdraw(25) # 70 withdraw(25) # 50 withdraw(60) # "In sufficient funds" withdraw(15) # 35
在這裡可以看到表達式widthdraw(25 )求值了兩次，但它產生的值卻不同，這是過程的一種新的行為方式。之前我們看到的過程都可以看做是一些可計算的數學函數的描述，兩次呼叫一個同一個過程，總是會產生相同的結果。
為了實現withdraw，我們可以用一個全域變數balance表示帳戶裡的現金金額，並將withdraw定義為一個存取balance的過程。下面是balance和widthdraw的定義：
balance = 100
def withdraw(amount):
global balance
if balance > amount:
balance = balance - amount
return balance
else:
return "Insufficient funds"#雖然withdraw能像我們期望的那樣工作，變數balance卻表現出一個問題。如上所示，balance是定義在全域環境中的一個名字，因此可以被任何程序檢查或修改。我們希望將balance做成withdraw內部的東西，因為這將使withdraw成為唯一能直接存取balance的過程，而其他過程只能間接地（透過對withdraw的呼叫）存取balance。這樣才能準確地模擬相關的概念：balance是一個只有withdraw使用的局部狀態變數，用來保存帳戶狀態的變化軌跡。
我們可以透過下面的方式重寫withdraw，讓balance成為它內部的東西：
def new_withdraw():
balance = 100
def inner(amount):
nonlocal balance
if balance > amount:
balance = balance - amount
return balance
else:
return "Insufficient funds"
return inner
W = new_withdraw()
print(W(25)) # 70
print(W(25)) # 50
print(W(60)) # "In sufficient funds"
print(W(15)) # 35這裡的做法是用創建起一個包含局部變數balance的環境，並使它初始值為100。在這個環境裡，我們創建了一個過程inner，它以amount作為一個參數，其行為就像是前面的withdraw過程。這樣最終回傳的過程就是new_withdraw，它的行為方式就像是withdraw，但其中的變數確實其他任何過程都不能存取的。用程式設計語言的行話，我們說變數balance被稱為是封裝在new_withedraw過程裡面。
将赋值语句与局部变量相结合，形成了一种具有一般性的程序设计技术，我们将一直使用这种技术区构造带有局部状态的计算对象。但这一技术也带来了麻烦，我们之前在代换模型中说，应用（apply）一个过程应该解释为在将过程的形式参数用对应的值取代之后再求值这一过程。但现在出现了麻烦，一旦在语言中引进了赋值，代换就不再适合作为过程应用的模型了（我们将在3.1.3节中看到其中的原因）。我们需要为过程应用开发一个新模型，这一模型将在3.2节中介绍。现在我们要首先检查new_withdraw所提出的问题的几种变形。
下面过程make_withdraw能创建出一种“提款处理器”。make_withdraw的形式参数balance描述了有关账户的初始余额值。
def make_withdraw(balance):
def withdraw(amount):
nonlocal balance
if balance > amount:
balance = balance - amount
return balance
else:
return "Insufficient funds"
return withdraw下面用make_withdraw创建了两个对象：
W1 = make_withdraw(100) W2 = make_withdraw(100) print(W1(50)) # 50 print(W2(70)) # 30 print(W2(40)) # Insufficient funds print(W1(40)) # 10
我们可以看到，W1和W2是相互完全独立的对象，每一个都有自己的局部状态变量balance，从一个对象提款与另一个毫无关系。
我们可以创建可以存款和取款的对象，这样就可以模拟简单的银行账户。以下是一个过程，它会返回一个“银行账户对象”，该对象具有特定的初始余额
def make_account(balance):
def withdraw(amount):
nonlocal balance
if balance >= amount:
balance = balance - amount
return balance
else:
return "In sufficient funds"
def deposit(amount):
nonlocal balance
balance = balance + amount
return balance
def dispatch(m):
nonlocal balance
if m == "withdraw":
return withdraw
if m == "deposit":
return deposit
else:
raise ValueError("Unkown request -- MAKE_ACOUNT %s" % m)
return dispatch对于make_acount的每次调用将设置好一个带有局部状态变量balance的环境，在这个环境里，make_account定义了能够访问balance过程deposit和withdraw，另外还有一个过程dispatch，它以一个“消息”做为输入，返回这两个局部过程之一。过程dispatch本身将会被返回，做为表示有关银行账户对象的值。这正好是我们在2.4.3节中看到过的程序设计的消息传递风格，当然这里将它与修改局部变量的功能一起使用。
acc = make_account(100)
print(acc("withdraw")(50)) # 50
print(acc("withdraw")(60)) # In sufficient funds
print(acc("deposit")(40)) # 90
print(acc("withdraw")(60)) # 30对acc的每次调用将返回局部定义的deposit或者withdraw过程，这个过程随后被应用于给定的amount。就像make_withdraw一样，对make_amount的另一次调用
acc2 = make_acount(100)
将产生出另一个完全独立的账户对象，维持着它自己的局部balance。
这里再举一个实现累加器的例子（事实上该例子在《黑客与画家》[2]第13章中也有出现，被用来说明不同编程语言编程能力的差异）。累加器是一个过程，反复用数值参数调用它，就会使得它的各个参数累加到一个和中。每次调用时累加器将返回当前的累加和。请写出一个生成累加器的过程make_accumulator，它所生成的每个累加器维持着一个独立的和。传给make_accumulator的输入描述了和的初始值。其Python实现代码如下：
def make_accumulator(sum_value):
def accumulator(number):
nonlocal sum_value
sum_value += number
return sum_value
return accumulator
A = make_accumulator(5)
print(A(10)) # 15
print(A(10)) # 25当然，Common Lisp的写法将更为简单：
(defun make_accumulator (sum_value) (lambda (number) (incf sum_value number)))
Ruby的写法与Lisp几乎完全相同：
def make_accumulator (sum_value)
lambda {|number| sum_value += number } end2 引进赋值带来的利益
正如下面将要看到的，将赋值引进所用的程序设计语言中，将会使我们陷入困难概念问题的丛林之中。但无论如何，将系统看做是带有局部状态的对象的集合，也是一种维护模块化设计的强有力技术。先让我们看一个简单的例子：如何设计出一个过程rand，每次它被调用就会返回一个随机选出的整数。这里的“随机选择”的意思并不清楚，其实我们希望的就是对rand的反复调用将产生一个具有均匀分布统计性质的序列。假定我们已经有一个过程rand-update，它的性质就是，如果从一个给点的数x1开始，执行下面操作
x2 = random_update(x1) x3 = random_update(x2)
得到的值序列x1、x2，x3，...将具有我们所希望的性质。
实现random_update的一种常见方法就是采用将xx更新为ax+bax+b取模mm的规则，其中a、b和m都是适当选出的整数。比如：
def rand_update(x):
a = int(pow(7, 5))
b = 0
m = int(pow(2, 31)) - 1
return (a * x + b) % mKnuth的TAOCP第二卷(半数值算法)[3]中包含了有关随机数序列和建立起统计性质的深入讨论。注意，random_update是计算一个数学函数，两次给它同一个输入，它将产生同一个输出。这样，如果“随机”强调的事序列中每个数与前面的数无关的话，由random_update生成的数序列肯定不是“随机的”。在“真正的随机性”与所谓伪随机序列（由定义良好的确定性计算产生出的但又具有适当统计性质的序列）之间的关系是一个非常复杂的问题，涉及到数学和哲学中的一些困难问题，Kolmogorov、Solomonoff、Chaitin为这些问题做出了很多贡献，从Chaitin 1975[4]可以找到有关讨论。
现在回到当前的话题来。我们已经实现好了random_update，接下来在此基础上实现rand。我们可以将rand实现为一个带有局部状态变量x的过程，其中将这个变量初始化为某个固定值rand_init。对rand的每次调用算出当前xx值的random_update值：
def make_rand(random_init):
x = random_init
def inner():
nonlocal x
x = rand_update(x)
return x
return inner
rand = make_rand(42)
print(rand()) # 705894
print(rand()) # 1126542223当然，即使不用赋值，我们也可以通过简单地调用rand_update，生成同样的随机序列。但是这意味着程序中任何使用随机数的部分都必须显式地记住，需要将x的当前值传给rand_update作为参数，这样会徒增烦恼。
接下来，我们考虑用随机数实现一种称为蒙特卡罗模拟的技术。
蒙特卡罗方法是通过从一个大集合中随机选择试验样本，以统计估计为基础做出推断的方法。例如，6/π26/π2是随机选取的两个整数之间没有公共因子（也即最大公因子为1）的概率。我们可以利用这一事实做出ππ的近似值（这个定理出自Cesaro，见TAOCP第二卷[3]4.5.2的讨论和证明）。
这一程序的核心是过程monte_carlo，它以某个试验的次数（trails）以及这个试验本身（experiment）作为参数。试验用一个无参过程cesaro_test表示，返回的是每次运行的结果为真或假。monte_carlo运行指定次数的这个试验，它返回所做的这些试验中得到真的比例。
rand = make_rand(42)
import math
def estimate_pi(trials):
return math.sqrt(6 / monte_carlo(trials, cesaro_test))
def cesaro_test():
return math.gcd(rand(), rand()) == 1
def monte_carlo(trials, experiment):
def iter(trials_remaining, trials_passed):
if trials_remaining == 0:
return trials_passed / trials
elif cesaro_test():
return iter(trials_remaining - 1, trials_passed + 1)
else:
return iter(trials_remaining - 1, trials_passed)
return iter(trials, 0)
print(estimate_pi(500)) # 3.178208630818641现在让我们试一试不用rand，直接用rand_update完成同一个计算。如果我们不使用赋值去模拟局部状态，那么将不得不采取下面的做法：
random_init = 42
def estimate_pi(trials):
return math.sqrt(6 / random_gcd_test(trials, random_init))
def random_gcd_test(trials, initial_x):
def iter(trials_remaining, trials_passed, x):
x1 = rand_update(x)
x2 = rand_update(x1)
if trials_remaining == 0:
return trials_passed / trials
elif math.gcd(x1, x2) == 1:
return iter(trials_remaining - 1, trials_passed + 1, x2)
else:
return iter(trials_remaining - 1, trials_passed, x2)
return iter(trials, 0, initial_x)
print(estimate_pi(500)) # 3.178208630818641虽然这个程序还是比较简单的，但它却在模块化上打开了一些令人痛苦的缺口，因为它需要显式地去操作随机数x1和x2，并通过一个迭代过程将x2传给random_update作为新的输入。这种对于随机数的显式处理与积累检查结果的结构交织在一起。此外，就连上层的过程estimate_pi也必须关心提供随机数的问题。由于内部的随机数生成器被暴露了出来，进入了程序的其它部分，我们很难将蒙特卡罗方法的思想隔离出来了。反观我们在程序的第一个版本中，由于通过赋值将随机数生成器的状态隔离在过程rand的内部，因此就使随机数生成的细节完全独立于程序的其它部分了。
由上面的蒙特卡洛方法实例体现的一种普遍性系统设计原则就是：对于行为随时间变化的计算对象（如银行账户和随机数生成器），我们需要设置局部状态变量，并用对这些变量的赋值去模拟状态的变化。
3 引进赋值的代价
正如上面所看到的，赋值操作使我们可以模拟带有局部状态的对象。然而，这一获益也有一个代价，也即使我们的程序设计语言不能再用前面所提到过的代换模型解释了。进一步说，任何具有“漂亮”数学性质的简单模型，都不可能继续适合作为处理程序设计语言里的对象和赋值的框架了。
只要我们不适用赋值，以同样参数对同一过程的两次求值一定产生出同样的结果，因此就可以认为过程是在计算数学函数。就像我们在之前的章节中所提到的那样，不用任何复制的程序设计称为函数式程序设计。
要理解复制将怎样使事情复杂化了，考虑3.1.1节中make_withdraw过程的一个简化版本，其中不再关注是否有足够余额的问题：
def make_simplified_withdraw(balance):
def simplified_withdraw(amount):
nonlocal balance
balance = balance - amount
return balance
return simplified_withdraw
W = make_simplified_withdraw(25)
print(W(20)) # 5
print(W(10)) # -5请将这一过程与下面make_decrementer过程做一个比较，该过程里没有用赋值运算：
def make_decrementer(balance):
return lambda amount: balance - amountmake_decrementer返回的是一个过程，该过程从指定的量balance中减去其输入，但顺序调用时却不会像make_simplifed_withdraw那样产生累积的结果。
D = make_decrementer(25) print(D(20)) # 5 print(D(10)) # 15
我们可以用代换模型解释make_decrementer如何工作。例如，让我们分析一下下面表达式的求值过程：
make_decrementer(25)(20)
首先简化组合式中的操作符，用25代换make_decrementer体里的balance，这样就规约出了下面的表达式：
(lambda amount: 25 - amount) (20)
随后应用运算符，用20代换lambda表达体里的amount：
25 - 20
最后结果是5。
现在再来看看，如果将类似的代换分析用于make_simplifed_withdraw，会出现什么情况：
make_simplified_withdraw(25)(20)
先简化其中的运算符，用25代换make_simplified_withdraw体里的balance，这样就规约出了下面的表达式（注意，Python的lambda表达式里不能进行赋值运算（据Guido说是故意加以限制从而防止Python成为一门函数式编程语言），下面这个式子不能在Python解释器中运行，只是为了方便大家理解）：
(lambda amount： balance = 25 - amount)(25)(20)
这里我们没有代换赋值表达式里的balance，因为赋值符号=的左边部分并不会进行求值，如果代换掉它，得到的25 = 25 - amount根本就没有意义。
现在用20代换lambda表达式体里的amount：
(balance = 25 - 20)(25)
如果我们坚持使用代换模型，那么就必须说，这个过程应用的结果是首先将balance设置为5，而后返回25作为表达式的值。这样得到的结果当然是错误的。为了得到正确答案，我们不得不对balance的第一次出现（在=作用之前）和它的第二次出现(在=作用之后)加以区分，而代换模型根本无法完成这件事情。
这里的麻烦在于，从本质上说代换的最终基础就是，这一语言里的符号不过是作为值的名字。而一旦引入了赋值运算=和变量的值可以变化的想法，一个变量就不再是一个简单的名字了。现在的一个变量索引着一个可以保存值的位置（place），而存储再那里的值也是可以改变的。在3.2节里将会看到，在我们的计算模型里，环境将怎样扮演者“位置”的角色。
同一和变化
这里暴露出的问题远远不是简单地打破了一个特定计算模型，它还使得以前非常简单明了的概念现在都变得有问题了。首先考虑两个物体实际上“同一”（“the same”）的概念。
假定我们用同样的参数调用make_decrementer两次，就会创建出两个过程：
D1 = make_decrementer(25) D2 = make_decrementer(25)
D1和D2是同一的吗？“是”是一个可接受的回答，因为D1和D2具有同样的计算行为——都是同样的将会从其输入里减去25点过程。事实上，我们确实可以在任何计算中用D1代替D2而不会改变结果，如下所示：
print(D1(20)) # 5 print(D1(20)) # 5 print(D2(20)) # 5
于此相对应的是调用make_simplified_withdraw两次：
W1 = make_simplified_withdraw(25) W2 = make_simplified_withdraw(25)
W1和W2是同一的吗？显然不是，因为对W1和W2的调用会有不同的效果，下面的调用显示出这方面的情况：
print(W1(20)) # 5 print(W1(20)) # -15 print(W2(20)) # 5
虽然W1和W2都是通过对同样表达式make_simplified_withdraw(25)求值创建起来的东西，从这个角度可以说它们“同一”。但如果说在任何表达式里都可以用W1代替W2，而不会改变表达式的求值结果，那就不对了。
如果一个语言支持在表达式里“同一的东西可以相互替换”的观念，这样替换不会改变有关表达式的值，这个语言就称为是具有引用透明性。而当我们的计算机语言包含赋值运算之后，就打破了引用透明性。
一旦我们抛弃了引用透明性，有关计算对象“同一”的意义问题就很难形式地定义清楚了。事实上，在我们企图用计算机程序去模拟的现实世界里，“同一”的意义本身就很难搞清楚的，这是由于“同一”和“变化”的循环定义所致：我们想要确定两个看起来同一的事物是否确实是“同一个东西”，我们一般只能去改变其中一个对象，看另一个对象是否也同样改变；但如果不观察“同一个”对象两次，看看对象的性质是否与另一次不同，我们就能确定对象是否“变化”。由是观之，我们必须要将“同一”作为一个先验观念引入（PS：这里可以参见康德的思想），否则我们就不可能确定“变化”。
现在举例说明这一问题会如何出现在程序设计里。现在考虑一种新情况，假定Peter和Paul有银行账户，其中有100块钱。关于这一事实的如下模拟：
peter_acc = make_account(100) paul_acc = make_account(100)
和如下模拟之间有着实质性的不同：
peter_acc = make_account(100) paul_acc = peter_acc
在前一种情况里，有关的两个银行账户互不相同。Peter所做的交易将不会影响Paul的账户，反之亦然。例如，当Peter拿了10块钱，Paul也取了10块钱，因此Paul账户中仍有90块钱
peter_acc("withdraw")(10)
print(paul_acc("withdraw")(10)) # 90而对于后一种情况，这里把paul_acc定义为与peter_acc是同一个东西，结果就使现在Peter和Paul共有一个共同的账户，此时当Peter取10块钱，Paul再取10块钱后，Paul就只剩80块钱了：
peter_acc("withdraw")(10)
print(paul_acc("withdraw")(10)) # 80这里一个计算对象可以通过多于一个名字访问的现象称为别名（aliasing）。这里的银行账户例子是最简单的，我们在3.3节里还将看到一些更复杂的例子，例如“不同”的数据结构共享某些部分，如果对某一个对象的修改可能由于“副作用”而修改了另一“不同的”的对象，因为这两个“不同”对象实际上只是同一个对象的不同别名，当我们忘记这一情况程序就可能出现错误。这种错误被称为副作用错误，特别难以定位和分析。因此某些人（如分布式计算大佬Lampson）就建议说，程序设计语言的设计不允许副作用或者别名。
命令式程序设计的缺陷
与函数式程序设计相对应的，广泛采用赋值的程序设计被称为命令式程序设计(imperative programming)。除了会导致计算模型的复杂性之外，以命令式风格写出的程序还容易出现一些不会在函数式程序中出现的错误。举例来说，现在重看一下在1.2.1节里的迭代求阶乘程序：
def factorial(n):
def iter(product, counter):
if counter > n:
return product
else:
return iter(counter * product, counter + 1)
return iter(1, 1)
print(factorial(4)) # 24我们也可以不通过内部迭代循环（这里假设Python支持尾递归）传递参数，而是采用更命令的风格，显式地通过赋值去更新变量product和counter的值：
def factorial(n):
product, counter = 1, 1
def iter():
nonlocal product, counter
if counter > n:
return product
else:
product = counter * product
counter = counter + 1
return iter()
return iter()
print(factorial(4)) # 24这样做不会改变程序的结果，但却会引进一个很微妙的陷阱。怎样才能确定两个赋值的顺序？虽然上述程序是正确的，但如果颠倒这两个赋值的顺序会怎样？
counter = counter + 1 product = counter * product
就会产生出与上面不同的错误结果：
print(factorial(4)) # 120， Wrong!
以上是Python如何實現SICP賦值與局部狀態的詳細內容。更多資訊請關注PHP中文網其他相關文章！