Введение
Простые языки программирования BlooP (Bounded loop) и FlooP (Free loop) (Ограниченный цикл и Свободный цикл) — это простые языки программирования, разработанные Дугласом Хофштадтером для иллюстрации идеи, представленной в его книге «Гёдель, Эшер, Бах». BlooP — это неполный по Тьюрингу язык программирования, основной структурой управления которого является ограниченный цикл (то есть рекурсия не допускается). Все программы на этом языке должны завершаться, и он может выражать только примитивно рекурсивные функции. FlooP идентичен BlooP, за исключением поддержки неограниченных циклов; это полный по Тьюрингу язык, способный выражать все вычислимые функции. Например, он может выражать функцию Аккермана, которая (не являясь примитивно рекурсивной) не может быть записана на BlooP. Заимствуя стандартную терминологию из математической логики, Хофштадтер называет неограниченные циклы FlooP MU-циклами. Как и все полные по Тьюрингу языки программирования, FlooP подвержен проблеме останова: программы могут не завершаться, и в общем случае невозможно определить, какие программы завершатся. BlooP и FlooP можно рассматривать как модели вычислений, и их иногда используют при обучении теории вычислимости.
BlooP (Bounded loop) and FlooP (Free loop) (Bounded loop and Free loop) are simple programming languages designed by Douglas Hofstadter to illustrate a point in his book Gödel, Escher, Bach. BlooP is a non Turing complete programming language whose main control flow structure is a bounded loop (i. e. recursion is not permitted). All programs in the language must terminate, and this language can only express primitive recursive functions. FlooP is identical to BlooP except that it supports unbounded loops; it is a Turing complete language and can express all computable functions. For example, it can express the Ackermann function, which (not being primitive recursive) cannot be written in BlooP. Borrowing from standard terminology in mathematical logic, Hofstadter calls FlooP's unbounded loops MU loops. Like all Turing complete programming languages, FlooP suffers from the halting problem: programs might not terminate, and it is not possible, in general, to decide which programs do. BlooP and FlooP can be regarded as models of computation, and have sometimes been used in teaching computability.
Примеры BlooP
Единственными переменными являются OUTPUT (возвращаемое значение процедуры) и CELL(i) (неограниченная последовательность переменных натуральных чисел, индексированных константами, как в машине с неограниченным регистром). Единственными операторами являются ⇐ (присваивание), + (сложение), × (умножение), < (меньше), > (больше) и = (равно). Каждая программа использует только конечное число ячеек, но числа в ячейках могут быть произвольно большими. Структуры данных, такие как списки или стеки, могут быть реализованы путем интерпретации числа в ячейке определенным образом, то есть с помощью нумерации Гёделя возможных структур. Конструкции управления потоком включают в себя ограниченные циклы, условные операторы, переход ABORT из цикла и переход QUIT из блока. BlooP не допускает рекурсию, безусловные переходы или что-либо, что имело бы тот же эффект, что и бесконечные циклы FlooP. Можно определять именованные процедуры, но они могут вызывать только ранее определенные процедуры.
Функция вычитания
Это не встроенная операция и, будучи определенной для натуральных чисел, никогда не возвращает отрицательный результат (например, 2 − 3 := 0). Обратите внимание, что OUTPUT начинается с 0, как и все ЯЧЕЙКИ, и поэтому не требует инициализации.
Пример FlooP
Приведенный ниже пример, реализующий функцию Аккермана, опирается на моделирование стека с использованием чисел Гёделя: а именно, на ранее определенных числовых функции PUSH, POP и TOP, удовлетворяющих условиям PUSH [N, S] > 0, TOP [PUSH [N, S]] = N и POP [PUSH [N, S]] = S. Поскольку используется неограниченный цикл MU, это не является допустимой программой BlooP. Инструкции QUIT BLOCK в данном случае переходят к концу блока и повторяют цикл, в отличие от ABORT, который завершает цикл.