Brainfuck
October 4, 2011
Our brainfuck interpreter “compiles” a brainfuck program by stripping comment characters and storing the program in a vector:
(define (compile prog)
(list->vector
(filter (lambda (c) (member c (string->list "><+-.,[]")))
(string->list prog))))
The interpreter keeps two global vectors: iv
is the compiled instruction vector, and dv
is the data store. The ip
instruction pointer and dp
data pointer are handled in the controlling loop that runs through the instructions, decoding each one and performing the appropriate action as long as the instruction pointer doesn’t run off the end of the instruction vector:
(define (brainfuck prog)
(let* ((iv (compile prog))
(len (vector-length iv))
(dv (make-vector 30000 0)))
(let loop ((ip 0) (dp 0))
(when (< ip len)
(case (vector-ref iv ip)
((#\>) (loop (+ ip 1) (+ dp 1)))
((#\<) (loop (+ ip 1) (- dp 1)))
((#\+) (vector-set! dv dp (+ (vector-ref dv dp) 1))
(loop (+ ip 1) dp))
((#\-) (vector-set! dv dp (- (vector-ref dv dp) 1))
(loop (+ ip 1) dp))
((#\.) (display (integer->char (vector-ref dv dp)))
(loop (+ ip 1) dp))
((#\,) (vector-set! dv dp (char->integer (read-char)))
(loop (+ ip 1) dp))
((#\[) (if (zero? (vector-ref dv dp))
(loop (+ (forward-match iv ip) 1) dp)
(loop (+ ip 1) dp)))
((#\]) (if (zero? (vector-ref dv dp))
(loop (+ ip 1) dp)
(loop (+ (backward-match iv ip) 1) dp))))))))
Two auxiliary functions find matching brackets:
(define (forward-match iv ip)
(let loop ((ip (+ ip 1)) (n 0))
(cond ((char=? (vector-ref iv ip) #\[)
(loop (+ ip 1) (+ n 1)))
((char=? (vector-ref iv ip) #\])
(if (zero? n) ip
(loop (+ ip 1) (- n 1))))
(else (loop (+ ip 1) n)))))
(define (backward-match iv ip)
(let loop ((ip (- ip 1)) (n 0))
(cond ((char=? (vector-ref iv ip) #\])
(loop (- ip 1) (+ n 1)))
((char=? (vector-ref iv ip) #\[)
(if (zero? n) ip
(loop (- ip 1) (- n 1))))
(else (loop (- ip 1) n)))))
You can run the program at http://programmingpraxis.codepad.org/aetegm3n.
It looks like that the above brainfuck code is slightly wrong. It should be:
++++++++++[>+++++++>++++++++++>+++>+<<<++.>+.+++++++..+++.>++.<.+++.——.——–.>+.>.
You replaced <<<< by >>. The correct code is on page 2.
My last post does not print well. For the correct code see http://en.wikipedia.org/wiki/Brainfuck
I think this works.
This was my first prolog program…
This works on the Hello World! program.
Paul: Fixed. Thanks.
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.
[…] today’s Programming Praxis exercise, our goal is to implement a Brainfuck interpreter. Let’s get […]
My Haskell solution (see http://bonsaicode.wordpress.com/2011/10/04/programming-praxis-brainfuck/ for a version with comments):
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 ‘]’.
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’.
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.
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.
(* 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)
In ruby (I believe it handles everything) …
October 4th, 2011.cpp:
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 :/ )sigh * Where I wrote
I meant to write