While语言

Question

对于我的理论计算语言类，我们得到了一项家庭作业的任务分配，用一种语言来实现一段代码，该语言只有流量控制语句（没有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循环以外。
• 没有作弊：上面的语法不包括任何中断语句，返回语句或异常。不要使用它们。

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

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

是图灵完备，你需要同时支持选择和迭代。虽然循环显然迭代。如果条件为真，则选择可以通过一次循环来完成，否则就不会完成。

因此，最糟糕的情况是，您可以通过应用这些技术来做您需要的一切。我想象一些复杂的控制流将会变得很难看。 :-)

Answer 4

会这样吗？

td := d 
x := 1 

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

Answer 5

如果不使用真或假分支的细节，并且在不重复谓词：

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's answer膨胀。

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

• 评估<condition>;
• 如果是，请执行then和else之间的声明;
• 否则，请执行else和fi之间的声明。

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

• 评估<condition>;
• 如果为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 and A（这是真的当且仅当A为true）
• 如果为真，则：
  • 执行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's）的回答与其他的回答分开。