Brainbool

From Esolang
Jump to: navigation, search

Brainbool is a Brainfuck derivative very similar to Boolfuck, in that it has input and output and operates only on bits. Brainbool's input and output consists solely of the characters '0' (zero) and '1' (one). Brainbool's express purpose for existence is to be interpreted by other esoteric programming languages. Many of the Brainfuck interpreters on the EsoInterpreters page (Thue, for instance) are actually interpreters of something very similar to Brainbool.

The rest of this page assumes the reader is familiar with Brainfuck.

Preamble

Many esoteric programming languages with character or line based input do not convert input characters to their numerical values and do not have operators to convert characters to/from numbers. This is the case for languages in the String-rewriting paradigm such as Thue and ///. The only way for these languages to convert an input character to an internal numerical representation is to compare the input character to each character in the entire input character set. The same difficulty exists when converting an internal numerical representation into an output character. By limiting the input and output character set, the number of necessary comparisons is reduced. Thus, for languages with the aforementioned limitations, interpreting a Brainbool program with input and/or output is much easier than interpreting a Brainfuck program with input and/or output.

The almost universal character set and character<->numeral conversion table that is used when dealing with Brainfuck is ASCII. However, it doesn't have to be ASCII, and this page will just use phrases like "character's numerical value" and not assume ASCII.

Input and Output

Input to Brainbool is character based, rather than raw binary as in Boolfuck. However, the only valid input characters are '0' and '1'. The input command "," sets the current cell to 1 if the next input character is a '1' and to 0 if the next input character is '0' or there is no more input. Any input character other than '0' and '1' produces undefined results. Implementations may require that each '0' or '1' is followed by a newline.

Implementations can, optionally, handle raw binary input instead, setting cells based on the input bitstream. If the raw binary input is character-based, the character bits should be supplied to the brainbool program in little-endian order. This is the input scheme used by Boolfuck.

Output is the characters '0' and '1' for the values 0 and 1, respectively. Often, the output stream of '0's and '1's will represent a little-endian bitstream of 8-bit characters. This is the case for Brainbool programs created by converting Brainfuck programs.

The reference Brainbool interpreter, brainbool.pl, provides facilities to convert back and forth between a character stream and a stream of '0's and '1's. Here is an example of a terminal session

$ ./brainfuck hello.b
Hello World!

$ ./brainbool.pl --to-brainbool hello.b > hello.bb

$ ./brainbool.pl hello.bb
00010010101001100011011000110110111101100000010011101010111101100100111000110110001001101000010001010000

$ ./brainbool.pl hello.bb | ./brainbool.pl --output
Hello World!

$ echo 100 | ./brainfuck prime.b
Primes up to: 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

$ ./brainbool.pl --to-brainbool prime.b > prime.bb

$ echo 100 | ./brainbool.pl --input | ./brainbool.pl prime.bb | ./brainbool.pl --output
Primes up to: 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

Instruction set

The default instruction set is the same as Brainfuck, except that - is eliminated.

>   Move pointer right
<   Move pointer left
+   "Logical NOT" the current cell
[   Jump past matching ] if cell under pointer is 0
]   Jump back to matching [
,   Set current cell to 1 if next input character is a '1' and to 0 if next input character is '0' or there is no more input
.   Output a '0' if the current cell is 0 and a '1' if it is 1

Other instruction sets exist, however and may be used instead.

Smallfuck

> < * [ ]
 -- "*" NOTs the current cell
 -- Use , and . for I/O

Boolfuck

> < + [ ] , ;
 -- ";" is equivalent to "." (this is not the case for real Boolfuck)

BF bit

> < @ [ ] , .
 -- "@" NOTs the current cell.

BitChanger

< } [ ]
 -- "}" combines ">+". Use "}<}" for ">", and "<}" for "+"
 -- Use , and . for I/O

Combining program data and input data

