How Python implements SICP assignment and local state

The so-called modularization means that these systems can be "naturally" divided into some coherent parts so that these parts can be developed and maintained separately.

Philosophically, the way a program is organized is closely related to our understanding of the system being simulated. Next we'll examine two distinctive organizational strategies that stem from two very different "world views" of system structure.

The first strategy focuses on

objects
• (objects), viewing a large system as a collection of different objects, their states and behaviors may It keeps changing over time.
  Another organizational strategy focuses on the streams of information flowing through the system, much like an EE engineer looking at a signal processing system .

• Both strategies impose significant language requirements on programming. For the object approach, we must focus on how objects can change while maintaining their identity. This will force us to abandon the substitution model of calculation mentioned earlier and turn to the environment model

  (environment model) of calculation that is more mechanical and theoretically less easy to grasp. The root of the difficulty in dealing with objects, changes, and identities is the time we need to grapple with in this computational model, which gets even worse when concurrency is introduced. Streaming decouples the simulation time in our model from the order of events in the evaluation process. We will do this through a technique called lazy evaluation. .

1 Local state variables

In the object world view, we want the computing object to have a state that changes over time, and this requires each computing object to have its own local state variables. . Now let's do a simulation of withdrawing cash from a bank account. We will use a procedure withdraw to accomplish this, which has a parameter amount

indicating the amount of cash withdrawn. If the balance is sufficient,

withdraw

returns the remaining amount in the account after withdrawal, otherwise returns the message

Insufficient funds (insufficient amount). Assuming that there is 100 yuan in the account at the beginning, we may get the following response sequence during the continuous use of withdraw:

withdraw(25) # 70
withdraw(25) # 50
withdraw(60) # "In sufficient funds"
withdraw(15) # 35

Here you can see the expression widthdraw(25 ) is evaluated twice, but the values ​​it produces are different, which is a new way for the procedure to behave. The procedures we have seen before can be regarded as descriptions of some computable mathematical functions. Calling the same procedure twice will always produce the same result. In order to achieve withdraw

, we can use a global variable

balance to represent the amount of cash in the account, and define withdraw

as an access

balance process. Here are the definitions of balance and widthdraw:

balance = 100
def withdraw(amount):
    global balance
    if balance > amount:
        balance = balance - amount
        return balance
    else: 
        return "Insufficient funds"

While withdraw works as we expect, the variable balanceBut it shows a problem. As shown above, balance

is a name defined in the global environment and can therefore be inspected or modified by any process. We want to make

balance something internal to withdraw, because that would make withdraw the only process that has direct access to balance, and Other procedures can only access balance indirectly (through a call to withdraw). In this way, the relevant concepts can be accurately simulated: balance is a local state variable used only by withdraw, which is used to save the change track of the account status. We can rewrite withdraw in the following way, making balance become something inside it:

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

The approach here is to create Create an environment containing the local variable

balance and make its initial value 100. In this environment, we create a procedure inner that takes amount

as a parameter and behaves like the previous

withdraw procedure. The final returned process is new_withdraw, which behaves like withdraw, but the variables in it are indeed inaccessible to any other process. In the jargon of programming languages, we say that the variable balance is called encapsulatedinside the new_withedraw procedure.

将赋值语句与局部变量相结合，形成了一种具有一般性的程序设计技术，我们将一直使用这种技术区构造带有局部状态的计算对象。但这一技术也带来了麻烦，我们之前在代换模型中说，应用（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 } end

2 引进赋值带来的利益

正如下面将要看到的，将赋值引进所用的程序设计语言中，将会使我们陷入困难概念问题的丛林之中。但无论如何，将系统看做是带有局部状态的对象的集合，也是一种维护模块化设计的强有力技术。先让我们看一个简单的例子：如何设计出一个过程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 引进赋值的代价

正如上面所看到的，赋值操作使我们可以模拟带有局部状态的对象。然而，这一获益也有一个代价，也即使我们的程序设计语言不能再用前面所提到过的代换模型解释了。进一步说，任何具有“漂亮”数学性质的简单模型，都不可能继续适合作为处理程序设计语言里的对象和赋值的框架了。

只要我们不适用赋值，以同样参数对同一过程的两次求值一定产生出同样的结果，因此就可以认为过程是在计算数学函数。就像我们在之前的章节中所提到的那样，不用任何复制的程序设计称为函数式程序设计。

要理解复制将怎样使事情复杂化了，考虑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!

The above is the detailed content of How Python implements SICP assignment and local state. For more information, please follow other related articles on the PHP Chinese website!