BlooP andFlooP (Bounded loop andFree loop) are simpleprogramming languages designed byDouglas Hofstadter to illustrate a point in his bookGödel, Escher, Bach.[1] BlooP is aTuring-incomplete programming language whose main control flow structure is a boundedloop (i.e.recursion is not permitted[citation needed]). All programs in the language must terminate, and this language can only expressprimitive recursive functions.[2]
FlooP is identical to BlooP except that it supports unbounded loops; it is a Turing-complete language and can express allcomputable functions. For example, it can express theAckermann function, which (not being primitive recursive) cannot be written in BlooP. Borrowing from standard terminology inmathematical logic,[3][4] Hofstadter calls FlooP's unbounded loops MU-loops. Like all Turing-complete programming languages, FlooP suffers from thehalting problem: programs might not terminate, and it is not possible, in general, to decide which programs do.
BlooP and FlooP can be regarded asmodels of computation, and have sometimes been used in teaching computability.[5]
The onlyvariables areOUTPUT (the return value of the procedure) andCELL(i) (an unbounded sequence of natural-number variables, indexed by constants, as in theUnlimited Register Machine[6]). The onlyoperators are⇐ (assignment),+ (addition),× (multiplication),< (less-than),> (greater-than) and= (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, byGödel numbering the possible structures.
Control flow constructs include bounded loops,conditional statements,ABORT jumps out of loops, andQUIT 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.[7]
DEFINE PROCEDUREFACTORIAL [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.
This is not a built-in operation and (being defined on natural numbers) never gives a negative result (e.g. 2 − 3 := 0). Note thatOUTPUT starts at 0, like all theCELLs, and therefore requires no initialization.
DEFINE PROCEDUREMINUS [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.
The example below, which implements theAckermann function, relies on simulating a stack usingGödel numbering: that is, on previously defined numerical functionsPUSH,POP, andTOP satisfyingPUSH [N, S] > 0,TOP [PUSH [N, S]] = N, andPOP [PUSH [N, S]] = S. Since an unboundedMU-LOOP is used, this is not a legal BlooP program. TheQUIT BLOCK instructions in this case jump to the end of the block and repeat the loop, unlike theABORT, which exits the loop.[3]
DEFINE PROCEDUREACKERMANN [M, N]:BLOCK 0: BEGINCELL(0) ⇐ M;OUTPUT ⇐ N;CELL(1) ⇐ 0;MU-LOOP:BLOCK 1: BEGINIF CELL(0) = 0, THEN:BLOCK 2: BEGINOUTPUT ⇐ 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: ENDIF OUTPUT = 0, THEN:BLOCK 3: BEGINOUTPUT ⇐ 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.
| Books |
|  |
|---|---|---|
Concepts and projects | ||
| Related | ||
| ||