函数式编程：密码学和素数

大家好，欢迎来到IT知识分享网。

3.1　密码学和素数

外星人坐在咖啡馆里，享受着他们精心制作的含咖啡因的饮料。他们要购买全套的《星球大战》传奇，但无法通过流传输到自己的星球！他们准备输入信用卡号，从Nile网站完成购买，但他们停下来想了一下：当他们的财务信息通过Wi-Fi和许多互联网节点到达Nile网站，再到他们的银行授权这次购买时，如何保护信息的安全。这种担心很合理。好消息是，即使通信链路是开放的和公开的，加密技术仍可确保此类交易的安全。

很快就要回家了，但先要再买一些东西！

RSA是最广泛使用的加密策略之一，它是3位设计者Ron Rivest、Adi Shamir和Leonard Adleman的姓氏首字母缩写。RSA的工作方式如下：在线商店具有自己的数学函数（可公开获得），所有用户都可以使用该函数对数据进行加密，然后再通过网络进行传输。（确切地说，浏览器或其他软件可以代表用户执行此操作。）仅将生成的加密数据从一个地方发送到另一个地方，即使在不安全的通道上也可以保证安全。设计该数学函数，以便任何人都可以轻松地使用它来加密数据，而只有商店（或其他受信任的代理，例如银行）可以“恢复”或“反转”该函数。因此，只有受信任的代理才能解密数据并恢复原始的敏感信息。

因为他们设计了密码系统RSA，Rivest、Shamir和Adleman获得了著名的图灵奖。

请注意，我们要发送的任何数据总是可以表示为数字。无论是什么数据，这都是真的，但是如果数据已经是一个数字（例如信用卡号），则尤其清楚。假设Nile网站告诉其用户，用加密函数f(x) = 2x来加密数字数据x。

对于这个简化的例子，我们可以很容易地加密我们要发送的任何数字，只需将它加倍即可。不幸的是，任何人都可以简单地将消息除以2，从而解密消息，这使得加密函数根本不安全。

真正的RSA方案使用较复杂的函数，但仅稍微复杂一些。如果x是我们的信用卡号，则RSA使用函数f(x) = xe mod n对其进行加密，其中e和n是精心选择的常数。上一章中提到，xe mod n表示xe 除以n的余数。在Python中，这可以用表达式(x**e) % n进行计算。

事实证明，如果适当选择e和n，那么在线商店将能够解密该消息以检索信用卡号x。但是即使公开了e和n，也没有其他人可以解密该消息！

怎么会这样？我们如何选择e和n（并与每个人共享，使得每个人都可以加密消息），但仍然只让我们自己有解密的能力？下面是具体做法。首先，我们随机选择两个不同的大素数p和q。接下来，我们将n定义为这两个数字的乘积，n = pq。然后，我们执行两个步骤以找到适合e的值：我们计算m = ( p-1)(q-1)，然后选择e为小于m的随机素数，它也不是m的因数。这就行了！它不像加倍那么简单，但也相当简单，用一个简短的Python程序就可以表示。

这就是选择e和n的过程，这些值可以与希望发送加密信息的任何人公开共享。加密很简单：对小于n的任意x，可以通过计算xe mod n进行加密。（较大的值可以分解为较小的值，但是我们在这里不必担心。）在典型的网上购物交易中，你的浏览器将从在线商店获取e和n的公开可用值，并使用它们来加密你的信用卡号x。值e和n一起称为该商店的公钥。在密码学中，公钥是一组可以安全发布的值，但不会泄露相应的私钥。让我们用一个具体的例子来详细说明。

在我们的例子中，令p = 3和q =5。尽管它们太小而不能实际确保安全，但它们肯定是素数。现在，n = 3 × 5 = 15且m = (3-1) × (5-1) = 8。对于我们的加密指数e，我们可以选择素数3，因为它小于8，并且也不是8的因数。现在，使用值e = 3和n = 15，我们可以加密小于n的任何数字。让我们对数字13进行加密：在Python中，我们可以将133 mod 15表达为（13 ** 3）%15。结果是7。所以7是我们的加密数字，我们通过互联网将它发送到在线商店。

