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

LOOP — это простой язык регистров, который точно фиксирует примитивные рекурсивные функции . ^[1] Язык является производным от противомашинной модели . Подобно машинам-счетчикам, язык LOOP содержит набор из одного или нескольких неограниченных регистров , каждый из которых может хранить одно неотрицательное целое число. С регистрами работают несколько арифметических инструкций (например, «CleaR», «INCrement», «DECrement», «CoPY» и т. д.). Единственная потока управления инструкция — это « LOOP x DO … END» . Он приводит к повторению инструкций в его области действия x раз. (Изменения содержимого регистра x во время выполнения цикла не влияют на количество проходов.)

История

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

Язык также был темой неопубликованной докторской диссертации Ричи. ^[3]^[4]

Его также представил Уве Шёнинг вместе с GOTO и WHILE . ^[5]

Философия дизайна и особенности

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

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

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

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

Синтаксис

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

{\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}}

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

Семантика

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

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

x_i := 0

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

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

x_i := x_i + 1

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

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

P₁; P₂

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

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

LOOP x DO P END

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

Создание «удобных инструкций»

Из базового синтаксиса создаются «удобные инструкции». Это не будут подпрограммы в обычном понимании, а скорее LOOP-программы, созданные на основе базового синтаксиса и имеющие мнемонику. Формально для использования этих программ необходимо либо (i) «расширить» их в код – они потребуют использования временных или «вспомогательных» переменных, поэтому это необходимо учитывать, либо (ii) спроектировать синтаксис со «встроенными» инструкциями.

Пример

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

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

Чтобы создать $\operatorname {assign}$ инструкции используйте блок кода ниже. $x_{j}:=\operatorname {assign} (x_{i})$ = _экв.

x_j := 0;
LOOP x_i DO
  x_j := x_j + 1
END

Опять же, все это только для удобства; ничто из этого не увеличивает внутреннюю мощность модели.

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

Добавление

Сложение определяется рекурсивно как:

{\begin{aligned}a+0&=a,&{\textrm {(1)}}\\a+S(b)&=S(a+b).&{\textrm {(2)}}\end{aligned}}

Здесь S следует читать как «преемник».

В последовательности гипероператоров это функция $\operatorname {H_{1}}$

$\operatorname {H_{1}} (x_{1},x_{2})$ может быть реализовано программой LOOP ADD( x ₁ , x ₂ )

LOOP x₁ DO
  x₀ := x₀ + 1
END;
LOOP x₂ DO
  x₀ := x₀ + 1
END

Умножение

Умножение - это функция гипероперации. $\operatorname {H_{2}}$

$\operatorname {H_{2}} (x_{1},x_{2})$ может быть реализован программой LOOP MULT( x ₁ , x ₂ )

x₀ := 0;
LOOP x₂ DO
  x₀ := ADD( x₁, x₀)
END

Программа использует программу ADD() в качестве «удобной инструкции». В расширенном виде программа MULT представляет собой программу LOOP с двумя вложенными инструкциями LOOP. ADD считается за единицу.

Больше гипероператоров

Дана программа LOOP для функции гипероперации. $\operatorname {H_{i}}$ , можно построить программу LOOP для следующего уровня

$\operatorname {H_{3}} (x_{1},x_{2})$ например (что означает возведение в степень ) может быть реализовано с помощью программы LOOP POWER( x ₁ , x ₂ )

x₀ := 1;
LOOP x₂ DO
  x₀ := MULT( x₁, x₀ )
END

Расширенная программа возведения в степень имеет три вложенные инструкции LOOP.

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

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

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

.

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

/* precondition: x2 = 0 */
LOOP x₁ DO
  x₀ := x₂;
  x₂ := x₂ + 1
END

В развернутом виде это программа

/* precondition: x₂ = 0 */
LOOP x₁ DO
  x₀ := 0;
  LOOP x₂ DO
    x₀ := x₀ + 1
  END;
  x₂ := x₂ + 1
END

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

x₀ := x₁ ∸ 1

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

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

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

x₀ := x₁
LOOP x₂ DO
  x₀ := x₀ ∸ 1
