C.A.R. Hoare

皇后大学

贝尔法斯特，北爱尔兰

这篇论文提出输入和输出是编程的基本原语，同时并行的通信顺序处理是一个基础的程序结构方法。当与Dijkstra的守护命令的发展结合时，这些概念显示出惊人的多功能性。它们的用途通过一系列熟悉的编程练习的样本解决方案来进行说明。

关键词和短语：编程、编程语言、编程基元、程序结构、并行编程、并发、输入、输出、守护命令、不确定性、协程、程序、多入口、多出口、类、数据表示、递归、条件关键区域、监视器、迭代数组。

CR分类：4.20, 4.22, 4.32。

1. 引言

在计算机编程的原始概念中，以及用来表达程序的高级语言中，赋值的行为是熟悉且被良好理解的。事实上，执行程序的机器的内部状态的任何改变都可以被模拟为对该机器的某个可变部分赋予一个新的值。然而，影响机器外部环境的输入和输出操作则没有那么容易理解。它们往往是在编程语言被设计完成后才被加入的。

在计算机程序的结构方法中，

这项研究得到了科学研究委员会的高级研究员奖学金的支持。

作者现地址：编程研究组，45，班伯里路，牛津，英国。

0 1978 ACM 0001-0782/78/0800-0666 $00.75

对于程序结构，三个基本结构得到了广泛的认可和使用：重复结构（例如 while 循环）、选择结构（例如条件 if..then..else）和常规的顺序程序组合（通常由分号表示）。关于其他重要程序结构的设计尚未达成一致意见，已经提出了许多建议：子例程（Fortran）、程序（Algol 60 [15]）、入口（PL/1）、协程（UNIX [17]）、类（SIMULA 67 [5]）、进程和监视器（并行Pascal [21]）、集群（CLU [13]）、表单（ALPHARD [19]）、演员（Hewitt [I]）。

传统的存储程序数字计算机主要是为了确定性地执行单个顺序程序而设计的。当对更高速度的需求导致引入并行性时，每一次尝试都是为了从程序员那里隐藏这个事实，无论是通过硬件本身（如CDC 6600的多功能单元）还是通过软件（如I/O控制包或多程序操作系统）。然而，处理器技术的发展表明，由多个相似的独立处理器（每个都有自己的存储器）构成的多处理器机器，可能会比伪装成单处理器的机器更加强大、容量更大、可靠性更高和经济。

为了有效地在单个任务上使用这样的机器，组成部分的处理器必须能够相互通信和同步。已经提出了许多实现这一目标的方法。一种广泛采用的通信方法是通过检查和更新公共存储器（如Algol 68 [18]、PL/1和许多机器代码）。然而，这可能在构建正确的程序时造成严重的问题，并且可能导致费用（例如交叉开关）和某些硬件实现技术中的不可靠性（例如故障）。为了同步，已经提出了更多种方法：信号量[6]、事件（PL/1）、条件关键区域[10]、监视器和队列（并行Pascal [21]）、路径表达式[3]。其中大多数都已经证明对于其目的是足够的，但是没有广泛公认的选择它们之间的标准。

本文尝试寻找一个解决所有这些问题的单一简单解决方案。基本的提议是：

(1) 采用Dijkstra的守护命令[8]（带有轻微的记号改变）作为顺序控制结构，以及引入和控制非确定性的唯一手段。

(2) 基于Dijkstra的parbegin[6]的并行命令，指定其组成的顺序命令（进程）的并发执行。所有进程同时开始，当它们都完成时，只有并行命令结束。它们不能通过更新全局变量相互通信。

(3) 引入简单形式的输入和输出命令。它们用于并发进程之间的通信。

(4) 这样的通信发生在一个进程将另一个进程命名为输出目的地，第二个进程将第一个进程命名为输入源。在这种情况下，要输出的值从第一个进程复制到第二个进程。没有自动缓冲：通常，输入或输出命令被延迟，直到另一个进程准备好相应的输出或输入。这种延迟对被延迟的进程是不可见的。

(5) 输入命令可能出现在守护程序中。只有当输入命令中命名的源准备执行相应的输出命令时，带有输入保护的守护命令才被选择执行。如果一组备选方案的多个输入保护都有准备好的目的地，只有一个被选择，其他的都没有效果；但它们之间的选择是任意的。在高效的实现中，一个长时间准备好的输出命令应该受到青睐；但语言的定义不能指定这一点，因为进程的执行速度是未定义的。

(6) 重复命令可能有输入保护。如果它们命名的所有源都已终止，那么重复命令也会终止。

(7) 使用一个简单的模式匹配功能，类似于[16]，用于区分输入消息的结构，并以安全的方式访问其组件。这个特性被用来禁止输入不匹配指定模式的消息。

本提议中的程序旨在能够通过一台带有单个主存储器的传统机器以及通过输入/输出通道连接的固定处理器网络来实现（尽管在不同的情况下适用非常不同的优化）。因此，这是一个相对静态的语言：程序的文本确定了并发操作的进程的固定上限；没有递归，也没有处理值变量的功能。在其他方面，该语言也已被削减到解释其更新颖特性所必需的最低限度。

在第3-5节中，通信顺序进程的概念被证明为提供了一种表达解决方案的方法，用于许多先前已被用来说明各种建议的编程语言特性的简单编程练习。这表明该过程可能构成了许多熟悉和新的编程思想的综合。读者可以跳过那些对他不感兴趣的例子。

然而，这篇文章也忽略了许多严重的问题。最严重的是，它未能提出任何证明方法来协助开发和验证正确的程序。其次，它没有关注高效实现的问题，这在传统的顺序计算机上可能尤为严重。解决这些问题可能需要：(1) 限制所提议特性的使用；(2) 为最常见和有用的特殊情况重新引入特殊符号；(3) 开发自动优化技术；以及(4) 设计适当的硬件。

因此，本文中介绍的概念和符号（尽管在下一部分以编程语言片段的形式描述）不应被视为适合作为编程语言使用，无论是抽象还是具体编程。它们最多只是对所面临的问题的部分解决方案。这些和其他点的进一步讨论将在第7节中找到。

2. 概念和符号

