提问人： 提问时间：2/3/2009 最后编辑：5 revs, 4 users 66%Jason Baker 更新时间：9/24/2019 访问量：6812
while 语言
The while language
问：
在我的计算理论语言课上，我们得到了一个家庭作业，用一种只有 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
无论如何，如果您想继续使用上面的语言规则来编写它，请继续。否则，请继续用您最熟悉的语言编写它。但有一些注意事项！
- 没有 if 语句或除 while 循环之外的任何其他类型的流控制。
- 没有作弊：上面的语法不包括任何中断语句、返回语句或异常。不要使用它们。
我已经为此编写了一段代码（我将发布它只是为了证明这不是向我展示代码帖子）。不过，我有点好奇其他人能想出什么。
答：
9赞
Jason Baker
#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
评论
1赞
jrcs3
2/3/2009
是的，我认为关键是一个 getOutOfJail 变量，用于短路 while 循环。我的 VB.NET，C#，Perl，PHP，Java，Javascript。ECMAScript 示例将遵循此模式。
0赞
BobbyShaftoe
2/3/2009
这不会给你带来“其他”效果。如果在第一个 while 循环中将“d”设置为非零数字会怎样？如果发生这种情况，那么您将同时运行 IF 路径和 ELSE 路径。
0赞
jrcs3
2/3/2009
另一个将是 while（getOutOfJail） ...（没有其他条件）在另一个 while 语句之后。
0赞
Jason Baker
2/3/2009
@BobbyShaftoe - 这就是 continue 变量的用途。如果 d 设置为非零，则 continue 将为 false，并且第二个循环将不会运行。
0赞
Brian Postow
2/3/2009
@Jason Baker，我认为你的解释是倒过来的，但代码是对的......
10赞
Toon Krijthe
#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。
评论
0赞
Brian Postow
2/3/2009
这会改变 d 和 a 的值，这可能会产生不良的副作用。你可以用以下方法解决这个问题： d1 ：= d;a1 ：= a;在开头和 d ：=d1;一个 ：= a1;在最后。
3赞
T.E.D.
#3
要实现图灵完备，您需要同时支持选择和迭代。虽然循环显然是迭代的。如果条件为真，则可以通过让它通过循环一次来完成选择，否则则完全不通过。
因此，最坏的情况是，您可以通过应用这些技术来做您需要的一切。不过，我想一些复杂的控制流程会很快变得丑陋。:-)
7赞
Zach Scrivena
#4
这行得通吗？
td := d
x := 1
while td != 0 do
x := a / d
td := 0
od
评论
0赞
Vesal
10/23/2018
因此，这通过覆盖默认值并优化谓词来避免另一个循环。可能值得只表达覆盖的想法：continue := True; x := 1; while d != 0 and continue do x := a/d; continue := False od
2赞
Eamon Nerbonne
#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
1赞
2 revsJonas Kölker
#6
这是对 Eamon 答案的扩展。
的语义如下：if <condition> then <stmt> else <stmt> fi
- 评价
<condition>; - 如果为 true，则执行 和 之间的语句
thenelse; - 否则，执行 和 之间的语句。
elsefi
的语义如下：while <condition> do <stmt> od
- 评价
<condition>; - 如果为 false，则语句完成执行;
while - 否则，执行 和 之间的语句，然后再次执行该语句。
doodwhile
要用 表示，请执行以下转换：if A then B else Cwhile
设为不用于任何其他变量的名称;然后发出以下代码gensymN
gensymN := 0;
while gensymN = 0 and A do B; gensymN = 1; od;
while gensymN = 0 do C; gensymN = 1; od
该程序的语义是：
- 将 0 分配给 。
gensymN - 评估（这是真的，iff是真的）
gensymN = 0 and AA - 如果为 true，则：
- 执行
B - 执行
gensymN = 1 - 评估（这是假的）
gensymN = 0 and A - 评估（这是假的）
gensymN = 0
- 执行
- else （if 为 false）：
gensymN = 0 and A- 评估（这是真的）
gensymN = 0 - 执行
C - 执行
gensymN := 1 - 评估（这是假的）
gensymN = 0
- 评估（这是真的）
观察上述的以下子结构：
- 它（有效地）评估
A; - 如果为 true，则执行 ，否则 。
BC - 除了 和 之外，程序（片段）只摆弄 ，而 在输入程序中不存在。
ABCgensymN
因此，该程序具有与
if A then B else C fi; gensymN := 1
一个脚注：如果评估时为真，则将再次评估（除非短路）。如果语言允许在变量中存储布尔值，则可以再引入一个虚拟变量并执行 .那么这两个评估本质上只是一个负载。如果计算布尔表达式不会产生副作用，则为了正确性，没有必要阻止第二次计算;它可能是（也可能不是）优化。Aanddummy := A; <insert the above program here, with dummy instead of A>dummy
以上述内容为“软证明”，加上前一段的附带条件，这是 to 的正确完全通用翻译。在我看来，完全的普遍性使这个（= Eamon的）答案与其他答案区分开来。ifwhile
评论