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

它可以用一个 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 2

这是我的代码：

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 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

这是Eamon 的答案的扩展。

if的语义 然后否则fi 如下：

• 评估;
• 如果为 true，则执行 then 和 else 之间的语句；
• 否则，执行else和fi之间的语句。

while的语义 做od 如下：

• 评估 ;
• 如果为 false，则 while 语句执行完毕；
• 否则，执行do和od之间的语句，并再次执行while语句。

要用 while 表达 if A then B else C，请执行以下转换：

令 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 和 A（如果 A 为真，则为真）
• 如果为真，则：
  • 执行B
  • 执行gensymN = 1
  • 评估gensymN = 0 和 A（错误）
  • 评估gensymN = 0（错误）
• else（如果 gensymN = 0 且 A 为假）：
  • 评估gensymN = 0（这是真的）
  • 执行C
  • 执行gensymN := 1
  • 评估gensymN = 0（错误）

观察上面的以下子结构：

• 它（有效地）评估A；
• 如果为 true，则执行 B，否则执行 C。
• 除了 A、B 和 C 之外，程序（片段）仅对 gensymN 进行摆弄，而 gensymN 并不存在在输入程序中。

因此，这个程序与一个脚注具有相同的语义

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

：如果A在求值时为真，它将再次求值（除非and是短路的）。 如果语言允许在变量中存储布尔值，则可以再引入一个虚拟变量并执行 dummy := A; <在此处插入上述程序，用虚拟代替 A>。 那么 dummy 的两次评估本质上只是一个负载。 如果评估布尔表达式不会产生副作用，则不必为了正确性而阻止第二次评估； 它可能是（也可能不是）优化。

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