以下描述的风格借鉴自Algol 60 [15]。并未处理类型、声明和表达式；在示例中，通常采用了类似Pascal的表示法[20]。大括号{}被引入到BNF中，表示对所包含材料的零次或多次重复。（括号内的句子是关于实现的：它们并不严格地是语言定义的一部分。）

<command> <simple command>l<structured command>

<simple command> <null command>l<assignment command> l<input command>

<structured command> ::= <alternative command> l<repetitive command> l<parallel command>

<null command> skip

<command list> (<declaration>; l<command>;) <command>

命令指定执行命令的设备的行为。它可能成功或失败。如果成功，简单命令的执行可能会影响执行设备的内部状态（在赋值的情况下），或影响其外部环境（在输出的情况下），或同时影响两者（在输入的情况下）。执行结构化命令涉及执行其某些或所有组成命令，如果其中任何一个失败，结构化命令也会失败。（在这种情况下，只要可能，实现应提供某种可理解的错误诊断消息。）空命令没有效果，永远不会失败。

命令列表指定按写入的顺序顺序执行其组成命令。每个声明都引入一个新变量，其范围从其声明扩展到命令的结尾。

2.1 并行命令

<parallel command> [<process>(l l<process>)] <process> <process label> <command list> <process label> :.= <empty>l<identifier> ::

subscript>{,<label subscript>}) ::

<label subscript> <integer

<integer constant>               l<bound variable>

<bound variable> <identifier>

<range> <bound variable>:<lower bound>..<upper bound>

<lower bound> ::= <integer constant>

<upper bound> <integer constant>

一个并行命令的每个进程都必须与该命令的任何其他进程不相交，意思是它不提及任何作为目标变量的变量（参见第2.2和2.3节）在任何其他进程中出现。

没有下标的进程标签，或者其标签下标都是整数常量的标签，作为其前缀的命令列表的名称；其范围延伸到整个并行命令。其标签下标包含一个或多个范围的进程代表一系列进程，每个进程都有相同的标签和命令列表，只是每个进程为绑定变量替换了不同的值组合。这些值的范围在下限和上限之间（包括上限和下限）。例如，X(i:1..n) :: CL 代表

X(1) tX(2) CL2... | X(n) CLn

其中每个CLj都是通过替换绑定变量i的每次出现为数字j而从CL形成的。在所有这样的扩展之后，一个并行命令中的每个进程标签只能出现一次，且进程必须是格式良好且不相交。

并行命令指定其组成进程的并发执行。它们都同时开始，只有当它们都成功终止时，并行命令才成功终止。它们执行的相对速度是任意的。例如：

(1) [cardreader?cardimage | lineprinter!lineimage]

并行执行两个组成命令，并且只有当两个操作都完成时才终止。所用的时间可能与每个组成进程所用的时间中的较长者一样短，即其计算、等待和传输时间之和。

(2) [west DISASSEMBLE | X SQUASH | east ASSEMBLE]

这三个进程分别名为"west"、"X"和"east"。大写的单词代表在后续示例中定义的命令列表。

(3) [room ROOMI fork(i:0..4) :: FORKI phil(i:0..4) PHILI

这里有十一个进程。"room"的行为由命令列表ROOM指定。五个进程fork(0)、fork(1)、fork(2)、fork(3)、fork(4)的行为由命令列表FORK指定，其中绑定变量i表示特定叉的身份。类似的注释适用于五个PHIL进程。

2.2 赋值命令

<assignment command> <target variable> := <expression>

<expression> <simple expression>l<structured expression>

<structured expression> <constructor>(<expression list>)

<constructor> <identifier>l<empty>

<expression list> <empty>l<expression>(,<expression>}

<target variable> <simple variable>|<structured target>

<structured target> <constructor>(<target variable list>)

<target variable list> <empty>l<target variable>

(,<target variable>}

表达式表示一个由执行设备通过对指定的操作数应用其构成的运算符来计算的值。如果其中任何操作未定义，则表达式的值未定义。简单表达式表示的值可以是简单或结构化的。结构化表达式表示的值是结构化的；它的构造函数是表达式的构造函数，其组件是表达式列表的组成表达式表示的值列表。

赋值命令指定其表达式的求值，并将表示的值分配给目标变量。可以为简单的目标变量分配简单或结构化的值。结构化的目标变量可以被分配一个与该构造函数相同的结构化值。这种分配的效果是将结构化目标的每个组成的简单变量分配给结构化值的相应组件。因此，如果在成功的赋值之后评估目标变量表示的值，则该值与赋值之前评估的表达式表示的值相同。

如果其表达式的值未定义，或者该值与目标变量不匹配，则赋值失败，具体来说：简单的目标变量与其类型的任何值都匹配。结构化的目标变量与结构化的值匹配，只要：(1)它们有相同的构造函数，(2)目标变量列表的长度与值的组件列表相同，(3)列表中的每个目标变量都与值列表的相应组件匹配。没有组件的结构化值被称为"信号"。

示例：

(1) x := x + 1x 的赋值之后的值与之前的 x + 1 的值相同。(2) (x, y) := (y, x)交换 x 和 y 的值。(3) x cons(left, right)构造一个结构化的值并将其赋给 x。(4) cons(left, right) := x如果 x 不具有 cons(y, z) 的形式，则失败；但如果它确实是这种形式，那么 y 被赋值给 left，z 被赋值给 right。(5) insert(n) := insert(2*x + l)等价于 n + l。将一个构造器为P，没有组件的“信号”赋值给c。(6) c := P() (7)如果c的值不是P()，则失败；否则没有效果。(8) insert(n) := has(n)失败，因为不匹配。

注意：(3) 和 (4) 的成功执行都确保了后置条件 x = cons(left, right) 的真实性; 但是(3)是通过改变 x 来实现的，而(4)是通过改变 left 和 right 来实现的。如果没有满足后置条件的 left 和 right 的值，示例(4)将会失败。

2.3 输入和输出命令。

<inpm command> ?..= <source>?<target variable>

<output command> <destination>!<expression>

<source> <process name>



<destination> <process name>

<process name> ::= <identifier>|<identifier>(<subscripts>)

<subscripts> <integer expression>{,<integer expression>)

输入和输出命令指定了两个同时操作的顺序进程之间的通信。这样的进程可以在硬件中实现为一个特定用途的设备（例如卡片阅读器或行打印机），或者其行为可以由并行命令的一个组成进程来指定。当一个并行命令的两个进程中的一个进程的输入命令将另一个进程的进程名指定为其来源；另一个进程的输出命令将其目的地指定为第一个进程的进程名；并且输入命令的目标变量与输出命令的表达式表示的值匹配时，就会发生通信。在这些条件下，输入和输出命令被认为是对应的。对应的命令同时执行，它们的组合效果是将输出命令的表达式的值分配给输入命令的目标变量。

如果其来源已终止，输入命令会失败。如果其目的地已终止或其表达式未定义，输出命令将失败。

(输入和输出命令的同步要求意味着实现将必须延迟两个命令中先准备好的那一个。当另一个进程中的相应命令也准备好或当另一个进程终止时，延迟结束。在后一种情况下，第一个命令失败。也有可能延迟永远不会结束，例如，如果一组进程正在尝试通信，但它们的输入和输出命令彼此之间都不相对应。这种失败形式被称为死锁。)

示例：

(l) cardreader?cardimage从卡片阅读器读取一张卡，并将其值（一个字符数组）赋给变量cardimage。(2) lineprinter!lineimage向名为X的进程中的行打印机发送lineimage的值以进行打印。(3) x ? (x, y)输入一对值并分别赋给x和y。(4) + b, 13)向DIV进程输出这两个值。

