bfloop, an interpreter for the BLooP and FLooP programming languages David Fified http://www.bamsoftware.com/software/bfloop/ bfloop is an interpreter for the BLooP and FLooP programming languages described in the book Gödel, Escher, Bach by Douglas Hofstadter. To install, run ./configure make make check make install If building from a bzr checkout, first run autoreconf -i bfloop is free software; see COPYING for the license (MIT license). This license covers the interpreter and its documentation. The Bison-generated files yyparse.c and yyparse.h are licensed under the GNU General Public License version 3 with an exception; see the file GPL. See under “Sample programs” for the copyright of the programs in the samples directory. The program can run in BLooP mode or FLooP mode. Use the --bloop or --floop option to choose which. The only difference is that in BLooP mode the MU-LOOP construction is prohibited. BLooP mode is the default. The program takes the names of files to run on the command line. If any of them have a filename of “.floop”, FLooP mode is used, unless overriden by --bloop. The program is run as if all the files were concatentated, except that a statement may not be split across files. If one procedure depends on another, and the two are in separate files, you must name them both in the correct order, as in bfloop minus.bloop remainder.bloop See more examples in the samples/sample.sh file. If a filename is “-”, it stands for standard input. When standard input is read from a terminal, each statement is executed as soon as it is entered. To load some procedures and then interatively execute them, put “-” at the end of the argument list, like this: $ bfloop samples/two-to-the-three-to-the.bloop - TWO-TO-THE-THREE-TO-THE [4]. 2417851639229258349412352 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 v*X or vu00d7 v<= or vu21d0 In the GNU screen terminal multiplexer, type avU+00d7 avU+21d0 == Implementation notes The syntax of BLooP and FLooP is not laid out explicitly in GEB but presented through examples. Here is a description of some of bfloop’s syntax rules and justification for them. In general, I was conservative in deciding what to allow. If I didn’t find an example of a feature’s use in GEB, I left it out. For example, you cannot string together multiple operators (“1 + 2 + 3”). Likewise AND is supported but not OR. A procedure definition must contain a BLOCK, not a bare statement. Contrast this with an IF, which may contain a single statement rather than a BLOCK. If this were not the case, the shortest Blue Program on page 419 would be shorter. The shortest Blue Program on page 419 also shows that a procedure must have at least one parameter, by the same reasoning. Page 413 says that a program consists of a chain of procedure definitions followed by zero or more calls to the procedures. However, the syntax for the following calls is not made clear. The example call on page 414 has no terminating punctuation, although that could be interpreted as being a snippet out of context. In the ENIUQ examples on pages 498 and 499, dots follow the procedure calls, and tellingly ENIUQ itself inserts a dot. Even though those examples are written in a “BlooP-like language,” I decided to require a dot after each toplevel function call; this is uniform with the way procedure definitions are handled. The Cowan bloop program (see “Other implementations”) looks for a dot after each call. The Weel bloop uses semicolons, as if inside a procedure. The body of an IF may be a BLOCK or a bare statement; compare PRIME? and GOLDBACH?. But LOOP and MU-LOOP require a BLOCK body. There's no example of a LOOP with a statement for a body. TWO-TO-THE-THREE-TO-THE has two LOOPs, wach with a BLOCK containing a single statement. The definition of MU-LOOP on page 424 uses a BLOCK. I am aware of only two instances of code from the book that doesn't run unmodified. The first is the examples for TORTOISE-PAIR? and TORTOISE? on page 416; the examples lack the question marks, an obvious mistake. The other is the GOLDBACH? test on page 414. It seems that there should be a semicolon after “BLOCK 2: END”; this would be consistent with how blocks are handled within loops. It has to be admitted that there is no other example of a BLOCK inside an IF to compare GOLDBACH? to, so perhaps that is the intended syntax. bfloop requires a semicolon in that position. == Sample programs Some sample programs are included in the samples directory. The programs goldbach?.bloop minus.bloop prime?.bloop two-to-the-three-to-the.bloop are from the book. pi-digit.bloop is a port of a C program by Fabrice Bellard, who says “pi.c is under the BSD license, so there is no problem if you want to redistribute it (you just have to keep my name in the source code).” The other samples are written by me and are in the public domain. The script samples/sample.sh runs all the sample programs and shows some output. Also try running test.sh (done by “make check”). If any test comes up FAIL, please report it as a bug. The algorithm in samples/pi-digit.bloop is from a paper by Fabrice Bellard at http://bellard.org/pi/. The code is a fairly direct port of pi.c from that page. As an aid to understanding, here are the values that various cells represent. Cells 100 and greater are used for temporary values. CELL(0) N CELL(1) 2 × N CELL(2) a CELL(3) νmax CELL(4) m CELL(5) b CELL(6) A CELL(7) α CELL(8) νdown CELL(9) νup CELL(10) k CELL(11) m1 CELL(12) m2 OUTPUT sum In the original algorithm ν is allowed to be negative. Because we can't represent negative numbers directly, ν is represented by νdown and νup, where νdown is what has been subtracted from ν and νup is what has been added. sum is an integer 0–9999 representing fractions 0.0–0.9999. == Other implementations http://code.google.com/p/bloop/ This implementation in Haskell by Jaap Weel converts BLooP/FLooP into C or scheme. http://catb.org/retro/ John Cowan wrote this one in Perl. http://tim-ryan.com/labs/bloopjs/ This is a port of the Cowan bloop into JavaScript by Tim Ryan.