while 语言

Question

在我的计算语言理论课程中，我们接到了一项作业，要求用一种只有 while 语句进行流程控制（没有 if 语句）的语言来实现一段代码。这主要是为了证明只用while循环就可以写出图灵完备的语言。

对于那些能够理解语言语法的人来说，以下是语言规则：

S -> S;S | while C do S od | id := E

E -> E + T | T | E - T

T -> T * F | F | F / T

F -> id | cons | (E)

C -> E = E | E > E | E < E | E >= E | E <= E | E != E | C and C | C or C | not(C)

这是从我的课堂笔记中复制的，所以如果有遗漏或不正确的地方，请不要责怪我！

要实现的代码片段是这样的：

if d = 0 do
    x := 1
else
    x := a / d

无论如何，如果您想继续使用上面的语言规则来编写它，那就继续吧。否则，请继续用您最熟悉的任何语言编写它。但有一些注意事项！

• 除了 while 循环之外，没有 if 语句或任何其他类型的流程控制。
• 别作弊：上面的语法不包含任何break语句、return语句或异常。不要使用它们。

我已经为此编写了一段代码（我发布它只是为了证明这不是一个向我展示代码的帖子）。我有点好奇其他人能想出什么。

Answer 1

这是我的代码：

continue := True
while d = 0 and continue do
    x := 1
    continue := False
od
while d != 0 and continue do
    x := a/d
    continue := False
od

Answer 2

可以用一个 while 循环来完成，但不太清楚：

while d == 0 do
  d := 1;
  a := 1
od
x := a / d;

解释一下，如果 d = 0，那么 d 将为 1，a 也将为 1。这结束了循环。

现在 x 设置为 a / d ，这很好，因为如果 d 为 0，则 a / d 的计算结果为 1。

Answer 3

这行得通吗？

td := d
x := 1

while td != 0 do
    x := a / d
    td := 0
od

Answer 4

要实现图灵完备，您需要支持选择和迭代。While 循环显然是迭代的。如果条件为真，则可以通过使其循环一次来完成选择，否则根本不循环。

因此，在最坏的情况下，您可以通过应用这些技术来完成您需要做的一切。我想一些复杂的控制流程会很快变得丑陋。:-)

Answer 5

不使用 true 或 false 分支的详细信息，也不重复谓词：

statementIncomplete := True
while d = 0 and statementIncomplete do
    x := 1
    statementIncomplete := False
od
while statementIncomplete do
    x := a/d
    statementIncomplete := False
od

Answer 6

这是一个扩展 埃蒙的回答.

的语义 if <condition> then <stmt> else <stmt> fi 如下：

• 评价 <condition>;
• 如果为真，则执行之间的语句 then 和 else;
• 否则，执行之间的语句 else 和 fi.

的语义 while <condition> do <stmt> od 如下：

• 评价 <condition>;
• 如果为假，则 while 语句执行完毕；
• 否则，执行之间的语句 do 和 od, ，并执行 while 再次声明。

表达 if A then B else C 按照 while, ，执行以下变换：

让 gensymN 是未用于任何其他变量的名称；然后发出以下代码

gensymN := 0;
while gensymN = 0 and A do B; gensymN = 1; od;
while gensymN = 0 do C; gensymN = 1; od

该程序的语义是：

• 将 0 分配给 gensymN.
• 评价 gensymN = 0 and A （这是真的，当且仅当 A 是真的）
• 如果为真，则：
  • 执行 B
  • 执行 gensymN = 1
  • 评价 gensymN = 0 and A （这是假的）
  • 评价 gensymN = 0 （这是假的）
• 否则（如果 gensymN = 0 and A 是假的）：
  • 评价 gensymN = 0 （这是真的）
  • 执行 C
  • 执行 gensymN := 1
  • 评价 gensymN = 0 （这是假的）

观察上面的以下子结构：

• 它（有效地）评估 A;
• 如果为 true，则执行 B, ， 否则 C.
• 除了 A, B 和 C, ，程序（片段）只摆弄 gensymN, ，它不存在于输入程序中。

因此该程序具有与以下相同的语义

if A then B else C fi; gensymN := 1

一个脚注：如果 A 评估时为 true，则会再次评估（除非 and 是短路）。如果该语言允许在变量中存储布尔值，则可以再引入一个虚拟变量并执行以下操作： dummy := A; <insert the above program here, with dummy instead of A>. 。那么这两个评价 dummy 本质上只是一个负载。如果评估布尔表达式不会产生副作用，则不必为了正确性而阻止第二次评估；它可能是（也可能不是）优化。

将上述作为“软证明”，加上前一段的附加条件，这是一个正确的 完全一般化 的翻译 if 到 while. 。在我看来，完整的普遍性使这个（=埃蒙的）答案与其他答案区分开来。