24

在我的计算语言理论课上，我们得到了一个家庭作业，用一种语言实现一段代码，该语言只有用于流控制的 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 循环之外的任何其他类型的流控制。
  • 不作弊：上面的语法不包括任何 break 语句、return 语句或异常。不要使用它们。

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

4

6 回答 6

10

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

于 2009-02-03T14:48:01.020 回答
9

这是我的代码：

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
于 2009-02-03T14:37:29.857 回答
7

这行得通吗？

td := d
x := 1

while td != 0 do
    x := a / d
    td := 0
od
于 2009-02-03T15:35:06.153 回答
3

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

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

于 2009-02-03T15:23:14.723 回答
2

不使用真假分支的细节，也不重复谓词：

statementIncomplete := True
while d = 0 and statementIncomplete do
    x := 1
    statementIncomplete := False
od
while statementIncomplete do
    x := a/d
    statementIncomplete := False
od
于 2011-01-28T11:00:48.103 回答
1

这是埃蒙答案的扩展。

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

  • 评估<condition>；
  • 如果为真，则执行 and 之间的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；
  • 如果为真，则执行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本质上只是一个负载。如果评估布尔表达式不会产生副作用，则不需要阻止第二次评估以确保正确性；它可能（也可能不是）是一种优化。

将上述内容作为“软证明”，加上前一段的附带条件，这是to的正确完全一般翻译。在我看来，完整的概括性使这个（= Eamon 的）答案与其他答案区分开来。ifwhile

于 2016-08-26T21:50:58.747 回答