Brainfuck

October 4, 2011

A commented version of the hello world program from the previous page is given below:

+++++ +++++             initialize counter (cell #0) to 10
[                       use loop to set the next four cells to 70/100/30/10
    > +++++ ++              add  7 to cell #1
    > +++++ +++++           add 10 to cell #2 
    > +++                   add  3 to cell #3
    > +                     add  1 to cell #4
    <<<< -                  decrement counter (cell #0)
]                   
> ++ .                  print 'H'
> + .                   print 'e'
+++++ ++ .              print 'l'
.                       print 'l'
+++ .                   print 'o'
> ++ .                  print ' '
<< +++++ +++++ +++++ .  print 'W'
> .                     print 'o'
+++ .                   print 'r'
----- - .               print 'l'
----- --- .             print 'd'
> + .                   print '!'
> .                     print '\n'

That program comes from the Wikipedia page on brainfuck, as does the rot13 program below; beware that, depending on your operating system and compiler, there may be input buffering issues when running rot13:

-,+[                         Read first character and start outer character reading loop
    -[                       Skip forward if character is 0
        >>++++[>++++++++<-]  Set up divisor (32) for division loop
                               (MEMORY LAYOUT: dividend copy remainder divisor quotient zero zero)
        <+<-[                Set up dividend (x minus 1) and enter division loop
            >+>+>-[>>>]      Increase copy and remainder / reduce divisor / Normal case: skip forward
            <[[>+<-]>>+>]    Special case: move remainder back to divisor and increase quotient
            <<<<<-           Decrement dividend
        ]                    End division loop
    ]>>>[-]+                 End skip loop; zero former divisor and reuse space for a flag
    >--[-[<->+++[-]]]<[      Zero that flag unless quotient was 2 or 3; zero quotient; check flag
        ++++++++++++<[       If flag then set up divisor (13) for second division loop
                               (MEMORY LAYOUT: zero copy dividend divisor remainder quotient zero zero)
            >-[>+>>]         Reduce divisor; Normal case: increase remainder
            >[+[<+>-]>+>>]   Special case: increase remainder / move it back to divisor / increase quotient
            <<<<<-           Decrease dividend
        ]                    End division loop
        >>[<+>-]             Add remainder back to divisor to get a useful 13
        >[                   Skip forward if quotient was 0
            -[               Decrement quotient and skip forward if quotient was 1
                -<<[-]>>     Zero quotient and divisor if quotient was 2
            ]<<[<<->>-]>>    Zero divisor and subtract 13 from copy if quotient was 1
        ]<<[<<+>>-]          Zero divisor and add 13 to copy if quotient was 0
    ]                        End outer skip loop (jump to here if ((character minus 1)/32) was not 2 or 3)
    <[-]                     Clear remainder from first division if second division was skipped
    <.[-]                    Output ROT13ed character from copy and clear it
    <-,+                     Read next character
]                            End character reading loop

Daniel B. Cristofani gives this program to print the fibonacci numbers, noting that you will have to kill the program because it doesn’t terminate:

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

Advertisements

Pages: 1 2 3

16 Responses to “Brainfuck”

  1. Paul Hofstra said

    It looks like that the above brainfuck code is slightly wrong. It should be:
    ++++++++++[>+++++++>++++++++++>+++>+<<<++.>+.+++++++..+++.>++.<.+++.——.——–.>+.>.
    You replaced <<<< by >>. The correct code is on page 2.

  2. Paul Hofstra said

    My last post does not print well. For the correct code see http://en.wikipedia.org/wiki/Brainfuck

  3. Axio said

    I think this works.
    This was my first prolog program…

    % Everyone a depth further!
    inc_dist([],[]).
    inc_dist([N|XS],[M|RS]) :- M is N+1, inc_dist(XS,RS).
    
    dec_dist([],[]).
    dec_dist([N|XS],[M|RS]) :- M is N-1, dec_dist(XS,RS).
    
    
    %% First, BF without loops, input, outputs.
    % No more command
    bf_exec([], L,H,R,_S,_T) :- reverse(L,M), append(M,[H|[]],X), append(X,R,Res), print(Res).
    
    %% Move to the right
    % Create a new cell with a 0 in it
    bf_exec([right|N], L, H, [],S,T) :- inc_dist(T,T2), bf_exec(N,[H|L],0,[],[right|S],T2).
    bf_exec([right|N], L, H, [X|XS],S,T) :- inc_dist(T,T2), bf_exec(N,[H|L],X,XS,[right|S],T2).
    
    % Move to the left
    % Create a new cell with a 0 in it
    bf_exec([left|N], [], H, R, S, T) :- inc_dist(T,T2), bf_exec(N,[],0,[H|R],[left|S],T2).
    bf_exec([left|N], [X|XS], H, R, S, T) :- inc_dist(T,T2), bf_exec(N,XS,X,[H|R],[left|S],T2).
    
    % Increment
    bf_exec([incr|N], L, H, R,S,T) :- inc_dist(T,T2), M is H+1, bf_exec(N,L,M,R,[incr|S],T2).
    % Decrement
    bf_exec([decr|N], L, H, R,S,T) :- inc_dist(T,T2), M is H-1, bf_exec(N,L,M,R,[decr|S],T2).
    
    %% Now with I/O
    % Input
    bf_exec([input|N], L, _H, R, S, T) :- inc_dist(T,T2), get_char(O), char_code(O,C), bf_exec(N, L, C, R,[input|S],T2).
    
    % Output
    bf_exec([output|N], L, H, R, S, T) :- inc_dist(T,T2), char_code(O,H), print(O), bf_exec(N, L, H, R,[output|S],T2).
    
    
    %% And now loops
    % Push a new loop handler
    bf_exec([startloop|N], L, H, R,S,T) :- inc_dist(T,T2), bf_exec(N, L, H, R,[startloop|S],[1|T2]).
    
    % End loop
    % Pop off the handler
    bf_exec([endloop|N], L, 0, R,S,[Top|Rest]) :- inc_dist([Top|Rest],[_Tap|NewRest]),
                                                  bf_exec(N, L, 0, R, [endloop|S],NewRest).
    % Rewind, restart
    bf_exec([endloop|N], L, H, R,S,T) :- bf_exec([rewind,endloop|N],L,H,R,S,T).
    
    
    % Reach loopstart.
    % Restart, No need to reset the handler.
    bf_exec([rewind|CL], L, H, R,[startloop|CS],[1|Rest]) :- bf_exec(CL,L,H,R,[startloop|CS],[1|Rest]).
    % Move back!
    bf_exec([rewind|CL], L, H, R,[X|XS],T) :- dec_dist(T,T2), bf_exec([rewind,X|CL],L,H,R,XS,T2).
    
    
    bf_eval(X) :- bf_exec(X,[],0,[],[],[]), !.
    
    
    % Hello World
    % bf_eval([incr,incr,incr,incr,incr,incr,incr,incr,incr,incr,startloop,right,incr,incr,incr,incr,incr,incr,incr,right,incr,incr,incr,incr,incr,incr,incr,incr,incr,incr,right,incr,incr,incr,right,incr,left,left,left,left,decr,endloop,right,incr,incr,output,right,incr,output,incr,incr,incr,incr,incr,incr,incr,output,output,incr,incr,incr,output,right,incr,incr,output,left,left,incr,incr,incr,incr,incr,incr,incr,incr,incr,incr,incr,incr,incr,incr,incr,output,right,output,incr,incr,incr,output,decr,decr,decr,decr,decr,decr,output,decr,decr,decr,decr,decr,decr,decr,decr,output,right,incr,output,right,output]).
    
    
  4. Paul Hofstra said

    This works on the Hello World! program.

    def parse(txt):
        data = [0] * 30000
        ptr = 0
        pos = 0
        output = []
        while pos < len(txt):
            c = txt[pos]
            if c == '<':    ptr -= 1
            elif c == '>':  ptr += 1
            elif c == '+':  data[ptr] += 1
            elif c == '-':  data[ptr] -= 1
            elif c == '.':  output.append(chr(data[ptr]))
            elif c == ',':
                try:
                    data[ptr] = ord(txt[pos+1])
                    pos += 1
                except IndexError:
                    data[ptr] = '\0'
            elif c == "[" and data[ptr] == 0:
                pos = txt.find("]", pos)
            elif c == "]":
                pos = txt.rfind("[", 0, pos) - 1
            pos += 1
        print("".join(output))
    
    parse("++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++.>+.+++++++..+++.>++.<<+++++++++++++++.>.+++.------.--------.>+.>.")
    
    
  5. programmingpraxis said

    Paul: Fixed. Thanks.

  6. Paul Hofstra said

    My earlier code did not work for nested loops. This code is slow, but it works. It is better to compile the function for speed.

    NUMBER_CELLS = 30000
    class BrainFuckException(Exception): pass
    def parse(txt, afile=None):
            data = [0] * NUMBER_CELLS
            ptr = 0
            pos = 0
            output = []
            while pos < len(txt):
                c = txt[pos]
                if c == '<':    ptr -= 1
                elif c == '>':  ptr += 1
                elif c == '+':  data[ptr] += 1
                elif c == '-':  data[ptr] -= 1
                elif c == '.':  output.append(chr(data[ptr]))
                elif c == ',':
                    data[ptr] = ord(afile.read(1) or '\0')
                elif c == "[" and data[ptr] == 0:
                    openbracket = 1
                    while pos < len(txt) - 1:
                        pos += 1
                        openbracket += txt[pos] == '['
                        openbracket -= txt[pos] == ']'
                        if openbracket == 0:
                            break
                    else:
                        raise BrainFuckException("unmatched close brace")
                elif c == "]":
                    closebracket = 1
                    while pos > 1:
                        pos -= 1
                        closebracket += txt[pos] == ']'
                        closebracket -= txt[pos] == '['
                        if closebracket == 0:
                            break
                    else:
                        raise BrainFuckException("unmatched open brace")
                    pos -= 1
                pos += 1
                assert 0 <= ptr < NUMBER_CELLS, "ptr=%d" % (ptr)
            print("".join(output))
    
    parse("++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++.>+.+++++++..+++.>++.<<+++++++++++++++.>.+++.------.--------.>+.>.")
    
  7. […] today’s Programming Praxis exercise, our goal is to implement a Brainfuck interpreter. Let’s get […]

  8. My Haskell solution (see http://bonsaicode.wordpress.com/2011/10/04/programming-praxis-brainfuck/ for a version with comments):

    import Data.List.Zipper
    
    run :: String -> IO String
    run = fmap toList . flip step (fromList $ replicate 30000 '\NUL') . fromList
    
    step :: Zipper Char -> Zipper Char -> IO (Zipper Char)
    step prog s = if endp prog then return s else
                  uncurry step =<< instruction (cursor prog) prog s
    
    instruction :: Char -> Zipper Char -> Zipper Char -> IO (Zipper Char, Zipper Char)
    instruction '<' prog s = return (right prog, left s)
    instruction '>' prog s = return (right prog, right s)
    instruction '+' prog s = return (right prog, replace (succ $ cursor s) s)
    instruction '-' prog s = return (right prog, replace (pred $ cursor s) s)
    instruction '.' prog s = putStr [cursor s] >> return (right prog, s)
    instruction ',' prog s = fmap ((,) (right prog) . flip replace s) getChar
    instruction '[' prog s = return $ (if cursor s == '\NUL' then
                                 right $ move right '[' ']' prog else right prog, s)
    instruction ']' prog s = return (move left ']' '[' prog, s)
    instruction _   prog s = return (right prog, s)
    
    move :: (Zipper Char -> Zipper Char) -> Char -> Char -> Zipper Char -> Zipper Char
    move dir open close = f 0 . dir where
        f 0 z | cursor z == close = z
        f n z = f (if cursor z == open  then n + 1 else
                   if cursor z == close then n - 1 else n) $ dir z
    
  9. Mike said

    Here’s my python 3 version. It is essentially the same as other’s above.

    A minor optimization is to implement looping using a loop stack. When ‘[‘ is encountered, ip (the instruction pointer)
    is pushed on the loop stack (ls)(at this point ip points to the instruction after the ‘[‘). When a ‘]’ is encounterd,
    d[dp] is tested. If d[dp] is non-zero a jump to the top of the loop is done by loading ip from the top of the loop stack.
    If d[dp] is zero, the loop stack is popped and execution continues after the ‘]’.

    import sys
    
    def bf(source):
        d  = [0]*30000
        dp = 0
        ip = 0
        ls = []
    
        while 0 <= ip < len(source):
            inst = source[ip]
            ip += 1
            
            if   inst in '<>':
                dp += 1 if inst == '>' else -1
    
            elif inst in '+-':
                d[dp] += 1 if inst == '+' else -1
            
            elif inst == '.':
                sys.stdout.write(chr(d[dp]))
                
            elif inst == ',':
                d[dp] = ord(sys.stdin.read(1))
            
            elif inst == '[':
                ls.append(ip)
                if not d[dp]:
                    nest = 0
                    while source[ip] != ']' or nest:
                        if source[ip] == '[': nest += 1
                        elif source[ip] == ']': nest -= 1
                        ip += 1
                        
            elif inst == ']':
                if d[dp]:
                    ip = ls[-1]
                else:
                    ls.pop()
    
    
  10. Mike said

    Just because, here is a bf-to-python cross-compiler.
    It optimizes runs of ‘+’, ‘-‘, ” to single statements. E.g., ‘+++’ is translated to ‘d[dp] += 3’.

    import re
    import sys
    
    def bf2py(source):
        d  = [0]*30000
        dp = 0
        ip = 0
    
        indent = 0
        fmt = "{0:>{1}}{2}{3}".format
    
        src = []
    
        code = re.sub(r"[^][<>.,+-]", '', source)
        for tok in re.findall(r"(\++|-+|<+|>+|,+|[].[])", code):
            if tok[0] == '>':
                src.append(fmt('', indent, "dp +=", len(tok)))
                
            elif tok[0] == '<':
                src.append(fmt('', indent, "dp -=", len(tok)))
    
            elif tok[0] == '+':
                src.append(fmt('', indent, "d[dp] +=", len(tok)))
    
            elif tok[0] == '-':
                src.append(fmt('', indent, "d[dp] -=", len(tok)))
    
            elif tok[0] == '.':
                src.append(fmt('', indent, "sys.stdout.write(chr(d[dp]))", ' ' ))
    
            elif tok[0] == ',':
                src.append(fmt('', indent, "d[dp] = ord(sys.stdin.read(1))", ' '))
    
            elif tok[0] == '[':
                src.append(fmt('', indent, "while d[dp]:", ' '))
                indent += 2
    
            elif tok[0] == ']':
                indent -= 2
            
        exec('\n'.join(src))
    
  11. Axio said

    Well, a loop is just a subroutine, so getting in/out of it should be handled by the evaluator.
    Parse the string into a tree, then eval the tree. Loops are then just subtrees that need to be evaluated before we can continue.

    (define (parse str)
      (let ((len (string-length str))
            (i 0))
        (define (aux)
          (if (= i len)
            '()
            (case (string-ref str i)
              ((#\[ ) (incr i)
                      (let ((res (aux)))
                        (cons res (aux))))
              ((#\]) (incr i)
                     '())
              (else
                (let ((c (string-ref str i)))
                  (incr i)
                  (if (member c (string->list "><+-.,[]"))
                    (cons c (aux))
                    (aux)))))))
        (aux)))
    
    
    (define (bf-eval str)
      (let ((*tape* (make-table test: =))
            (*tc* 0)
            (l (parse str)))
        (define (aux l)
          (when (not (null? l))
            (case (car l)
              ((#\>) (incr *tc*)
                     (aux (cdr l)))
              ((#\<) (decr *tc*)
                     (aux (cdr l)))
              ((#\+) (table-set! *tape* *tc* (1+ (table-ref *tape* *tc* 0)))
                     (aux (cdr l)))
              ((#\-) (table-set! *tape* *tc* (1- (table-ref *tape* *tc* 0)))
                     (aux (cdr l)))
              ((#\.) (display (integer->char (table-ref *tape* *tc* 0)))
                     (aux (cdr l)))
              ((#\,) (table-set! *tape* *tc* (char->integer (string-ref (read-line) 0)))
                     (aux (cdr l)))
              (else ;; it's a loop, with more body 
                (if (zero? (table-ref *tape* *tc* 0))
                  ;; next
                  (aux (cdr l))
                  ;; body, and then self again
                  (begin (aux (car l))
                         (aux l)))))))
        (pp l)
        (aux l)
        ;(table->list *tape*)
        ))
    
  12. DGel said

    My slightly larger than necessary version. Note that I got the idea of using a loop stack from Mike, my first idea was similar to Paul Hofstra’s first answer, and wouldn’t have worked properly.

    func parse_bf(raw_instr []byte) {
    	re, err := regexp.Compile(`[^<>\+\-\,\.\[\]]`)
    	if err != nil {
    		fmt.Println("couldn't compile regexp:", err)
    	}
    	instr := re.ReplaceAll(raw_instr, []byte(""))
    	
    	dp := 0
    	ip := 0
    	
    	var loopstack vector.IntVector
    	data := make([]byte, 30000)
    	
    	in_out := make([]byte, 1)
    	
    	for ip < len(instr) {
    		switch instr[ip] {
    			case '+':
    				if dp >= 0 && dp < 30000 {
    					data[dp]++
    				} else {
    					fmt.Println("Error: data pointer outside memory:", dp)
    					return
    				}
    			case '-':
    				if dp >= 0 && dp < 30000 {
    					data[dp]--
    				} else {
    					fmt.Println("Error: data pointer outside memory:", dp)
    					return
    				}
    			case '>':
    				dp++
    			case '<':
    				dp--
    			case '[':
    				loopstack.Push(ip)
    				if data[dp] == 0 {
    					nestLevel := 1
    					for nestLevel > 0 {
    						ip++
    						if instr[ip] == '[' {nestLevel++}
    						if instr[ip] == ']' {nestLevel--}
    					}
    					ip-- // ensure the loop gets popped
    				}
    			case ']':
    				if (data[dp] > 0) {
    					ip = loopstack.Last()
    				} else {
    					if len(loopstack) > 0 {
    						loopstack.Pop()
    					} else {
    						fmt.Println("Error: unmatched close loop statement")
    						return;
    					}
    				}
    			case '.':
    				in_out[0] = data[dp]
    				_, err := os.Stdout.Write(in_out)
    				if err != nil {fmt.Println("Error: can't write do stdout: ", err); return}
    			case ',':
    				_, err := os.Stdin.Read(in_out)
    				if err != nil {fmt.Println("Error: can't read from stdin: ", err); return}
    				data[dp] = in_out[0]
    		}
    		ip++
    	}
    }
    
  13. ecc said

    (* Brainfuck “compiler” in OCaml *)

    let src = open_in Sys.argv.(1)

    let right (f, i) = f, i + 1
    let left (f, i) = f, i – 1

    let set f i x j = if j = i then x else f j

    let inc (f, i) = set f i (f i + 1), i
    let dec (f, i) = set f i (f i – 1), i
    let inp (f, i) = set f i (try input_byte stdin with End_of_file -> 0), i

    let cur (f, i) = f i

    let out s = output_byte stdout (cur s); s
    let rec loop p s = if cur s 0 then loop p (p s) else s

    let id x = x

    let (>>) f g x = g (f x)

    let rec compile () =
    let emit q = q >> compile () in
    try match (input_char src) with
    | ‘>’ -> emit right
    | ‘ emit left
    | ‘+’ -> emit inc
    | ‘-‘ -> emit dec
    | ‘.’ -> emit out
    | ‘,’ -> emit inp
    | ‘[‘ -> emit (loop (compile ()))
    | ‘]’ -> id
    | _ -> compile ()
    with End_of_file -> id

    let const c x = c

    let _ = (compile ()) (const 0, 0)

  14. slabounty said

    In ruby (I believe it handles everything) …

    def bf_parse(program)
        data = Array.new(30000, 0)
        data_pointer = 0
        program_pointer = 0
        program_array = program.split(//)
        output = ""
    
    
        while program_pointer < program.size do 
    
            c = program_array[program_pointer]
    
            case c
            when '<'
                # < move the data pointer one cell left
                data_pointer -= 1
            when '>'
                # > move the data pointer one cell right
                data_pointer += 1
            when '+'
                # + increment the cell at the current data pointer
                data[data_pointer] += 1
            when '-'
                # - decrement the cell at the current data pointer
                data[data_pointer] -= 1
            when '.'
                # . output the cell at the current data pointer as a character
                output << data[data_pointer]
            when ','
                # , input the next character to the cell at the current data pointer
                c = STDIN.getc
                data[data_pointer] = c.ord if c != nil
            when '['
                # [ if the cell at the current data pointer is zero, move the instruction pointer to the matching ]
                if data[data_pointer] == 0 then
                    bracket_count = 1
                    while program_pointer < program.size do 
                        program_pointer +=1
                        case program_array[program_pointer]
                        when '['
                            bracket_count += 1
                        when ']'
                            bracket_count -= 1
                        end
                        break if bracket_count == 0
    
                    end
                end
            when ']'
                # ] move the instruction pointer to the matching [
                bracket_count = -1
                while program_pointer < program.size do 
                    program_pointer -=1
                    case program_array[program_pointer]
                    when '['
                        bracket_count += 1
                    when ']'
                        bracket_count -= 1
                    end
                    break if bracket_count == 0
                        
                end
                program_pointer -=1
            else
                puts "Illegal BrainFuck character in program #{c}"
            end
    
            program_pointer += 1
        end
    
        output
    end
    
  15. sealfin said

    October 4th, 2011.cpp:

    #include "seal_stack.h" /* <http://GitHub.com/sealfin/C-and-C-Plus-Plus/blob/master/seal_stack.h> */
    #include <stdlib.h>
    #include <stdio.h>
    #include <string.h>
    
    char *g_nameOfFile;
    FILE *g_file = NULL;
    
    struct t_Instruction
    {
      char m_instruction;
      size_t m_indexOfInstructionToJumpTo;
    };
    
    struct t_Instruction *g_instructions = NULL;
    
    //#define M_DataStoreBytesAreSigned
    
    typedef
    #ifdef M_DataStoreBytesAreSigned
    signed
    #else
    unsigned
    #endif
    char t_DataStoreByte;
    
    //#define M_DataPointerWrapsAround
    
    void p_CleanUp( void );
    
    void p_CleanUp( void )
    {
      #ifdef __MWERKS__
      free( g_nameOfFile );
      #endif
      if( g_file != NULL )
        fclose( g_file );
      if( g_instructions != NULL )
        free( g_instructions );
    }
    
    char *f_ReadStringFromFile( FILE * const p );
    
    char *f_ReadStringFromFile( FILE * const p )
    {
      char c, *s = ( char* )malloc( sizeof( char ));
      size_t s_length = 1;
    
      while(( fscanf( p, "%c", &c ) != EOF ) && ( c != '\n' ))
      {
        s[ s_length - 1 ] = c;
        s_length ++;
        s = ( char* )realloc( s, sizeof( char ) * s_length );
      }
      s[ s_length - 1 ] = '\0';
      return s;
    }
    
    bool f_CharacterIsInSet( const char p_character, const char * const p_set );
    
    bool f_CharacterIsInSet( const char p_character, const char * const p_set )
    {
      size_t i = 0;
    
      for( ; i < strlen( p_set ); i ++ )
        if( p_character == p_set[ i ] )
          return true;
      return false;
    }
    
    int main( const int argc, const char * const argv[] )
    {
      bool error_occurred;
    
      atexit( p_CleanUp );
      #ifndef __MWERKS__
      error_occurred = argc != 2;
      if( !error_occurred )
      {
        g_nameOfFile = ( char* )argv[ 1 ];
        g_file = fopen( g_nameOfFile, "r" );
        if( g_file == NULL )
          error_occurred = true;
      }
      if( error_occurred )
      {
        fprintf( stderr, "\nThis program must be passed, via the command line, the path to a brainfuck source code file, which this program will then interpret.\n\n" );
        exit( EXIT_FAILURE );
      }
      #else
      do
      {
        printf( "Please enter the name of a brainfuck source code file, which must be in the same folder as this program, which this program will then interpret.\n" );
        printf( "\nYour input: " );
        g_nameOfFile = f_ReadStringFromFile( stdin );
        g_file = fopen( g_nameOfFile, "r" );
        error_occurred = g_file == NULL;
        if( error_occurred )
        {
          printf( "\nSorry, an error occurred: there is no brainfuck source code file named \"%s\" in the same folder as this program.\n", g_nameOfFile );
          free( g_nameOfFile );
          printf( "\nPlease press the Return key to try again." );
          free( f_ReadStringFromFile( stdin ));
          printf( "\n" );
        }
      }
      while( error_occurred );
      #endif
    
      char c;
      size_t number_of_instructions = 0;
      seal_Stack<size_t> indices_of_instructions_to_jump_to;
      FILE * const fileToPrintErrorMessagesTo = 
      #ifdef __MWERKS__
      stdout
      #else
      stderr
      #endif
      ;
      const char * const k_ExitMessage = 
      #ifdef __MWERKS__
      "\nThis program will now quit."
      #else
      ""
      #endif
      ;
    
      while( fscanf( g_file, "%c", &c ) != EOF )
        if( f_CharacterIsInSet( c, "<>+-.,[]" ))
        {
          number_of_instructions ++;
          if( number_of_instructions == 1 )
            g_instructions = ( struct t_Instruction* )malloc( sizeof( struct t_Instruction ));
          else
            g_instructions = ( struct t_Instruction* )realloc( g_instructions, sizeof( struct t_Instruction ) * number_of_instructions );
          g_instructions[ number_of_instructions - 1 ].m_instruction = c;
          if( c == '[' )
            indices_of_instructions_to_jump_to.p_Push( number_of_instructions - 1 );
          else
            if( c == ']' )
              if( !indices_of_instructions_to_jump_to.f_IsEmpty())
              {
                const size_t index_of_instruction_to_jump_to = indices_of_instructions_to_jump_to.f_Pop();
    
                g_instructions[ index_of_instruction_to_jump_to ].m_indexOfInstructionToJumpTo = number_of_instructions - 1;
                g_instructions[ number_of_instructions - 1 ].m_indexOfInstructionToJumpTo = index_of_instruction_to_jump_to;
              }
              else
              {
                fprintf( fileToPrintErrorMessagesTo, "\nSorry, an error occurred: an unmatched unconditional jump instruction (']') was encountered in the brainfuck source code file named \"%s\".\n%s\n", g_nameOfFile, k_ExitMessage );
                exit( EXIT_FAILURE );
              }
        }
      if( !indices_of_instructions_to_jump_to.f_IsEmpty())
      {
        fprintf( fileToPrintErrorMessagesTo, "\nSorry, an error occurred: an unmatched conditional jump instruction ('[') was encountered in the brainfuck source code file named \"%s\".\n%s\n", g_nameOfFile, k_ExitMessage );
        exit( EXIT_FAILURE );
      }
      fclose( g_file );
      g_file = NULL;
    
      signed long long data_pointer = 0;
      const size_t k_LengthOfDataStore = 30000;
      t_DataStoreByte data_store[ k_LengthOfDataStore ];
      size_t instruction_pointer = 0;
    
      for( ; data_pointer < k_LengthOfDataStore; data_pointer ++ )
        data_store[ data_pointer ] = 0;
      data_pointer = 0;
      for( ; instruction_pointer < number_of_instructions; instruction_pointer ++ )
        switch( g_instructions[ instruction_pointer ].m_instruction )
        {
          case '<':
            data_pointer --;
            if( data_pointer < 0 )
            {
              #ifdef M_DataPointerWrapsAround
              data_pointer = k_LengthOfDataStore - 1;
              #else
              fprintf( fileToPrintErrorMessagesTo, "\nSorry, an error occurred: the data pointer was decremented beyond the left-most end of the data store whilst interpreting the brainfuck source code file named \"%s\".\n%s\n", g_nameOfFile, k_ExitMessage );
              exit( EXIT_FAILURE );
              #endif
            }
            break;
          case '>':
            data_pointer ++;
            if( data_pointer >= k_LengthOfDataStore )
            {
              #ifdef M_DataPointerWrapsAround
              data_pointer = 0;
              #else
              fprintf( fileToPrintErrorMessagesTo, "\nSorry, an error occurred: the data pointer was incremented beyond the right-most end of the data store whilst interpreting the brainfuck source code file named \"%s\".\n%s\n", g_nameOfFile, k_ExitMessage );
              exit( EXIT_FAILURE );
              #endif
            }
            break;
          case '+':
            data_store[ data_pointer ] ++;
            break;
          case '-':
            data_store[ data_pointer ] --;
            break;
          case '.':
            printf( "%c", data_store[ data_pointer ] );
            break;
          case ',':
            scanf( "%c", &data_store[ data_pointer ] );
            break;
          case '[':
            if( data_store[ data_pointer ] == 0 )
              instruction_pointer = g_instructions[ instruction_pointer ].m_indexOfInstructionToJumpTo;
            break;
          case ']':
            instruction_pointer = g_instructions[ instruction_pointer ].m_indexOfInstructionToJumpTo - 1;
            break;
        }
      printf( "%s\n", k_ExitMessage );
      exit( EXIT_SUCCESS );
    }

    The interpreter is known to run on an Apple Power Mac G4 (AGP Graphics) (450MHz processor, 1GB memory) on both Mac OS 9.2.2 (International English) (the program interpreted using Leonardo IDE 3.4.1) and Mac OS X 10.4.11 (the program compiled using Xcode 2.2.1).

    The description of the problem fails to specify whether the bytes of the data store are unsigned or signed; therefore, I’ve provided the option to specify, when compiling the interpreter, whether the bytes of the data store are unsigned (by leaving line 17 commented out) or signed (by reinstating the aforementioned line).

    Similarly, the description of the problem fails to specify the behaviour of the interpreter if the data pointer is decremented beyond the leftmost- or incremented beyond the rightmost- end of the data store; therefore, I’ve provided the option to specify, when compiling the interpreter, whether the interpreter quits with an error message (by leaving line 27 commented out) or whether the data pointer “wraps around” to the opposite end of the data store (by reinstating the aforementioned line).

    The description of the problem specifies that the instruction pointer is incremented after unconditional jump (‘]’) instructions; this is incorrect, as if the instruction pointer were to be incremented after unconditional jump instructions the conditional jump instructions (‘[’) jumped to would not be evaluated and any loop entered would never be exited.

    (I’ve just completed a gig at London South Bank University and so I’m again just trying to solve the problems posed by this ‘site whilst I try to get a job (and I’ve solved this problem in particular to test my seal_Stack template class I might use in the fourth version of my SDL2 joystick interrogator utility); I’m well-aware that my solutions are far from the best – but, in my defence, I don’t have any traditional qualifications in computer science :/ )

  16. sealfin said

    sigh * Where I wrote

    (the program interpreted using Leonardo IDE 3.4.1)

    I meant to write

    (the program compiled using Metrowerks CodeWarrior IDE 2.1 (Discover Programming Edition))

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s

%d bloggers like this: