[2008-07] Learning Brainfuck - First Program and Python Interpreter

brainfuck.py

#!/usr/bin/env python
# encoding: utf-8
# 
# Rudementary Python Brainfuck Interpreter
# [email protected] 
# 
# Usage: brainfuck.py program.bf
# 
# Input is from stdin, output to stdout, obviously.
# The grid is infinite in both directions.
# Value overflows wrap as uint8_t.
# 
# I've tested only on my single brainfuck program.
# There are probably bugs.
# 

import sys
from collections import defaultdict

def input():
	try:
		return ord(sys.stdin.read())
	except:
		return 0 # EOF or other errors

def output(b):
	return sys.stdout.write(chr(b))

def main():
	flags = []
	files = [] # Only the first is actually executed.
	
	for arg in sys.argv[1:]:
		if arg[0] == "-":
			flags.append(arg[1:])
		else:
			files.append(arg)
		
	if files:
		try:
			program = open(files[0], "r").read()
		except IOError:
			print >> sys.stderr, "Unable to read file %s." % (sys.argv[1])
			return 1
		
		cells = defaultdict(lambda: 0)
		pointer = 0 # Program pointer in cells
		
		returns = [] # Stack of return points for loops
		location = 0 # Interpreter pointer in program
		
		while location < len(program):
			code = program[location] # Convenience
			
			if   code == "[":
				if cells[pointer] != 0:
					returns.append(location)
				else:
					depth = 1
					
					while depth:
						location += 1
						
						if location < len(program):
							if   program[location] == "[":
								depth += 1
							elif program[location] == "]":
								depth -= 1
						else:
							print >> sys.stderr, "Unexpected EOF inside loop at location %i." % (location)
			elif code == "]":
				if returns:
					if cells[pointer] != 0:
						location = returns.pop()
						continue # Don't want to flow forward like the others
					else:
						returns.pop()
				else:
					print >> sys.stderr, "Unexpected \"]\" at location %i." % (location)
					return 1
			elif code == ">":
				pointer += 1
			elif code == "<":
				pointer -= 1
			elif code == "+":
				cells[pointer] = (cells[pointer] + 1) % 256
			elif code == "-":
				cells[pointer] = (cells[pointer] - 1) % 256
			elif code == ".":
				output(cells[pointer])
			elif code == ",":
				cells[pointer] = input()
				
			location += 1
		
		if "n" in flags:
			print >> sys.stdout
		
		if "d" in flags:
			print >> sys.stderr
			print >> sys.stderr, "Program terminated successfully."
			if len(files) > 1:
				print >> sys.stderr, "Ignored files: %s" % (", ".join(files[1:]))
			print >> sys.stderr
			
			cells[pointer] # We always want to see where we are.
			debugCells = cells.items()
			debugCells.sort(cmp = lambda a, b: cmp(a[0], b[0]))
			
			previousKey = None
			
			for cell in debugCells:
				if previousKey is not None and previousKey + 1 < cell[0]:
					print >> sys.stderr, "       ..."
				
				mark = "->" if cell[0] == pointer else "  "
				
				print >> sys.stderr, " %2s [%1s%3i]%4i" % (
					mark,
					"+" if cell[0] > 0 else "-" if cell[0] < 0 else " ",
					abs(cell[0]), cell[1]
				)
				
				previousKey = cell[0]
			
			print >> sys.stderr
		
		return 0
	else:
		print >> sys.stderr, "Usage: brainfuck.py [-n] [-d] file"
		return 1
	

if __name__ == "__main__": sys.exit(main())

multiplication_readable.bf

I want to learn brainfuck!
I haven't used it before!
Let's try integer multiplication!
My comments are probably crap!
It is designed to be understandable and is not at all efficient!

It seems to work now! Yay!

* (0) is the result
* (1) and (2) are the factors
* (3) and (4) are used internally (mutable copies of (1) and (2))
* (5) is used internally (temporary space for copying)
* (6) is used internally (for output formatting)

Let's multiply two by three:
	>   ++ (1)
	>  +++ (2)
	<<     (0)

Copy (1) to (3) using (5) for temporary storage
	> (1)
	Move (1) to (3) and (5)
		[
			>>   + (3)
			>>   + (5)
			<<<< - (1)
		]
	Move (5) to (1)
		>>>> (5)
		[
			<<<< + (1)
			>>>> - (5)
		]
		<<<< (1)
	< (0)

The multiplication
	>>> (3)
	Increment (0) by (2/4) for each (1/3)
		[
			Copy (2) to (4) using (5) for temporary storage
				< (2)
				Move (2) to (4) and (5)
					[
						>>  + (4)
						>   + (5)
						<<< - (1)
					]
				Move (5) to (2)
					>>> (5)
					[
						<<< + (2)
						>>> - (5)
					]
					<<< (2)
				> (3)
			
			Increment (0) for each (2/4)
				> (4)
				[
					<<<< + (0)
					>>>> - (4)
				]
				< (3)
			
			- (3)
		]
	<<< (0)

(Destructive) Display the factors and the product (all must be between 0 and 9)
	Set (5) to ASCII '*'
		>>>>> (5)
		++++++++++++++++++++++++++++++++++++++++++
		<<<<< (0)
	
	Set (6) to ASCII '='
		>>>>>>
		+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
		<<<<<<
	
	  ++++++++++++++++++++++++++++++++++++++++++++++++ (0)
	> ++++++++++++++++++++++++++++++++++++++++++++++++ (1)
	> ++++++++++++++++++++++++++++++++++++++++++++++++ (2)
	
	<      . (1)
	>>>>   . (5)
	<<<    . (2)
	>>>>   . (6)
	<<<<<< . (0)

mutplication_raw.bf

>  ++  First Factor
> +++ Second Factor

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