bfloop

A Blooper from Super Mario Bros., in a photograph taken very close to a TV screen so that individual phosphor triads are visible.

bfloop is an interpreter for the BLooP and FLooP programming languages described in the book Gödel, Escher, Bach by Douglas Hofstadter. It is free software (MIT license).

BLooP is a language that has only bounded loops, in other words before you enter a loop you have to give a fixed upper limit on the number of times to run the body, and you can’t change the limit while in the loop. It is impossible for a BLooP program to run forever; it always quits with an output in some finite time, an upper limit for which is predictable in advance. Functions that BLooP can compute are called primitive recursive functions, and it turns out that not all functions are primitive recursive. The FLooP language is the same as BLooP with the addition of an unbounded loop (MU-LOOP). FLooP can calculate anything your computer can calculate, but you cannot say in general whether a FLooP program will eventually terminate.

Features

Supports integers of arbitrary size. In other words, TWO-TO-THE-THREE-TO-THE [5] works.
Easy to use: written in C, uses the standard GNU build process.
Hard to use: requires the use of UTF-8 and non-ASCII characters.

What do programs look like?

They look a lot like programs in other block-structured languages, with minimal facilities. Not even subtraction is built in. Here is a sample (BLooP) program that determines whether various numbers are prime.

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.

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

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.

PRIME? [2].
PRIME? [10].
PRIME? [113].

The output of this program is

YES
NO
YES

The above program would probably be run like this:

bfloop minus.bloop remainder.bloop prime?.bloop -

If you look in the samples directory of the distribution you will find exactly those files. The program is the concatenation of all the input files. The - at the end means to read from standard input. That’s typically where you would type in expressions to be evaluated.

Each file must be encoded in UTF-8 and be composed of the limited alphabet shown on page 419 of GEB. Newline and tab are recognized as synonyms of space. Alphabetic characters must be upper case. The multiplication operator is ×, U+00D7. The assignment operator is ⇐, U+21D0. To enter these characters in the Vim editor, type

Ctrl-v * X or Ctrl-v u 0 0 d 7
Ctrl-v < = or Ctrl-v u 2 1 d 0

In the GNU screen terminal multiplexer, type

Ctrl-a Ctrl-v U + 0 0 d 7
Ctrl-a Ctrl-v U + 2 1 d 0

Why UTF-8? UTF-8 is the only sane encoding of Unicode. It deserves to be the next ASCII.

Sample programs

There are sample programs in the samples directory. Some of them were copied from GEB. The others are implementations of most of the “Suggested Exercises” starting on page 415. I even wrote PI-DIGIT, which gives you the nth digit of π, based on an algorithm by Fabrice Bellard, actually just a port of the file pi.c. It’s very slow.

See the included README file for help running the sample programs.

Download

bfloop-1.2.tar.gz

Use this command to get a Bazaar checkout.

bzr get http://www.bamsoftware.com/bzr/bfloop

The entry at the Free Software Directory: http://directory.fsf.org/project/bfloop/.

History

bfloop 1.0 was released on July 19, 2009. I had gotten GEB for the previous Christmas. I wanted to be able to run the programs in the book and not just think about them. Also, I wanted to learn how to use the Bison parser generator.

bfloop 1.1 was released on October 9, 2009.

bfloop 1.2 was released on October 28, 2010. This release fixes a serious bug that caused undefined behavior when running on 64-bit architectures (anywhere where unsigned long has the same size as unsigned long long).

Other implementations

bloop by Jaap Weel, compiles to Scheme or C.

bloop by John Cowan, translates to Perl. Release 1 (current as of 2015) has a bug: ‘<’ and ‘>’ both mean “less than”:

	if ($ns eq "=") {
		$code .= " == ";
		}
	elsif ($ns eq "<") {
		$code .= " < ";
		}
	elsif ($ns eq ">") {
		$code .= " < ";
		}
	else {
		last;
		}

JavaScript port of the Cowan bloop by Tim Ryan.

More GEB stuff

Some smaller programs I wrote while reading GEB are here.