按照指定的值执行。

注意：如果名为DIV的进程发出命令(3)，并且名为X的进程发出命令(4)，这些命令将同时执行，效果与赋值命令相同：(x, y) := (3?a + b, 13) (s x + b; y 3 13)。

(5) console(i)?c 从一个数组的第i个控制台元素中，输入一个值并赋给c。

(6) console(j - l)!"A"向第(j - l)个控制台输出字符"A"，从数组的第i个进程X中输入信号V( )。(7) X(i)?V()拒绝输入任何其他信号。(8) sem!P( )向sem输出一个P( )信号。

2.4 选择与重复命令。

<repetitive command> command>

<alternative command> [<guarded command>

([]<guarded command>)]

<guarded command> <guard> —+ <command list>

I <command list>

<guard> <guard list>l<guard list>;<input command> t<input command>

<guard list> <guard element>(;<guard element>)

<guard element> <boolean expression>l<declaration>

一个带有一个或多个范围的守护命令代表一系列守护命令，每一个都具有相同的守护和命令列表，但每一个都为绑定变量替换了不同的值组合。值的范围在包括下界和上界的范围内。例如，(i: l..n)G —+ CL表示

GI -+ CL1、G2 —+ CL2、...、Gn —+ CLn，其中每一个Gj —+ CLj都是通过将G —+ CL中的绑定变量i的每次出现替换为数字j来形成的。

只有当其守护执行不失败时，才执行守护命令。首先执行其守护，然后执行其命令列表。通过从左到右执行其组成元素来执行一个守护。评估一个布尔表达式：如果它表示为false，则守护失败；但表示为true的表达式没有效果。一个声明引入了一个新变量，其范围从声明扩展到守护命令的结束。仅当执行相应的输出命令时，才在守护的末尾执行输入命令。（实施可以简单地通过尝试执行守护来测试守护是否失败，并在失败时中止执行。这是有效的，因为这样的中止执行不会影响执行设备的状态。）

备选命令指定执行其一个组成的守护命令。因此，如果所有守护都失败，则备选命令失败。否则，选择并执行一个成功可执行的守护命令。（实施应该利用其选择的自由来确保有效的执行和良好的响应。例如，当输入命令作为守护出现时，通常应该优先考虑与最早准备好并匹配的输出命令相对应的命令；而且，肯定不应该经常无理由地忽视可执行且准备好的输出命令。）

重复命令指定其组成的备选命令的尽可能多的迭代。因此，当所有守护都失败时，重复命令终止，没有效果。否则，执行一次备选命令，然后再次执行整个重复命令。（考虑一个重复命令，当所有真实的守护列表都以输入守护结束时。这样的命令可能需要被延迟，直到要么（1）输出命令准备好与输入守护之一相对应，要么（2）输入守护命名的所有源都已终止。在第二种情况下，重复命令终止。如果两个事件都不发生，则进程失败（处于死锁）。示例：

(1) [x >=y -> m := x|y >= x -> m := y]

如果 x ≥ y，将 x 赋值给 m；如果 y ≤ x，将 y 赋值给 m；如果 x ≥ y 和 y ≤ x 同时满足，两个赋值语句都可以执行。

(2) i < size; content(l) n i:= i + 1]

重复命令扫描元素 content(i)，其中 i = 0, 1, ...，直到 i ≥ size 或找到一个等于 n 的值为止。

**(3) [c:character; west?c -> east!c]*

这读取了由west输出的所有字符，并逐个地输出它们给east。当west进程终止时，重复操作就终止了。

