ブループとフロープ

BlooPとFlooP (境界ループと自由ループ) は、ダグラス・ホフスタッターが著書『ゲーデル、エッシャー、バッハ』の論点を説明するために設計したシンプルなプログラミング言語です。 ^[1] BlooP はチューリング不完全なプログラミング言語で、主な制御フロー構造は境界ループです(つまり、再帰は許可されていません^{[要出典] )。この言語のすべてのプログラムは終了する必要があり、この言語は}基本的な再帰関数しか表現できません。 ^[2]

FlooP は、無制限ループをサポートしていることを除いて BlooP と同一です。チューリング完全な言語であり、すべての計算可能な関数を表現できます。たとえば、アッカーマン関数を表現できますが、これは (原始再帰ではないため) BlooP では記述できません。数理論理学の標準用語を借りて、^{[3] [4]} Hofstadter は FlooP の無制限ループを MU ループと呼んでいます。すべてのチューリング完全なプログラミング言語と同様に、FlooP は停止問題を抱えています。つまり、プログラムが終了しない可能性があり、一般にどのプログラムが終了しているかを判断することはできません。

BlooPとFlooPは計算モデルとみなすことができ、計算可能性の教育に使用されることもあります。^[5]

唯一の変数はOUTPUT(手続きの戻り値) と(無制限レジスタマシン^[6]のように定数でインデックス付けされた自然数変数の無制限のシーケンス) です。唯一の演算子は(代入)、(加算)、(乗算)、(より小さい)、(より大きい)、(等しい) です。CELL(i)⇐+×<>=

各プログラムでは有限の数のセルのみを使用しますが、セル内の数値は任意の大きさにすることができます。リストやスタックなどのデータ構造は、セル内の数値を特定の方法で解釈することによって、つまり、可能な構造をゲーデル数付けすることによって処理できます。

制御フロー構造には、境界ループ、条件文、ABORTループからのジャンプ、QUITブロックからのジャンプが含まれます。BlooPでは、再帰、無制限のジャンプ、またはFlooPの無制限ループと同じ効果を持つその他のものは許可されません。名前付きプロシージャを定義することはできますが、これらは以前に定義されたプロシージャのみを呼び出すことができます。^[7]

手順階乗を定義する[N]:
ブロック0: 開始
        出力⇐ 1;
        セル(0) ⇐ 1;
        最大 N 回ループ:
        ブロック 1: 開始
                出力⇐出力×セル(0);
                セル(0) ⇐ セル(0) + 1;
        ブロック 1: 終了;
ブロック0: 終了。

これは組み込み演算ではなく、（自然数で定義されているため）負の結果を返すことはありません（例：2 − 3 := 0）。 はOUTPUTすべての と同様に 0 から始まるためCELL、初期化は不要であることに注意してください。

プロシージャMINUS [M,N]を定義する:
ブロック0: 開始
        M < Nの場合:
        ブロック0を終了します。
        最大M + 1回ループします:
        ブロック 1: 開始
                出力 + N = M の場合:
                ループ1を中止します。
                出力⇐ 出力 + 1;
        ブロック 1: 終了;
ブロック0: 終了。

以下の例は、アッカーマン関数を実装していますが、ゲーデル番号付けを使用したスタックのシミュレーションに依存しています。つまり、 、、 、を満たす、以前に定義された数値関数PUSH、、 です。無制限の が使用されているため、これは正当な BlooP プログラムではありません。この場合の命令は、ループを終了する とは異なり、ブロックの最後にジャンプしてループを繰り返します。 ^[3]POPTOPPUSH [N, S] > 0TOP [PUSH [N, S]] = NPOP [PUSH [N, S]] = SMU-LOOPQUIT BLOCKABORT

手順ACKERMANN [M, N]を定義する:
ブロック0: 開始
	セル(0) ⇐ M;
	出力⇐N;
	セル(1) ⇐ 0;
	MUループ:
	ブロック 1: 開始
		CELL(0) = 0の場合:
		ブロック2: 開始
			出力⇐ 出力 + 1;
			CELL(1) = 0の場合: ループ1を中止します。
			セル(0) ⇐ 上 [セル(1)];
			セル(1) ⇐ POP [セル(1)];
			ブロック 1 を終了します。
		ブロック2: 終了
		出力 = 0 の場合:
		ブロック3: 開始
			出力⇐ 1;
			セル(0) ⇐ マイナス[セル(0), 1];
			ブロック 1 を終了します。
		ブロック3: 終了
		出力⇐ マイナス [出力、1];
		セル(1) ⇐ PUSH [MINUS [セル(0), 1], セル(1)];
	ブロック 1: 終了;
ブロック0: 終了。

• いつも止まる機械

• プログラミング言語辞書 - BLooP
• プログラミング言語辞書 - FLooP
• レトロコンピューティング博物館
• ポートランドパターンリポジトリ: Bloop Floop と Gloop
• BlooP および FlooP 用のコンパイラ