END

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

x₀ := x₁ ∸ x₂

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

Оператор if-then-else, где if x ₁ > x ₂ then P1 else P2:

x_n1 := x₁ ∸ x₂;
x_n2 := 0;
x_n3 := 1;
LOOP x_n1 DO
  x_n2 := 1;
  x_n3 := 0
END;
LOOP x_n2 DO
  P1
END;
LOOP x_n3 DO
  P2
END;

См. также

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

^ Эндертон 2012 .
↑ Перейти обратно: Перейти обратно: ^а ^б ^с Мейер и Ричи 1967 .
^ «Обнаружение потерянной диссертации Денниса Ритчи» . ЧМ . 19.06.2020 . Проверено 14 июля 2020 г.
^ Проект структуры программы и вычислительной сложности | 102790971 | Музей истории компьютеров . 1967 год . Проверено 14 июля 2020 г. {{cite book}}: |website= игнорируется ( помогите )
↑ Перейти обратно: Перейти обратно: ^а ^б Шенинг 2008 , с. 105.
^ Шёнинг 2008 , с. 93.
^ Шёнинг 2001 , с. 122.
^ Шёнинг 2008 , с. 112.

Библиография

Топор, Пол (1966). «Итерация относительной примитивной рекурсии». Математические летописи . 167 : 53–55. дои : 10.1007/BF01361215 . S2CID 119730846 .
Акст, Пол (1970). «Итерация примитивной рекурсии» . Журнал символической логики . 35 (3): 253–255. дои : 10.1002/malq.19650110310 .
Калуде, Кристиан (1988). Теории вычислительной сложности . Том. 35. Издательская компания Северной Голландии . ISBN 9780080867755 . {{cite book}}: |journal= игнорируется ( помогите )
Чернявский, Джон Чарльз (1976). «Простые программы реализуют именно формулы Пресбургера». SIAM Journal по вычислительной технике . 5 (4): 666–677. дои : 10.1137/0205045 .
Чернявский, Джон Чарльз; Камин, Сэмюэл Ной (1979). «Полная и непротиворечивая аксиоматика Хоара для простого языка программирования» . Ассоциация вычислительной техники . 26 (1): 119–128. дои : 10.1145/322108.322120 . S2CID 13062959 .
Констебль, Роберт Л.; Бородин, Аллан Б. (1972). «Субрекурсивные языки программирования, часть I: Эффективность и структура программы» . Журнал АКМ . 19 (3): 526–568. дои : 10.1145/321707.321721 . S2CID 42474303 .
Кролард, Тристан; Лакас, Сэмюэл; Валарше, Пьер (2006). «О выразительной силе петлевого языка» . Северный журнал вычислительной техники . 13 : 46–57.
Кролард, Тристан; Полоновский, Эммануэль; Валарше, Пьер (2009). «Расширение языка циклов процедурными переменными высшего порядка» (PDF) . Транзакции ACM в вычислительной логике . 10 (4): 1–37. дои : 10.1145/1555746.1555750 . S2CID 1367078 .
Эндертон, Герберт (2012). Теория вычислимости . Академическая пресса. дои : 10.1145/1555746.1555750 .
Фачини, Эмануэла; Маджоло-Скеттини, Андреа (1979). «Иерархия примитивно-рекурсивных функций последовательности» . РАЙРО - Informatique Théorique - Теоретическая информатика . 13 (1): 49–67. дои : 10.1051/ita/1979130100491 .
Фачини, Эмануэла; Маджиоло-Скеттини, Андреа (1982). «Сравнение иерархий примитивно-рекурсивных функций последовательностей». Журнал математической логики и оснований математики . 28 (27–32): 431–445. дои : 10.1002/malq.19820282705 .
Гетце, Бернхард; Эрлих, Вернер (1980). «Структура циклических программ и субрекурсивных иерархий» . Журнал математической логики и оснований математики . 26 (14–18): 255–278. дои : 10.1002/malq.19800261407 .
Ибарра, Оскар Х.; Лейнингер, Брайан С. (1981). «Характеризации функций Пресбургера». SIAM Journal по вычислительной технике . 10 (1): 22–39. дои : 10.1137/0210003 .
Ибарра, Оскар Х.; Розье, Луи Э. (1983). «Простые языки программирования и ограниченные классы машин Тьюринга» . Теоретическая информатика . 26 (1–2): 197–220. дои : 10.1016/0304-3975(83)90085-3 .
Кфури, Эй Джей; Молл, Роберт Н.; Арбиб, Майкл А. (1982). Программный подход к вычислимости . Спрингер, Нью-Йорк, штат Нью-Йорк. дои : 10.1007/978-1-4612-5749-3 . ISBN 978-1-4612-5751-6 .
Махти, Майкл (1972). «Языки расширенных циклов и классы вычислимых функций» . Журнал компьютерных и системных наук . 6 (6): 603–624. дои : 10.1016/S0022-0000(72)80032-1 .
ПланетаМатематика. «примитивная рекурсивная векторная функция» . Проверено 21 августа 2021 г.
Матос, Армандо Б. (3 ноября 2014 г.). «Закрытая форма примитивно-рекурсивных функций: от императивных программ к математическим выражениям и функциональным программам» (PDF) . Проверено 20 августа 2021 г.
Матос, Армандо Б. (2015). «Эффективность примитивно-рекурсивных функций: взгляд программиста» . Теоретическая информатика . 594 : 65–81. дои : 10.1016/j.tcs.2015.04.022 .
Мейер, Альберт Р .; Ричи, Деннис Макалистер (1967). Сложность циклических программ . ACM '67: Материалы 22-й национальной конференции 1967 года. дои : 10.1145/800196.806014 .
Мински, Марвин Ли (1967). Вычисления: конечные и бесконечные машины . Прентис Холл. дои : 10.1017/S0008439500029350 . S2CID 227917578 .
Ричи, Деннис Макалистер (1967). Структура программы и вычислительная сложность (черновик) (PDF) .
Ричи, Роберт Уэллс (ноябрь 1965 г.). «Классы рекурсивных функций, основанные на функции Аккермана» . Тихоокеанский математический журнал . 15 (3): 1027–1044. дои : 10.2140/pjm.1965.15.1027 .
Шенинг, Уве (2001). Теоретическая информатика-кратко (4-е изд.). Лондон: Издательство Оксфордского университета. ISBN 3-8274-1099-1 .
Шенинг, Уве (2008). Теоретическая информатика-вкратце (5-е изд.). Лондон: Издательство Оксфордского университета. ISBN 978-3-8274-1824-1 . ДНБ 986529222 .
Цихрицис, Деннис С. (1970). «Проблема эквивалентности простых программ». Журнал АКМ . 17 (4): 729–738. дои : 10.1145/321607.321621 . S2CID 16066171 .
Цихрицис, Деннис С. (1971). «Заметка о сравнении субрекурсивных иерархий». Письма об обработке информации . 1 (2): 42–44. дои : 10.1016/0020-0190(71)90002-0 .

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

Освоение искусства циклов в программировании: пошаговое руководство

[FOOTNOTEEnderton2012-1] Эндертон 2012 .

[FOOTNOTEMeyerRitchie1967-2] Перейти обратно: Перейти обратно: ^а ^б ^с Мейер и Ричи 1967 .

[3] «Обнаружение потерянной диссертации Денниса Ритчи» . ЧМ . 19.06.2020 . Проверено 14 июля 2020 г.

[4] Проект структуры программы и вычислительной сложности | 102790971 | Музей истории компьютеров . 1967 год . Проверено 14 июля 2020 г. {{cite book}}: |website= игнорируется ( помогите )

[FOOTNOTESchöning2008105-5] Перейти обратно: Перейти обратно: ^а ^б Шенинг 2008 , с. 105.

[FOOTNOTESchöning200893-6] Шёнинг 2008 , с. 93.

[FOOTNOTESchöning2001122-7] Шёнинг 2001 , с. 122.

[FOOTNOTESchöning2008112-8] Шёнинг 2008 , с. 112.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]