整个语言是什么意思？

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语句或异常。请勿使用它们。

我已经为此编写了我的一部分代码（为了证明这不是一个“show me teh codez”贴子，我会把它发布出来）。但我很好奇其他人能想出什么来。

- Jason Baker

---

在完成作业的基础上，额外努力获取更多反馈会得到加分。 - Mostlyharmless

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。

- Gamecat

---

这会改变d和a的值，可能会产生不良影响。您可以通过以下方式进行修复： 在开头添加： d1：= d; a1：= a;在结尾添加： d：= d1; a：= a1; - Brian Postow

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

- Jason Baker

---

是的，我认为关键是一个名为getOutOfJail的变量，用于终止while循环。我的VB.NET、C#、Perl、PHP、Java、Javascript和ECMAScript示例将遵循这种模式。 - jrcs3

这并不会给你带来“否则”的效果。如果'd'在第一个while循环中设置为非零数字，那么会发生什么？如果发生了这种情况，那么IF路径和ELSE路径都将运行。 - BobbyShaftoe

@Jason Baker，我认为你的解释颠倒了，但代码是正确的... - Brian Postow

语言定义中没有“True”或“False”，除非cons允许。你可能需要使用C风格的布尔值（1和0）和“and continue = 1”。但除此之外，这是一个好的解决方案。 - paxdiablo

我的教授并没有非常清楚地讲解那个问题。根据其他的课程，我想我有点作弊了。 :-) - Jason Baker

Answer 3

这个方案可行吗？

td := d
x := 1

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

- Zach Scrivena

---

因此，通过覆盖默认值并优化谓词，可以避免另一个循环。也许值得仅表达覆盖思想：continue := True; x := 1; while d != 0 and continue do x := a/d; continue := False od - Vesal

Answer 4

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

因此，最坏情况下，你可以通过应用这些技术来完成所需的一切。但我想象一些复杂的控制流程可能会变得非常丑陋。 :-)

- T.E.D.

Answer 5

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

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

- Eamon Nerbonne

Answer 6

这是Eamon's answer的扩展内容。

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

• 评估 <condition>；
• 如果为真，则执行 then 和 else 之间的语句；
• 否则，执行 else 和 fi 之间的语句。

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

• 评估 <condition>；
• 如果为假，则 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 and A（当且仅当A为真时为真）。 - 如果为真，则执行以下操作：

- 执行B。 - 执行gensymN = 1。 - 计算gensymN = 0 and A（它为假）。 - 计算gensymN = 0（它为假）。

- 否则（如果gensymN = 0 and A为假）：

- 计算gensymN = 0（它为真）。 - 执行C。 - 执行gensymN := 1。 - 计算gensymN = 0（它为假）。

观察上述内容的以下子结构：

• 它（有效地）评估A；
• 如果为真，则执行B，否则执行C。
• 除了A、B和C之外，程序（片段）只对gensymN进行操作，该变量不在输入程序中。

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

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

一点注释：如果在评估时A为真，则会再次评估它（除非and是短路的）。 如果语言允许在变量中存储布尔值，则可以引入一个虚拟变量并执行dummy：= A; <insert the above program here, with dummy instead of A>。 然后，对dummy的两次评估本质上只是一次加载。 如果评估布尔表达式不能产生副作用，则不需要防止第二次评估以确保正确性； 它可能（或可能不）是一种优化。

将上述内容视为“软证明”，前提是前面的段落，这是将if完全通用地转换为while的正确方法。 在我看来，这种完全通用性使得这个答案（即Eamon的答案）与其他答案有所不同。

- Jonas Kölker