Editing BlooP and FlooP

{{Short description|Simple programming languages}}
{{abbr|'''BlooP'''|Bounded loop}} and {{abbr|'''FlooP'''|Free loop}} ('''Bounded loop''' and '''Free loop''') are simple [[programming language]]s designed by [[Douglas Hofstadter]] to illustrate a point in his book ''[[Gödel, Escher, Bach]]''.<ref>[[Douglas Hofstadter]] (1979), ''[[Gödel, Escher, Bach]]'', Basic Books, Chapter XIII.</ref> BlooP is a [[Turing completeness|Turing-incomplete programming language]] whose main control flow structure is a bounded [[loop (computing)|loop]] (i.e. [[Recursion (computer science)|recursion]] is not permitted{{citation needed|date=October 2023}}). All programs in the language must terminate, and this language can only express [[primitive recursive function]]s.<ref>[http://plato.stanford.edu/entries/computability/ Stanford Encyclopedia of Philosophy:  Computability and Complexity]</ref>

FlooP is identical to BlooP except that it supports unbounded loops; it is a Turing-complete language and can express all [[computable function]]s. 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]],<ref name="Hofstadter424">Hofstadter (1979), p. 424.</ref><ref>Thomas Forster (2003), ''[https://books.google.com/books?id=mVeTuaRwWssC&pg=PA130 Logic, Induction and Sets]'', Cambridge University Press, p. 130.</ref> 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 [[model of computation|models of computation]], and have sometimes been used in teaching computability.<ref>David Mix Barrington (2004), CMPSCI 601: Theory of Computation, University of Massachusetts Amherst, [http://www.cs.umass.edu/~barring/cs601f04/lecture/27.pdf Lecture 27].</ref>

==BlooP examples==

The only [[variable (programming)|variable]]s are <code>OUTPUT</code> (the return value of the procedure) and <code>CELL(''i'')</code> (an unbounded sequence of natural-number variables, indexed by constants, as in the [[Counter machine models#1963: Shepherdson and Sturgis' model|Unlimited Register Machine]]<ref>Hofstadter refers to these cells as a set of "auxiliary variables."</ref>). The only [[operator (programming)|operator]]s are <code>⇐</code> ([[assignment (computer science)|assignment]]), <code>+</code> (addition), <code>×</code> (multiplication), <code>&lt;</code> (less-than), <code>&gt;</code> (greater-than) and <code>=</code> (equals).

Each program uses only a finite number of cells, but the numbers in the cells can be arbitrarily large. Data structures such as lists or stacks can be handled by interpreting the number in a cell in specific ways, that is, by [[Gödel numbering for sequences|Gödel numbering]] the possible structures.

Control flow constructs include bounded loops, [[Conditional (programming)|conditional statements]], <code>ABORT</code> jumps out of loops, and <code>QUIT</code> jumps out of blocks. BlooP does not permit recursion, unrestricted jumps, or anything else that would have the same effect as the unbounded loops of FlooP. Named procedures can be defined, but these can call only previously defined procedures.<ref>Hofstadter (1979), p. 413.</ref>

=== Factorial function ===
{{pre|
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.
}}

=== Subtraction function ===
This is not a built-in operation and (being defined on natural numbers) never gives a negative result (e.g. 2 &minus; 3 := 0). Note that <code>OUTPUT</code> starts at 0, like all the <code>CELL</code>s, and therefore requires no initialization.

{{pre|1=
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 example==

The example below, which implements the [[Ackermann function]], relies on simulating a stack using [[Gödel numbering for sequences|Gödel numbering]]: that is, on previously defined numerical functions <code>PUSH</code>, <code>POP</code>, and <code>TOP</code> satisfying <code>PUSH [N, S] > 0</code>, <code>TOP [PUSH [N, S]] = N</code>, and <code>POP [PUSH [N, S]] = S</code>. Since an unbounded <code>MU-LOOP</code> is used, this is not a legal BlooP program. The <code>QUIT BLOCK</code> instructions in this case jump to the end of the block and repeat the loop, unlike the <code>ABORT</code>, which exits the loop.<ref name="Hofstadter424"/>

{{pre|1=
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.
}}

==See also==
* [[Machine that always halts]]

==References==
{{reflist}}

==External links==
*[http://cgibin.erols.com/ziring/cgi-bin/cep/cep.pl?_key=BLooP Dictionary of Programming Languages - BLooP]
*[http://cgibin.erols.com/ziring/cgi-bin/cep/cep.pl?_key=FLooP Dictionary of Programming Languages - FLooP]
*[http://www.catb.org/retro/ The Retrocomputing Museum]
*[http://c2.com/cgi/wiki?BloopFloopAndGloop Portland Pattern Repository: Bloop Floop and Gloop]
*[https://code.google.com/p/bloop A compiler for BlooP and FlooP]
{{Douglas Hofstadter}}

[[Category:Esoteric programming languages]]
[[Category:Experimental programming languages]]