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

Question

Для моей теории класса языков вычислений мы получили домашнее задание для реализации части кода на языке, который имеет только инструкции для управления потоком (без операторов if). Это в основном доказывает, что вы можете написать язык Turing с полным циклом 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, операторов возврата или исключений. Не используйте их.

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

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 d == 0 do 
    d := 1; 
    a := 1 
od 
x := a/d; 

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

Теперь х устанавливается в/д, который в порядке, потому что, если d 0, а/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 еще раз.

Чтобы выразить 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) ответ, кроме других.