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 {\ displaystyle {\ begin {array} {lrl} P :: = x_ {i}: = 0 \\ | x_ {i}: = x_ {i} +1 \\ | P; P \ \ | {\ mathtt {LOOP}} \, x_ {i} \, {\ mathtt {DO}} \, P \, {\ mathtt {END}} \ end {array}}}{\ displaystyle {\ begin {array} {lrl} P :: = x_ {i}: = 0 \\ | x_ {i}: = x_ {i} +1 \ \ | P; P \\ | {\ mathtt {LOOP}} \, x_ {i} \, {\ mathtt {DO}} \, P \, {\ mathtt {END}} \ end {массив} }}

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

Семантика

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

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

xi: = 0

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

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

xi: = x i + 1

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

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

P1; P 2

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

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

LOOP x DO P END

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

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

Присвоение

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

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

В своей основополагающей статье Мейер и Ричи сделали назначение xj: = xi {\ displaystyle x_ {j}: = x_ {i}}{\ 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 {\ displaystyle U_ {i} ^ {k} (x_ {1},..., x_ {i},..., x_ {k}) = x_ {i}}{\ displaystyle U_ {i} ^ {k} (x_ {1},..., x_ {i},..., x_ {k}) = x_ {i}} , который извлекает i-ю координату из упорядоченного кортежа k.

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

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

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

Эта функция может быть вычислена с помощью следующей программы LOOP, которая устанавливает для переменной x 0 {\ displaystyle x_ {0}}x_ {0} значение pred (x 1) {\ displaystyle pred (x_ {1})}{\ 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 {\ displaystyle x_ {0}}x_ {0} устанавливается равной сумме переменных x 1 { \ displaystyle x_ {1}}x_ {1} и x 2 {\ displaystyle x_ {2}}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 {\ displaystyle x_ {1}}x_ {1} и x 2 {\ displaystyle x_ {2}}x_ {2} .

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

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

x0: = x 1 ∸ x 2

Умножение

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

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

Эта программа умножения использует синтаксис, введенный подпрограммой сложения из предыдущего примера. Здесь умножение выполняется путем добавления значения x 2 {\ displaystyle x_ {2}}x_ {2} в сумме x 1 {\ displaystyle x_ {1}}x_ {1} раз, сохранение результатов в x 0 {\ displaystyle x_ {0}}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;

См. Также

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

  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

Внешние ссылки

Последняя правка сделана 2021-05-26 08:55:13
Содержание доступно по лицензии CC BY-SA 3.0 (если не указано иное).
Обратная связь: support@alphapedia.ru
Соглашение
О проекте