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

LOOP - это язык, который точно передает примитивно-рекурсивные функции. Единственные операции, поддерживаемые в языке, - это присваивание, сложение и повторение цикла, которое фиксируется до начала выполнения цикла.

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

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

Он также был представлен Уве Шёнинг вместе с и WHILE.

• 1 Особенности
• 2 Формальное определение
  • 2.1 Синтаксис
  • 2.2 Семантика
• 3 Примеры программ
  • 3.1 Назначение
  • 3.2 Проекция
  • 3.3 Предшественник
  • 3.4 Сложение
  • 3.5 Вычитание отсечки
  • 3.6 Умножение
  • 3.7 Если тогда еще
• 4 См. Также
• 5 Примечания и ссылки
• 6 Внешние ссылки

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

В отличие от программ и программ, программы LOOP всегда завершаются. Следовательно, набор функций, вычисляемых программами LOOP, является надлежащим подмножеством вычислимых функций (и, следовательно, подмножеством вычисляемых программными функциями WHILE и GOTO).

Пример Общая вычислимая функция, которая не является вычислимой LOOP, - это функция Аккермана.

Синтаксис

LOOP-программы состоят из символов LOOP, DO, END, :=, +, -и ;, а также любое количество переменных и констант. LOOP-программы имеют следующий синтаксис в модифицированной форме Бэкуса – Наура :

$P\; ::\; =\; x\; i:\; =\; 0\; |\; x\; i:\; =\; x\; i\; +\; 1\; |\; П\; ;\; P\; |\; LOOP\; xi\; DOPEND\; \{\backslash \; displaystyle\; \{\backslash \; begin\; \{array\}\; \{lrl\}\; P\; ::\; =\; x\_\; \{i\}:\; =\; 0\; \backslash \backslash \; |\; x\_\; \{i\}:\; =\; x\_\; \{i\}\; +1\; \backslash \backslash \; |\; P;\; P\; \backslash \; \backslash \; |\; \{\backslash \; mathtt\; \{LOOP\}\}\; \backslash ,\; x\_\; \{i\}\; \backslash ,\; \{\backslash \; mathtt\; \{DO\}\}\; \backslash ,\; P\; \backslash ,\; \{\backslash \; mathtt\; \{END\}\}\; \backslash \; end\; \{array\}\}\}$

Здесь, $V\; ar:\; =\; \{x\; 0,\; x\; 1,...\; \}\; \{\backslash \; displaystyle\; Var:\; =\; \backslash \; \{x\_\; \{0\},\; x\_\; \{1\},...\; \backslash \}\}$- имена переменных и $c\; \in \; N\; \{\backslash \; displaystyle\; c\; \backslash \; in\; \backslash \; mathbb\; \{\; N\}\}$- константы.

Семантика

Если P - программа LOOP, P эквивалентна функции $f:\; N\; k\; \to \; N\; \{\backslash \; displaystyle\; е:\; \backslash \; mathbb\; \{N\}\; ^\; \{k\}\; \backslash \; rightarrow\; \backslash \; mathbb\; \{N\}\}$. Переменные с $x\; 1\; \{\backslash \; displaystyle\; x\_\; \{1\}\}$по $xk\; \{\backslash \; displaystyle\; x\_\; \{k\}\}$в программе LOOP соответствуют аргументам function $f\; \{\backslash \; displaystyle\; f\}$, и инициализируются перед выполнением программы соответствующими значениями. Все остальные переменные получают нулевое начальное значение. Переменная $x\; 0\; \{\backslash \; displaystyle\; x\_\; \{0\}\}$соответствует значению, которое принимает $f\; \{\backslash \; displaystyle\; f\}$при заданных значениях аргументов из $x\; 1\; \{\backslash \; displaystyle\; x\_\; \{1\}\}$через $xk\; \{\backslash \; displaystyle\; x\_\; \{k\}\}$.

оператор формы

xi: = 0

означает, что значение переменной $xi\; \{\backslash \; displaystyle\; x\_\; \{i\}\}$установлено на 0.

. Оператор формы

xi: = x i + 1

означает, что значение переменной $xi\; \{\backslash \; displaystyle\; x\_\; \{i\}\}$увеличивается на 1.

. Оператор формы

P1; P 2

представляет собой последовательное выполнение подпрограмм $P\; 1\; \{\backslash \; displaystyle\; P\_\; \{1\}\}$и $P\; 2\; \{\backslash \; displaystyle\; P\_\; \{2\}\}$, именно в таком порядке.

. Оператор вида

LOOP x DO P END

означает повторное выполнение частичной программы $P\; \{\backslash \; displaystyle\; P\}$всего $x\; \{\backslash \; displaystyle\; x\}$раз, где используется значение, которое $x\; \{\backslash \; displaystyle\; x\}$имеет в начале выполнения оператора. Даже если $P\; \{\backslash \; displaystyle\; P\}$изменит значение $x\; \{\backslash \; displaystyle\; x\}$, это не повлияет на то, сколько раз $P\; \{\; \backslash \; displaystyle\; P\}$выполняется в цикле. Если $x\; \{\backslash \; displaystyle\; x\}$имеет нулевое значение, то $P\; \{\backslash \; displaystyle\; P\}$не выполняется внутри оператора LOOP. Это позволяет использовать ветки в программах LOOP, где условное выполнение частичной программы зависит от того, имеет ли переменная значение ноль или единицу.