A Brainbool interpreter that is reading in the Brainbool program on STDIN needs to know when the program source is fully read in and the input to the program begins. The classic method of doing this is "dbfi style", where the end of Brainfuck input is indicated with a "!" character. This is implemented in the reference Brainbool interpreter, brainbool.pl:

# uses prime.bb, which was created above

$ { cat prime.bb; echo -n '!'; echo 100 | ./brainbool.pl --input; } | ./brainbool.pl --bang | ./brainbool.pl --output
Primes up to: 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

A brainbool program that interprets brainbool could, of course, read in the source brainbool program as a character stream converted to 8 '1's & '0's per character. However, brainbool only uses 7 characters (><+[],.) plus '!'. Three bits is sufficient. The following table is the standard 3-"bit" (3-character) representation of the brainbool instruction set:

brainbool command    3-digit replacement
>                    "001"
<                    "010"
+                    "011"
,                    "100"
.                    "101"
[                    "110"
]                    "111"
!                    "000"

brainbool.pl provides a facility to convert a brainbool program into a 3-bit representation

$ ./brainbool.pl --to-brainfuck --3digit --bang hello.b > hello.bb

$ ./brainbool.pl --3digit hello.bb | ./brainbool.pl --output
Hello World!

# a brainbool self-interpreter
$ cat hello.bb | ./brainbool.pl bb_self_3.bb | ./brainbool.pl --output
Hello World!

Converting Brainfuck to Brainbool

This conversion table is shamelessly stolen from Sam Hughes' excellent Boolfuck page.

Brainfuck command	Boolfuck replacement
+			>[>]+<[+<]>>>>>>>>>[+]<<<<<<<<<
-			>>>>>>>>>+<<<<<<<<+[>+]<[<]>>>>>>>>>[+]<<<<<<<<<
<			<<<<<<<<<
>			>>>>>>>>>
,			>,>,>,>,>,>,>,>,<<<<<<<<
.			>.>.>.>.>.>.>.>.<<<<<<<<
[			>>>>>>>>>+<<<<<<<<+[>+]<[<]>>>>>>>>>[+<<<<<<<<[>]+<[+<]
]			>>>>>>>>>+<<<<<<<<+[>+]<[<]>>>>>>>>>]<[+<]

The above conversion assumes 8-bit wrapping (e.g. 255 + 1 = 0 and 0 - 1 = 255) cells and left-terminated tape. Every Brainfuck cell takes up nine Brainbool cells. A slight speedup can be achieved if non-wrapping cells is assumed. The reference Brainbool interpreter, brainbool.pl, performs a non-wrapping conversion when given the --to-brainbool switch. It uses wrapping cells when also given the --wrap switch.

Converting Brainbool to Brainfuck

One Brainbool cell takes up two Brainfuck cells. The resultant Brainfuck program expects all input to be '0' or '1' and outputs only '0' or '1'.

Boolfuck command	Brainfuck replacement
+			>+<[->-<]>[-<+>]<
<			<<
>			>>
,			,>++++++[-<-------->]<
.			>++++++[-<++++++++>]<.>++++++[-<-------->]<
[			[
]			]

The reference Brainbool interpreter, brainbool.pl, performs this conversion when given the --to-brainfuck switch.

Computational class

The Brainbool tape is left-terminated and right-infinite. All cells are initially zero. All programs begin with the pointer on the leftmost cell. Program size and the number of [ ] loops and the level of [ ] nesting are all unbounded. Brainbool without I/O is equivalent to F2, which makes Brainbool Turing-complete.

Postamble

Brainbool is essentially a formalization of a modification/variation to brainfuck that has been employed on an ad-hoc basis in the past. There are direct conversion rules between brainbool and brainfuck for input, output and program. These conversion rules could be implemented by a Finite-state automaton. Thus, any language that can interpret brainbool can (by one definition) interpret brainfuck. In many cases, expanding an esolang brainbool interpreter so it can interpret full-fledged brainfuck is possible if the interpreter program is given a ponderous list of character conversion rules.

See also