主编寄语
《大众科学》杂志正在庆祝其166周年。鉴于它是美国持续出版时间最长的杂志，它触动了许多读者的生活和职业道路也就不足为奇了——包括为我们撰写文章的科学家以及我们报道其工作的科学家。所以，就像经常发生的那样，当我在谷歌科学展览会上担任评委时遇到了谷歌的研究主管彼得·诺维格，我们开始聊起了《大众科学》。他提到这本杂志对他个人影响深远。虽然对他最具启发性的文章在很多方面都被证明是正确的，但在其他方面最终却是错误的。我说了类似这样的话：“这真的很有趣。我想知道那些是什么——而且我敢打赌其他人也会想知道。你愿意为我们写一篇关于这个的文章吗？”
这是启发诺维格的文章。看完之后，您可以阅读诺维格在这篇博客中令人着迷的想法。
关于支持科学新闻业
如果您喜欢这篇文章，请考虑通过以下方式支持我们屡获殊荣的新闻业 订阅。通过购买订阅，您正在帮助确保关于塑造我们当今世界的发现和想法的具有影响力的故事的未来。
我们不时会提供关于《大众科学》杂志的其他见解——既来自在研究领域工作的科学家（该杂志与读者分享这个领域），也来自我们的工作人员和撰稿人，他们可以向您提供关于我们正在进行的新项目的内幕消息。一如既往，我们很乐意收到您的评论和反馈。如果您受到《大众科学》的启发，请与我们分享您的故事：submit@sciam.com —玛丽埃特·迪克里斯蒂娜
最初发表于1966年9月刊的《大众科学》。
一句被所有的习字帖和名人在演讲时重复的深刻而错误的陈词滥调是，我们应该培养思考我们正在做什么的习惯。事实恰恰相反。文明的进步是通过扩展我们可以不经思考就能执行的重要操作的数量来实现的。思想的运作就像战斗中的骑兵冲锋——它们的数量严格限制，它们需要新鲜的马匹，并且只能在决定性的时刻进行。 - 阿尔弗雷德·诺思·怀特海德
本文是关于如何让计算机做你想做的事情，以及为什么它几乎总是比你预期的要花费更长的时间。以下内容不是关于编程技术发展水平的详细报告，而是试图展示如何开始编写程序。编写程序的过程主要是直觉的，而不是形式化的；因此，我们将更关注编程的指导原则，而不是将程序呈现给机器的特定语言。
我们将从一个具体的编程问题示例开始，这个问题显然是不平凡的，但又足够简单，无需任何先前的编程知识即可理解。我选择了解决这个问题的非正统方法，对于许多专业程序员来说，这种方法看起来会很奇怪。这种方法使我们能够处理一个例子，否则这个例子会过于复杂而无法解释。
我们的问题是编写一个程序，让计算机下跳棋。我们应该如何着手呢？这个问题主要有两个方面。为了使计算机能够处理这个游戏，我们必须找到一种方法来表示棋盘和棋盘上的位置，并为计算机提供一个程序，用于识别合法走法并进行走棋。这是一个编程问题。其次，我们必须为机器提供一种从可用的走法中选择合适的走法的方法。这主要是一个博弈问题。国际商业机器公司的亚瑟·L·塞缪尔对博弈方面进行了广泛而相当成功的研究。然而，由于我们关注的是编程而不是博弈，我们将满足于一个简单的通用策略，并将大部分细节留待解决。
编写程序的常用方法，特别是对于复杂的问题，是将过程分为两个阶段。第一个阶段称为系统分析。它包括分析任务，以确定确切需要做什么，并制定总体计划。一旦决定了要执行工作的总体纲要，第二个阶段就是以适合计算机的形式编写所需的操作。这涉及大量更详细的决策（例如，如何在机器中表示信息以及如何存储表示）。程序的详细形式将取决于要使用的特定计算机。
关于这两个阶段的命名，已经产生了混淆。一些程序员将术语“编程”保留给第二阶段；另一些人称第一阶段为“编程”，第二阶段为“编码”；还有一些人使用术语“编程”来表示整个过程——第一阶段和第二阶段。我自己的观点是，系统分析和编程之间的区别不是很有用。如果系统分析能够深入到用比目前使用的语言稍微严格的语言来描述程序概要，那么应该可以将生成机器语言详细程序的剩余整个过程委托给计算机本身。
让我们继续讨论编写程序让计算机与对手下跳棋的问题。我们应该如何表示游戏的相关特征，以及我们希望能够对它们执行哪些类型的操作？一个好的工作规则是从操作开始，让操作决定你需要表示在机器中的内容。在这种情况下，我们显然需要从表示位置和走法以及与它们相关的值开始。
我们可以通过使用函数符号来接近计算机所需的精度，同时避免陷入过早的细节。我们用P表示一个位置，并同意将P不仅包括棋盘上棋子的数量和排列，还包括各种其他重要事实，例如轮到哪个玩家走棋。一个位置的价值可以用函数PositionValue(P)来表示。任何走法（例如M）的价值显然取决于它所处的起始位置；因此，在编写函数MoveValue(M,P)时，我们必须指定位置。接下来，为了能够展望未来并检查走法的可能后果，计算机将需要第三个函数：MakeMove(M,P)，其中P表示走法所处的起始位置。此函数的结果是走法产生的新位置。最后，程序需要第四个函数来查找可以从给定位置进行的所有合法走法：LegalMovesFrom(P)。此函数的结果是一个走法列表。
这四个函数，以及两种类型的对象（P和M），足以指定我们的跳棋程序的核心。跳棋游戏中有两个玩家（在我们的例子中是机器及其对手），对一个玩家有利的位置对另一个玩家不利。因此，我们必须使我们对位置价值的理解更加精确，即PositionValue(P)给出位置P对于必须从该位置走棋的玩家的价值。我们可以合理地假设位置P对于另一个玩家的价值是这个价值的负数；也就是说，如果一个位置对一个玩家的价值是v，那么它对另一个玩家的价值将是-v。（这个假设在博弈论中用跳棋是零和博弈来表达。）
接下来，我们可以将走法对于执行走法的玩家的价值定义为结果位置对他/她的价值。假设从位置P执行走法M的结果是位置P。记住对手必须从P开始走棋，我们可以看到走法M对于执行走法的玩家的价值将是-PositionValue(P)。因此，在我们的符号中，我们可以将走法的价值定义如下：MoveValue(M,P) = -Position Value [MakeMove(M,P) ]。这个正式的陈述可以解释为，为了评估你自己的走法，你执行它，找到结果位置对你的对手的价值，并改变它的符号。
我们应该如何找到一个位置的价值？游戏的基本程序是探索你所有可能的走法和对手对一些深度的所有可能回复，并评估结果位置。让我们将这些称为“终局”位置，并说它们的价值是由函数TerminalValue(P)产生的。此函数对位置进行即时评估（可能根据诸如仍在游戏中的棋子数量、它们的移动性、对棋盘中心的控制等因素），而无需进一步展望未来。我们现在可以说，如果P是终局位置，则其价值为TerminaIValue(P)，如果不是，则其价值是可能从中进行的最佳合法走法的价值。请注意，位置是否为终局位置可能不仅取决于位置本身，还取决于展望未来的深度（el）。为了限制机器展望未来的深度，这是必要的。
我们一直在编写的定义实际上是循环的（例如，Position Value的定义涉及MoveValue的使用，反之亦然），这些函数被称为递归函数，因为每个函数都是根据其他函数定义的。这种循环性没有缺点；实际上，它使得可以直接从中间开始，设置许多函数，这些函数的目的在一开始仅凭直觉理解，并将它们中的每一个都根据其他函数定义。这种递归或分层的编程方法是处理复杂操作的最简单方法，因为它允许将它们分解为可以单独考虑的较小单元。
我们现在构建了一个通用的博弈方案，而没有决定策略的细节或游戏本身的结构。我们可以通过决定位置和走法的表示形式并定义四个函数来完成我们程序的概要。函数Legal- MovesFrom(P)和MakeMove(M,P)，以及P和M的形式，将决定游戏的性质，而函数Terminal(P,d)和TerminalValue(P)之间将决定策略。
选择在计算机中表示对象的方式是一门艺术，我们在系统地决定最佳方式方面几乎无能为力。主要要求是表示形式应尽可能紧凑，并且尽可能易于操作。为了表示跳棋盘上的各种位置，我们有两种不同的可能性。为了描述一个特定的位置，我们可以指定棋盘上32个可用方格中的每一个是否被占用，如果是，则被什么占用，或者我们可以仅给出仍在游戏中的棋子的位置。从查找合法走法的角度来看，第一种选择更方便，因为它更容易发现哪些方格是未被占用的。
当我们详细考虑走法的表示时，我们发现普通棋盘上的方格编号很不方便，因为有两种类型的方格（在交替的行上）需要不同的规则。塞缪尔设计了一种巧妙的方法来避免这种困难。通过用未使用的行和列扩展棋盘并重新编号方格，他产生了一个方案，在该方案中，对于实际使用的棋盘部分上的所有方格，可能的走法都是相似的。
所有可能的走法（除了那些棋子被吃掉的走法）都分为四种类型，每种类型都可以用一个字（由45位或二进制数字组成）表示，该字可以指定其类型的任何走法。在我们一直在使用的符号方案框架内，表示吃子走法和将兵晋升为王也很简单。
讨论工作跳棋程序的所有细节将超出本文的范围。然而，编写此类程序的过程的主要轮廓现在应该很明显了。第一步是对如何解决问题有一个模糊的想法。第二步是指定执行此初始计划所需的操作，通过命名这些操作要作用的对象来使其形式化。第三步是澄清对象的定义并确定每个对象的表示形式。这些表示形式应主要由要对对象执行的操作决定。一旦确定了表示形式，就可以根据它们更精确地定义组件操作。然后，可以继续完善程序，更正可能在表示形式中显示的错误或缺陷，并相应地调整操作。
在这个阶段，程序的主要智力工作似乎已经完成。我们已经精确地指定了我们希望计算机做什么。其余的——将程序转换为计算机的指令——应该只是例行公事。不幸的是，事情并非完全如此，任何没有使用计算机经验的人都会对仍然需要的时间和精力感到不愉快地惊讶。
首先，计算机无法直接接受我们希望给它的相当复杂的指令类型。几乎可以肯定的是，我们将使用对于任何计算机来说都太过分的操作。为了绕过机器无法直接执行我们想要的操作，我们可以用标准编程语言编写我们的程序，并让机器将其翻译成它自己的更简单的代码。这似乎是很好地利用计算机为我们做苦力，但不幸的是，它并没有消除所有的劳动。我们必须做大量的看似无关紧要和临时的工作，以迫使程序进入适合现有编程语言的形式。
现在有相当多的这些编程语言：FORTRAN、ALGOL和MAD（主要用于科学问题）；JOVIAL（用于军事应用）；COBOL；SIM SCRIPT；LI SP；PL/I；CPL等等。为了指示语言的不同风格，给出了三个示例：一个简单的程序（用于查找数学函数eX）分别用CPL、ALGOL和FORTRAN编写。
大约九年前出现的这种类型的编程语言极大地丰富了编程艺术。在此之前，包含5,000条指令的程序被认为相当大，只有最有经验或最鲁莽的程序员才会尝试。今天，一个人可以处理大约大10倍的程序；一个团队通过合作努力可以产生仍然大五到十倍的程序。
到目前为止，最重要的新编程语言是FORTRAN；据估计，直到最近，超过90%的科学和工程程序都是用它编写的。在过去的几年中，逐渐清楚的是，当前的编程语言绝非完美，FORTRAN的巨大成功是由于其相对优点而不是绝对优点。诸如ALGOL和LISP之类的其他编程语言表明，至少在计算机上执行某些操作有更简单的方法。
回到我们的跳棋程序：我已经用CPL（代表“组合编程语言”）的非正式且有些扩展的版本编写了完整的程序（除了某些细节，包括输入和输出安排）。程序以符号形式以及使用的术语列表及其定义显示在上一页。该程序绝不是最终形式；它尚未在机器上运行，因此，根据下面表达的观点，可能仍然包含一些错误。感兴趣的读者可能想寻找它们。
在计算机编程的早期——比如15年前——数学家们曾经认为，只要足够小心，他们就能够编写出正确的程序。令他们非常惊讶和懊恼的是，他们发现情况并非如此，并且除了极少数例外，编写的程序都包含大量错误。事实证明，发现、定位和纠正这些错误的过程非常困难，通常比首先编写程序花费的时间要长得多，并且使用了大量的机器时间。
尽管自早期以来编程技术已经得到了极大的改进，但查找和纠正程序中的错误的过程——如果说不优雅的话，也生动地被称为“调试”——仍然是最困难、最混乱和最令人不满意的操作。这种情况的主要影响是心理上的。尽管我们都很乐意口头上赞同“人非圣贤，孰能无过”的格言，但我们大多数人喜欢在真正尝试的特殊场合对自己的表现保留一点私人保留意见。当机器公开且无可辩驳地表明，即使我们确实尝试了，我们实际上犯的错误也与其他人的错误一样多时，这有点令人泄气。如果你的骄傲无法从这种打击中恢复过来，你永远不会成为程序员。
事实上，人类的本性并非完美准确，并且不现实地相信他们永远会是。获得正确程序的唯一合理方法是假设它最初会包含错误，并采取步骤来发现这些错误并纠正它们。这种态度对于任何接触过任何大规模操作计划的人来说都非常熟悉，但对于大多数没有接触过的人来说却完全陌生。
我认为问题在于，太多的教育过程都非常重视第一次获得正确答案。如果你在考试题中给出了错误的答案，你就会失去你的分数，事情就到此为止了。如果你在编写程序时犯了错误——或者，实际上，在课堂外的许多其他生活情况中——这绝不是一场灾难；但是，你必须找到你的错误并纠正它。也许更多的学术教学也采用这种态度会更好。
当我们第一次开始接触计算机并实际尝试运行程序时，无论是为了测试它还是为了获得一些有用的结果，我们才真正开始感到沮丧。尽管机器本身的速度备受赞誉，但通常需要几个小时，有时甚至几天才能真正得到即使是最短程序的答案。当这种延迟加上计算机及其编程语言和编译器通常非常无助的事实，以至于你在一天等待结束时收到的唯一信息可能是你的程序仍然是错误的，很容易理解为什么这么多人认为使用计算机更多的是与机器和系统作斗争，而不是合作。
造成这种奇怪情况的原因是希望使计算机（这是一种非常昂贵的机器）尽可能长时间地充分运转。计算机外部的组织（通常雇用相当多的操作人员）几乎占了所有的“周转时间”和相当一部分的挫败感。时间共享系统的引入应该消除这种挫败感的来源，但代价是大大增加了操作系统的大小和复杂性。
实际运行程序所涉及的大部分工作可以由计算机本身完成。诸如将编程语言翻译成详细的机器代码、在计算机内部分配存储空间、保留记录以协助诊断程序错误、组织来自不同用户的短作业序列的调度和核算等操作正是计算机可以处理的高级例行文书工作，因此期望机器来完成它是合理的。
使机器执行这些操作的程序非常重要。大多数计算机用户与它们的接触将远远多于与计算机本身的接触，因此，操作系统程序被称为系统的软件（与计算机本身（称为硬件）相对）。实际上，系统的性能在很大程度上取决于其软件及其硬件，而软件系统的规划和编写正在迅速成为计算机制造商的主要问题。整个程序集，称为软件包，可能很容易花费机器制造商与生产和调试机器本身一样多的成本。结果，即使在许多方面它们严重不足，也存在不更改编程语言或操作系统的强大压力。
为什么从程序的构思到机器的执行之路如此漫长而乏味？为什么今天的操作系统——软件——如此昂贵且令人不满意？我们是否可能达到了人类编写复杂程序的能力极限，而当前的软件危机是否真的是试图完成人类不可能完成的任务的结果？任何今天与大型计算机系统打交道的人都知道，整个事情是多么接近在自身复杂性的重压下崩溃。
毫无疑问，使用当前的技术，我们几乎达到了编程的极限。但是，我们难道不能改进技术吗？我们在本文中考虑的跳棋示例强烈暗示，简化的方法和编程语言的改进将使事情变得容易得多。如果存在合适的编程语言，那么显然应该可以按照上述概述的方式编写整个跳棋程序，并将几乎所有剩余阶段留给计算机执行。事实上，现在几乎可以做到这一点，并且构建一种可以实现这一目标的语言可能并不太困难。
建立一个大型而复杂的程序的唯一合理方法是使用分层方法。由于我们一次可以掌握在头脑中的问题的大小和复杂性是有限的，因此扩展我们能力的最佳方法似乎是将相对较大且复杂的操作视为单个单元，并将这些单元分层组合。当前的编程语言都至少在口头上对这个想法表示赞同，但是许多语言不允许真正的和无限的分层结构——程序员必须同时考虑的只有两到三个操作级别（例如“本地”和“全局”）。那些允许真正分层处理问题的语言在处理表示形式方面只有有限的能力。
当今的计算机本身是使用分层（或递归）编写的程序的绊脚石。由于计算机不适合这种组织，因此运行此类程序比以传统方式编写和编码的程序慢得多。但是，我深信，这种编程方式的优点将远远超过可能需要的任何机器时间的增加。这些优点是如此之大，以至于我相信分层方法最终将被普遍采用。毕竟，任何机器的主要目的都是为了节省人类的麻烦；因此，我们不应过分担心让计算机承担更多的人的工作。此外，我们有充分的理由期望可以设计出能够更自然、更有效地处理深度分层程序的计算机。这些机器可能会比目前的机器稍微复杂一些，但是成本上的差异将是非常值得的。
我把在我看来是最困难，但也是最有趣和最有潜在回报的问题留到了最后，这个问题是关于编程语言的。这是为构建程序的层次系统奠定坚实的数学基础，并开发用于操作它们的微积分。
困难主要源于这样一个事实，即编程向我们提出了某些新的问题，这些问题在数学的任何其他分支中都不存在，或者至少不重要。数学问题有两个方面。第一个方面是如何显式且详细地处理复杂的结构（涉及数据表示），不仅要给出整个结构的名称，而且还要给出其组成部分的名称并为其分配值。困难的第二个方面是在编程中使用命令（01' 命令）引入变量，而一般数学不承认这种意义上的变量的存在，即值随时间变化。在其传统分支中，数学仅处理静态情况。即使是微积分，它也关注对象接近极限，也是根据一系列固定值来处理这个主题。通常，数学家称之为变量的东西要么是值尚未知的常数，要么是为了逻辑语法目的而引入的不存在的量（例如“没有人”）。另一方面，在编程中，我们通过过程的本质来处理随时间变化的变量；程序本质上是一个更改计划。
一位经验丰富的程序员在阅读本文时会注意到，在跳棋程序的制定中，我没有使用任何命令，尤其是程序不包含任何赋值语句（将值分配给名称或对象的语句）。这样做的原因是，我们只知道如何在没有赋值语句的情况下将递归定义的函数组合成层次结构。如果包含它们，仍然没有令人满意的方法来做同样的事情。
我已经讨论过的数学问题的研究现在已经开始。一开始就很清楚，要探索的领域几乎是全新的，没有像数学研究的大多数其他领域那样的既定指导方针。同样明显的是，第一个也是最困难的任务是澄清在编程上下文中，我们所说的“名称”和“值”是什么意思。主要的麻烦是，赋值（值随情况变化而变化）的引入使得术语的含义从它们在数学中通常使用的方式来看是模棱两可的，因此似乎我们可能需要生成新的概念，以便牢牢把握住情况。
现在在编程语言领域中完成的大部分理论工作都与语言语法有关。本质上，这意味着研究关注的不是语言说什么，而是它如何说。这种方法似乎在形成新概念的道路上设置了几乎无法逾越的障碍——至少就语言含义而言是这样。我相信，对于程序员来说，进步之路在于研究含义而不是语法。主要通过对含义的研究，我们将开发出构建层次结构所需的概念。