Присвоение

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

xj: = 0; LOOP x i DO x j : = x j + 1 END

В своей основополагающей статье Мейер и Ричи сделали назначение $xj:\; =\; xi\; \{\backslash \; displaystyle\; x\_\; \{j\}:\; =\; x\_\; \{i\}\}$базовый оператор. Как показывает приведенная выше программа, присвоение является избыточным и может быть удалено из списка основных операторов. Его можно использовать как подпрограмму в других программах LOOP. Синтаксис LOOP может быть расширен с помощью следующего оператора, эквивалентного вызову вышеупомянутой подпрограммы:

xj: = x i

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

Проекция

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

x0: = x i

Эта программа вычисляет k-арную функцию проекции $U\; ik\; (x\; 1,...,\; xi,....,\; xk)\; =\; xi\; \{\backslash \; displaystyle\; U\_\; \{i\}\; ^\; \{k\}\; (x\_\; \{1\},...,\; x\_\; \{i\},...,\; x\_\; \{k\})\; =\; x\_\; \{i\}\}$, который извлекает i-ю координату из упорядоченного кортежа k.

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

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

$pred\; \; (n)\; =\; \{0,\; если\; n\; =\; 0,\; n\; -\; 1\; в\; противном\; случае\; \{\backslash \; displaystyle\; \backslash \; operatorname\; \{pred\}\; (n)\; =\; \{\backslash \; begin\; \{case\}\; 0\; \{\backslash \; t\_dv\; \{if\}\}\; n\; =\; 0,\; \backslash \backslash \; n-1\; \{\backslash \; t\_dv\; \{else\}\}\; \backslash \; end\; \{cases\}\}\}$.

Эта функция может быть вычислена с помощью следующей программы LOOP, которая устанавливает для переменной $x\; 0\; \{\backslash \; displaystyle\; x\_\; \{0\}\}$значение $pred\; (x\; 1)\; \{\backslash \; displaystyle\; pred\; (x\_\; \{1\})\}$.

/ * предварительное условие: x 2 = 0 * / LOOP x 1 DO x 0 : = 0; LOOP x 2 DO x 0 : = x 0 + 1 END; x 2 : = x 2 + 1 END

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

x0: = x 1 ∸ 1

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

Сложение

В следующей программе переменная $x\; 0\; \{\backslash \; displaystyle\; x\_\; \{0\}\}$устанавливается равной сумме переменных $x\; 1\; \{\; \backslash \; displaystyle\; x\_\; \{1\}\}$и $x\; 2\; \{\backslash \; displaystyle\; x\_\; \{2\}\}$.

LOOP x 1 DO x 0 : = x 0 + 1 КОНЕЦ; LOOP x 2 DO x 0 : = x 0 + 1 END

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

x0: = x 1 + x 2

Вычитание отсечки

Если в программа 'сложения' над вторым циклом уменьшает x 0 вместо увеличения, программа вычисляет разность (отсекается на 0) переменных $x\; 1\; \{\backslash \; displaystyle\; x\_\; \{1\}\}$и $x\; 2\; \{\backslash \; displaystyle\; x\_\; \{2\}\}$.

x0: = x 1 LOOP x 2 DO x 0 : = x 0 ∸ 1 END

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

x0: = x 1 ∸ x 2

Умножение

Следующая программа LOOP устанавливает значение переменной $x\; 0\; \{\backslash \; displaystyle\; x\_\; \{0\}\}$равным произведению переменных $x\; 1\; \{\backslash \; displaystyle\; x\_\; \{1\}\}$и $x\; 2\; \{\backslash \; displaystyle\; x\_\; \{2\}\}$.

LOOP x 1 DO x 0 : = x 0 + x 2 END

Эта программа умножения использует синтаксис, введенный подпрограммой сложения из предыдущего примера. Здесь умножение выполняется путем добавления значения $x\; 2\; \{\backslash \; displaystyle\; x\_\; \{2\}\}$в сумме $x\; 1\; \{\backslash \; displaystyle\; x\_\; \{1\}\}$раз, сохранение результатов в $x\; 0\; \{\backslash \; displaystyle\; x\_\; \{0\}\}$.

If then else

Оператор if-then-else с if x 1>x2then P1 else P2:

xn1: = x 1 ∸ x 2 ; х n2 : = 0; х n3 : = 1; LOOP x n1 DO x n2 : = 1; x n3 : = 0 КОНЕЦ; LOOP x n2 DO P1 END; LOOP x n3 DO P2 END;

• μ-рекурсивная функция
• примитивно-рекурсивная функция
• BlooP и FlooP

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

• Цикл, переход и пока