BlooP and FlooP

BLooP and FLooP 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 only control flow structure is a bounded loop (i.e. recursion is not permitted). This language can only express primitive recursive functions, and all programs in the language must terminate.

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.

BLooP and FLooP can be regarded as models of computation.

BLooP examples

The only variables are output (the return value of the procedure) and cell(i) (an unbounded sequence of natural numbers, indexed by constants, as in the Unlimited Register Machine). The only operators 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 can be handled by interpreting the number in a cell in specific ways, that is, by Gödel numbering the possible structures.

Factorial function:

DEFINE PROCEDURE ''FACTORIAL'' [N]:
BLOCK 0: BEGIN
        OUTPUT ⇐ 1;
        CELL(0) ⇐ 1;
        LOOP 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):

DEFINE PROCEDURE ''MINUS'' [M,N]:
BLOCK 0: BEGIN
        IF M < N, THEN:
        QUIT BLOCK 0;
        OUTPUT ⇐ 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.

External links

• Dictionary of Programming Languages - BLooP
• Dictionary of Programming Languages - FLooP
• The Retrocomputing Museum
• Portland Pattern Repository: Bloop Floop and Gloop
• A compiler for BlooP and FlooP