mbomb007 mbomb007 - 4 months ago 30
Brainfuck Question

My Python interpreter for Self-modifying Brainf*** has a bug

I wrote this Python interpreter for a language called Self-modifying Brainf*** (SMBF). Today I discovered a bug where if the program dynamically creates code at the initial cell or after on the tape, it will not be executed. I wrote this interpreter to look as close as possible to the Ruby interpreter on the linked page. Note that this bug may exist in the original Ruby interpreter, too. I don't know, I haven't used it.

The way SMBF is different from normal BF is that the source code is placed on the tape to the left of the cell that the pointer starts at. So the program

<.
would print the last character of the source (a period). This works.

Note that I trimmed some code out so it's still runnable but takes less space in this post.

The interpreter:



from __future__ import print_function
import os, sys

class Tape(bytearray):
def __init__(self):
self.data = bytearray(b'\0' * 1000)
self.center = len(self.data) // 2

def __len__(self):
return len(self.data)

def __getitem__(self, index):
try:
return self.data[index + self.center]
except:
return 0

def __setitem__(self, index, val):

i = index + self.center

if i < 0 or i >= len(self.data):
# resize the data array to be large enough

new_size = len(self.data)

while True:
new_size *= 2
test_index = index + (new_size // 2)
if test_index >= 0 and test_index < new_size:
# array is big enough now
break

# generate the new array
new_data = bytearray(b'\0' * new_size)
new_center = new_size // 2

# copy old data into new array
for j in range(0, len(self.data)):
new_data[j - self.center + new_center] = self.data[j]

self.data = new_data
self.center = new_center

self.data[index + self.center] = val & 0xff

class Interpreter():
def __init__(self, data):
self.tape = Tape()

# copy the data into the tape
for i in range(0, len(data)):
self.tape[i - len(data)] = data[i]

# program start point

self.entrypoint = -len(data)

def call(self):
pc = self.entrypoint
ptr = 0

# same as -len(self.tape) // 2 <= pc + self.tape.center < len(self.tape) // 2
while -len(self.tape) <= pc < 0: # used to be "while pc < 0:"
c = chr(self.tape[pc])
if c == '>':
ptr += 1
elif c == '<':
ptr -= 1
elif c == '+':
self.tape[ptr] += 1
elif c == '-':
self.tape[ptr] -= 1
elif c == '.':
print(chr(self.tape[ptr]), end="")
elif c == ',':
sys.stdin.read(1)
elif c == '[':
if self.tape[ptr] == 0:
# advance to end of loop
loop_level = 1
while loop_level > 0:
pc += 1
if chr(self.tape[pc]) == '[': loop_level += 1
elif chr(self.tape[pc]) == ']': loop_level -= 1
elif c == ']':
# rewind to the start of the loop
loop_level = 1
while loop_level > 0:
pc -= 1
if chr(self.tape[pc]) == '[': loop_level -= 1
elif chr(self.tape[pc]) == ']': loop_level += 1
pc -= 1
pc += 1

# DEBUG
#print(pc, self.tape.data.find(b'.'))

def main():
# Working "Hello, World!" program.
#data = bytearray(b'<[.<]>>>>>>>>+\x00!dlroW ,olleH')

# Should print a period, but doesn't.
data = bytearray(b'>++++++++++++++++++++++++++++++++++++++++++++++')

intr = Interpreter(data)
intr.call()
#print(intr.tape.data.decode('ascii').strip('\0'))

if __name__ == "__main__":
main()


The problem:



This line is how I set the program (so I can run this on Ideone.com):

data = bytearray(b'++++++++++++++++++++++++++++++++++++++++++++++')


The program adds to the cell until it is 46, which is the decimal value for an ASCII
.
, which should print the current cell (a period). But for some reason, the program counter
pc
never gets to that cell. I want the program to run all code it finds until it hits the end of the tape, but I'm having a hard time getting the program counter to take into account the center of the tape, and ensure that it's still correct if the tape is resized in
__setitem__
.

The relevant line is (what I was trying out):

while -len(self.tape) <= pc < 0:


which was originally this:

while pc < 0:


So I think that the
while
line either needs to be adjusted, or I need to change it to
while True:
and just use a
try/except
while getting
chr(self.tape[pc])
to determine if I've hit the end of the tape.

Does anyone see what is wrong or how to fix it?

Answer

Found a solution thanks to Sp3000.

self.end = 0 in Tape.__init__, self.end = max(self.end, index+1) in Tape.__setitem__ and replace the while in Interpreter.call with while pc < self.tape.end:.