126
\$\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
  • 7
    \$\begingroup\$ You should clarify about 1) size of memory 2) is memory circled 4) maybe any other details \$\endgroup\$
    – Nakilon
    Jan 28 '11 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 '11 at 7:52
  • 43
    \$\begingroup\$ I'd love to see someone answer this in brainfuck. \$\endgroup\$
    – Hannesh
    Mar 14 '11 at 19:15
  • 6
    \$\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 '16 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 '16 at 14:09

63 Answers 63

1 2
3
1
\$\begingroup\$

ARM Thumb-2 Machine code (Linux), 116 bytes

Hexdump (little endian)

9802 2705 df00 f44f 3280 ebad 0d42 4669
2703 df00 466b 1889 2201 cb20 b355 2001
2d3e bf08 3101 2d3c bf08 3901 780e 2d5b
d014 2d5d bf04 bc08 3b04 2d2b bf08 3601
2d2d bf08 3e01 700e 2d2e d101 2704 df00
2d2c d1e2 2000 2703 df00 e7de b10e b408
e7db cb20 2d5d d101 3801 d0d6 2d5b bf08
3001 e7f6

Commented assembly

        .syntax unified
        .arch armv6t2
        .thumb
        // The BF program must be saved in UTF-32LE, not ASCII. Use iconv if you have to.
        .equ BUFSIZ, 65536 // should be movable

        .thumb_func
        .globl _start
_start:
        // Open the file
        // file = open(argv[1], O_RDONLY /* = 0 */)
        ldr     r0, [sp, #8] // argv[1] is at sp + 8
        movs    r7, #5 // open
        svc     #0

        // Create a buffer for the file and the tape (todo: improve reg shuffling)
        mov     r2, #BUFSIZ
        sub.w   sp, sp, r2, lsl #1 // doubled
        // Read into the file
        // read(file, insn_ptr, BUFSIZ)
        mov     r1, sp
        movs    r7, #3 // read
        svc     #0
        // insn_ptr = sp
        mov     r3, sp
        // tape_ptr = &insn_ptr[BUFSIZ]
        adds    r1, r2
        movs    r2, #1 // 1 byte for read/write syscalls

        // ----- Interpreter loop ------
.Linterpret:
        // insn = *insn_ptr++
        ldm     r3!, {r5}
        // Null terminator
        cbz     r5, .Lexit
        movs    r0, #1 // stdout, also loop depth
        // > -> right
        cmp     r5, #'>'
        it      eq
        addeq   r1, #1
        // < -> left
        cmp     r5, #'<'
        it      eq
        subeq   r1, #1
        // Load
        ldrb    r6, [r1]
        // [ -> start
        cmp     r5, #'['
        beq     .Ldo_loop // outlined
        // ] -> end
        cmp     r5, #']'
        // Pop insn_ptr
        itt     eq
        popeq   {r3}
        subeq   r3, #4
        // + -> inc
        cmp     r5, #'+'
        it      eq
        addeq   r6, #1
        // - -> dec
        cmp     r5, #'-'
        it      eq
        subeq   r6, #1
        // Store
        strb    r6, [r1]
        // . -> print
        cmp     r5, #'.'
        bne     .Lnot_dot
.Ldot:
        // write(STDOUT_FILENO, tape_ptr, 1)
        // r0 is already 1 for stdout.
        movs    r7, #4 // write
        svc     #0
.Lnot_dot:
        // , -> read
        cmp     r5, #','
        bne     .Linterpret
.Lcomma:
        // read(STDIN_FILENO, tape_ptr, 1)
        movs    r0, #0 // stdin
        movs    r7, #3 // read
        svc     #0
        // Loop
        b       .Linterpret

        // loop handling
.Ldo_loop:
        // depth = 1; (from above)
        // if (tape_val != 0)
        cbz     r6, .Ldo_loop.scan
.Ldo_loop.no_jump:
        // Push insn_ptr to the call stack and continue
        push    {r3}
        b       .Linterpret
        // else
        //   scan for the closing brace and jump.
.Ldo_loop.scan:
        ldm     r3!, {r5}
        // ] -> --depth
        cmp     r5, #']'
        bne     .Ldo_loop.not_rb
.Ldo_loop.rb:
        // if (--depth == 0) break;
        subs    r0, #1
        beq     .Linterpret
.Ldo_loop.not_rb:
        // [ -> ++depth
        cmp     r5, #'['
        it      eq
        addeq   r0, #1
        b       .Ldo_loop.scan
.Lexit:
        // segfault like a true chad :D

Notes

  • Compiled as clang --target= arm-linux-gnueabi -nostdlib -static bfarm.s -o bfarm.
  • The filename of the BF file is passed as the first command line argument.
  • The BF file is encoded in UTF-32LE (not ASCII). (This saves 4 bytes thanks to ldm). The input and output is still through 8-bit bytes though.
    • iconv -f UTF-8 -t UTF-32LE prog.bf > prog.bf32 if you need to convert.
  • The BF file must be shorter than 65536 bytes (16384 codepoints) long and not contain null codepoints. The size can be configured, though, with some tweaking.
  • You get a whopping 65536 u8 cells, non-wrapping
  • Expects the default Linux ELF startup state.
    • argv is an array at sp + 4
    • The unused stack memory is clear
    • All registers but sp and pc are zeroed
  • Segfaults to exit by leaving the end of the .text section like a true gigachad.
  • EOF leaves the cell unchanged.
\$\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 '16 at 1:29
  • \$\begingroup\$ @VoteToClose No, I have not yet implemented some of the commands found in this program. \$\endgroup\$ Feb 28 '16 at 1:31
  • 1
    \$\begingroup\$ ‪:c crosses fingers for Simplex implementation \$\endgroup\$ Feb 28 '16 at 1:43
1 2
3

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.