В то время как язык

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

В любом случае, если вы хотите пойти дальше и написать это, используя языковые правила выше, продолжайте. В противном случае продолжайте и напишите это на том языке, на котором вам удобнее всего. Но есть несколько предостережений!

• Нет операторов if или любого другого типа управления потоком, кроме циклов while.
• Никакого обмана: приведенная выше грамматика не включает в себя операторы break, return-операторы или исключения. Не используйте их.

У меня для этого написан кусок кода (который я опубликую, чтобы доказать, что это не шоу для поста с кодом). Мне любопытно, что кто-то еще может придумать.

Answer 1

Это можно сделать с помощью одного цикла while, но это не так ясно:

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

Пояснение, если d = 0, то d будет 1, а также будет 1. Это завершает цикл.

Теперь для x установлено значение a / d, и это нормально, потому что если d равно 0, значение a / d будет равно 1.

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

Answer 3

Будет ли это работать?

td := d
x := 1

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

Answer 4

Чтобы быть завершенным по Тьюрингу, необходимо поддерживать как выбор, так и итерацию. Хотя циклы явно повторяются. Выделение может быть выполнено путем однократного прохождения цикла, если условие истинно, и совсем не иначе.

Так что в худшем случае вы можете делать все, что вам нужно, применяя эти методы. Я предполагаю, что некоторые сложные потоки управления будут ужасно быстрыми. : -)

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

Это расширение ответ Имон .

Семантика if <condition> then <stmt> else <stmt> fi следующая:

• оценить <condition>;
• если это правда, выполнить оператор между then и 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 (это правда, если A верно)
• Если это правда, то:
  • выполнить B
  • выполнить gensymN = 1
  • оценить gensymN = 0 and A (неверно)
  • оценка gensymN = 0 (неверно)
• else (если gensymN = 0 and A было ложным):
  • оценить gensymN = 0 (это правда)
  • выполнить C
  • выполнить gensymN := 1
  • оценить gensymN = 0 (неверно)

Обратите внимание на следующую подструктуру вышеупомянутого:

• (эффективно) оценивает A;
• Если true, выполняется 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) ответ от других.