6
\$\begingroup\$

From now on considering the word "fuck" to be non-profane would be a good idea

Make the smallest compiler or an interpreter for the Brainfuck variant, Boolfuck. It has to be executable in Windows, DOS, or a Unix operating system (so Linux, Mac, OpenBSD etc). Boolfuck is very similar to Brainfuck, and a complete definition can be found here.

Differences from Brainfuck

  1. Works with bits not bytes (each cell is a single bit)
  2. The output character is ; not .
  3. The input is read in little endian mode and reads a single bit at a time.
  4. Output is stored to a stream, then outputted in little endian mode

Rules

  1. Use bits for the cells, not bytes
  2. Support the complete list of operations from the official definition:

    +  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.
    
    ;  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. If
       the end-of-file character has been input, outputs a zero to the 
       bit under the pointer.
    
    <  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.
    

    Any character not in the official definition is ignored.

  3. The program must start in the middle of the tape, not on an end.

  4. The tape must be unbounded in size (infinite in both directions).

Here is a sample Boolfuck program; it outputs Hello, world!:

;;;+;+;;+;+;
+;+;+;+;;+;;+;
;;+;;+;+;;+;
;;+;;+;+;;+;
+;;;;+;+;;+;
;;+;;+;+;+;;
;;;;;+;+;;
+;;;+;+;;;+;
+;;;;+;+;;+;
;+;+;;+;;;+;
;;+;;+;+;;+;
;;+;+;;+;;+;
+;+;;;;+;+;;
;+;+;+;
\$\endgroup\$
  • 1
    \$\begingroup\$ Would a just-in-time compiler satisfy the requirement of 'compiler'? \$\endgroup\$ – primo May 18 '14 at 3:26
  • \$\begingroup\$ In my sleep-deprived state, I was really excited when it occurred to me that it would be really simple to make a Brainfuck to Boolfuck compiler. Then I realized that that was the opposite of what was asked. :( \$\endgroup\$ – millinon May 18 '14 at 5:40
  • \$\begingroup\$ You could still do it... It wouldn't meet the requirements for the question though. It WOULD be very easy to do that, because the website I gave in the question gives all the conversion you need @millinon \$\endgroup\$ – OVER9000 May 18 '14 at 9:32
  • \$\begingroup\$ @primo Yes it would \$\endgroup\$ – OVER9000 May 18 '14 at 9:32
  • \$\begingroup\$ @OVER9000 how about an interpreter? \$\endgroup\$ – Martin Ender May 18 '14 at 10:59
8
\$\begingroup\$

Perl - 171 bytes

#!perl -0
%h=qw(< --$p > ++$p + $$p^=1 [ while($$p){ ] } ; $o|=$$p<<$g++;$g&=7or$o=!print+chr$o , $f&=7or$_=getc;$$p=1&ord>>$f++);$p=-1e9;eval<ARGV>=~s/./$h{$&};/gr;$g&&print+chr$o

Counting the shebang as 1 byte.

This translates the source into perl, and then evaluates the translation. The target program is taken as a command line argument, input sent to the program should be piped via stdin.

Sample usage:

$ perl boolf.pl hello.blf
Hello, world!

Details

Each of the commands is translated as follows:

<--$p;
>++$p;
+$$p^=1;
[while($$p){
]}
;$o|=$$p<<$g++;$g&=7or$o=!print+chr$o;
,$f&=7or$_=getc;$$p=1&ord>>$f++;

Negative integers are valid variable names, which is exploited here. $p, the cell pointer, is initialized as -1000000000, which is approximately at the center of the valid range, -2147483648 .. -1.

I've violated the specification in one regard: output is not printed all at once at the end, but rather as soon as a full byte has been collected. It's slightly longer this way, but I think it's more useful, as it allows for interactive scripts. For example, the Rot13 program below can be run in 'interactive mode', terminating the program with an eof char (^D on linux, ^Z on windows).

Edit - Demonstration of Endianness

There seems to be some doubt as to whether this interpreter reads bits in the proper (little-endian) order. I offer the following Boolfuck program, which reads a total of 8 bits, one at a time, and outputs each value read as its numeric ascii representation (0 outputs character 48, 1 outputs character 49). Each value is output entirely before the next bit is even read.

,;[+];;;+;;+;;
,;[+];;;+;;+;;
,;[+];;;+;;+;;
,;[+];;;+;;+;;
,;[+];;;+;;+;;
,;[+];;;+;;+;;
,;[+];;;+;;+;;
,;[+];;;+;;+;;

Sample usage:

$ echo a | perl boolf.pl test.blf
10000110

From the problem description:
"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."

According to this description, the bits are read in the proper order.


Stress Testing

First, a script to translate Brainfuck programs into Boolfuck:

#!perl -n0

%h = (
  '+' => '>[>]+<[+<]>>>>>>>>>[+]<<<<<<<<<',
  '-' => '>>>>>>>>>+<<<<<<<<+[>+]<[<]>>>>>>>>>[+]<<<<<<<<<',
  '<' => '<<<<<<<<<',
  '>' => '>>>>>>>>>',
  ',' => '>,>,>,>,>,>,>,>,<<<<<<<<',
  '.' => '>;>;>;>;>;>;>;>;<<<<<<<<',
  '[' => '>>>>>>>>>+<<<<<<<<+[>+]<[<]>>>>>>>>>[+<<<<<<<<[>]+<[+<]',
  ']' => '>>>>>>>>>+<<<<<<<<+[>+]<[<]>>>>>>>>>]<[+<]'
);

$o .= $h{$_} for /./g;
$o =~ s/<(?R)?>//g;
print $o

The Rot13 program from the Brainfuck Wiki Page translates thusly (with slight modification for null byte eof, rather than 255):

,>,>,>,>,>,>,>,>+<<<<<<<<+[>+]<[<]>>>>>>>>>[+<<<<<<<<[>]+<[+<]>>>>>>>>>+<<<<<<<<+[>+]
<[<]>>>>>>>>>[+<<<<<<<<[>]+<[+<]>>>>>>>>>>>>>>>>>>>[>]+<[+<]>>>>>>>>>[+]<<<<<<<<[>]+<
[+<]>>>>>>>>>[+]<<<<<<<<[>]+<[+<]>>>>>>>>>[+]<<<<<<<<[>]+<[+<]>>>>>>>>>[+]+<<<<<<<<+[
>+]<[<]>>>>>>>>>[+<<<<<<<<[>]+<[+<]>>>>>>>>>>[>]+<[+<]>>>>>>>>>[+]<<<<<<<<[>]+<[+<]>>
>>>>>>>[+]<<<<<<<<[>]+<[+<]>>>>>>>>>[+]<<<<<<<<[>]+<[+<]>>>>>>>>>[+]<<<<<<<<[>]+<[+<]
>>>>>>>>>[+]<<<<<<<<[>]+<[+<]>>>>>>>>>[+]<<<<<<<<[>]+<[+<]>>>>>>>>>[+]<<<<<<<<[>]+<[+
<]>>>>>>>>>[+]<<<<<<<<<+<<<<<<<<+[>+]<[<]>>>>>>>>>[+]+<<<<<<<<+[>+]<[<]>>>>>>>>>]<[+<
]<<<<<<<<[>]+<[+<]>>>>>>>>>[+]<<<<<<<<<+<<<<<<<<+[>+]<[<]>>>>>>>>>[+]+<<<<<<<<+[>+]<[
<]>>>>>>>>>[+<<<<<<<<[>]+<[+<]>>>>>>>>>>[>]+<[+<]>>>>>>>>>[+]>[>]+<[+<]>>>>>>>>>[+]>>
>>>>>>>+<<<<<<<<+[>+]<[<]>>>>>>>>>[+]+<<<<<<<<+[>+]<[<]>>>>>>>>>[+<<<<<<<<[>]+<[+<]>>
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>+<<<<<<<<+[>+]<[<]>>>>>>>>>]<[+<]+<<<<<<<<+[>+]<[<]
>>>>>>>>>[+<<<<<<<<[>]+<[+<]>>>>>>>>>+<<<<<<<<+[>+]<[<]>>>>>>>>>[+<<<<<<<<[>]+<[+<]>>
>>>>>>>>[>]+<[+<]>>>>>>>>>[+]<<<<<<<<<+<<<<<<<<+[>+]<[<]>>>>>>>>>[+]+<<<<<<<<+[>+]<[<
]>>>>>>>>>]<[+<]>>>>>>>>>>>>>>>>>>>[>]+<[+<]>>>>>>>>>[+]>>>>>>>>>+<<<<<<<<+[>+]<[<]>>
>>>>>>>]<[+<]<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<+<<<<<<<<+[>+]<[<]>>>>>>>>>[+]+<<<<<
<<<+[>+]<[<]>>>>>>>>>]<[+<]>>>>>>>>>+<<<<<<<<+[>+]<[<]>>>>>>>>>]<[+<]>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>>>>>+<<<<<<<<+[>+]<[<]>>>>>>>>>[+<<<<<<<<[>]+<[+<]>>>>>>>>>+<<<<<<<<+
[>+]<[<]>>>>>>>>>[+]+<<<<<<<<+[>+]<[<]>>>>>>>>>]<[+<]>[>]+<[+<]>>>>>>>>>[+]>>>>>>>>>+
<<<<<<<<+[>+]<[<]>>>>>>>>>[+]+<<<<<<<<+[>+]<[<]>>>>>>>>>[+]+<<<<<<<<+[>+]<[<]>>>>>>>>
>[+<<<<<<<<[>]+<[+<]>>>>>>>>>+<<<<<<<<+[>+]<[<]>>>>>>>>>[+]+<<<<<<<<+[>+]<[<]>>>>>>>>
>[+<<<<<<<<[>]+<[+<]+<<<<<<<<+[>+]<[<]>>>>>>>>>[+]>[>]+<[+<]>>>>>>>>>[+]<<<<<<<<[>]+<
[+<]>>>>>>>>>[+]<<<<<<<<[>]+<[+<]>>>>>>>>>[+]+<<<<<<<<+[>+]<[<]>>>>>>>>>[+<<<<<<<<[>]
+<[+<]>>>>>>>>>+<<<<<<<<+[>+]<[<]>>>>>>>>>[+]+<<<<<<<<+[>+]<[<]>>>>>>>>>]<[+<]>>>>>>>
>>+<<<<<<<<+[>+]<[<]>>>>>>>>>]<[+<]>>>>>>>>>+<<<<<<<<+[>+]<[<]>>>>>>>>>]<[+<]+<<<<<<<
<+[>+]<[<]>>>>>>>>>[+<<<<<<<<[>]+<[+<]>[>]+<[+<]>>>>>>>>>[+]<<<<<<<<[>]+<[+<]>>>>>>>>
>[+]<<<<<<<<[>]+<[+<]>>>>>>>>>[+]<<<<<<<<[>]+<[+<]>>>>>>>>>[+]<<<<<<<<[>]+<[+<]>>>>>>
>>>[+]<<<<<<<<[>]+<[+<]>>>>>>>>>[+]<<<<<<<<[>]+<[+<]>>>>>>>>>[+]<<<<<<<<[>]+<[+<]>>>>
>>>>>[+]<<<<<<<<[>]+<[+<]>>>>>>>>>[+]<<<<<<<<[>]+<[+<]>>>>>>>>>[+]<<<<<<<<[>]+<[+<]>>
>>>>>>>[+]<<<<<<<<[>]+<[+<]>>>>>>>>>[+]<<<<<<<<<+<<<<<<<<+[>+]<[<]>>>>>>>>>[+<<<<<<<<
[>]+<[+<]>>>>>>>>>>>>>>>>>>+<<<<<<<<+[>+]<[<]>>>>>>>>>[+]+<<<<<<<<+[>+]<[<]>>>>>>>>>[
+<<<<<<<<[>]+<[+<]>>>>>>>>>>[>]+<[+<]>>>>>>>>>[+]>>>>>>>>>>>>>>>>>>+<<<<<<<<+[>+]<[<]
>>>>>>>>>]<[+<]>>>>>>>>>>>>>>>>>>+<<<<<<<<+[>+]<[<]>>>>>>>>>[+<<<<<<<<[>]+<[+<]>[>]+<
[+<]>>>>>>>>>[+]+<<<<<<<<+[>+]<[<]>>>>>>>>>[+<<<<<<<<[>]+<[+<]<<<<<<<<[>]+<[+<]>>>>>>
>>>[+]>>>>>>>>>+<<<<<<<<+[>+]<[<]>>>>>>>>>[+]+<<<<<<<<+[>+]<[<]>>>>>>>>>]<[+<]>>>>>>>
>>>[>]+<[+<]>>>>>>>>>[+]>>>>>>>>>>>>>>>>>>+<<<<<<<<+[>+]<[<]>>>>>>>>>]<[+<]<<<<<<<<<<
<<<<<<<<<<<<<<<<<<<<<<<<<<+<<<<<<<<+[>+]<[<]>>>>>>>>>[+]+<<<<<<<<+[>+]<[<]>>>>>>>>>]<
[+<]>>>>>>>>>>>>>>>>>>>>>>>>>>>+<<<<<<<<+[>+]<[<]>>>>>>>>>[+<<<<<<<<[>]+<[+<]<<<<<<<<
[>]+<[+<]>>>>>>>>>[+]>>>>>>>>>+<<<<<<<<+[>+]<[<]>>>>>>>>>[+]+<<<<<<<<+[>+]<[<]>>>>>>>
>>]<[+<]>>>>>>>>>>>>>>>>>>+<<<<<<<<+[>+]<[<]>>>>>>>>>[+<<<<<<<<[>]+<[+<]>>>>>>>>>+<<<
<<<<<+[>+]<[<]>>>>>>>>>[+]+<<<<<<<<+[>+]<[<]>>>>>>>>>[+<<<<<<<<[>]+<[+<]>>>>>>>>>+<<<
<<<<<+[>+]<[<]>>>>>>>>>[+]<<<<<<<<<<<<<<<<<<+<<<<<<<<+[>+]<[<]>>>>>>>>>[+<<<<<<<<[>]+
<[+<]>>>>>>>>>+<<<<<<<<+[>+]<[<]>>>>>>>>>[+]+<<<<<<<<+[>+]<[<]>>>>>>>>>]<[+<]>>>>>>>>
>>>>>>>>>>>>>>>>>>>+<<<<<<<<+[>+]<[<]>>>>>>>>>]<[+<]<<<<<<<<<+<<<<<<<<+[>+]<[<]>>>>>>
>>>[+<<<<<<<<[>]+<[+<]<<<<<<<<<+<<<<<<<<+[>+]<[<]>>>>>>>>>[+]>>>>>>>>>>>>>>>>>>+<<<<<
<<<+[>+]<[<]>>>>>>>>>[+]+<<<<<<<<+[>+]<[<]>>>>>>>>>]<[+<]>>>>>>>>>>>>>>>>>>>>>>>>>>>+
<<<<<<<<+[>+]<[<]>>>>>>>>>]<[+<]<<<<<<<<<+<<<<<<<<+[>+]<[<]>>>>>>>>>[+<<<<<<<<[>]+<[+
<]<<<<<<<<<<<<<<<<<[>]+<[+<]>>>>>>>>>[+]>>>>>>>>>>>>>>>>>>+<<<<<<<<+[>+]<[<]>>>>>>>>>
[+]+<<<<<<<<+[>+]<[<]>>>>>>>>>]<[+<]>>>>>>>>>+<<<<<<<<+[>+]<[<]>>>>>>>>>]<[+<]+<<<<<<
<<+[>+]<[<]>>>>>>>>>[+<<<<<<<<[>]+<[+<]>>>>>>>>>+<<<<<<<<+[>+]<[<]>>>>>>>>>[+]+<<<<<<
<<+[>+]<[<]>>>>>>>>>]<[+<]<<<<<<<<;>;>;>;>;>;>;>;>+<<<<<<<<+[>+]<[<]>>>>>>>>>[+<<<<<<
<<[>]+<[+<]>>>>>>>>>+<<<<<<<<+[>+]<[<]>>>>>>>>>[+]+<<<<<<<<+[>+]<[<]>>>>>>>>>]<[+<]+<
<<<<<<<+[>+]<[<]>>>>>>>>>[+]<<<<<<<<,>,>,>,>,>,>,>,>+<<<<<<<<+[>+]<[<]>>>>>>>>>]<[+<]

On a 26 character string, this runs in approximately 0.17 seconds:

$ echo abcdefghijklmnopqrstuvwxyz | timeit perl boolf.pl rot13.blf
nopqrstuvwxyzabcdefghijklm

Elapsed Time:     0:00:00.171

The squares.b from Daniel Cristofani's site:

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

Runs in about 2.4s:

$ timeit perl boolf.pl out.dat
0
1
4
9
16
25
36
49
64
81
100
121
144
169
196
225
256
289
324
361
400
441
484
529
576
625
676
729
784
841
900
961
1024
1089
1156
1225
1296
1369
1444
1521
1600
1681
1764
1849
1936
2025
2116
2209
2304
2401
2500
2601
2704
2809
2916
3025
3136
3249
3364
3481
3600
3721
3844
3969
4096
4225
4356
4489
4624
4761
4900
5041
5184
5329
5476
5625
5776
5929
6084
6241
6400
6561
6724
6889
7056
7225
7396
7569
7744
7921
8100
8281
8464
8649
8836
9025
9216
9409
9604
9801
10000

Elapsed Time:     0:00:02.421
| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ Shame the tape isn't infinite (within memory constraints of course). Still: well done! \$\endgroup\$ – ɐɔıʇǝɥʇuʎs May 19 '14 at 11:37
  • \$\begingroup\$ Also a shame the byte is read big-endian \$\endgroup\$ – OVER9000 Jun 10 '14 at 0:03
  • \$\begingroup\$ @OVER9000 it isn't, though. $f&=7or$_=getc;$$p=1&ord>>$f++; The lowest bit is read first (if f is greater than 7, read a new byte and set f zero. Set the current cell to the ordinal value of the character just read, right shifted by f (post increment), mod 2. \$\endgroup\$ – primo Jun 10 '14 at 2:15
  • \$\begingroup\$ @OVER9000 I've added a demonstration of endianness to the answer. Please review. \$\endgroup\$ – primo Jun 10 '14 at 10:25
  • 1
    \$\begingroup\$ @primo yes you are correct, thanks for clearing that up* \$\endgroup\$ – OVER9000 Jun 13 '14 at 6:39
3
\$\begingroup\$

Python (531 byte compiler)

This is a source-to-source compiler: it compiles Boolfuck to Python. Takes input from a file as its first argument, outputs Python code to file o in the current dict.

exec"eJxdUs1u8yAQvOcpEBez/lNS9RDZpS+C+CQ3xg5RwlKMmkTV9+5l7bZue2RmZ4YdGAJe2HSfmL14DDFvndy2o0RvnOjC+KZ2Gupgul5A20vFh7/zM2CjCRHxvMI+2UQ5mZh0KJXmuu2LpD9J9WKdwNCLO4Bqdk210wMGdmfWsSn21n3G6dbKS+eFdbE8HLskytWtyLZZfk53u0G1J9mNZCcNwO3AS54OIzPnyXCuN8QfiB8bynY5Z7wQPP6T7/4/zRdcysMyHuuu74UHOzBbe/QCCGYxXeaCbyYxS8C3AJOjJ/OoiWlXxldyR9DTD6hYoOcVuh7t2bDFoSFOrRxPy7tCPrJfMKtmQK/AdjN3ijLL6hOmhqivKYbyqzcEmOtHNTRDsdeMKhkoM3RuNGJbUpcI5T4l0ka47D7XLPbVzKr0QpB4H5LlV9LhGChBvKqGXrB8ACDvV/JGSK89/6A8w2sG9TWkDyKyzae2B/gAiGHBlw".decode('base64').decode('zip')

If you really really mind the cheating with the zip and all that, the actual code is 631 bytes long (longer than the original Brainfuck compiler, but shorter than the original False compiler):

from sys import*;n=0;g=open(argv[1]).read();d=["from sys import*;from itertools import*;p=0;t=set();o=[]"];d+=["j=[bin(ord(y))[:1:-1]for y in stdin.read()];i=map(int,chain(*[x+'0'*len(x)-8for x in j]))"if","in g else""]
for c in g:d+=[n*" "+("t^={p}"if"+"==c else"t.add(p)if i.pop()else t.remove(p)"if","==c else"o+=[p in t]"if";"==c else"p-=1"if"<"==c else"p+=1"if">"==c else"while p in t:"if"["==c else"")];n+=4 if"["==c else -4 if"]"==c else 0
d+=["o=''.join(map(str,map(int,o)));o=[o[f:f+8] for f in range(0,len(o),8)];o+=[o.pop()+'0'*(8-len(o[-1]))];print''.join(chr(int(q[::-1],2))for q in o)"];open(*'ow').write('\n'.join(d))

This is possibly the fugliest python I've ever written, even though the open(*'ow') instead of open('o','w') made me feel really smart ;)

With a (slightly) better layout:

import sys

n = 0
g = open(sys.argv[1]).read()
d = ["from sys import*;from itertools import*;p=0;t=set();o=[]"]
d += [
    "j=[bin(ord(y))[:1:-1]for y in stdin.read()];i=map(int,chain(*["
    "x+'0'*len(x)-8for x in j]))" if "," in g else ""]
for c in g:
    d += [n * " " + (
        "t^={p}" if "+" == c
        else "t.add(p)if i.pop()else t.remove(p)" if "," == c
        else "o+=[p in t]" if ";" == c
        else "p-=1" if "<" == c
        else "p+=1" if ">" == c
        else "while p in t:" if "[" == c
        else "")]
    n += 1 if "[" == c else -1 if "]" else 0
d += [
    "o=''.join(map(str,map(int,o)));o=[o[f:f+8] for f in range(0,len(o),"
    "8)];o+=[o.pop()+'0'*(8-len(o[-1]))];print''.join(chr(int(q[::-1],"
    "2))for q in o)"]

open(*'ow').write('\n'.join(d))

And lastly, the example output for the "Hello World" test you gave:

from sys import*;from itertools import*;p=0;t=set();o=[]

o+=[p in t]
o+=[p in t]
o+=[p in t]
t^={p}
o+=[p in t]
t^={p}
o+=[p in t]
o+=[p in t]
t^={p}
o+=[p in t]
t^={p}
o+=[p in t]

t^={p}
o+=[p in t]
t^={p}
o+=[p in t]
t^={p}
o+=[p in t]
t^={p}
o+=[p in t]
o+=[p in t]
t^={p}
o+=[p in t]
o+=[p in t]
t^={p}
o+=[p in t]

o+=[p in t]
o+=[p in t]
t^={p}
o+=[p in t]
o+=[p in t]
t^={p}
o+=[p in t]
t^={p}
o+=[p in t]
o+=[p in t]
t^={p}
o+=[p in t]

o+=[p in t]
o+=[p in t]
t^={p}
o+=[p in t]
o+=[p in t]
t^={p}
o+=[p in t]
t^={p}
o+=[p in t]
o+=[p in t]
t^={p}
o+=[p in t]

t^={p}
o+=[p in t]
o+=[p in t]
o+=[p in t]
o+=[p in t]
t^={p}
o+=[p in t]
t^={p}
o+=[p in t]
o+=[p in t]
t^={p}
o+=[p in t]

o+=[p in t]
o+=[p in t]
t^={p}
o+=[p in t]
o+=[p in t]
t^={p}
o+=[p in t]
t^={p}
o+=[p in t]
t^={p}
o+=[p in t]
o+=[p in t]

o+=[p in t]
o+=[p in t]
o+=[p in t]
o+=[p in t]
o+=[p in t]
t^={p}
o+=[p in t]
t^={p}
o+=[p in t]
o+=[p in t]

t^={p}
o+=[p in t]
o+=[p in t]
o+=[p in t]
t^={p}
o+=[p in t]
t^={p}
o+=[p in t]
o+=[p in t]
o+=[p in t]
t^={p}
o+=[p in t]

t^={p}
o+=[p in t]
o+=[p in t]
o+=[p in t]
o+=[p in t]
t^={p}
o+=[p in t]
t^={p}
o+=[p in t]
o+=[p in t]
t^={p}
o+=[p in t]

o+=[p in t]
t^={p}
o+=[p in t]
t^={p}
o+=[p in t]
o+=[p in t]
t^={p}
o+=[p in t]
o+=[p in t]
o+=[p in t]
t^={p}
o+=[p in t]

o+=[p in t]
o+=[p in t]
t^={p}
o+=[p in t]
o+=[p in t]
t^={p}
o+=[p in t]
t^={p}
o+=[p in t]
o+=[p in t]
t^={p}
o+=[p in t]

o+=[p in t]
o+=[p in t]
t^={p}
o+=[p in t]
t^={p}
o+=[p in t]
o+=[p in t]
t^={p}
o+=[p in t]
o+=[p in t]
t^={p}
o+=[p in t]

t^={p}
o+=[p in t]
t^={p}
o+=[p in t]
o+=[p in t]
o+=[p in t]
o+=[p in t]
t^={p}
o+=[p in t]
t^={p}
o+=[p in t]
o+=[p in t]

o+=[p in t]
t^={p}
o+=[p in t]
t^={p}
o+=[p in t]
t^={p}
o+=[p in t]
o=''.join(map(str,map(int,o)));o=[o[f:f+8] for f in range(0,len(o),8)];o+=[o.pop()+'0'*(8-len(o[-1]))];print''.join(chr(int(q[::-1],2))for q in o)

A memfiller, +[>+] also works really well (and quick, consuming about 2 gigs in 10 seconds):

from sys import*;from itertools import*;p=0;t=set();o=[]

t^={p}
while p in t:
    p+=1
    t^={p}

o=''.join(map(str,map(int,o)));o=[o[f:f+8] for f in range(0,len(o),8)];o+=[o.pop()+'0'*(8-len(o[-1]))];print''.join(chr(int(q[::-1],2))for q in o)
| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

Perl, 325 bytes

undef$/;open C,'<',pop;@I=split//,unpack'b*',<>;@C=split//,<C>;while($c<@C){$_=$C[$c];$D=\$D{$d};$$D=!$$D if/\+/;$$D=shift@I if/,/;/</&&$d--;/>/&&$d++;$O.=$$D?1:0if/;/;if(/\[/&&!$$D){$L=1;while($L){$L++if$C[++$c]eq'[';$L--if$C[$c]eq']'}}if(/]/){$L=1;while($L){$L++if$C[--$c]eq']';$L--if$C[$c]eq'['}$c--}$c++}print pack'b*',$O

The script boofuck.pl is an interpreter for Boolfuck. The argument is a file name that contains a Boolfuck program. It reads STDIN and outputs to STDOUT.

Remarks:

  • I have ignored the last sentence of the description for operator ;, because I haven't understood it:

    If the end-of-file character has been input, outputs a zero to the bit under the pointer.

  • The script always reads STDIN, even if the boolfuck program does not contain a , operator.

Ungolfed:

# name conventions:
# "I" for input:
#         @I is array with "0" and "1" for the bits in STDIN
# "O" for output:
#         $O is output string with "O" and "1" for the output bits
# "C" for code:
#         @C is array of code byts
#         $c is code pointer
# "D" for data:
#         %D is "infinite" data band, hash is used to allow negative indexes
#         $d is data pointer
undef $/;                    # without input line separator <> reads the whole file.
open C, '<', pop;            # open program file, given as command line argument
@I = split //,             #/# split input bit string into array of (bit) characters
     unpack 'b*',            # convert input string into bit string with 0 and 1
     <>;                     # get STDIN
@C = split //,             #/# split program code string in byte array
     <C>;                    # get program code as string
while ($c < @C) {            # finished if the end of the program code is reached
    $_ = $C[$c];             # $_ contains operator
    $D = \$D{$d};            # $D is a reference to the data bit under the data pointer
# case '+':
    $$D = !$$D if /\+/;      # flip data bit value under the data pointer
# case ',':
    $$D = shift @I if /,/; #/# store input bit to data bit under the pointer
# case ';':
    $O .= $$D ? 1 : 0 if /;/;
                           #/# append current data bit to the output
# case '<':
    /</ && $d--;           #/# move data pointer to the left
# case '>':
    />/ && $d++;           #/# move data pointer to the right
# case '[':
    if (/\[/ && !$$D) {      # if current data bit is unset,
                             # jump to the matching ']'
        $L = 1;              # each '[' increments $L,
                             # each ']' decrements $L
        while ($L) {         # $L is zero in case of a matching ']'
            $L++ if $C[++$c] eq '[';
            $L-- if $C[$c]   eq ']'
        }
        # at the end of the outer loop, the code pointer is automatically increased
        # to get right after the matching ']'
    }
# case ']':
    if (/]/) {               # jump back to the matching '['
        $L = 1;
        while ($L) {
            $L++ if $C[--$c] eq ']';
            $L-- if $C[$c]   eq '['
        }
        $c--                 # at the end of the outer loop the code pointer
                             # is increased; therefore the code pointer is
                             # decreased to get right at the matching '['
    }
# else:
    # ignore other characters
# continue:
    $c++                     # increment code pointer
}
print pack'b*', $O           # convert output bits to bytes and print result

Examples:

  • "Hello World" example from the question

    perl boolfuck.pl helloworld.boolfuck </dev/null
    

    Result (with new line at the end):

    Hello, world!
    
  • Example that reverses the input from the Boolfuck website:

    >,>,>,>,>,>,>,>,<<<<<<<<
    >>>>>>>>>+<<<<<<<<+[>+]<[<]>>>>>>>>>[+<<<<<<<<[>]+<[+<]
    >>>>>>>>>
    >,>,>,>,>,>,>,>,<<<<<<<<
    >>>>>>>>>+<<<<<<<<+[>+]<[<]>>>>>>>>>]<[+<]
    <<<<<<<<<
    >>>>>>>>>+<<<<<<<<+[>+]<[<]>>>>>>>>>[+<<<<<<<<[>]+<[+<]
    >;>;>;>;>;>;>;>;<<<<<<<<
    <<<<<<<<<
    >>>>>>>>>+<<<<<<<<+[>+]<[<]>>>>>>>>>]<[+<]
    

    Running it:

    echo -ne "\nHello World" perl boolfuck.pl reverse.boolfuck
    

    Result (with new line at the end):

    dlroW olleH
    
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ I also don't understand the ;. \$\endgroup\$ – Justin May 19 '14 at 6:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.