我认为密码学的在数学上应该称为“离散数学”！

商店如何解密这个7，以发现原来的数字实际上是13？在计算加密指数e的同时，商店还计算了解密指数d，它具有两个属性：介于1和m-1之间，并且e × d mod m = 1。由于e和m的选择方式不同，总是只有一个具有这两个属性的值（对于证明，我们听离散数学家的）。我们将该值d称为e模m的乘法逆（multiplicative inverse）。在我们的例子中，e = 3且m = 8，因此d也是3（并非总是与e相同，尽管可以相同）。我们确认e × d mod 8 = 9 mod 8 = 1。

利用这个解密指数d，在线商店可以通过计算yd mod n解密它收到的任意数字y。在我们的示例中，我们收到了加密数字y =7。我们用Python表达式((7**3) % 15)计算了73 mod 15，结果为13。确实，这就是我们刚才加密的值！请记住，虽然加密密钥e和n是公开的，但在线商店保持解密密钥d私有。能够获得d的任何人，都可以解密用加密密钥发送的任何消息。

在离散数学或算法导论课程中常常会展示该方案始终有效的证明。然而，对我们而言，更重要的问题是：“为什么这种方案是安全的？”由于值e和n是公开的，因此如果邪恶的特工能够找到最初选作n的因数的两个素数p和q，他们也可以找出m和d，然后从那里激活成功教程代码。但是，将数字n“因数分解”为素数之积是一个难计算问题。难计算问题是指用已知最好的技术，需要很长时间才能计算出来的问题。第7章更详细地探讨了该主题。但是现在，考虑一下：美国国家标准技术研究院（National Institute of Standards and Technology, NIST）估计，如果今天我们用大约900位数字的公共密钥来加密消息，那么通过因数分解的结果来解密将远远超出2042年——即便用非常快的计算机进行攻击。

3.2　一等函数

在上一章中，我们了解了Python函数，并探讨了递归的“威力”。我们研究过的程序设计风格［即由相互调用的函数（可能还会调用它们自己）构成的程序］称为函数式编程。

在Python这样的函数式编程语言中，函数是数据，就像数字、列表和字符串是数据一样。在Python之类的语言中，我们说函数是该语言的“一等公民”，因为我们可以编写一些函数，以其他函数作为其输入。我们还可以编写一些函数，以其他函数作为其返回值。在本章中，我们将探讨这些思想。首先我们来编写一个简短的程序，该程序可以有效地生成较长的素数列表。我们将构建可在RSA加密中实现加密和解密的函数。在本章结束时，你将编写一些Python程序，用于发送和接收加密数据，即只有你和你的朋友才能解密的数据。

我喜欢所有事都做到一等！

3.3　生成素数

受RSA密码学的激励，我们的首要任务是找到一种生成素数列表的方法。我们计划：先编写一个函数，确定其参数是否为素数；然后，我们可以利用该函数测试一系列连续整数是否为素数，并将是素数的整数保存在一个列表中。

如何测试单个正整数n是不是素数？根据定义，如果2～n-1的任意整数能整除n，则n不是素数。如果2～n-1没有整数能整除n，则n是素数。只要测试2～sqrt(n)的数字就足够了，但目前我们就测试2～n-1的所有可能的因数。我们将设计一个函数divisors，可以实现这些可能性以及更多的可能性。

为此，我们设计divisors(n, low, high)，它接受整数n、low和high作为输入。如果n在low和high之间（包括两个端点）有任何因数，则函数divisors应返回True。如果n在low和high之间没有因数，则divisors应返回False。

让我们设定期望的结果：一方面，divisors(15, 2, 14)应该返回True，因为15在2到14之间（包括2和14）有因数，实际上有几个；另一方面，divisors(11, 2, 10)应该返回False，因为11在2到10之间（包括2和10）没有因数。如果divisors(n, 2, n-1)返回False，则数字n就是素数。

