Языковой язык

Для моей теории класса языков вычислений мы получили домашнее задание для реализации части кода на языке, который имеет только инструкции для управления потоком (без операторов 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

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

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

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

Ответ 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

Ответ 2

Это можно сделать с помощью одного цикла 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.

Ответ 3

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

td := d
x := 1

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

Ответ 4

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

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

Ответ 5

Без использования деталей истинных или ложных ветвей и без повторения предиката:

statementIncomplete := True
while d = 0 and statementIncomplete do
    x := 1
    statementIncomplete := False
od
while statementIncomplete do
    x := a/d
    statementIncomplete := False
od

Ответ 6

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

Семантика 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 (это верно, если if A истинно)
Если true, то:
- выполнить 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) ответ, кроме других.