БлуП и ФлуП

BlooP и FlooP ( Ограниченный цикл и Свободный цикл ) — простые языки программирования, разработанные Дугласом Хофштадтером для иллюстрации мысли из его книги «Гедель, Эшер, Бах» . BlooP — это неполный по Тьюрингу язык программирования , основная структура потока управления которого представляет собой ограниченный цикл (т. е. рекурсия не разрешена). ). Все программы на языке должны завершаться, а этот язык может выражать только примитивно-рекурсивные функции .

FlooP идентичен BlooP, за исключением того, что он поддерживает неограниченные циклы; это тьюринг-полный язык, который может выражать все вычислимые функции . Например, он может выражать функцию Аккермана , которую (не будучи примитивно-рекурсивной) нельзя написать в BlooP. Заимствуя стандартную терминологию математической логики , Хофштадтер называет неограниченные циклы FlooP MU-петлями. Как и все тьюринг-полные языки программирования, FlooP страдает от проблемы остановки : программы могут не завершаться, и в целом невозможно решить, какие программы завершают работу.

BlooP и FlooP можно рассматривать как модели вычислений , и иногда их используют при обучении вычислимости.

Примеры BlooP

Единственными переменными являются OUTPUT (возвращаемое значение процедуры) и CELL(i) (неограниченная последовательность переменных натуральных чисел, индексированных константами, как в неограниченной регистровой машине ). Единственные операторы ​ ⇐ ( назначение ), + (добавление), × (умножение), < (меньше, чем), > (больше чем) и = (равен).

Каждая программа использует только конечное число ячеек, но числа в ячейках могут быть сколь угодно большими. Структуры данных, такие как списки или стеки, можно обрабатывать, интерпретируя число в ячейке определенным образом, то есть путем нумерации возможных структур по Гёделю.

Конструкции потока управления включают ограниченные циклы, условные операторы , ABORT выпрыгивает из петель и QUIT выпрыгивает из блоков. BlooP не допускает рекурсию, неограниченные переходы или что-либо еще, что имело бы тот же эффект, что и неограниченные циклы FlooP. Можно определить именованные процедуры, но они могут вызывать только ранее определенные процедуры.

Факториал

DEFINE PROCEDURE FACTORIAL [N]:
BLOCK 0: BEGIN
        OUTPUT ⇐ 1;
        CELL(0) ⇐ 1;
        LOOP AT MOST N TIMES:
        BLOCK 1: BEGIN
                OUTPUT ⇐ OUTPUT × CELL(0);
                CELL(0) ⇐ CELL(0) + 1;
        BLOCK 1: END;
BLOCK 0: END.

Функция вычитания

Это не встроенная операция и (определяемая для натуральных чисел) никогда не дает отрицательного результата (например, 2 − 3 := 0). Обратите внимание, что OUTPUT начинается с 0, как и все CELLs и поэтому не требует инициализации.

DEFINE PROCEDURE MINUS [M,N]:
BLOCK 0: BEGIN
        IF M < N, THEN:
        QUIT BLOCK 0;
        LOOP AT MOST M + 1 TIMES:
        BLOCK 1: BEGIN
                IF OUTPUT + N = M, THEN:
                ABORT LOOP 1;
                OUTPUT ⇐ OUTPUT + 1;
        BLOCK 1: END;
BLOCK 0: END.

Пример FlooP

Приведенный ниже пример, реализующий функцию Аккермана , основан на моделировании стека с использованием нумерации Гёделя : то есть на ранее определенных числовых функциях. PUSH, POP, и TOP удовлетворяющий PUSH [N, S] > 0, TOP [PUSH [N, S]] = N, и POP [PUSH [N, S]] = S. Поскольку неограниченное MU-LOOP используется, это не легальная программа BlooP. QUIT BLOCK инструкции в этом случае переходят в конец блока и повторяют цикл, в отличие от ABORT, который выходит из цикла.

DEFINE PROCEDURE ACKERMANN [M, N]:
BLOCK 0: BEGIN
	CELL(0) ⇐ M;
	OUTPUT ⇐ N;
	CELL(1) ⇐ 0;
	MU-LOOP:
	BLOCK 1: BEGIN
		IF CELL(0) = 0, THEN:
		BLOCK 2: BEGIN
			OUTPUT ⇐ OUTPUT + 1;
			IF CELL(1) = 0, THEN: ABORT LOOP 1;
			CELL(0) ⇐ TOP [CELL(1)];
			CELL(1) ⇐ POP [CELL(1)];
			QUIT BLOCK 1;
		BLOCK 2: END
		IF OUTPUT = 0, THEN:
		BLOCK 3: BEGIN
			OUTPUT ⇐ 1;
			CELL(0) ⇐ MINUS [CELL(0), 1];
			QUIT BLOCK 1;
		BLOCK 3: END 
		OUTPUT ⇐ MINUS [OUTPUT, 1];
		CELL(1) ⇐ PUSH [MINUS [CELL(0), 1], CELL(1)];
	BLOCK 1: END;
BLOCK 0: END.

См. также

• Машина, которая всегда останавливается

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

• Словарь языков программирования — BLooP
• Словарь языков программирования — FLooP
• Музей ретрокомпьютеров
• Репозиторий шаблонов Портленда: Bloop Floop и Gloop
• Компилятор для BlooP и FlooP.