为了强化上一章中的递归设计思想，我们用递归来编写divisors(n, low, high)。首先是基本情况：如果low>high，则从low到high的范围内没有整数。故而，在该范围内不可能存在因数。因此，如果low > high，则divisors应返回False。

如果low <= high，那么我们需要检查low是不是n的因数。我们可以测试n是否可以被n整除，如果可以，则可以找到该范围内的因数。在这种情况下，divisors必须返回True。

当low<=high，但low不是n的因数时，存在什么递归子结构？如果low不是n的因数，则只需要检查从low + 1到high的整数。这可以通过调用divisors(n, low+1, high)来实现，函数编写如下：

def divisors(n, low, high): """ divisors returns True if n has a divisor between low and high (inclusive) otherwise, divisors returns False """ if low > high: return False elif n % low == 0: # check if n is divisible by low? return True else: return divisors(n , low+1, high)

如前所述，我们可以通过检查n在2到n-1之间是否有因数，来测试n是不是素数：

def isPrime(n): """ For any n greater than or equal to 2, isPrime returns True if n is prime. isPrime returns False if n is not prime """ # if there's a divisor, it's not prime if divisors(n, 2, n-1) == True: return False else: return True

可以更简洁地编写如下：

def isPrime(n): """ For any n greater than or equal to 2, isPrime returns True if n is prime. isPrime returns False if n is not prime """ return not divisors(n, 2, n-1)

回想一下，not用于否定一个布尔值。如果divisors(n, 2, n-1)为True，则not divisors(n, 2, n-1)为False；如果divisors(n, 2, n-1)为False，则not divisors(n, 2, n-1)为True。尽管更简洁，但后一个版本不一定可读性更好。有些人更喜欢前者，而有些人更喜欢后者。

无论哪种方式，我们接下来都使用isPrime生成素数列表，再次利用递归。想象一下，我们想知道从整数low（至少2）到上限high（例如100）的所有素数。对于该范围内的每个数字，我们可以测试它是不是素数，如果是素数，就将它加入一个不断增长的素数列表中。在查看下面的代码之前，看看你是否能确定这个函数的基本情况和递归情况。

下面是一个Python实现：

def listPrimes(low, high): """ Returns a list of prime numbers between low and high, inclusive """ if low > high: return [] elif isPrime(low) == True: return [low] + listPrimes(low+1, high) else: return listPrimes(low+1, high)

在elif语句块中，我们返回[low] + listPrimes(low+1, high)而不是low + listPrimes (low+1, high)。为什么？

请记住，listPrimes(low+1, high)返回一个列表。后一个表达式尝试向该列表添加一个整数low。前一个表达式（正确的表达式）将一个列表[low]添加到该列表。Python在实现列表加列表时很轻松，这是“列表连接”。Python不会将整数加入列表。（尝试一下，你收到的错误消息也会这么说！）

上述生成素数的策略是可行的，但速度很慢。问题是它重复了很多工作。例如，按照上面的写法，listPrimes(2,100)会发现2是素数，并且仍然检查2的每一个倍数是否为素数。同样，它会发现3是素数，然后继续检查3的每一个倍数是否为素数。也许，一旦找到一个素数，就可以避免检查该素数的倍数，因为我们确信这些倍数不是素数。

尚不十分清楚Eratosthenes是否真的发现了名为“埃拉托斯特尼筛法”的算法。

一种更快的生成素数的算法称为“埃拉托斯特尼筛法”（sieve of Eratosthenes），以古代希腊数学家的名字命名。我们的想法是对已经发现的素数的倍数进行筛选或过滤。如前所述，listPrimes(2,100)会发现2是素数。然后，我们从考虑的数字中删除或筛掉2的所有倍数，这些倍数不是素数。数字3是筛掉所有2的倍数后剩下的最小值，因此3是素数。然后，我们从剩余值中筛掉所有3的倍数，它们也不是素数。完成后，剩余值中最小的是5。因此5是素数，我们筛掉它的倍数。我们继续这个过程，直到达到high或100。

