いわゆるモジュール化とは、これらのシステムをいくつかの一貫した部分に「自然に」分割できるため、これらの部分を個別に開発および保守できることを意味します。 哲学的には、プログラムの編成方法は、シミュレートされるシステムの理解と密接に関係しています。次に、システム構造の 2 つの非常に異なる「世界観」に由来する 2 つの特徴的な組織戦略を検討します。
最初の戦略は、
オブジェクトもう 1 つの組織戦略は、EE エンジニアが信号処理システムを観察するのと同じように、システム内を流れる情報のストリームに焦点を当てています。
どちらの戦略も、プログラミングに重要な言語要件を課します。オブジェクトアプローチの場合、オブジェクトがそのアイデンティティを維持しながらどのように変化できるかに焦点を当てる必要があります。これにより、前述の計算の代替モデルを放棄し、より機械的で理論的には理解しにくい計算の 環境モデル (環境モデル)に頼らざるを得なくなります。オブジェクト、変更、アイデンティティを扱う際の難しさの根源は、この計算モデルで取り組む必要がある時間にあり、同時実行性が導入されるとさらに悪化します。ストリーミングにより、モデルのシミュレーション時間が評価プロセスのイベントの順序から切り離されます。遅延評価と呼ばれる手法を通じてこれを行います。
オブジェクトの世界観では、コンピューティング オブジェクトには時間の経過とともに変化する状態が必要であり、そのためには各コンピューティング オブジェクトが独自のローカル状態変数を持つ必要があります。 。では、銀行口座から現金を引き出すシミュレーションをしてみましょう。これを達成するために、プロシージャ withdraw を使用します。このプロシージャには、引き出した現金の金額を示すパラメータ amount があります。残高が十分な場合、
withdraw (金額不足) を返します。最初に口座に 100 元があると仮定すると、withdraw
を継続的に使用すると、次の応答シーケンスが得られる可能性があります: <div class="code" style="position:relative; padding:0px; margin:0px;"><pre class="brush:plain;">withdraw(25) # 70
withdraw(25) # 50
withdraw(60) # "In sufficient funds"
withdraw(15) # 35</pre><div class="contentsignin">ログイン後にコピー</div></div>
ここで、式 widthdraw が確認できます。 (25 )
は 2 回評価されますが、生成される値は異なります。これは、プロシージャの新しい動作方法です。これまで見てきたプロシージャは、計算可能な数学関数の記述とみなすことができ、同じプロシージャを 2 回呼び出すと、常に同じ結果が得られます。 withdraw
を実現するには、グローバル変数
を使用してアカウント内の現金の金額を表し、withdraw
を定義します。 access
プロセスとして。 balance
と widthdraw
の定義は次のとおりです。 <div class="code" style="position:relative; padding:0px; margin:0px;"><pre class="brush:py;">balance = 100
def withdraw(amount):
global balance
if balance > amount:
balance = balance - amount
return balance
else:
return "Insufficient funds"</pre><div class="contentsignin">ログイン後にコピー</div></div>
withdraw
は期待どおりに機能しますが、変数 balance
しかし、それは問題を示しています。上で示したように、balance
はグローバル環境で定義された名前であるため、どのプロセスでも検査または変更できます。
を withdraw
の内部のものにしたいと考えています。そうすることで、withdraw
が balance
に直接アクセスできる唯一のプロセスになるためです。他のプロシージャは、balance
に間接的にのみアクセスできます (withdraw
の呼び出しを通じて)。このようにして、関連する概念を正確にシミュレートできます。残高は、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
を含み、その初期値を 100 にします。この環境では、amount
をパラメータとして受け取り、前の withdraw
プロシージャと同様に動作するプロシージャ
を作成します。最後に返されるプロセスは new_withdraw
で、withdraw
と同様に動作しますが、その中の変数には他のプロセスからアクセスできません。プログラミング言語の専門用語では、変数 balance
は new_withedraw
プロシージャ内で encapsulated
と呼ばれます。 <p>将赋值语句与局部变量相结合,形成了一种具有一般性的程序设计技术,我们将一直使用这种技术区构造带有局部状态的计算对象。但这一技术也带来了麻烦,我们之前在代换模型中说,应用(apply)一个过程应该解释为在将过程的形式参数用对应的值取代之后再求值这一过程。但现在出现了麻烦,一旦在语言中引进了赋值,代换就不再适合作为过程应用的模型了(我们将在3.1.3节中看到其中的原因)。我们需要为过程应用开发一个新模型,这一模型将在3.2节中介绍。现在我们要首先检查<code>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 } end
正如下面将要看到的,将赋值引进所用的程序设计语言中,将会使我们陷入困难概念问题的丛林之中。但无论如何,将系统看做是带有局部状态的对象的集合,也是一种维护模块化设计的强有力技术。先让我们看一个简单的例子:如何设计出一个过程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) % m
Knuth的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.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 - amount
make_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 中国語 Web サイトの他の関連記事を参照してください。