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

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

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

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

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

Функции

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

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

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

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

Синтаксис

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

{ 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 {массив}}}

Здесь, ${ displaystyle Var: = {x_ {0}, x_ {1}, ... }}$ имена переменных и ${ displaystyle c in mathbb {N}}$ являются константами.

Семантика

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

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

Икс_я := 0

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

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

Икс_я : = х_я + 1

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

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

п₁; п₂

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

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

LOOP x DO п КОНЕЦ

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

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

Назначение

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

Икс_j : = 0; ПЕТЛЯ x_я DO x_j : = х_j +1END

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

Икс_j : = х_я

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

Проекция

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

Икс₀ : = х_я

Эта программа вычисляет k-арную функцию проекции ${ displaystyle U_ {i} ^ {k} (x_ {1}, ..., x_ {i}, ..., x_ {k}) = x_ {i}}$ , который извлекает i-ю координату из упорядоченного набора k.

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

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

{ displaystyle operatorname {pred} (n) = { begin {cases} 0 & { mbox {if}} n = 0, n-1 & { mbox {else}} end {cases}}}

.

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

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

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

Икс₀ : = х₁ ∸ 1

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

Добавление

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

ПЕТЛЯ x₁ DO x₀ : = х₀ + 1END; LOOP x₂ DO x₀ : = х₀ +1END

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

Икс₀ : = х₁ + х₂

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

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

Икс₀ : = х₁ПЕТЛЯ x₂ DO x₀ : = х₀ ∸ 1END

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

Икс₀ : = х₁ ∸ х₂

Умножение

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

ПЕТЛЯ x₁ DO x₀ : = х₀ + х₂КОНЕЦ

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

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

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

Икс_n1 : = х₁ ∸ х₂;Икс_n2 : = 0; х_n3 : = 1; ПЕТЛЯ x_n1 DO x_n2 : = 1; Икс_n3 : = 0END; ЦИКЛ x_n2 DO P1END; LOOP x_n3 СДЕЛАЙТЕ P2END;

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

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

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

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

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

[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

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]