网上有埃拉托斯特尼筛法的精美动画。其中最后一个画面显示如图3.1所示。

我们来实现一种基于筛子的算法（本着埃拉托斯特尼筛法的精神），我们称之为primeSieve。primeSieve函数将接受我们感兴趣的整数列表，返回一个列表，仅包含原始列表中的素数。Python有一个内置函数range(low, high)，该函数创建顺序的整数列表。下面是使用range的两个例子：

>>> list(range(0,5)) [0, 1, 2, 3, 4] 　 >>> list(range(3,7)) [3, 4, 5, 6]

图3.1　埃拉托斯特尼筛法

请注意，我们从range返回的列表似乎过早停止了，少了一个数字——最终整数为high-1。这是Python中的约定。另外，要查看得到的列表的各个元素，我们需要在结果上调用list。因此，如果要查看2～1000的整数列表，可以调用list(range(2, 1001))。试试吧！

在编写primeSieve之前，让我们考虑一下它如何工作。设想我们从列表range(2, 11)开始，它是：

[2, 3, 4, 5, 6, 7, 8, 9, 10]

将此列表传递给primeSieve就是问：“您能在这个列表中找到所有素数吗？”为了回应这个礼貌的请求，primeSieve函数应提取第一个元素2并保留它，因为2是素数。然后，应从该列表中筛掉所有2的倍数，从而得到一个新列表：

[3, 5, 7, 9]

现在怎么办？好吧，我们现在有一个较小的列表，想知道它的哪些元素是素数。啊哈！我们可以将这个较小的列表发送回primeSieve——毕竟，primeSieve的任务是返回输入列表中存在的素数。递归！

继续我们的例子，我们第一次调用primeSieve时发现了2，筛掉2的倍数后得到列表[3, 5,7,9]，并在新列表上调用primeSieve。递归调用返回的所有结果都将附加在我们当前保持的2之后，因此我们会得到2～10的所有素数的列表。

设想我们有一个名为sift(p, L)的函数，该函数以数字p和一个列表L作为输入，返回一个列表，从L中删除了p的所有倍数。然后，我们可以像这样实现primeSieve：

def primeSieve(numberList): """ primeSieve returns the list of all primes in numberList using a prime sieve algorithm """ if numberList == []: # if the input list is empty, return [] # ...we're done else: p = numberList[0] # the first element is prime return [p] + primeSieve(sift(p, numberList[1:]))

在这里，primeSieve假定其初始输入是从2开始的整数顺序列表。因此，每次递归调用时p都是素数。例如，筛掉2的倍数后，对primeSieve的递归调用将接受参数列表[3, 5, 7, 9]。然后else语句块将从列表的最前面取得3，筛掉3的所有倍数，得到[5, 7]，然后再次递归。在下一次递归调用中，p将为5，并且函数将对列表[7]递归调用。该递归调用将取得7并递归到空列表。每次输入列表都会变得越来越短，更接近于处理空列表输入的基本情况。在这种情况下，primeSieve正确报告“输入参数中所有素数的列表为空”，并且它会返回空列表。

自顶向下的设计？将它称之为“如意算盘”方法怎么样？因为我们的愿望是在需要时就有一个辅助函数！

我们仍然需要一个可以进行实际筛选的函数！上面，我们设想有一个名为sift的函数，该函数接受两个参数（一个数字p和一个列表L），并返回L中不是p的倍数的所有数字。请注意，即使尚未实现sift，我们已经在假设有sift的情况下编写了primeSieve。这种编写程序的方法称为“自顶向下的设计”，因为我们从“顶部”（我们想要的）开始，然后逐步进行到所需的细节。

接下来，我们将着手编写sift函数。

