149
\$\begingroup\$

Write the shortest program in your favourite language to interpret a brainfuck program. The program is read from a file. Input and output are standard input and standard output.

  1. Cell size: 8bit unsigned. Overflow is undefined.
  2. Array size: 30000 bytes (not circled)
  3. Bad commands are not part of the input
  4. Comments begin with # and extend to the end of line Comments are everything not in +-.,[]<>
  5. no EOF symbol

A very good test can be found here. It reads a number and then prints the prime numbers up to that number. To prevent link rot, here is a copy of the code:

compute prime numbers
to use type the max number then push Alt 1 0
===================================================================
======================== OUTPUT STRING ============================
===================================================================
>++++++++[<++++++++>-]<++++++++++++++++.[-]
>++++++++++[<++++++++++>-]<++++++++++++++.[-]
>++++++++++[<++++++++++>-]<+++++.[-]
>++++++++++[<++++++++++>-]<+++++++++.[-]
>++++++++++[<++++++++++>-]<+.[-]
>++++++++++[<++++++++++>-]<+++++++++++++++.[-]
>+++++[<+++++>-]<+++++++.[-]
>++++++++++[<++++++++++>-]<+++++++++++++++++.[-]
>++++++++++[<++++++++++>-]<++++++++++++.[-]
>+++++[<+++++>-]<+++++++.[-]
>++++++++++[<++++++++++>-]<++++++++++++++++.[-]
>++++++++++[<++++++++++>-]<+++++++++++.[-]
>+++++++[<+++++++>-]<+++++++++.[-]
>+++++[<+++++>-]<+++++++.[-]

===================================================================
======================== INPUT NUMBER  ============================
===================================================================
+                          cont=1
[
 -                         cont=0
 >,
 ======SUB10======
 ----------

 [                         not 10
  <+>                      cont=1
  =====SUB38======
  ----------
  ----------
  ----------
  --------

  >
  =====MUL10=======
  [>+>+<<-]>>[<<+>>-]<     dup

  >>>+++++++++
  [
   <<<
   [>+>+<<-]>>[<<+>>-]<    dup
   [<<+>>-]
   >>-
  ]
  <<<[-]<
  ======RMOVE1======
  <
  [>+<-]
 ]
 <
]
>>[<<+>>-]<<

===================================================================
======================= PROCESS NUMBER  ===========================
===================================================================

==== ==== ==== ====
numd numu teid teiu
==== ==== ==== ====

>+<-
[
 >+
 ======DUP======
 [>+>+<<-]>>[<<+>>-]<

 >+<--

 >>>>>>>>+<<<<<<<<   isprime=1

 [
  >+

  <-

  =====DUP3=====
  <[>>>+>+<<<<-]>>>>[<<<<+>>>>-]<<<

  =====DUP2=====
  >[>>+>+<<<-]>>>[<<<+>>>-]<<< <


  >>>


  ====DIVIDES=======
  [>+>+<<-]>>[<<+>>-]<   DUP i=div

  <<
  [
    >>>>>+               bool=1
    <<<
    [>+>+<<-]>>[<<+>>-]< DUP
    [>>[-]<<-]           IF i THEN bool=0
    >>
    [                    IF i=0
      <<<<
      [>+>+<<-]>>[<<+>>-]< i=div
      >>>
      -                  bool=0
    ]
    <<<
    -                    DEC i
    <<
    -
  ]

  +>>[<<[-]>>-]<<          
  >[-]<                  CLR div
  =====END DIVIDES====


  [>>>>>>[-]<<<<<<-]     if divides then isprime=0


  <<

  >>[-]>[-]<<<
 ]

 >>>>>>>>
 [
  -
  <<<<<<<[-]<<

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

  >>




  ===================================================================
  ======================== OUTPUT NUMBER  ===========================
  ===================================================================
  [>+<-]>

  [
   ======DUP======
   [>+>+<<-]>>[<<+>>-]<


   ======MOD10====
   >+++++++++<
   [
    >>>+<<              bool= 1
    [>+>[-]<<-]         bool= ten==0
    >[<+>-]             ten = tmp
    >[<<++++++++++>>-]  if ten=0 ten=10
    <<-                 dec ten     
    <-                  dec num
   ]
   +++++++++            num=9
   >[<->-]<             dec num by ten

   =======RROT======
      [>+<-]
   <  [>+<-]
   <  [>+<-]
   >>>[<<<+>>>-]
   <

   =======DIV10========
   >+++++++++<
   [
    >>>+<<                bool= 1
    [>+>[-]<<-]           bool= ten==0
    >[<+>-]               ten = tmp
    >[<<++++++++++>>>+<-] if ten=0 ten=10  inc div
    <<-                   dec ten     
    <-                    dec num
   ]
   >>>>[<<<<+>>>>-]<<<<   copy div to num
   >[-]<                  clear ten

   =======INC1=========
   <+>
  ]

  <
  [
   =======MOVER=========
   [>+<-]

   =======ADD48========
   +++++++[<+++++++>-]<->

   =======PUTC=======
   <.[-]>

   ======MOVEL2========
   >[<<+>>-]<

   <-
  ]

  >++++[<++++++++>-]<.[-]

  ===================================================================
  =========================== END FOR ===============================
  ===================================================================


  >>>>>>>
 ]
 <<<<<<<<



 >[-]<
  [-]
 <<-
]

======LF========

++++++++++.[-]
@

Example run:

