LOOP (язык программирования) - LOOP (programming language) - Wikipedia

ПЕТЛЯ это язык, который точно передает примитивные рекурсивные функции.[1]Единственные операции, поддерживаемые в языке, - это присваивание, сложение и повторение цикла, которое фиксируется до начала выполнения цикла.

Язык LOOP был представлен в статье 1967 г. Альберт Р. Мейер и Деннис М. Ричи. [2]Мейер и Ричи показали соответствие между языком LOOP и примитивные рекурсивные функции.

Деннис М. Ричи сформулировал язык LOOP, который также был темой его неопубликованной докторской диссертации. Тезис.[3][4]

Его также представили Уве Шёнинг, вместе с ИДТИ К и ПОКА.[5]

Функции

Каждый примитивная рекурсивная функция LOOP-вычислим, и наоборот.[6]

В отличие от ИДТИ К программы и ПОКА программы, программы LOOP всегда прекратить.[7] Следовательно, множество функций, вычислимых LOOP-программами, является собственным подмножеством вычислимые функции (и, следовательно, подмножество вычисляемых программными функциями WHILE и GOTO).[8]

Примером полной вычислимой функции, которая не является вычислимой LOOP, является Функция Аккермана.[9]

Формальное определение

Синтаксис

LOOP-программы состоят из символов ПЕТЛЯ, ДЕЛАТЬ, КОНЕЦ, :=, +, - и ; а также любое количество переменных и констант. LOOP-программы имеют следующие синтаксис в модифицированном Форма Бэкуса – Наура:

Здесь, имена переменных и являются константами.

Семантика

Если п это программа LOOP, п эквивалентно функции . Переменные через в программе LOOP соответствуют аргументам функции , и инициализируются перед выполнением программы соответствующими значениями. Все остальные переменные получают нулевое начальное значение. Переменная соответствует значению, которое принимает, когда заданы значения аргументов из через .

Заявление формы

Икся := 0

означает значение переменной установлен на 0.


Заявление формы

Икся : = хя + 1

означает значение переменной увеличивается на 1.


Заявление формы

п1; п2

представляет собой последовательное выполнение подпрограмм и , в этой последовательности.


Заявление формы

LOOP x DO п КОНЕЦ

означает повторное выполнение частичной программы Всего раз, где значение, которое has в начале выполнения оператора. Даже если меняет значение , это не повлияет на то, сколько раз выполняется в цикле. Если имеет нулевое значение, то не выполняется внутри ПЕТЛЯ утверждение. Это позволяет ветви в программах LOOP, где условное выполнение частичной программы зависит от того, имеет ли переменная значение ноль или единицу.

Примеры программ

Назначение

Следующая программа LOOP присваивает значение переменной xя к переменной xj.

Иксj : = 0; ПЕТЛЯ xя DO xj : = хj +1END

В своей основополагающей статье [10] Мейер и Ричи выполнили задание основное заявление. Как показывает приведенная выше программа, присвоение является избыточным и может быть удалено из списка основных операторов. Его можно использовать как подпрограмму в других программах LOOP. Синтаксис LOOP может быть расширен с помощью следующего оператора, эквивалентного вызову указанного выше как подпрограммы:

Иксj : = хя

Замечание: Следует иметь в виду, что все переменные глобальны. Что новый оператор эквивалентен подпрограмме не значит, что это подпрограмма. Обычно запись об активации предотвращает все побочные эффекты. Однако в этом случае никакая другая переменная, кроме xj влияет, поэтому побочные эффекты не возникают, при условии, что xj, который на этом этапе выполнения программы может содержать ненулевое значение, инициализируется значением 0.

Проекция

Частным случаем программы присваивания является программа (мы используем расширенные обозначения):

Икс0 : = хя

Эта программа вычисляет k-арную функцию проекции , который извлекает i-ю координату из упорядоченного набора k.

Предшественник

Функция-предшественник определяется как

.

Эту функцию можно вычислить с помощью следующей программы LOOP, которая устанавливает переменную к .