3.4　过滤

Python有一个名为filter的内置函数，它几乎完成了我们要进行的所有筛选工作。filter的不寻常之处在于，它接受一个函数作为输入参数。我们来看看filter的样子以及工作原理。首先，我们将定义一个供filter使用的函数：

def is_not_divisible_by_two(n): """ this function returns True if n is NOT divisible by 2, and returns False if n IS divisible by 2 """ return n%2 != 0

这似乎是个奇怪的函数！

回想一下，n%2 == 0会检查n是否可被2整除。因此，如果n无法被2整除，则n%2！= 0将返回True。例如：

>>> is_not_divisible_by_two(41) True >>> is_not_divisible_by_two(42) False

利用我们的函数is_not_divisible_by_two，下面是使用filter的一个例子：

>>> list(filter(is_not_divisible_by_two, [2,3,4,5,6,7,8,9,10])) [3, 5, 7, 9]

你可能已经推断出filter在做什么：它的第一个输入参数是一个函数，第二个输入参数是一个列表。输入函数需要接受单个输入并返回布尔值。返回布尔值的函数称为“谓词”（predicate）。你可以认为谓词是在告诉我们它是否“喜欢”它的参数。然后filter会返回列表中该谓词“喜欢”的所有元素。在我们的例子中，is_not_divisible_by_two是“喜欢”奇数的谓词，因此filter返回一个列表，包含原始列表中所有的奇数。

与range一样，filter要求将它的结果传递给list，以便我们查看它的值。这是因为这两个函数会等待，直到需要结果时，才会计算其结果。

一个函数接受其他函数作为参数？也许很奇怪，但绝对是允许的，甚至是鼓励的！这个想法对于函数式编程非常重要：函数可以像其他任何类型的数据一样传入或传出其他函数。实际上，第4章将说明为什么这个想法根本不那么奇怪。

数字列表不是唯一可以过滤的数据类型。下面是filter的另一个例子，这次使用字符串列表。为了准备再次访问地球，外星人正尝试掌握英语和许多其他语言。他们有很多单词需要学习，但是他们听说4个字母的单词是最关键的，他们首先关注这些单词。因此，假设外星人希望过滤[‘aardvark’,’darn’,’wow’,’spam’,’zyzzyva’]这样的列表，以获取仅有4个字母的单词列表[‘darn’,’spam’]作为输出。

如前所述，我们先定义一个谓词函数：一个名为hasFourLetters的函数。该函数以一个名为s的字符串作为输入，如果输入字符串的长度为4，则返回布尔值True，否则返回False。

def hasFourLetters(s): """ returns True if the length of s is 4, else returns False """ return len(s) == 4

利用hasFourLetters，下面是filter的另一个例子：

>>> list(filter(hasFourLetters, ['ugh', 'darn', 'wow', 'spam', 'zyzzyva'])) ['darn', 'spam']

3.5　lambda

我们已经看到，函数filter可以帮助我们筛选数字列表，但到目前为止，我们只筛掉了偶数数字，留下了不能被2整除的值。请记住，埃拉托斯特尼筛法利用反复筛选，即针对序列中的不同值进行筛选。如果要筛选3的倍数，可以使用另一个辅助函数：

def is_not_divisible_by_3(n): """ returns True if n is not divisible by 3, else False """ return n % 3 != 0

以这种方式继续，我们需要一个函数来删除5的倍数，另一个针对7，再针对11，依此类推。但这种方法不通用！作为替代，我们可以尝试在谓词函数中添加第二个参数，如下所示：

def is_not_divisible_by_d(n, d): """ returns True if n is not divisible by d, else False """ return n % d != 0

这个函数执行正确的计算，但filter要求它的第一个输入是只接受一个输入自变量的谓词函数，而不是像我们在这里所做的那样接受两个输入。

我们真正需要的是一次性使用的函数——在我们需要它时，可以用当前要过滤的数字来定义它，然后在用完后立即丢弃它。Python支持临时函数的创建和使用，甚至我们都不必为它们命名！这样的函数称为“匿名函数”。

