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

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

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

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

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

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, а также будет 1. Это завершает цикл.

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

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>;
• если ложь, 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;
• Если 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) ответ от других, на мой взгляд.