$ python2 bf.py PRIME.BF 
Primes up to: 100
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 
\$\endgroup\$
27
  • 9
    \$\begingroup\$ You should clarify about 1) size of memory 2) is memory circled 4) maybe any other details \$\endgroup\$
    – Nakilon
    Jan 28, 2011 at 1:37
  • 3
    \$\begingroup\$ I wonder if there should be two categories: Those programs that use eval (or shell out to compile) -- and those that don't. \$\endgroup\$ Feb 15, 2011 at 7:52
  • 47
    \$\begingroup\$ I'd love to see someone answer this in brainfuck. \$\endgroup\$
    – Hannesh
    Mar 14, 2011 at 19:15
  • 8
    \$\begingroup\$ What does "no EOF symbol" mean? That the cell value remains unchanged when trying , on EOF? Or that it's up to us to choose a value when trying , on EOF? Or is EOF undefined behaviour altogether? \$\endgroup\$ Apr 1, 2016 at 14:07
  • 4
    \$\begingroup\$ Likewise, what should happen when someone tries to leave the 30k cells to either side? Should the tape head remain in place or is this undefined behaviour? \$\endgroup\$ Apr 1, 2016 at 14:09

78 Answers 78

1 2
3
2
\$\begingroup\$

JavaScript (ES6), 222 200 197 196 bytes

-19 bytes by stealing the idea of indexOfing from @GezaKerecsenyi's answer.

Takes BF code (b) and input (i) via currying, and returns the output.

b=>i=>eval(`m=Array(3e4).fill(k=p=0);o='';${[...b].map(c=>'m[p]++@m[p]--@p++@p--@while(m[p]){@}@m[p]=i.charCodeAt(k++)|0@o+=String.fromCharCode(m[p])'.split`@`['+-><[],.'.indexOf(c)]).join`;`};o`)

Try it online!

It works by generating a piece of valid JS code from the BF, then evals it. (If you strip away eval, you can see the generated code.)

Technical details

  • Tape length: 30000 cells
  • Tape left-hand-side: unusable
  • Tape wrap-around: no
  • Max value: 253-1 (JS MAX_SAFE_INTEGER)
  • Negative numbers: allowed
  • EOF: 0 (solution with -2 bytes possible by letting EOF corrupt the tape with a NaN)
\$\endgroup\$
2
\$\begingroup\$

Rattle, 234 bytes

\&[0]*199&99&\|!I[g0P4I~n[62P2g+s][60P2g-s][43f6+f5][45f6-f5][46f6,][91f6[0f0]]
[93f6[^0f1]][44g3P5I~nP2f5P5g+s]P4g+sg0I^[~q]g]0;P6g=+s[P4g+f2[91f3]g8[93f4[0f]]]0
;P6g=+s[P4g-f2[93f3]g8[91f4[0f]]]0;sg0I~ns8;P6g+s;P6g-s;r`g1l(~,\);g1P2I~

(without the line breaks)

Try it Online!

This is by far Rattle's most complicated program yet.

This takes Brainf*** code as the first line of input and input for the Brainf*** code as the second line of input. Note that Rattle expects the second line to exist even if there is no input for Brainf***.

Here's a similar example except instead of the classic Hello World!, I've modified it to take ! as input but otherwise still output the same thing.

Explanation

This program is a little lengthy to do a full explanation for but here's a much more human-readable version of the program:

\&[0]*199&99&\|!I

[
  g0 P4 I~n

  [62 g2 + s2]
  [60 g2 - s2]
  [43 g1 P2 I~ + r` g1 l(~,\)]
  [45 g1 P2 I~ - r` g1 l(~,\)]
  [46 g1 P2 I~ ,]
  [91 g1 P2 I~ [0 f0]]
  [93 g1 P2 I~ [^0 f1]]
  [44 g3 P5 I~ n r` g1 P2 l(~,\) g5 + s5]

  g4 + s4
  g0 I^ P4 [~q]
  P4g
]0

;g6 =+ s6 [g4 + s4 g0 P4 I~ n s8 [91 g6 + s6] g8 [93 g6 - s6 [0 f]]]0
;g7 =+ s7 [g4 - s4 g0 P4 I~ n s8 [93 g7 + s7] g8 [91 g7 - s7 [0 f]]]0

:(this line and below is just a comment)
data tape values:
0 - code
1 - code data tape
2 - code pointer
3 - input
4 - code command index
5 - input character index
6 - open loop counter
7 - close loop counter
8 - temp
\$\endgroup\$
2
\$\begingroup\$

nice-expr, 660 bytes

var f is func(str)none func(var C is str)none{var T is list[int]repeat(0,30001);var p is int;var B is map[int]int;var b is list[int];for var i is int0{var c is str C_i;if c="["then{set b+[i];}else if c="]"then{set B@b_-1is i;set B@i is b_-1;set b is b_0..-1;};set i+1;if i>=len(C)then{break;};};for var i is int0{var c is str C_i;if c=">"then{set p+1;}else if c="<"then{set p-1;}else if c="+"then{set T@p is(T_p)+1;}else if c="-"then{set T@p is(T_p)-1;}else if c="."then{print(char(T_p));}else if c=","then{set T@p is ord(inputchar());}else if c="["and(T_p)=0then{set i is B_i;}else if c="]"and(T_p)!=0then{set i is B_i;};set i+1;if i>=len(C)then{break;};};};

This is a function that takes takes in the brainfuck code as a string.

This certainly can be golfed down; half the code in the solution is only dedicated to pairing up brackets to each other.