初次接触时，匿名（或无名）函数似乎违反直觉，但请记住，Python（和每种编程语言）很自然地支持匿名数据：

>>> 14 * 3 42 >>> [6,7] + [8,9] [6,7,8,9]

在这两个例子中，正在操作的数据和结果都没有Python名称。我们没有分配变量来保存它们。我们对它们有自然语言名称，例如“四十二”或“八，九的列表”，但这些语言便利性与Python无关。

由于Python将函数视为一等公民，因此它们也可以不用名称来表达和使用。下面是一个匿名函数的例子：

>>> lambda x: 2*x <function _ _main_ _.<lambda>>

“lambda”源自名为“lambda演算”的数学分支（请参见3.6.3节的补充内容），它影响了第一种函数式编程语言LISP。

请注意，Python将这视为函数。lambda不是名字，而是一个Python保留字，表示我们正在定义一个匿名函数。在关键字lambda后面出现该函数的输入参数的名称。在这个例子中，它有一个名为x的参数，接着是一个冒号，然后是匿名函数应返回的值。

让我们看3个使用lambda的例子：

>>> (lambda x: 2*x)(50) # compare to f(50) 100 >>> (lambda x, y: x-2*y)(50,4) # compare to f(50,4) 42 >>> (lambda n: n%2 != 0)(41) # compare to is_not_divisible_by_2(41) False

匿名函数的工作原理与命名函数完全相同。为了直接调用它们，有必要将它们放在括号内，但是如果它们用于传递，就不必放在括号内。

最后一个示例lambda n: n%2 != 0，完全等价于我们的is_not_divisible_by_2函数。从而：

>>> list(filter(lambda n: n%2 != 0, [2,3,4,5,6,7,8,9,10])) [3,5,7,9]

Python中的匿名函数语法不寻常，因为我们没有将函数的参数括起来，也没有return语句。作为替代，Python中的匿名函数返回冒号后面的任意值。

为了指出匿名函数确实是完全意义下的函数，我们想说，如果你愿意，可以给它们命名，就像所有其他Python数据一样：

>>> double = lambda x: 2*x >>> double(50) 100

在第一行中，我们将一个名为double的变量赋值lambda x: 2 * x。从那里开始，double行为就像是以更传统的方式用def定义的函数一样。所以double是一个函数，带有一个参数。如果要使用它，需要以习惯的方式向它传递一个值。

让我们利用匿名函数完成sift的编写，如下所示：

def sift(toRemove, numList): """ sift takes a number, toRemove, and a list of numbers, numList. sift returns the list of those numbers in numList that are not multiples of toRemove """ return list(filter(lambda x: x%toRemove != 0, numList))

我们传递给filter的匿名函数在其函数体中使用了整数toRemove，而不必将它作为参数传入。匿名函数是在toRemove已经存在并具有值的环境中定义的。

为了进行比较，我们还可以用列表推导式来编写sift（请参见3.6.1节的补充内容）：

def sift(toRemove, numList): """ sift takes a number, toRemove, and a list of numbers, numList. sift returns the list of those numbers in numList that are not multiples of toRemove """ return [x for x in numList if x%toRemove != 0]

因此，我们再次完成了primeSieve函数，现在有了一个改进的sift：

def primeSieve(numberList): """ primeSieve returns the list of all primes in numberList using a prime sieve algorithm """ if numberList == []: # if the input list is empty, return [] # ...we're done else: p = numberList[0] # the first element is prime return [p] + primeSieve(sift(p, numberList[1:]))

尝试运行primeSieve生成较长的素数列表。如果给它足够大的列表，Python会“抱怨”。例如：

>>> primeSieve(list(range(2, 10000)))

