Befunge Interpreter

befunge.py

from StringIO import StringIO
import inspect
from functools import wraps
import random

DEBUG = False

instructions = {}

def instr(opcode):
	def decorator(func):
		@wraps(func)
		def wrapper(ip):
			argspec = inspect.getargspec(func)
			num_args = len(argspec[0])-1  # first arg is the interpreter instance
			num_missing = max((num_args - len(ip.stack), 0))
			popped_args = [ip.stack.pop() for _ in range(num_args-num_missing)]
			if num_missing:
				popped_args.extend([0]*num_missing)
			ret = func(ip, *popped_args)
			if ret is None:
				return
			elif isinstance(ret, int):
				ip.stack.append(ret)
			else:
				for v in ret:
					ip.stack.append(v)
		instructions[opcode] = wrapper
	return decorator

instructions.update({
	"0": lambda ip: ip.stack.append(0),
	"1": lambda ip: ip.stack.append(1),
	"2": lambda ip: ip.stack.append(2),
	"3": lambda ip: ip.stack.append(3),
	"4": lambda ip: ip.stack.append(4),
	"5": lambda ip: ip.stack.append(5),
	"6": lambda ip: ip.stack.append(6),
	"7": lambda ip: ip.stack.append(7),
	"8": lambda ip: ip.stack.append(8),
	"9": lambda ip: ip.stack.append(9),
})

@instr("+")
def add(ip, a, b):
	return a + b

@instr("-")
def subtract(ip, a, b):
	return b - a

@instr("*")
def multiply(ip, a, b):
	return a * b

@instr("/")
def divide(ip, a, b):
	if b == 0:
		return 0
	return b // a

@instr("%")
def modulo(ip, a, b):
	if b == 0:
		return 0
	return b % a

@instr("!")
def logical_not(ip, a):
	return 1 if a == 0 else 0

@instr("`")
def greater_than(ip, a, b):
	return 1 if b > a else 0

@instr(">")
def move_right(ip):
	ip.direction = RIGHT

@instr("v")
def move_down(ip):
	ip.direction = DOWN

@instr("<")
def move_left(ip):
	ip.direction = LEFT

@instr("^")
def move_up(ip):
	ip.direction = UP

@instr("?")
def move_rand(ip):
	ip.direction = random.choice((RIGHT, DOWN, LEFT, UP))

@instr("_")
def pop_move_left_right(ip, a):
	ip.direction = RIGHT if a == 0 else LEFT

@instr("|")
def pop_move_up_down(ip, a):
	ip.direction = DOWN if a == 0 else UP

@instr('"')
def string_mode(ip):
	for ins in ip.opcode_iterator():
		if ins == '"':
			return
		ip.stack.append(ord(ins))

@instr(":")
def duplicate(ip, a):
	return (a, a)

@instr("\\")
def swap(ip, a, b):
	return (a, b)

@instr("$")
def pop(ip, a):
	pass

@instr(".")
def print_int(ip, a):
	ip.output.write(str(a))

@instr(",")
def print_chr(ip, a):
	ip.output.write(chr(a))

@instr("#")
def skip(ip):
	next(ip.opcode_iterator())

@instr("p")
def put(ip, y, x, v):
	ip.code[y][x] = chr(v)

@instr("g")
def get(ip, y, x):
	return ord(ip.code[y][x])

@instr("@")
def end(ip):
	raise InterpreterStop()


class InterpreterStop(Exception):
	pass

RIGHT, DOWN, LEFT, UP = (1, 0), (0, 1), (-1, 0), (0, -1)
class Interpreter(object):
	def __init__(self, instructions):
		self.instructions = instructions

		self.stack = []
		self.direction = RIGHT
		self.output = StringIO()
		self.code = []
		self.running = False
		self.x = -1
		self.y = 0
		self.size_y = 0
		self.size_x = 0
	
	def load(self, code):
		for line in code.split("\n"):
			self.code.append([opcode for opcode in line])
		self.size_y = len(self.code)
		self.size_x = max(len(x) for x in self.code)
		for row in self.code:
			diff = self.size_x - len(row)
			for _ in range(diff):
				row.append(" ")
	
	def run(self):
		#i = 0
		for opcode in self.opcode_iterator():
			#i += 1
			#if i > 20: break
			f = self.instructions.get(opcode)
			if DEBUG:
				print "at x={} y={} opcode={} direction x={} y={} Stack={}".format(self.x, self.y, opcode, self.direction[0], self.direction[1], self.stack)
			if not f:
				continue
			try:
				f(self)
			except InterpreterStop:
				if DEBUG:
					print "Output:", self.output.getvalue()
				break
			except:
				print "Exception at x={} y={} opcode={}".format(self.x, self.y, opcode)
				print "Direction x={} y={}".format(self.direction[0], self.direction[1])
				print "Stack: {}".format(self.stack)
				print "Code:"
				print "\n".join("".join(row) for row in self.code)
				print "Output:", self.output.getvalue()
				raise

	def opcode_iterator(self):
		while True:
			self.x = (self.x + self.direction[0] + self.size_x)%self.size_x
			self.y = (self.y + self.direction[1] + self.size_y)%self.size_y
			yield self.code[self.y][self.x]


			
if DEBUG:
	for k,v in instructions.iteritems():
		print k, v




def interpret(code):
	if DEBUG:
		for line in code.split("\n"):
			print repr(line)
	ip = Interpreter(instructions)
	ip.load(code)
	ip.run()
	return ip.output.getvalue()


DEBUG = True

assert interpret('01->1# +# :# 0# g# ,# :# 5# 8# *# 4# +# -# _@') == '01->1# +# :# 0# g# ,# :# 5# 8# *# 4# +# -# _@'
assert interpret('>987v>.v\nv456<  :\n>321 ^ _@') == '123456789'