BlooP

BlooP (short for “Bounded loop”) is a small programming language that Douglas Hofstadter made up for Chapter XIII of his 1979 book Gödel, Escher, Bach: an Eternal Golden Braid. Its one defining rule is that every loop has to state an upper limit on its iterations before it starts. That rule means every BlooP program must halt, and it limits the language to exactly the primitive recursive functions. BlooP was never meant to be practical. Hofstadter wanted a language simple enough that readers with no mathematics background could see what “a predictably terminating computation” means, and then see why some computable functions fall outside it.

History & Origins

Gödel, Escher, Bach (usually shortened to GEB) was published by Basic Books in 1979. In 1980 it won the Pulitzer Prize for General Nonfiction and the National Book Award for Science (hardcover). The book leads up to Gödel’s incompleteness theorem, moving back and forth between dialogues and expository chapters. Chapter XIII, “BlooP and FlooP and GlooP”, introduces three languages at once. In Hofstadter’s words, quoted in John Cowan’s documentation of the language:

“BlooP, FlooP, and GlooP are not trolls, talking ducks, or the sounds made by a sinking ship — they are three computer languages, each one with its own special purpose. These languages were invented specially for this Chapter.”

The three languages are:

Hofstadter didn’t write a BlooP implementation. The language exists as a specification in prose, with worked examples printed in the book.

The idea of a loop-only language that captures the primitive recursive functions was already known in computability theory; Albert Meyer and Dennis Ritchie’s 1967 “LOOP” programs are the best-known earlier example. Hofstadter’s contribution was a readable, ALGOL-flavoured version for a general audience. He does not name BlooP’s influences, so none are listed here.

Design Philosophy

BlooP is designed so that you can always tell in advance that a program will finish. Everything else in the language supports that:

• Every loop has a fixed bound. The number of iterations is computed once, before the loop starts, and nothing inside the loop can change it.
• No recursion and no GOTO. A procedure can call only procedures that were defined before it, so it can’t call itself, even indirectly.
• Only natural numbers. There are no strings, arrays or records. Lists and stacks can be represented only by packing them into a single integer (Gödel numbering).
• Very few primitives. Addition, multiplication and comparisons are built in. Subtraction and division are not, so the reader writes them as MINUS and REMAINDER procedures.

Together these rules make BlooP easy to reason about. A reader can check by hand that every procedure terminates, which is the property the rest of the chapter depends on.

Key Features

Program structure

A BlooP program is a list of procedure definitions. Each procedure has numbered blocks, and each block begins with BLOCK n: BEGIN and ends with BLOCK n: END. The factorial procedure below is the standard example; its structure matches the book’s example:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

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.

Features to note:

• Procedure names go inside doubled apostrophes (''FACTORIAL'').
• Assignment uses the arrow ⇐, and multiplication uses ×.
• The only variables are the procedure’s parameters, a special OUTPUT variable (the return value), and an unlimited set of auxiliary cells CELL(0), CELL(1), and so on. They are all local and all start at zero.

Control flow

Tests: procedures that answer YES or NO

A procedure whose name ends in ? is a test. It sets OUTPUT to YES or NO. Tests let BlooP state number-theoretic questions directly. The book’s examples include primality, perfect numbers, Goldbach’s conjecture for a given number, and the “Tortoise property”. Here is a primality test in the book’s style (it relies on MINUS and REMAINDER procedures defined earlier):

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

DEFINE PROCEDURE ''PRIME?'' [N]:
BLOCK 0: BEGIN
        IF N = 0, THEN:
        QUIT BLOCK 0;
        CELL(0) ⇐ 2;
        LOOP AT MOST MINUS [N,2] TIMES:
        BLOCK 1: BEGIN
                IF REMAINDER [N,CELL(0)] = 0, THEN:
                QUIT BLOCK 0;
                CELL(0) ⇐ CELL(0) + 1;
        BLOCK 1: END;
        OUTPUT ⇐ YES;
BLOCK 0: END.

Because OUTPUT starts at zero (NO), any early QUIT BLOCK 0 answers NO.

FlooP’s single addition

FlooP is BlooP with one extra statement, MU-LOOP:. It repeats its block until an ABORT fires, with no bound given in advance. The name appears to echo the μ (minimization) operator of recursion theory. With it, FlooP can compute non-primitive-recursive functions such as the Ackermann function, and it can also express searches whose termination is an open question. One example is a WONDROUS? test, which asks whether the “3n+1” (Collatz) process reaches 1 for a given number. The book discusses these “wondrous” numbers, and Cowan’s and Fifield’s implementations both ship FlooP versions of the test. The cost is the halting problem: in general you cannot tell whether a FlooP program will ever stop.

The Argument BlooP Exists to Make

BlooP is there so that a limit can be proved about it. Hofstadter notes that BlooP programs can be listed in order, and he calls the programs that compute a one-argument function “Blue programs”. He then applies Cantor’s diagonal method to that list and defines a function (Bluediag) that differs from every Blue program at some input. Bluediag is clearly computable, since you can find the Nth BlooP program, run it on N, and add one. But no BlooP program can compute it. So bounded loops cannot express every computable function. That result prepares the ground for FlooP, for the halting problem, and later in the book for Gödel’s theorem.

Evolution and Implementations

BlooP has had no official versions. The text in GEB is the only specification, and the chapter has stayed in print, including in the 1999 twentieth-anniversary edition, whose main addition was a new preface. Programmers have written a few interpreters and compilers for it:

The sample files from these projects differ slightly in spelling and keyword details. That is expected, because each author worked from the prose description in the book, not from a formal grammar.

Esolang community variants also exist. For example, “Restricted BlooP/FlooP” removes addition, multiplication, comparison and conditionals, keeps only a successor operation, and rebuilds everything else from that.

Current Relevance

BlooP is a finished artifact: nobody is developing it, and there’s nothing new to develop. It still reaches new readers every year through GEB, and it remains one of the most accessible illustrations of three ideas:

• the difference between primitive recursive and general recursive functions;
• why some useful languages deliberately give up Turing completeness (total functional languages, proof assistants, and configuration and query languages all make the same trade-off to guarantee termination);
• how the diagonal argument turns “we can list all programs of this kind” into “some function lies outside this kind”.

No Docker image or official toolchain exists. To run BlooP today, you would build one of the hobbyist implementations above from source.

Why It Matters

Many esoteric languages are jokes about syntax. BlooP is a deliberate limitation used to teach. With one restriction, that every loop must declare its bound, Hofstadter gave general readers a real language they can trace by hand, then showed where its limits are. The pair BlooP/FlooP is a clear, memorable way to show the boundary between programs that must halt and programs that might not.