导致了很长的、看似不友好的错误消息。问题在于，每个递归调用都会在栈内存中创建一个栈帧，如果没有更多可用的栈内存，计算将崩溃。第4章将详细介绍执行递归函数时计算机内部发生的情况，那时栈内存问题就更有意义了！现在，请注意，通过在源文件的提示符或顶部添加以下几行内容，你可以要求Python提供更多的栈内存：

import sys sys.setrecursionlimit(20000) # Allow 20000 # stack frames

在这里，我们要求为20000个栈帧留出空间。某些操作系统允许你要求的栈帧可能比这更多或更少。大多数现代计算机会允许更多。

CS课程的大胆推销！

这将我们带到了最后一个知识点：尽管primeSieve相当高效，但是RSA方案的大多数良好实现都使用更为有效的方法来生成较大的素数。实际上，在对互联网交易进行编码时，RSA使用的素数通常有几百位数！有关算法或密码学的计算机科学或数学课程，可能会展示更复杂、更有效的算法来生成素数。

本文摘自《计算机科学概论（Python版）》

本书是美国哈维玛德学院“计算机科学通识”课程的配套教材，随后在美国许多学院和大学中被采用。在哈维玛德学院，几乎每个一年级学生都会学习这门课程（不论学生的最终专业是什么），它是学院核心课程的一部分。我们的教材也被克莱蒙特学院联盟的许多学校采用，包括主修人文科学、社会科学和艺术的学生都在使用。因此，这是学生的第一门计算课程，无论他们的专业是什么。

从第1章开始，本书强调解决问题和重要思想的特点就很明确。我们在第1章中描述了一种非常简单的编程语言，用于控制虚拟的“Picobot”机器人。读者花十分钟就可以掌握其语法，但这里提出的计算问题是深刻而有趣的。

本书的其余部分遵循了同样的思路。我们使用Python语言，因为它的语法简单，并且有一套丰富的工具和软件包，让新手程序员能够编写有用的程序。在第2章中，我们对使用Python进行编程的介绍仅限于该语言语法的有限子集，这体现了函数式编程语言的精神。通过这种方式，读者很早就掌握了递归，并意识到他们可以用极少的代码编写有趣的程序。

第3章在函数式编程上更进一步，介绍了高阶函数的概念。第4章关注一个问题：“我的计算机如何做到这一切？”我们研究了计算机的内部工作原理，从数字逻辑到计算机组织，再到用机器语言编程。

既然已经揭开了计算机的“神秘面纱”，读者也看到了“幕后”发生的事情的物理表示，于是我们在第5章中继续探讨了计算中更复杂的思想，同时探讨了诸如引用和可变性等概念，以及包括循环在内的构造、数组和字典。我们利用第4章介绍的计算机物理模型来解释这些概念和结构。根据我们的经验，如果读者建立了底层的物理模型，就更容易理解这些概念。所有这些都是在读者熟悉的场景下完成的，这就是一个推荐程序，就像在线购物中使用的那种。

内容新！有改进！有许多“边缘的”有用注释！

在第6章中，我们探讨了面向对象编程和设计中的一些关键思想。这里的目标不是培养专业级的程序员，而是解释面向对象范式的基本原理，并让读者了解一些关键概念。最后，在第7章中，我们研究了问题的“难度”——在计算复杂性和可计算性方面，提供了一些优雅的，但数学上非常合理的处理方法，最终证明了计算机上无法解决的许多计算问题。我们使用Python作为模型，而不是使用形式化的计算模型（如图灵机）。

本书意在与我们为课程开发的大量资源一起使用，这些资源可从网站https://www.cs. hmc.edu/csforall上获得。这些资源包括完整的授课PPT、丰富的每周作业集、一些附带的软件和文档，以及关于该课程已发表的论文。

我们有意让这本书的篇幅相对较短，并努力让它变得有趣、可读性好。本书准确地反映了课程的内容，而不是一本不可能在一个学期学完的、令人望而生畏的百科全书。我们编写这本书时相信，读者可以随着课程的进行而舒适地阅读所有内容。