Ungolfed Explanation

var interpret is func(str)none func(var code is str)none {
    // there are neither 8-bit, nor unsigned, types in nice-expr.
    // a list of ints will have to do.
    var tape is list[int] repeat(0,30000);
    var ptr is int 0; // start on the start of the tape.

    var brackets is map[int]int <||>; // keys and values are indexes of brackets.

    var bracketStack is list[int] []; // stack that holds left bracket indexes
    for var i is int 0 { // first pass: match up brackets
        var c is str code_i;
        if c = "[" then {
            set bracketStack + [i]; // push a left bracket
        } else if c = "]" then {
            // pop a left bracket
            var left is int bracketStack_-1;
            set bracketStack is bracketStack_0..-1;
            var right is int i;
            set brackets@left is right;
            set brackets@right is left;
        };
        set i + 1;
        if i >= len(code) then { break; };
    };

    for var i is int 0 {
        var c is str code_i;
        if c = ">" then {
            set ptr + 1;
        } else if c = "<" then {
            set ptr - 1;
        } else if c = "+" then {
            set tape@ptr is (tape_ptr) + 1;
        } else if c = "-" then {
            set tape@ptr is (tape_ptr) - 1;
        } else if c = "." then {
            print(char(tape_ptr));
        } else if c = "," then {
            set tape@ptr is ord(inputchar());
        } else if c = "[" and (tape_ptr) = 0 then {
            set i is brackets_i; // jump to the matching right bracket
        } else if c = "]" and (tape_ptr) != 0 then {
            set i is brackets_i; // jump to matching left bracket
        };

        set i + 1;
        if i >= len(code) then { break; };
    };
};
\$\endgroup\$
2
\$\begingroup\$

ASCII FALSE, 365 bytes

Takes Brainfuck program and input separated by $ ("end of Brainfuck"); very slow (replacing a cell is a linear time operation with bad constant factors; loops search for the matching bracket each time they are executed). Could be optimized by (1) doing peephole optimizations on most commands, most notably stripping loops, memorizing loop targets and compressing sequences of +/- into single instructions (2) using binary trees as the array representation, giving better O(log n) modification time (much more complex; requires managing binary trees, and basic GC if no memory is to be leaked).

