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.
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? . PRIME? . PRIME? .
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 7In the GNU screen terminal multiplexer, type
Ctrl-v < = or Ctrl-v u 2 1 d 0
Ctrl-a Ctrl-v U + 0 0 d 7Why UTF-8? UTF-8 is the only sane encoding of Unicode. It deserves to be the next ASCII.
Ctrl-a Ctrl-v U + 2 1 d 0
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.
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/.
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
unsigned long long).
Some smaller programs I wrote while reading GEB are here.