(4) ,[(i:l..10)continue(t); console(i)?c-:, X!(i, c); console(0!ack(); continue(i) := (c # sign off)]

这个命令反复地从任意十个控制台中输入，前提是相应的布尔数组continue的元素为真。绑定变量i用于识别起源控制台。它的值，连同刚输入的字符，都被输出到X，并且一个确认信号被发送回原始控制台。如果字符表示“退出”，则将continue(1)设置为假，以防止从该控制台进一步输入。当continue的所有十个元素都为假时，重复命令终止。(实现应确保准备好提供输入的任何控制台不会被无理由地忽视。)

(5) ,In:integer; X?insert(n) -> INSERT |n:integer; X?has(n) -> SEARCH; X!(i < size) ]

(这里和其他地方，大写的词INSERT和SEARCH作为另外定义的程序文本的缩写。)

在每次迭代中，此命令从X接受以下请求：(a) "insert(n)"的请求（后面跟着INSERT）或(b) "has(n)"的问题，然后将答案输出回X。选择(a)还是(b)由X中的下一个输出命令决定。当X终止时，重复命令也终止。如果X发送一个不匹配的消息，将导致死锁。

**(6) [X?V() -> val := val + 1|val > 0; Y?P() -> val := val - 1]*

在每次迭代中，从X接受一个V()信号并递增val，或从Y接受一个P()信号并递减val。但除非val是正数，否则不能选择第二种方案（之后val将始终不为负）。(当val > 0时，选择取决于X和Y的相对速度，并且是不确定的)。当X和Y都终止时，或者当X终止且val ≤ 0时，重复命令将终止。

3. Coroutines

在并行编程中，协程被视为比子程序更基本的程序结构，而子程序可以被视为一个特殊情况（在下一节中进行处理）。

3.1 复制

问题：编写一个过程X，将由过程west输出的字符复制到过程east。解决方案：

X :: ,[c:character; west?c -> east!c]

注解：（1）当west终止时，输入"west?c"会失败，导致重复命令的终止，以及X过程的终止。此后从east发来的任何输入命令都会失败。（2）X过程在west和east之间充当一个单字符缓冲。它允许west在生产下一个字符之前，即使east还没有准备好输入前一个字符，也能继续工作。

3.2 压缩

问题：调整前面的程序，使得每两个连续的星号都被替换为向上的箭头“↑”。假设输入的最后一个字符不是星号。解决方案：

X :: ,[c:character; west?c ->

[c != asterisk -> east!c

? [c = asterisk -> west?c;

? [c != asterisk -> east!asterisk; east!c

? [c = asterisk -> east!upward arrow

? ]] ]

备注：(1) 由于west不以星号结束，第二个"west?c"不会失败。 (2) 作为练习，适应这个过程来合理处理以奇数个星号结束的输入。

3.3 拆解

问题：从卡片文件中读取卡片，并将它们包含的字符流输出到X进程。每张卡的末尾应该插入一个额外的空格。

***[cardimage:(1..80)character; cardfde?cardimage ->**

? i:integer, i := 1;

? ***[i <= 80 ->X!cardimage(i); i = i+1]**

? X!space

]

备注：(1) “(1..80)character”声明了一个有80个字符的数组，下标范围在1和80之间。 (2) 当卡片文件进程结束时，重复命令终止。

3.4 组装

问题：从X进程中读取字符流，并在行打印机上以每行125个字符打印它们。如果必要，最后一行应以空格完成。

解决方案：

lineimage:(1 .. 125)cbaractct;

i:integer; i := 1;

***[c:character; X?c ->**

? lineimage(i) := c;

? [i <= 124 -> i := i+1

? [i = 125 -> lineprinter!lineimage; i := 1

] ];

[ i = 1 -> ship]

**[i > 1 -> [i <= 125 -> lineimage(i) := space; i = i + I];*

? lineprinter!lineimage

]

备注：(1) 当X终止时，这个过程的第一个重复命令也将终止。然后，如果它有任何字符，将打印最后一行。

3.5 重新格式化

问题：读取每张80个字符的卡片序列，并在行打印机上以每行125个字符打印字符。每张卡片后面应该有一个额外的空格，并且如果需要的话，最后一行应该用空格完成。

解决方案：

[west::DISASSEMBLE||X::COPY||east::ASSEMBLE]

备注：(1) 大写的名字代表在前一部分中定义的程序文本。 (2) 并行命令设计为在卡片文件终止后终止。

(3) 没有协程，这个基础问题很难优雅地解决。

3.6 康威的问题 [4]

问题：调整上述程序，将每对连续的星号替换为向上的箭头。解决方案：

[west::DISASSEMBLE||X::SQUASH||ease::ASSEMBLE]

4. 子程序和数据表示

常规的非递归子程序可以作为协程来实现，只要（1）它的参数是“按值”和“按结果”调用的，且（2）它与其调用程序是分离的。像 Fortran 子程序一样，协程可以保留局部变量的值（在 Algol 术语中是 own 变量），并且它可以用输入命令以比 PL/1 更安全的方式实现“多入口点”的效果。因此，协程可以像 SIMULA 类实例一样用作抽象数据的具体表示。

作为子程序的协程是一个与其用户进程并行运行的过程，它在并行命令中： **[subr::SUBROUTINE||X::USER]。SUBROUTINE 将包含（或由）一个重复命令：*[X?(value params) -> ... ; X!(result params)]**，其中...从输入值计算结果。子程序将在其用户终止时终止。用户将通过一对命令调用子程序：subr!(arguments); ... ; subr?(results)。这两者之间的任何命令都将与子程序并发执行。

作为数据[l l]的表示的多入口子程序，也将包含一个重复命令，该命令用结构化目标的备用输入来表示每个入口，入口名作为构造函数。例如，

***[X?entry1(value params) -> ...**

[X?entry2(value params) -> ...]

]

调用进程 X 将决定每次重复时激活哪个选项。当 X 终止时，这个重复命令也就终止了。用户程序中的类似技术可以实现多个退出的效果。

递归子程序可以通过一个进程数组来模拟，每个递归级别有一个。用户进程是第零级。每个激活都会与其前者通信参数和结果，并在必要时调用其后继：

[recsub(0)::USER||(recsub(i: 1 ..reclimit)::RECSUB].

用户将调用

recsub: recsub(1)!(arguments); ... ; recsub(1)?(results);.

中的第一个元素。

语言的“静态”设计要求对递归深度施加固定的上限。

这种模拟递归的笨拙方法对于相互递归的算法来说会更加笨拙。它不推荐用于常规编程；它可能更适合于微处理器数组，对于该数组，固定的上限也是现实的。

在本节中，我们假设每个子程序只被单个用户进程使用（当然，它本身可能包含并行命令）。

4.1 函数：带余数的除法

问题：构建一个代表函数类型子程序的过程，该过程接受一个正的被除数和除数，并返回它们的整数商和余数。

效率不是关注点。

解决方案：

[DIV::*[x,y.integer,X?(x,y) ->

? quit,rem:integer;quot := 0; rem := x;

? ***[rem >= y -> rem := rem - y; quot := quot + 1];**

? X!(quit, rem)

? ]

||X::USER

]

4.2 递归：阶乘

问题：通过递归方法计算阶乘，到给定的限制。解决方案：

[fac(i:1 .. limit)::

***[n:integer,fac(i - 1)?n ->**

? [n = 0 -> fac(i - 1)!]

? [n > 0 -> fac(i + 1)!n - 1;

? r:integer,fac(i + 1)?r,fac(i - 1)!(n * r)

? ]]

||fac(0)::USER

]

注意：这个不切实际的例子介绍了“迭代数组”的技术，这将在后面的例子中得到更好的应用。

4.3 数据表示：小整数集 [11]

问题：将不超过100个整数的集合表示为一个进程S，该进程从其调用进程X接受两种类型的指令：（1）S!insert(n)，将整数n插入集合中，和（2）S!has(n)? ? S?b，如果n在集合中，b被设为真，否则为假。集合的初始值为空。

解决方案：

S::

content:(0..99)integer; size:integer; size := 0;

***[n:integer; X?has(n) -> SEARCH;X!(i < size)]**

[n:integer; X?insert(n) -> SEARCH;

? [i < size -> skip]

? [i = size; size < 100 ->

? content (size) := n; size := size + 1

] ]

其中 SEARCH 是以下内容的缩写：

i:integer; i := 0;

***[i < size; content(i) != n -> i := i + i]**

注释：(1) 如果尝试插入超过100个元素，带有"size < 100"守卫的alternative命令将会失败。 (2) 插入的活动通常会与调用进程同时发生。但是，对S的任何后续指令都将被延迟，直到前一个插入完成。

4.4 扫描一组数据

问题：通过提供一种快速方法来扫描集合中的所有成员而不改变集合的值，扩展4.3的解决方案。用户程序将包含以下形式的重复命令：

S!scan( ); more:boolean; more true;

***[more;x:integer; S?next(x) -> ... deal with x ....**

[more; S?noneleft( ) -> more := false]

]

其中，S!scan( ) 将表示设置为扫描模式。这个重复命令作为一个for语句，从集合中输入x的连续成员并检查它们，直到最终该表示发送一个信号表明没有剩下的成员。重复命令的主体不允许以任何方式与S通信。

解决方案：向S的外部重复命令添加第三个带守卫的命令：

... [X?scan() -> i:integer; i := 0;

? ***[i < size -> X!next(content(0)); i := i + 1];**

? X!noneleft( )

]

4.5 递归数据表示：小整数集

问题：与上面相同，但要使用一组进程来实现高度的并行性。每个进程最多应包含一个数字。当它不包含数字时，它应对所有有关成员资格的询问回答“假”。在第一次插入时，它转变为第二阶段的行为，在这个阶段，它处理来自其前任的指令，将其中一些传递给它的后继。调用进程将被命名为S(0)。为了效率，集合应该被排序，即第i个进程应该包含第i大的数字。

解决方案：

S(i:1 .. 100)::

***[n:integer; S(i - 1)?has(n) -> S(0)!false**

[n:integer; S(i - 1)?insert(n) ->

? ***[m:integer; S(i - 1)?has(m) ->**

? [m <= n -> S(0)!(m = n)]

? [m > n -> S(i + 1)!has(m)]

? ]

? [m:integer; S(i - 1)?insert(m) ->

? [m < n -> S(i + 1)!insert(n); n := m]

? [m = n -> skip]

? [m > n -> S(i + 1)!insert(m)]

]]]

注释：(1) 用户进程 S(0) 通过命令 S(1)!has(n); ... ;[(i:1 .. 100)S(i)?b -> skip] 查询 n 是否为成员。相应的进程会通过第2行或第5行的输出命令响应输入命令。这个技巧避免了将答案“沿着链”传回。(2) 许多插入操作可以并行进行，但任何后续的“has”操作都将被正确执行。(3) 所有的重复命令和数组的所有进程都将在用户进程 S(0) 终止后终止。

4.6 多出口：删除最小成员

练习：扩展上述解决方案，以响应一个命令，产生集合中的最小成员并从集合中删除它。用户程序将通过一对命令调用该功能：

S(l)!lest(); [x:integer;S(1)?x -> ... deal with x ...

? [S(1)?noneleft() -> ...

]]

或者，如果他希望扫描并清空集合，他可以这样写：

S(i)!least(); more:boolean; more := true;

? ***[more; x:integer; S(1)?x -> ... deal with x ... ; S(1)!least()**

? [more; S(1)?noneleft() -> more := false]

提示：引入一个布尔变量b，初始化为true，并将其加到内循环的所有守护程序前面。在对前任的!least()命令作出响应后，每个进程都会返回其包含的值n，询问其后继者的最小值，并将响应存储在n中。但是，如果后继者返回"noneleft()"，b将被设置为false，并且内循环终止。因此，该进程回到其初始状态（解决方案归功于David Gries）。

5. 监视器和调度

本节将展示如何将监视器视为一个与多个用户进程通信的单一进程。然而，每个用户进程必须有一个不同的名字（例如，生产者、消费者）或一个不同的下标（例如，XO）并且每个与用户的通信必须唯一地标识其来源或目的地。

因此，当监视器准备与其任何用户进程通信时（即，无论哪个用户进程首先调用），它将使用带范围的守护命令。例如：***[(i:1 .. 100)X(i)?(value parameters)] -> ... ; X(i)!(results)]**。在这里，边界变量i用于将结果发送回调用进程。如果监视器在给定的时刻不准备接受来自某个特定用户（例如，X(J)）的输入，那么输入命令可能会被一个布尔守卫所前导。例如，通过 *j = 0; [(i:1 .. 100)i != j; X(i)?(values) -> ... ; j := i] 来抑制来自同一进程的两个连续输入。任何来自X(J)的尝试输出都将被延迟，直到某个后续的迭代，在接受并处理了来自其他进程X(i)的输出之后。

同样，条件可以用来延迟接受会违反调度约束的输入——推迟它们，直到某个其他进程使监视器进入一个可以有效接受输入的状态时。这种技术类似于条件临界区域[10]，它排除了对事件、队列或条件等特殊同步变量的需求。然而，这些特殊设施的缺失肯定使得解决涉及优先级的问题变得更加困难或效率更低——例如，磁盘上的头部移动的调度。

5.1 有界缓冲区

问题：构建一个缓冲过程X，以平滑生产者进程输出部分和消费者进程输入部分的速度变化。消费者包含X!more(); X?p的命令对，生产者包含形式为X!p的命令。缓冲区应该包含多达十个部分。

解决方案：

X::

buffer:(0..9) portion;

in,out:integer; in := 0; out := 0;

comment 0 <= out <= in <= out + 10;

? ***[in < out + 10; producer?buffer(in mod 10) -> in := in + 1]**

? [out < in; consumer?more() -> consumer!buffer(out mod 10);

? out := out + 1

? ]

备注：(1) 当 out < in < out + 10 时，在重复命令中选择替代方案将取决于生产者是在消费者消费之前生产的，还是反之。 (2) 当 out = in 时，缓冲区为空，即使消费者准备好了它的命令 X!more()，也不能选择第二种替代方案。

然而，在生产者生产了下一部分之后，消费者的请求可以在下一次迭代中被满足。 (3) 对于生产者，当 in - out + 10 时，也适用类似的注解。 (4) X 被设计为在 out = in 且生产者已终止时终止。

5.2 整数信号量

问题：要实现一个整数信号量 S，它在客户端进程数组 X(i:1..100) 中共享。每个进程可能通过 S!V() 增加信号量，或通过 S!P() 减少它，但如果信号量的值不是正数，那么后一个命令必须被延迟。

解决方案：

S::val:integer; val := 0;

? ***[i:1 .. 100)X(i)?V() -> val := val + 1**

? [(i:1 .. 100)val > 0; X(i)P() -> val := val - 1]

? ]

备注：(1) 在这个过程中，没有使用到调用进程的下标 i 的知识。 (2) 只有当进程数组 X 的所有一百个进程都终止时，信号量才终止。

5.3 餐桌哲学家问题（由 E.W. Dijkstra 提出）

问题：五位哲学家度过了他们的一生，沉浸在思考和吃饭中。这些哲学家共享一个共同的餐厅，那里有一张五把椅子围着的圆桌，每把椅子都属于一位哲学家。在桌子的中央有一个大碗的意大利面，桌子上放着五把叉子（见图 1）。当感到饿的时候，一位哲学家会走进餐厅，坐在他自己的椅子上，并捡起他位置左边的叉子。不幸的是，意大利面如此纠缠，以至于他还需要捡起并使用他右边的叉子。当他吃完后，他放下两把叉子，并离开房间。房间应该保持记录其中的哲学家数量。

图 1.

解决方案：第 i 位哲学家的行为可以描述如下：

*PHIL = [... during ith lifetime ... ->

? THINK;

? room!enter();

? fork(i)!pickup(); fork((i + l) mod 5)!pickup();

? EAT;

? fork(i)!putdown(); fork((i + 1) mod 5)!putdown();

? room!exit()

? ]

第 i 把叉子的命运是要被坐在它任一侧的哲学家拿起并放下。

FORK =

? ***[phil(i)?pickup() -> phil(i)?putdown()**

? (phil(i - 1)mod 5)?pickup() -> phil((i - 1) mod 5)?putdown()

]

房间的故事可以简单地描述如下：

ROOM occupancy:integer; occupancy := 0;

? ***[(i:0..4)Phil(i)>enter()] -> occupancy := occupancy + 1)**

? (i:0..4)Phil(i)?exit() -> occupancy := occupancy - 1

]

所有这些组件都是并行操作的：

[room::ROOM||fork(i:0..4)::FORK||phil(i:0..4)::PHIL].

注释：（1）上述给出的解决方案不能防止所有五位哲学家进入房间，每人拿起他的左叉子，然后因为他不能拿起他的右叉子而饿死。（2）练习：调整上面的程序，以避免这种可悲的可能性。提示：防止超过四位哲学家进入房间。（解决方案由E. W. Dijkstra提供）。

6. 杂项

本节包含了使用 communicating sequential processes 解决一些不太熟悉问题的更多示例；Eratosthenes筛法的并行版本，以及迭代数组的设计。提出的解决方案比前几节的还要更加推测性，而在第二个例子中，甚至忽略了终止的问题。

6.1 质数：Eratosthenes筛法 [14]

问题：以升序打印小于10000的所有质数。使用一个进程数组SIEVE，其中每个进程从其前任输入一个质数并打印它。然后，该进程从其前任输入一个升序数字流，并将它们传递给它的后继，抑制原始质数的任何倍数。

解决方案：

[SIEVE(i:1..100)::

? p,mp:integer;

? SIEVE(i - 1)?p;

? print!p;

? mp := p; comment mp is a multiple of p;

***[m:integer; SIEVE(i - 1)?m ->**

? ***[m > mp -> mp := mp + p];**

? [m = mp -> skip]

? [m < mp -> SIEVE(i + 1)!m]

] ]

注释：（1）这个美丽的解决方案由David Gries贡献。（2）它在算法上类似于在[7，pp. 27—32]中开发的程序。

6.2 迭代数组：矩阵乘法

问题：给定一个3阶的方阵A。要输入三个流，每个流代表数组IN的一列。要输出三个流，每个代表乘积矩阵IN X A的一列。经过初始延迟后，结果应以与输入消耗相同的速率产生。因此，需要高度的并行性。解决方案应采取图2所示的形式。九个非边界节点中的每一个都从西部输入一个向量分量和从北部输入一个部分和。每个节点将向量分量输出到它的东部，并向南部更新部分和。输入数据由西边界节点产生，所需的结果由南边界节点消耗。北边界是零的恒定源，东边界只是一个汇。不需要为终止提供，也不需要更改数组A的值。

图2.

解决方案：有二十一个节点，分为五组，包括中央方格和四个边界：

[M(i:1..3,0)::WEST

||M(0,j:1..3)::NORTH

||M(i:1..3,4)::EAST

||M(4,j:1..3)::SOUTH

||M(i:1..3,j:1..3)::CENTER

]

西边和南边边界是用户程序的进程；其余的进程为：

*NORTH = [true -> M(1,j)!0]

*EAST = [x:real; M(i,3)?x -> skip]

*CENTER = [x:real; m(i,j - 1)?x ->

? M(i,j + 1)!x; sum:real;

? *M(i - 1,j)?sum; M(i + 1,j)!(A(i,j)x + sum)

]

7. 讨论

一种编程语言的设计必须涉及许多看似相当武断的决定。本节的讨论旨在解释一些基础动机，并提及一些未解决的问题。

7.1 符号表示法

我选择了单字符符号（例如！,？）来表达原始概念，而不是更传统的粗体或下划线英文单词。因此，这些例子具有类似APL的简洁性，有些读者可能觉得这不太合口味。我的解释是（与APL相对），这里只有很少的几个基本概念，并且数学的标准做法（也是良好的编码实践）是用简短的符号（例如+，x）来表示常见的基本概念。当大声读出时，这些符号被单词（例如plus，times）替代。

一些读者建议用赋值表示法表示输入和输出：

<target variable> := <source>

<destination> := <expression>

我发现这个建议容易引起误解：最好将输入和输出视为不同的原语，因而用不同的符号表示。

我用同一对括号（[...l）来括住所有的程序结构，而不是更为熟悉的多种括号（if..fi, begin..end, case...esac, 等等）。在这一点上，我遵循了正常的数学实践，但我也必须承认对像fi, od, 或esac这样的词的发音感到不喜。

我对于我的符号表示法为结构表达式和带下标的变量赋予了相同的语法感到不满。或许应该用一个特殊的符号（比如#）来区分标签和其他标识符。

我曾经尝试引入一种联合声明和输入的缩写，例如X?(n:integer)来表示n:integer; X?n。

7.2 明确命名

我的设计坚持每个输入或输出命令必须明确地命名其来源或目的地。这使得编写可以包含在后续程序中的进程库变得不方便，而不考虑该程序中使用的进程名。对此问题的部分解决方案是允许并行命令的一个进程（主进程）有一个空的标签，并允许该命令中的其他进程使用空的进程名作为输入或输出的来源或目的地。

对于构建大型程序，还将需要一些更通用的技术。至少应允许用程序文本替换在其他地方定义的名称——这是一种在本文中一直非正式使用的技术。Cobol的COPY动词也允许在复制的文本中替换形式参数。但无论引入哪种设施，我都会推荐以下原则：每个程序，在与其库例程组合后，应该能够完全用这种语言打印为文本，并且这个打印的文本应该描述程序的执行，独立于哪些部分来自库。

由于我无意设计一种完整的语言，我忽略了库的问题，以便集中研究实际执行的程序的基本语义概念。

7.3 端口名称

明确命名来源和目标的一种替代方法是命名一个将要进行通信的端口。端口名称将局限于进程内部，并且在并行命令的头部可以声明通过通道连接的一对端口的方式。

这是一种有吸引力的替代方案，可以设计来引入一定程度的可语法检查的冗余。但在语义上，只要每个端口仅连接到另一进程中的另一个端口，它与当前的提案等价。在这种情况下，每个通道都可以与标签以及另一端的进程的名称相对应。由于我想集中精力研究语义，我更喜欢在本文中使用最简单和最直接的符号表示法，并避免提出通过单一通道连接多个端口的可能性的问题。

7.4 自动缓冲

与输入和输出的同步相比，通常有一种建议，即允许输出进程继续进行，即使输入进程还没有准备好接受输出。实现期望自动插入一组缓冲区来保存还未被输入的输出消息。

我故意拒绝了这个替代方案，有两个原因：(1) 在多个不相交的处理器中实现这一点是不太现实的，(2) 当某个特定通道需要缓冲时，可以使用给定的原语轻松地指定它。当然，也可以同样争论说，通过使用一对缓冲的输入和输出命令，可以在需要的时候指定同步。

7.5 无界进程激活

对于进程数组的符号表示允许相同的程序文本（像Algol递归程序一样）具有多个同时的"激活"；但是，确切的数量必须事先指定。在传统的单处理器实现中，这可能导致不便和浪费，就像Fortran的固定长度数组一样。因此，允许进程数组在元素数量上没有事先规定的界限将是有吸引力的；并指定程序的特定执行所需的确切元素数量应该像Algol程序的递归最大深度或重复命令的迭代次数一样，动态确定。

然而，每个实际运行的程序，其无界数组应与所有其数组都提前设定界限的某个程序的运行相同，这是一个好的原则。因此，无界程序应被定义为一系列界限逐渐增加的有界程序的“极限”（在某种意义上）。我选择集中研究有界情况的语义——这无论如何都是必要的，并且对于在多个微处理器上的实现更为现实。

7.6 公平性

考虑以下并行命令：

[X:: Y!stop()||Y::continue:boolean; continue true;

? ***[continue; X?stop() -> continue := false**

? ||continue -> n := n + I

? ]

]

如果实现总是在Y的重复命令中偏爱第二种替代方案，那么它被认为是不公平的，因为尽管X中的输出命令可以在无数次机会上被执行，但实际上它总是被忽略。

这引出了一个问题：编程语言的定义应该指定实现必须是公平的吗？在这里，我相当确定答案是不。否则，尽管它的非确定性是无界的，实现仍会被迫成功完成上面展示的示例程序。因此，我建议程序员有责任证明他的程序可以正确终止——而不依赖于实现的公平性假设。因此，上面显示的程序是不正确的，因为其终止不能被证明。

尽管如此，我建议高效的实现应该试图表现得相当公平，并且应确保在输出命令首次变得可执行之后不会被无理延迟。但是，正确性的证明不能依赖于高效实现的这一属性。考虑以下与顺序程序的类比：一个高效实现的替代命令倾向于偏爱可以最有效执行的替代方案，但程序员必须确保他的程序的逻辑正确性不依赖于他的实现的这一属性。

规避公平性问题的这种方法不适用于如操作系统这样的程序，因为这类程序旨在永远运行，因此在这种情况下终止证明不相关。但我怀疑编写或执行这样的程序是否真的明智。即便是操作系统也应该被设计成在输入指示它这样做的消息后不久将自己带到有序的结束。否则，停止它的唯一方法就是让它“崩溃”。

7.7 函数协程

将这里描述的进程与[121]中提出的进程进行比较是有趣的；差异最为显著。在那里，协程是严格确定性的：在输入源之间没有选择。输出命令会被自动缓冲到任何所需的程度。一个进程的输出可以自动扩展到任意数量的进程（包括它自己！）且可以以不同的速率消耗它。最后，在那里的进程被设计成永远运行，而我的提议的并行命令通常是预期要终止的。[121]中的设计基于一个优雅的理论，该理论允许证明程序的属性。这些差异不是偶然的——它们似乎是编程的更抽象的应用性（或功能性）方法和更以机器为导向的命令性（或过程性）方法之间的差异的自然结果，后者是由通信顺序进程采用的。

7.8 输出监护

由于输入命令可能出现在守护中，允许输出命令似乎会更对称。这会在一些示例程序中允许一个明显且有用的简化，例如，在有界缓冲区（5.1）中。也许更有说服力的理由是要确保每个并行命令的外部可见效应和行为都可以由某个顺序命令建模。为了模拟并行命令：

Z :: [X!2||Y!3]

我们需要能够编写顺序替代命令：

Z :: [X!2 -> Y!3||Y!3 -> X!2]

注意，这个命令不能完成这个任务。

Z :: [true -> X!2; Y!3||true -> Y!3; X!2]

这个命令可能会失败，如果进程 Z 选择了第一个选项，但是进程 Y 和 X 彼此同步，以这样的方式，Y 必须在 X 之前从 Z 处输入，例如。

Y :: Z>y; X!go() || X :: y?go; Z?x

7.9 限制：带输入保护的重复命令

在提出一种不常见的编程语言特性时，首先规定一种高度限制性的版本而不是提出扩展似乎更明智——特别是当该语言特性声称是原始的时候。例如，很明显，多维进程数组不是原始的，因为它可以容易地在只允许单维数组的语言中被构建。但我对带输入保护的重复命令有更为严重的疑虑。

一个重复命令在其所有输入保护的源终止时的自动终止是一项极其强大且方便的特性，但它也涉及一些规范的微妙之处，以确保它是可实现的；并且它肯定不是原始的，因为通过明确交换“end()”信号可以达到所需的效果（尽管带来相当的不便）。

例如，子程序 DIV（4.1）可以被重写：

[DIV :: continue:boolean; continue := true;

? ***[continue; X?end() -> continue := false**

? ||continue; x,:integer; X?(x,y) -> ...; X!(quot, rem)

? ||X :: USER PROG; DIV!end()

]

但其他例子会更加不方便。

但是，方便设施的危险是众所周知的。例如，带输入保护的重复命令可能会诱使程序员在没有为它们的终止制定充分计划的情况下编写它们；如果事实证明自动终止是不满意的，那么为显式终止重新编程将涉及严重的变更，甚至会影响进程之间的接口。

8. 结论

本文提出了输入、输出和并发应被视为编程的基元，它们是许多熟悉和不太熟悉的编程概念的基础。然而，得出这些基元可以完全替代编程语言中的其他概念的结论将是不合理的。在更为复杂的构造（例如过程或监视器）经常有用、其属性更容易被证明，并且比一般情况更能高效实现的地方，有充分的理由在编程语言中为该构造包含一个特殊的符号。该构造可以用更简单的基元来定义的事实是一个有用的保证，表明它的包含在逻辑上与语言的其余部分一致。

致谢。本文中报告的研究得到了英国科学研究委员会的高级研究员奖励和支持。技术灵感来自于Edsger W. Dijkstra [91]，D. Gries、D. Q. M. Fay、Edsger W. Dijkstra、N. Wirth、Robert Milne、M. K. Harper 和审稿人的宝贵且细致的建议在表达和内容上改进了论文。非常愉快和感激地承认了IFIP W.G.2.3作为一个展示和讨论的论坛的作用。

收稿日期：1977年3月；修订日期：1977年8月。

参考文献

1. Atkinson, R., 和 Hewitt, C. actor系统中的同步。

工作报告83，M.I.T.，剑桥，马萨诸塞州，1976年11月。

1. Brinch Hansen, P。并行Pascal编程语言。IEEE Trans. Software Eng. 1, 2 (1975年6月)，199-207。3. Campbell, R.H.，和 Habermann, A.N. 通过路径表达式指定进程同步。Lecture Notes in Computer Science 16, Springer，1974，页数：89—102。4. Conway, M.E. 可分离过渡图编译器的设计。Comm. ACM 6, 7 (1963年7月)，396-408。
2. Dahl, O-J. 等。SIMULA 67，通用基础语言。挪威计算中心，Forskningveien，奥斯陆，1967。
3. Dijkstra, E.W. 协作顺序进程。在编程语言中，F. Genuys，Ed.，学术出版社，纽约，1968，页数：43-112。
4. Dijkstra, E.W. 结构化编程的笔记。在结构化编程中，学术出版社，纽约1972，页数：1—82。8. Dijkstra, E.W. 保护的命令，非决定性，和程序的正式推导。Comm. ACM 18, 8 (1975年8月)，453—457。
5. Dijkstra, E.W. 口头交流，Marktoberdorf，1975年8月。
6. Hoare, C.A.R. 迈向并行编程的理论。在操作系统技术中，学术出版社，纽约，1972，页数：61-71。
7. Hoare, C.A.R. 数据表示的正确性证明。Acta Informatica 1, 4 (1972)，271-281。
8. Kahn, G. 一个简单并行编程语言的语义。在Proc. IFIP Congress 74中，North Holland，1974。13. Liskov, B.H. 关于CLU的注释。Computation Structures Group Memo. 112，M.I.T.，剑桥，马萨诸塞州，1974。
9. Mcllroy, M.D. 协同程序。Bell Laboratories，Murray Hill，NJ.，1968。
10. Naur, P., 编辑。关于算法语言ALGOL 60的报告。

Comm. ACM 3, 5 (1960年5月)，299-314。

1. Reynolds, J.C. COGENT。ANL-7022，Argonne Nat, Lab.，Argonne，Ill.，1965。
2. Thompson, K. UNIX命令语言。在结构化编程中，Infotech，Nicholson House，Maidenhead，英格兰，1976，页数：375-384。
3. van Wijngaarden, A. 编辑。关于算法语言ALGOL 68的报告。Numer. Math. 14 (1969)，79-218。
4. Wulf, W.A.，London. R.L.，和 Shaw, M. 在ALPHARD中的抽象和验证。计算机科学系，卡内基-梅隆大学，匹兹堡，Pa.，1976年6月。
5. Wirth, N. 编程语言PASCAL。Acta Informatica 1, 1 (1971)，35-63。