/ * предварительное условие: x2 = 0 * / LOOP x1 DO x0 : = 0; ПЕТЛЯ x2 DO x0 : = х0 + 1 КОНЕЦ; Икс2 : = х2 +1END

Эта программа может использоваться как подпрограмма в других программах LOOP. Синтаксис LOOP может быть расширен с помощью следующего оператора, эквивалентного вызову указанного выше как подпрограммы:

Икс0 : = х1 ∸ 1

Замечание: Опять же, нужно помнить о побочных эффектах. Программа-предшественница изменяет переменную x2, который может использоваться где-то еще. Чтобы развернуть утверждение x0 : = х1 ∸ 1 можно было инициализировать переменные xп, Иксп + 1 и хп + 2 (для достаточно большого n) до 0, x1 и 0 соответственно, запустите код для этих переменных и скопируйте результат (xп) к x0. Компилятор может это сделать.

Добавление

В следующей программе переменная устанавливается равным сумме переменных и .

ПЕТЛЯ x1 DO x0 : = х0 + 1END; LOOP x2 DO x0 : = х0 +1END

Эта программа может использоваться как подпрограмма в других программах LOOP. Синтаксис LOOP может быть расширен с помощью следующего оператора, эквивалентного вызову указанного выше как подпрограммы:

Икс0 : = х1 + х2

Отсечка вычитания

Если в программе сложения выше второй цикл уменьшает x0 вместо увеличения, программа вычисляет разность (отсекается от 0) переменных и .

Икс0 : = х1ПЕТЛЯ x2 DO x0 : = х0 ∸ 1END

Как и раньше, мы можем расширить синтаксис LOOP с помощью оператора:

Икс0 : = х1 ∸ х2

Умножение

Следующая программа LOOP устанавливает значение переменной к произведению переменных и .

ПЕТЛЯ x1 DO x0 : = х0 + х2КОНЕЦ

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

Если тогда еще

Оператор if-then-else с if x1 > х2 затем P1 иначе P2:

Иксn1 : = х1 ∸ х2;Иксn2 : = 0; хn3 : = 1; ПЕТЛЯ xn1 DO xn2 : = 1; Иксn3 : = 0END; ЦИКЛ xn2 DO P1END; LOOP xn3 СДЕЛАЙТЕ P2END;

Смотрите также

Примечания и ссылки

  1. ^ Герберт Эндертон (2012). Теория вычислимости. Академическая пресса.
  2. ^ Мейер, Альберт Р.; Ричи, Деннис М. (1967). Сложность циклических программ. ACM '67: Материалы 22-й национальной конференции 1967 года. Дои:10.1145/800196.806014.
  3. ^ "Обнаружение утерянной диссертации Денниса Ричи". CHM. 2020-06-19. Получено 2020-07-14.
  4. ^ «Проект структуры программы и вычислительной сложности | 102790971 | Музей истории компьютеров». www.computerhistory.org. Получено 2020-07-14.
  5. ^ Шёнинг, Уве (2008). Теоретическая информатика-kurz gefasst (5-е изд.). Лондон: Издательство Оксфордского университета. п. 105. ISBN  978-3-8274-1824-1. DNB 986529222.
  6. ^ Шёнинг, Уве (2008). Теоретическая информатика-kurz gefasst (5-е изд.). Лондон: Издательство Оксфордского университета. п. 105. ISBN  978-3-8274-1824-1. DNB 986529222.
  7. ^ Шёнинг, Уве (2008). Теоретическая информатика-kurz gefasst (5-е изд.). Лондон: Издательство Оксфордского университета. п. 93. ISBN  978-3-8274-1824-1. DNB 986529222.
  8. ^ Шёнинг, Уве (2001). Теоретическая информатика-kurz gefasst (4-е изд.). Лондон: Издательство Оксфордского университета. п. 122. ISBN  3-8274-1099-1.
  9. ^ Шёнинг, Уве (2008). Теоретическая информатика-kurz gefasst (5-е изд.). Лондон: Издательство Оксфордского университета. п. 112. ISBN  978-3-8274-1824-1. DNB 986529222.
  10. ^ Мейер и Ричи: Сложность циклических программ, ACM 1967

внешняя ссылка