(For the rest of this document, I recommend considering “fuck” to be non-profane.)

Boolfuck

Weaker, less useful, more futile: Boolfuck.
- William Sharkey

This language, Boolfuck, is based off of the programming language Brainfuck, for which it is very difficult to write useful programs. There are very few differences between this language and Brainfuck; the primary difference is that Boolfuck works with bits instead of bytes.

You might want to visit the link above if you do not already know what Brainfuck is. This document mainly highlights differences between the two languages.

Brainfuck works with an array of cells containing eight-bit characters. The array might be of a fixed size, such as 30 000. At any rate, the program starts with its pointer at the left end of the array. Boolfuck, on the other hand, consists of an infinitely-sized array. The pointer starts somewhere in the middle; there is no edge.

The other difference is that instead of having cells that can contain numbers from zero to 255, the cells contain numbers that are either zero or one. All commands work with a single bit.

Also, the character ';' is used for output, rather than Brainfuck's '.', the full stop. This makes it easy to figure out what language a program is written in. The '-' command has been removed from the language, since it performs the same operation as '+'.

Table of Functions

CharacterFunctionality
+Flips the value of the bit under the pointer.
,Reads a bit from the input stream, storing it under the pointer. The end-user types information using characters, though. Bytes are read in little-endian order—the first bit read from the character a, for instance, is 1, followed by 0, 0, 0, 0, 1, 1, and finally 0. If the end-of-file has been reached, outputs a zero to the bit under the pointer.
;Outputs the bit under the pointer to the output stream. The bits get output in little-endian order, the same order in which they would be input. If the total number of bits output is not a multiple of eight at the end of the program, the last character of output gets padded with zeros on the more significant end.
<This moves the pointer left by one bit.
>This moves the pointer right by one bit.
[If the value under the pointer is zero, jumps forward, just past the matching ] character.
]Jumps back to the matching [ character.

The notion of “matching character” should be described precisely. A matching character is the nearest character (given certain constraints) with the property that between the original character and itself, the number of [ characters equals the number of ] characters.

In other words, brackets nest.

Hello, world!

Now it is time to write a program that outputs the text, “Hello, world!” and politely follows up with a newline. This program demonstrates how the last output character gets filled with zeros if less than eight of its bits have been output, for only the “0101” of the newline character gets output; the rest gets filled with zeros, producing “01010000”, which is the number ten since the units digit is on the left end.

;;;+;+;;+;+;
+;+;+;+;;+;;+;
;;+;;+;+;;+;
;;+;;+;+;;+;
+;;;;+;+;;+;
;;+;;+;+;+;;
;;;;;+;+;;
+;;;+;+;;;+;
+;;;;+;+;;+;
;+;+;;+;;;+;
;;+;;+;+;;+;
;;+;+;;+;;+;
+;+;;;;+;+;;
;+;+;+;

Converting Brainfuck to Boolfuck

Any Brainfuck program can be easily converted to Boolfuck. The process is simple: it involves dumbly replacing each Brainfuck command with a long string of Boolfuck commands. In memory, nine bits are used to store what would be storn in eight bits using Brainfuck; the extra bit is used as a guard character when doing operations like incrementing and decrementing.

It's assumed that the to-be-converted program is written for a Brainfuck interpreter which inputs zeros after the end-of-input marker has been reached. (As opposed to one of those which inputs -1 or fails to change the cell. Those heathens.)

Brainfuck commandBoolfuck replacement
+
>[>]+<[+<]>>>>>>>>>[+]<<<<<<<<<
-
>>>>>>>>>+<<<<<<<<+[>+]<[<]>>>>>>>>>[+]<<<<<<<<<
<
<<<<<<<<<
>
>>>>>>>>>
,
>,>,>,>,>,>,>,>,<<<<<<<<
.
>;>;>;>;>;>;>;>;<<<<<<<<
[
>>>>>>>>>+<<<<<<<<+[>+]<[<]>>>>>>>>>[+<<<<<<<<[>]+<[+<]
]
>>>>>>>>>+<<<<<<<<+[>+]<[<]>>>>>>>>>]<[+<]

For example, the Brainfuck program ,[>,]<[.<], which outputs a reversed copy of its input, would, using the above method, get converted to the following Boolfuck program:

>,>,>,>,>,>,>,>,<<<<<<<<

>>>>>>>>>+<<<<<<<<+[>+]<[<]>>>>>>>>>[+<<<<<<<<[>]+<[+<]

>>>>>>>>>

>,>,>,>,>,>,>,>,<<<<<<<<

>>>>>>>>>+<<<<<<<<+[>+]<[<]>>>>>>>>>]<[+<]

<<<<<<<<<

>>>>>>>>>+<<<<<<<<+[>+]<[<]>>>>>>>>>[+<<<<<<<<[>]+<[+<]

>;>;>;>;>;>;>;>;<<<<<<<<

<<<<<<<<<

>>>>>>>>>+<<<<<<<<+[>+]<[<]>>>>>>>>>]<[+<]

There are many optimizabilities, such as <<<<<<<<< >>>>>>>>>. But the program works correctly, it reverses its input.

Boolfuck Interpreter

Distributed as source code. (This is a newer, 10th anniversary edition, from 2015.)
impl2.cpp

You can compile it with the line g++ -std=c++11 impl2.cpp -o boof.

Update: Nov 16 2015

I'm happy to see that in main.cpp I disclaimed that I'm probably not the first to invent this. I made Boolfuck in 2004 or 2005, in my freshman year of college. You can see that Smallfuck is from 2002, and on its talk page (and elsewhere on the internet) you can see mention of the F language by r.e.s., which I've also seen mentioned as “Flip” on a newsgroup or mailing discussion that I can't find right now. Unfortunately, its web page at http://r.s.home.mindspring.com/F/ is linkrotted, and a robots.txt keeps it from appearing on the Wayback Machine.

The discussion of F or Flip showed it was Turing complete by building a “tag machine,” whatever that is. The Smallfuck Announcement (scroll down) mentions that it's “quite trivial” to convert from Brainfuck to Smallfuck.

The only reason Boolfuck exists at all is that I couldn't find a bit-wise version of Brainfuck back then! (It is possible that I saw Smallfuck but was unhappy with its lack of I/O, but I didn't see r.e.s.'s F.) Boolfuck's main contribution to the world is that it has a snappier name and its webpage is still around.

The old implementation consisted of the following three files (I've updated them to have the zlib license):
main.cpp - boolfuck.cpp - boolfuck.h

What an embarrassment it was. Did I really write a function with signature grow_and_accommodate(unsigned char * & p)? There's such unnecessary complexities in the implementation and algorithm. Why do we have loop_stack? Why the bureaucracy of the bf_interpreter class? Oh, and the assignment operator for boolpit mishandles self-assignment, and pointer arithmetic happily goes out of bounds before doing a range-check. And it's strewn about 3 files.

So use the new version.


Thanks go to Daniel Cristofani for an improvement to the conversion section.


Copyright © 2005-2016 Sam Hughes