EOF is all ones (255; it's unclear what "no EOF symbol" is supposed to mean). Overflow being undefined behavior is taken advantage of. The pointer not over/underflowing is taken advantage of as well.

Runs "hello world" correctly as well as the prime finder, though it is very inefficient (as expected). I recommend first stripping the prime finder of comments, then appending $<small number>:

>++++++++[<++++++++>-]<++++++++++++++++.[-]>++++++++++[<++++++++++>-]<++++++++++++++.[-]>++++++++++[<++++++++++>-]<+++++.[-]>++++++++++[<++++++++++>-]<+++++++++.[-]>++++++++++[<++++++++++>-]<+.[-]>++++++++++[<++++++++++>-]<+++++++++++++++.[-]>+++++[<+++++>-]<+++++++.[-]>++++++++++[<++++++++++>-]<+++++++++++++++++.[-]>++++++++++[<++++++++++>-]<++++++++++++.[-]>+++++[<+++++>-]<+++++++.[-]>++++++++++[<++++++++++>-]<++++++++++++++++.[-]>++++++++++[<++++++++++>-]<+++++++++++.[-]>+++++++[<+++++++>-]<+++++++++.[-]>+++++[<+++++>-]<+++++++.[-]+[->,----------[<+>-------------------------------------->[>+>+<<-]>>[<<+>>-]<>>>+++++++++[<<<[>+>+<<-]>>[<<+>>-]<[<<+>>-]>>-]<<<[-]<<[>+<-]]<]>>[<<+>>-]<<>+<-[>+[>+>+<<-]>>[<<+>>-]<>+<-->>>>>>>>+<<<<<<<<[>+<-<[>>>+>+<<<<-]>>>>[<<<<+>>>>-]<<<>[>>+>+<<<-]>>>[<<<+>>>-]<<<<>>>[>+>+<<-]>>[<<+>>-]<<<[>>>>>+<<<[>+>+<<-]>>[<<+>>-]<[>>[-]<<-]>>[<<<<[>+>+<<-]>>[<<+>>-]<>>>-]<<<-<<-]+>>[<<[-]>>-]<<>[-]<[>>>>>>[-]<<<<<<-]<<>>[-]>[-]<<<]>>>>>>>>[-<<<<<<<[-]<<[>>+>+<<<-]>>>[<<<+>>>-]<<<>>[>+<-]>[[>+>+<<-]>>[<<+>>-]<>+++++++++<[>>>+<<[>+>[-]<<-]>[<+>-]>[<<++++++++++>>-]<<-<-]+++++++++>[<->-]<[>+<-]<[>+<-]<[>+<-]>>>[<<<+>>>-]<>+++++++++<[>>>+<<[>+>[-]<<-]>[<+>-]>[<<++++++++++>>>+<-]<<-<-]>>>>[<<<<+>>>>-]<<<<>[-]<<+>]<[[>+<-]+++++++[<+++++++>-]<-><.[-]>>[<<+>>-]<<-]>++++[<++++++++>-]<.[-]>>>>>>>]<<<<<<<<>[-]<[-]<<-]++++++++++.[-]
$20

This runs in about 1s for me, producing

Primes up to: 2 3 5 7 11 13 17 19

(Since input is given after the program in stdin, the number "up to" which primes are printed is of course missing from the output; this could be addressed by outputting all read characters (insert $, after ^), if desired.)

Note: This is ASCII FALSE, using O instead of ø (if ø were to be used instead, it would be a couple bytes longer) and B instead of ß (buffering is not relevant here however). Interpreters for ASCII FALSE can be found here.

Golfed

[n;0=$[%%x;0~]?~[$0=$[% % n;1-n:q;!0 0~]?~[$1&\2/\ $[% q;!2*1|0~]?~[q;!2*]?]?]?]q:0c:[^$'$=~][c;1+c:]#%30000$t:[1-$][0\]#0i:0p:[t;c;+i;-1-O]o:[x:p;n:q;!]s:[o;!$'[=[b;1+b:]?']=[b;1-b:]?]j:[c;i;>][o;!k:k;'.=[p;O,]?k;',=[^255&s;!]?k;'>=[p;1+p:]?k;'<=[p;1-p:]?k;'+=[p;O1+s;!]?k;'-=[p;O1-s;!]?k;'[=[p;O0=[1b:[b;][i;1+i:j;!]#]?]?k;']=[p;O[1_b:[b;][i;1-i:j;!]#]?]?i;1+i:]#

There are most probably quite a few more easy golfs possible.

Ungolfed

The core function is q ("shove/splice"), which allows fully using the stack like an array by remembering items on the call stack, then mutating the stack by replacing an element, and then restoring the elements remembered on the call stack. Once we can use the stack as an array, the rest is straightforward.

{
    shove/splice (q):
    pop n elements, remembering them on the call stack,
    then mutate the stack, dropping an item and replacing it with x,
    then restore the popped elements

    invocation: 101x: 42n: q;!
}
[
    n;0=
    $[% %x; 0~]?
    ~[
        $0=
        $[
            % {kill cond}
            % {kill dup'd zero on stack}
            n; 1- n:
            q;!
            0 {this is to be left on the stack}
            0~
        ]?
        ~[
            $ 1& {extract lowest bit}
            \ 2/ \ {>> 1 thing on stack}
            $[
                % q;! 2* 1| 0~
            ]?
            ~[
                q;! 2*
            ]?
        ]?
    ]?
]q:

0c: {# commands}
[^$ '$=~][c;1+c:]# {loop until `$` is encountered, leaves chars on stack}
% {drop '$}

30000$t:[1-$][0\]# {leave 30k 0's on the stack (note: final iteration will leave zeroed counter itself on stack)}

0i: {instruction pointer}
0p: {data pointer (0-based)}
[t;c;+ {depth of stack} i;- 1- O]o: {get (o)p}

[x: p;n: q;!]s: {set item}

[
    o;!
    $'[=[b;1+b:]?
    ']=[b;1-b:]?
]j: {count bracket balance}

[c;i;>][
    o;! k:
    k;'.=[p;O ,]?
    k;',=[^ 255& s;!]?
    k;'>=[
        p;1+p:
    ]?
    k;'<=[
        p;1-p:
    ]?
    k;'+=[p;O 1+ s;!]?
    k;'-=[p;O 1- s;!]?
    k;'[=[
        p;O 0=[
            1b: {balance}
            [b;][
                i;1+i:
                j;!
            ]#
        ]?
    ]?
    k;']=[
        p;O [
            {analogeous with two small changes}
            1_ b: {balance}
            [b;][
                i;1-i:
                j;!
            ]#
        ]?
    ]?
    i;1+i:
]#
```
\$\endgroup\$
2
\$\begingroup\$

C (gcc) Linux AArch64, 483 461 449 439 424 413 bytes

#define S(x)"(\0@9\b\5\0"#x"(\0\0\71":
*T=" \0\1J\b\xfc\0\21!@\0\xd4",c,h,*mmap(),*wcpcpy();d[7500];(*p)();*j(int*a){int*t=a,*n,q=0;for(;read(h,&c,!q);)t=c==91?n=j(t+2),*t++='9@\0(',*t=n-t<<5|8|90<<25,n:c==93?q=*t=a-t-2&33554431|22<<24,t+1:wcpcpy(t,c-60?c-62?c-45?c-43?c-46?c-44?t:T:T+1:S(\21)S(Q)"!\4\0\x91":"!\4\0\xd1");return t;}main(P,g)int**g;{*j(p=mmap(0,1<<20,6,34,h=open(g[1],0),0))=3596551104;p(1,d,1);}

This is a JIT that compiles BF code into AArch64 machine language at runtime. This performs a straight translation so commonly occurring sequences such as >>>, <<<, +++ and --- aren't coalesced into faster instructions.

This is a port of the "JIT" for x86_64 https://codegolf.stackexchange.com/a/178298/52904

Less golfed version:

#include<wchar.h>
// size of data area
c,*mmap();d[7500];h;(*p)();
*j(int*a){
  int*t=a,*n,q=0;
  for(;read(h,&c,!q);){
    t=c==91?
      // ldrb w8, [x1]
      // cbz w8, n-t
      n=j(t+2),
      *t++=0x39400028,
      *t=n-t<<5|8|180<<24,
      n
    :c==93?
      // b a-t-2
      q=a-t-2,
      *t=q&0x1ffffff|22<<24,
      t+1
    :
      wcpcpy(t,c-'<'?
                 c-'>'?
                   c-'-'?
                     c-'+'?
                       c-'.'?
                         c-','?
                           L""
                         :
                           // eor w0, w1, w1
                           // add w8, w0, #0x3f ; read(0,buf,1)
                           // svc #0x201        ; Linux is not picky about the argument
                           L"\x4a010020\x1100fc08\xd4004021"
                       :
                         // add w8, w0, #0x3f ; write(1,buf,1)
                         // svc #0x201        ; w0 was 1 from last syscall
                         L"\x1100fc08\xd4004021"
                     :
                       // ldrb w8, [x1]
                       // add w8,w8, 1
                       // strb w8, [x1]
                       L"\x39400028\x11000508\x39000028"
                   :
                     // ldrb w8, [x1]
                     // sub w8,w8, 1
                     // strb w8, [x1]
                     L"\x39400028\x51000508\x39000028"
                 :
                   // add x1, x1, 1
                   L"\x91000421"
               :
                 // sub x1, x1, 1
                 L"\xd1000421"
      );
  }
  return t;
}
main(P,g)int**g;{
  // allocate text (executable) memory and mark as executable
  p=mmap(0,1<<20,6,34,h=open(g[1],0),0);
  // run JIT, exit gracefully
  *j(p)=0xd65f03c0;
  // set %x2=1 and call code like a function
  p(1,d,1);
}
\$\endgroup\$
1
\$\begingroup\$

Lua (to long)

I made some Lua implementation, but I can't get the bracket stuff right. Here it is anyway:

-- >    increment the data pointer (to point to the next cell to the right).
-- <    decrement the data pointer (to point to the next cell to the left).
-- +    increment (increase by one) the byte at the data pointer.
-- -    decrement (decrease by one) the byte at the data pointer.
-- .    output a character, the ASCII value of which being the byte at the data pointer.
-- ,    accept one byte of input, storing its value in the byte at the data pointer.
-- [    if the byte at the data pointer is zero, then instead of moving the instruction pointer forward to the next command, jump it forward to the
--      command after the matching ] command*.
-- ]    if the byte at the data pointer is nonzero, then instead of moving the instruction pointer forward to the next command, jump it back to the
--      command after the matching [ command*.
s=setmetatable({0},{__index=function() return 0 end})

i=1 -- index array
j=1 -- index input
l=loadstring
t="><+-.,[]"
o=0
fh=arg[1] and io.open(arg[1]) or io.stdin
I=fh:read"*a":gsub("[^><%+%-%.,%[%]]","")
fh:close()
print(I)
for k=1,#I do io.write(k%5==1 and"+"or"-") end
io.write"\n"
for k=1,math.ceil(#I/5) do local n=5*(k-1)+1 local s=(" "):rep(4-math.floor(math.log10(n))) io.write(n,s) end
io.write"\n"
dbg=true
f={
"i=i+1 ",   -- array index ++
"i=i-1 ",   -- array index --
"s[i]=(s[i]+1)%256 ",   -- byte + 1
"s[i]=(s[i]-1)%256 ",   -- byte - 1
"io.write(string.char(s[i])) ", -- put byte
"local c=io.read(1):byte()s[i]=c==10 and s[i] or c",        -- read byte "Newline required!"
[=[if s[i]==0 then
    o=0
    repeat
        if dbg then print(j,"Forward!",o,b) end
        b=I:sub(j,j):match'[%[%]]'
        o= b=='['and o+1 or b==']' and o-1 or o;
        j=j+1
    until b==']' and o == 0
end
]=],    -- jump to matching ]
[=[
if s[i]~=0 then
    o=0
    count=0
    repeat 
        if dbg then print(j,"Backwards",o,b) end
        b=I:sub(j,j):match"[%[%]]"
        o= b=='['and o-1 or b==']' and o+1 or o;
        j=j-1
    until b=='[' and o == 0
end
]=],    -- jump to matching ]
}
for k,v in ipairs(f) do f[t:sub(k,k)],e=l(v) if e then error(e)end end
function run()
j=1
while j<=#I do
    f[I:sub(j,j)]()
    j=j+1
end
end
res,err = pcall(run)
if not res then
    print('error=',err)
    print('Dumping state')
    print('','stack')
    for k,v in pairs(s) do print("",k,v) end
end
if debug then
    print("stack")
    for k,v in pairs(s) do print(k,v) end
end

It doesn't pass the prime test, but acts nicely with Hello World and all echo and reverse examples I tried. So if anyone sees the bug, feel free to catch it.

\$\endgroup\$
1
\$\begingroup\$

Smalltalk, Squeak 4.x flavour 414 chars

Here is an interpreter which works exclusively with streams and block closures:

b:=[:c :i :o :n |
| v |
v := 1 to: n.
v := (v collect: [:x| | t |
    t := 0.
    Dictionary newFrom: {
        $+ -> [t:=t+1\\256].
        $- -> [t:=t-1\\256].
        $. -> [o nextPut:t].
        $, -> [t:=i next].
        $< -> [v back].
        $> -> [v next].
        $[ -> [t=0 and: [
            [c next=$[
                ifTrue: [(v peek at: $[) value].
             c peek=$]] whileFalse.
            c next]].
        $] -> [t=0 or: [c back.
            [c back=$]
                ifTrue: [(v peek at: c next) value. c back;back].
             c peek=$[] whileFalse.
            c next]].
        }]) readStream.
[c atEnd] whileFalse: [(v peek at: c next ifAbsent: [[]]) value]]
  • c is a readStream on code
  • i is a readStream on input (a ByteArray)
  • o is a writeStream on output (a ByteArray)
  • v is a readStream on interpreters (an Array)
  • n is number of cells

For each cell, we create an interpreter - that is a Dictionary which associate a Block to each BF command (a Character).
Those blocks close over a value t, initialized at zero.
The jump instructions are implemented recursively.
The pointers (code and data) are hidden in streams state.

To use the interpreter, we just have to feed this block with proper streams:

c := 'http://esoteric.sange.fi/brainfuck/bf-source/prog/PRIME.BF' asUrl retrieveContents contents readStream.
i := '15\' withCRs withUnixLineEndings asByteArray readStream.
o := #[] writeStream.
n := 30000.
b valueWithArguments: {c.i.o.n}.
^'',o contents

The interpreter can be golfed to 414 chars, using as:Dictionary which is shorter and by removing overflow and underflow protections (the cell value is then unbound).

b:=[:c :i :o :n||v|v:=1to:n.v:=(v collect:[:x||t|t:=0.{$+->[t:=t+1].$-->[t:=t-1].$.->[o nextPut:t].$,->[t:=i next].$<->[v back].$>->[v next].$[->[t=0and:[[c next=$[ifTrue:[(v peek at:$[)value].c peek=$]]whileFalse.c next]].$]->[t=0or:[c back.[c back=$]ifTrue:[(v peek at:c next)value.c back;back].c peek=$[]whileFalse.c next]]}as:Dictionary])readStream.[c atEnd]whileFalse:[(v peek at:c next ifAbsent:[[]])value]].
\$\endgroup\$
1
\$\begingroup\$

C: 317 characters (reads from a file)

#include <stdio.h>
char t[30000],*p=t,b[30000],c;void r(char*a){while((c=*a++)&&c-93){p+=c==62;p-=c==60;*p+=c==43;*p-=c==45;c^46||putchar(*p);c^44||(*p=getchar());if(c==91){while(*p)r(a);c=1;while(c+=(*a==91)-(*a++==93));}}}int main(int n,char**a){FILE*f;f=fopen(a[1],"r");fread(b,1,30000,f);fclose(f);r(b);return 0;}

This is my brainfuck interpreter that I wrote for a couple of months ago, it's quite a bit longer than it needs to be, but that is because I didn't focus on size when I wrote it, I focused on readability (just the fact that it compiles without error and even includes a library suggest that it is heavily shrinkable).

And expanded:

#include <stdio.h>
char t[30000],*p=t,b[30000],c;
void r(char*a){
    while((c=*a++)&&c-93){
        p+=c==62;
        p-=c==60;
        *p+=c==43;
        *p-=c==45;
        c^46||putchar(*p);
        c^44||(*p=getchar());
        if(c==91){
            while(*p)r(a);
            c=1;
            while(c+=(*a==91)-(*a++==93));
        }
    }
}
int main(int n,char**a){
    FILE*f;
    f=fopen(a[1],"r");
    fread(b,1,30000,f);
    fclose(f);
    r(b);
    return 0;
}

I might return with an actually golfed version.

\$\endgroup\$
1
\$\begingroup\$

LiveScript evaling JavaScript: 263

Note that this is currently untested.

p='process.std';g=p+'in.read';f='function(x){return';eval "eval('var i=0,m=[#{[0]*3e4*\,}];'+#g().map(#f'[]+-<>,.'.indexOf(x)).filter(#f~-x).map(#f['#{"while(8){,},i++,i--,8++,8--,#{p}out.write(String.fromCharCode(8)),#g(1)"/','*"','"/'8'*'m[i]'}'][x]).join(''))"

Ungolfed:

p='process.std'
g=p+'in.read'
f='function(x){return'
eval """
  eval('
      var i = 0,
          m=[#{[0]*3e4*\,}];' +
    #{g}()
      .map(#{f} '[]+-<>,.'.indexOf(x))
      .filter(#{f} ~-x)
      .map(#{f} ['#{
        "while( 8 ){ 0
         } 0
         i++ 0
         i-- 0
         8++ 0
         8-- 0
         #{p}out.write(String.fromCharCode( 8 )) 0
         #{g}(1)" / '0' * "','" / '8' * 'm[i]'
       }'][x])
       .join(''))
"""
\$\endgroup\$
1
\$\begingroup\$

Binary Lambda Calculus 104 bytes (829 bits)

I didn't come up with this solution. Go credit whoever put it on wikipedia. However it is amazing.

( λ 11 ) ( λ ( λ λ λ 1 ( λ ( λ 2111 ( λ λ 133 ( λ λ 1 ( λ λ ( λ 7 ( 1 ( 3 ( λ λ λ λ λ 10 ̲ ( 1 ( λ 6143 ) ) ( λ 15 ( 65432 ) ) ) ( λ λ 2 ( ( λ 11 ) ( λ λ λ 2 ( λ λ λ 662 ( λ λ 6 ( λ 1 ( 26 ) 3 ) ( 15 ̲ ( 51 ( λ 1 ) ) ( 5 ( λ 1 ) 1 ) ) ) ) ( 12 ( λ λ λ 312 ) ) ) 1 ( λ λ 2 ) ) ) ) ) ( 3 ( 1 ( λ λ λ λ 9 ( 1 ( λ 51 ( λ 154 ) ) ) ( 24 ( λ 142 ) ) ) ) ( 5 ( 11 ̲ ( λ 1 ) ) ( 12 ̲ ( λ 2 ( ( λ 11 ) ( λ λ λ 1 ( ( λ 11 ) ( λ λ λ 2 ( 1 ( 33 ) ) ( λ 8 ( 771 ) ) ) ) 21 ) ) ) ) ) ) ) ( λ 12 ̲ ( λ 12 ̲ ( λ 3 ( 21 ) ) ) ) ) ) ) ) ( λ λ 1 ) ) ) ( 11 ) ) ( λ ( λ 11 ) ( λ λ 1 ( ( λ 1 ( 1 ( 1 ( λ λ 1 ( λ λ 2 ) 2 ) ) ) ) ( λ λ 2 ( 21 ) ) ( λ λ 1 ) ) ( 22 ) ) ( 1 ( λ λ λ λ λ λ 1 ) ) 1)

\$\endgroup\$
1
  • 1
    \$\begingroup\$ I'm not sure that this actually fulfills the criteria – it doesn't handle non-brainfuck-syntax as comments, and it has an unbounded tape instead of the bounded one required by the question. \$\endgroup\$ Nov 29, 2015 at 10:15
1
\$\begingroup\$

SmileBASIC, 258 bytes

C=0DEF B S,K
DIM M[3E4]FOR I=0TO LEN(S)-1C=ASC(S[I])N=M[P]ON!F GOTO@C?CHR$(N)*(C==46);
O=C==91F=!N*O
K=K+CHR$(I)*O*!F
IF C==93THEN I=ASC(POP(K))-1
M[P]=N-N(42)P=P+N(59)IF C==44THEN M[P]=ASC(SHIFT(K))@C:F=F-N(90)
NEXT
END
DEF N(L)RETURN(C-L-2)*(C<L&&C<L+4)END

Call the function as B code,input

\$\endgroup\$
1
\$\begingroup\$

Python 3, 306 bytes (no eval)

from sys import*
s=open(argv[1]).read()
d=[0]*30000
i=p=a=0
k=[]
j=k+d
for o in s:
 if o==']':j[a]=k.pop();j[j[a]]=a
 k+=[a]*(o=='[');a+=1
while i<a:x,r='[]<>,.+-'.find(s[i]),d[p];d[p],p=(r+(x==6)-(x>6))%256if 4!=x else ord(stdin.read(1)),p+(x==3)-(x==2);i=j[i] if x==(r>0)else 1+i;print(end=chr(r)*(5==x))

Outputs null (0x00) characters though, and times out on prime example but should theoretically finish.
Can still be improved a bit.

\$\endgroup\$
1
\$\begingroup\$

Go, 377 bytes

I just had to Golf this. Straightforward implementation; leverages constraints (no overflows, no bad instructions), prime finder works as expected. Takes path to Brainfuck program as first argument and input over stdin.

package main
import."os"
func main(){
var t[30000]uint8
d,i,s:=0,0,[]byte{0}
c,_:=ReadFile(Args[1])
for;i<len(c);i++{m:=func(j int){b:=j
for b!=0{i+=j
switch c[i]{case'[':b++
case']':b--}}}
switch c[i]{case',':Stdin.Read(s);t[d]=s[0]
case'.':s[0]=t[d];Stdout.Write(s)
case'<':d--
case'>':d++
case'+':t[d]++
case'-':t[d]--
case '[':if t[d]==0{m(1)}
case ']':if t[d]!=0{m(-1)}}}}
\$\endgroup\$
1
\$\begingroup\$

Lua, 353 bytes

Doesn't beat the other working Lua solution which transpiles the entire source to Lua, then runs that rather than doing the mish-mash this one does; very inefficient due to the use of heavy pattern matching for finding matching brackets concisely.

s=io.open(...):read"*a"f="if(d[p]or 0)%s0 then i=%s end"d={}p=1 i=1 while#s>i do load(({[43]="d[p]=(d[p]or 0)+1",[45]="d[p]=(d[p]or 0)-1",[60]="p=p-1",[62]="p=p+1",[46]="io.write(string.char(d[p]or 0))",[44]="d[p]=io.read(1):byte()",[91]=f:format("==","s:find('^%b[]()',i)-1"),[93]=f:format(">","s:sub(1,i):find('()%b[]$')")})[s:byte(i)]or"")()i=i+1 end

Or with some formatting:

s=io.open(...):read"*a"
f="if(d[p]or 0)%s0 then i=%s end"
g=""d={}p=1
i=1
while#s>i do
    load(({
        [43]="d[p]=(d[p]or 0)+1",
        [45]="d[p]=(d[p]or 0)-1",
        [60]="p=p-1",
        [62]="p=p+1",
        [46]="io.write(string.char(d[p]or 0))",
        [44]="d[p]=io.read(1):byte()",
        [91]=f:format("==","s:find('^%b[]()',i)-1"),
        [93]=f:format(">","s:sub(1,i):find('()%b[]$')")
    })[s:byte(i)]or"")()i=i+1
end
\$\endgroup\$
1
\$\begingroup\$

Atto-8*, 0 bytes

*with brainfuck frontend

Unfortunately couldn't manage to golf off additional bytes. Open to suggestions if anyone has pointers.

Explanation

The Atto-8 microprocessor, when built with its brainfuck frontend, begins executing ASCII-encoded brainfuck directly from RAM, on bare metal. The microprocessor's machine code is brainfuck source code, and so no interpreter is required.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ Welcome to Code Golf! Atto-8 looks very cool, thanks for sharing it on this site. I think you would have to change the header of this post to "Atto-8 + BF Frontend, 0 bytes". I'd be interested in seeing some golf submissions written for the Atto-8, maybe in some sort of assembly. \$\endgroup\$
    – noodle man
    Nov 7, 2023 at 20:58
1
\$\begingroup\$

Julia 1.7, 193 bytes

!x="let a=fill(0,8^5),i=1
"*replace(x*"]",(["><+-.,[]"...].=>[["i" "a[i]"].*["+=1";"-=1"]...
"print('\0'+a[i])"
"a[i:i]=read(stdin,1)"
"while a[i]>0"
"end"].*";")...,r"."s=>"")|>Meta.parse|>eval

Attempt This Online!

Julia 1.7 is needed for replace with multiple patterns

ungolfed code:

!x="let a=fill(0,8^5),i=1
"*replace(x*"]",	# add `end` to close the `let` block
'>' => "i+=1;",
'<' => "i-=1;",
'+' => "a[i]+=1;",
'-' => "a[i]-=1;",
'.' => "print('\0'+a[i]);",
',' => "a[i:i]=read(stdin,1);",
'[' => "while a[i]>0;",
']' => "end;",
r"."s => ""		# remove all other characters
)|>Meta.parse|>eval

Attempt This Online!

This function takes the program as parameter.
Program with the stricter IO (as a file given as argument): 206 bytes

\$\endgroup\$
0
\$\begingroup\$

JavaScript - Partial Solution (241 235)

Does not read from file - does not manage PRIMES.BF, but works for Hello World!

// not included in 235 count, the hello world code from wikipedia
var p="++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++.>+.+++++++..+++.>++.<<+++++++++++++++.>.+++.------.--------.>+.>.",

// partial solution - dies on primes
a=[0,0,0,0,0],b=0
eval(p.replace(/[^\][.,+><-]/g,'').replace(/(.)/g,function(e){return "0while(a[b]){0}0console.log(String.fromCharCode(a[b]))0a[b]=prompt()0++a[b]0--a[b]0++b0--b".split(0)[" [].,+-><".search(new RegExp("\\"+e))]+";"}))

Just copy and paste it into javascript console to see it in action. Works in node.js, or broswer.

I was hoping to get PRIMES.BF to work in node.js, but not been able to emulate STDIN in a synchronous way yet.


With comments

// should read from file - easy with node.js
// this is the `Hello World! ` program from wikipedia
var p="++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++.>+.+++++++..+++.>++.<<+++++++++++++++.>.+++.------.--------.>+.>.",

// declare a and b. If a needs to be longer, can use:
//     a=[];for(0;a.length<30000;a.push(0))b=0
a=[0,0,0,0,0],b=0

// evaluate
eval(
  // the brainfuck code
  p
  // replacing all the non brainfuck commands with nothing 
  .replace(/[^\][.,+><-]/g,'')
  // replacing all commands (captured in parenthesis) with callback
  .replace(/(.)/g,function(e){
     // return swapped commands
     return "0while(a[b]){0}0console.log(String.fromCharCode(a[b]))0a[b]=prompt()0++a[b]0--a[b]0++b0--b"
     // split into array on the 0 (used as seperator - shorter than "|" when
     // called in .split(0) function)
     .split(0)[
       // matching brainfuck commands
       " [].,+-><"
       // searched with escaped, captured command
       .search(new RegExp("\\"+e))
       // add a semicolon to all statements - extra semicolons do not interfere
       // with execution of javascript
     ]+";"
  })
)
\$\endgroup\$
0
\$\begingroup\$

Simplex v.0.5, 103 bytes

br{j'>=?[v'R;Ru]'<=?[v'L;Ru]'+=?[v'I;Ru]'-=?[v'M;Ru]'.=?[v's;Ru]',=?[v'G;Ru]'[=?[v'{;Ru]']=?[v'};Ru]LL}
b                     ~~ Takes a string input (BF prgm)
 r                    ~~ Reverses the string (pointer is at end)
  {               LL} ~~ Loop until empty cell is found
   j                  ~~ Inserts an empty cell at pointer
    '>                ~~ Sets empty cell to character (>) 
      =               ~~ Sets cell to 1 if > is the current character
       ?[      ]      ~~ Evaluate inside if cell is 1
         v    u       ~~ Goes down, then up
          'R          ~~ Puts the character (R) to the byte
            ;         ~~ Adds the current cell to the outer program
             R        ~~ Goes right (frees up next cell)
    '< =? [v'L;Ru]    ~~ …etc
    '+ =? [v'I;Ru]
    '- =? [v'M;Ru]
    '. =? [v's;Ru]
    ', =? [v'G;Ru]
    '[ =? [v'{;Ru]
    '] =? [v'};Ru]

I used this program to prove that Simplex is Turing-complete, it being reducible to a Turing-complete language. It's simple enough; after evaluation of this program, a second program is evaluated, which contains the BF "transcript". Yeah, it really just compiled BF to Simplex. But hey! I think this is the shortest answer thus posted.

(Note that I implemented a theoretically infinite (unbound) version, as Simplex is thus.)

\$\endgroup\$
3
  • \$\begingroup\$ Is this still accurate? \$\endgroup\$ Feb 28, 2016 at 1:29
  • \$\begingroup\$ @VoteToClose No, I have not yet implemented some of the commands found in this program. \$\endgroup\$ Feb 28, 2016 at 1:31
  • 1
    \$\begingroup\$ ‪:c crosses fingers for Simplex implementation \$\endgroup\$ Feb 28, 2016 at 1:43
1 2
3

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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