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

いずれにせよ、先に進み、上記の言語規則を使用してそれを書きたい場合は、先に進んでください。それ以外の場合は、最も使いやすい言語で書いてください。ただし、いくつかの注意点があります。

  • while ループ以外の if ステートメントやその他の種類のフロー制御はありません。
  • チート禁止: 上記の文法には、break ステートメント、return ステートメント、または例外が含まれていません。それらを使用しないでください。

私はこれのためにコードを書きました (コードの投稿を見せてくれるものではないことを証明するために投稿します)。私はちょっと興味がありますが、他の誰かが思い付くことができます。

4

6 に答える 6

10

単一の while ループで実行できますが、それほど明確ではありません。

while d == 0 do
  d := 1;
  a := 1
od
x := a / d;

説明、d = 0 の場合、d は 1 になり、a も 1 になります。これでループが終了します。

d が 0 の場合、a / d は 1 と評価されるため、x は a / d に設定されます。

于 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 ループは明らかに反復します。条件が true の場合はループを 1 回通過させ、それ以外の場合はループを通過させないことで、選択を実行できます。

したがって、最悪の場合、これらの手法を適用することで、必要なすべてのことを行うことができます. ただし、一部の複雑な制御フローは醜いものになると思います。:-)

于 2009-02-03T15:23:14.723 に答える
2

true 分岐または false 分岐の詳細を使用せず、述語を繰り返さずに:

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

これはEamon's answer の拡張です。

のセマンティクスif <condition> then <stmt> else <stmt> fiは次のとおりです。

  • 評価し<condition>ます。
  • thentrue の場合、との間のステートメントを実行しelseます。
  • それ以外の場合は、 ～ の間のステートメントを実行しelseますfi。

のセマンティクスwhile <condition> do <stmt> odは次のとおりです。

  • 評価し<condition>ます。
  • false の場合、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する (true の場合Aは true)
  • true の場合:
    • 実行するB
    • 実行するgensymN = 1
    • 評価するgensymN = 0 and A（それは偽です）
    • 評価するgensymN = 0（それは偽です）
  • それ以外 ( gensymN = 0 and Afalse の場合):
    • 評価しgensymN = 0ます（本当です）
    • 実行するC
    • 実行するgensymN := 1
    • 評価するgensymN = 0（それは偽です）

上記の次の部分構造を観察します。

  • それは（効果的に）評価しAます;
  • true の場合は を実行し、それ以外の場合は を実行BしますC。
  • A、Bおよび とは別に、プログラム (フラグメント)は、入力プログラムには存在しない をCいじるだけです。gensymN

したがって、このプログラムは、

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

1 つの脚注:Aが評価されたときに true の場合、もう一度評価されます (andが短絡していない限り)。言語がブール値を変数に格納できる場合、もう 1 つのダミー変数を導入して do を実行できますdummy := A; <insert the above program here, with dummy instead of A>。その場合、 の 2 つの評価dummyは本質的に単なる負荷です。ブール式の評価に副作用があり得ない場合、正確さのために 2 番目の評価を防止する必要はありません。最適化である場合もあれば、そうでない場合もあります。

上記を「ソフトプルーフ」として、前の段落の条件付きで、これが の正しい完全に一般的な翻訳であることを確認ifしてwhileください。私の見解では、完全な一般性により、この（= Eamonの）回答は他の回答とは一線を画しています。

于 2016-08-26T21:50:58.747 に答える