Brainfuck Interpreter

Stellt hier eure Projekte vor.
Internetseiten, Skripte, und alles andere bzgl. Python.
Antworten
Karl
User
Beiträge: 252
Registriert: Freitag 29. Juni 2007, 17:49

Hi.
Ich habe einen Brainfuck Interpreter geschrieben, beziehungsweise viel mehr eine Klasse dafür, eine richtige GUI kommt vielleicht noch irgendwann.
Nach dem Thread in dem es um einen kleinen Bug in meinem Code ging, ist er jetzt auch mal fertig.
Ich würde mich freuen, wenn ihr mir ein paar Dinge zu meinem Code sagen könntet.
Ich habe bestimmt einige Dinge gemacht, die man besser machen könnte/sollte.
Achja, wer nicht mit Brainfuck vertraut ist, sich aber trotzdem mit dem Code befassen will (wovon ich zwar nicht ausgehe), sollte sich mal den Brainfuck Artikel auf Wikipedia anschaun. Da steht eigentlich alles wichtige drin und es ist wirklich nicht schwer zu verstehen.

Code: Alles auswählen

class NumError(Exception):
    def __init__(self, description = ""):
        self.description = description
    def __str__(self):
        print self.description
        return self.description

class BFSyntaxError(Exception):
    def __init__(self, description = ""):
        self.description = description
    def __str__(self):
        print self.description
        return self.description 

class Brainfuck():
    """
    This class can run Brainfuck code
    """
    def __init__(self, arraysize=30000, fieldsize=256):
        """
        arraysize:  The number of fields that the array consists of.
                    Usually this is 30000 but if you want to display
                    self.array for example you should set it as low as
                    you need it
        """
        self.arraysize = arraysize
        self.fieldsize = fieldsize  # Should be a byte or a multiple of it
        self.loops = []  # Used to store the informations about the loops
        self.code = ""
        self.set_chars()
        self.array = []
        self.pointer = 0
        self.reset()

    def check_syntax(self):
        """
        Checks the Brainfuck code for the correct using of '[' and ']'
        """
        i = 0
        x = 0
        for i in xrange(len(self.code)):
            # this will find the matching loop-end for this loop-begin
            if self.code[i] == self.chars[4]:  # char 4 = [
                x += 1
            elif self.code[i] == self.chars[5]:  # char 5 = ]
                x -= 1
            i += 1
        if x == 0:
            return True
        else:
            raise BFSyntaxError()
    
    def set_chars(self, chars=["+", "-", ">", "<", "[", "]", ".", ","]):
        """
        With this Method you can rename the standard Brainfuck characters with
        other characters.
        The code will always interpret the characters in this order:
        + - > < [ ] . ,
        """
        self.chars = chars
        print self.chars
        self.char_handler = {self.chars[0]:self.increase_field,
                            self.chars[1]:self.decrease_field,
                            self.chars[2]:self.increase_pointer,
                            self.chars[3]:self.decrease_pointer,
                            self.chars[4]:self.loop_begin,
                            self.chars[5]:self.loop_end,
                            self.chars[6]:self.printchar,
                            self.chars[7]:self.readchar}
                                
                      
    def reset(self):
        """
        This method resets all variables that have to be resetted to work
        corretly with any other Brainfuck-Code
        """
        self.array = [0] * self.arraysize
        self.pointer = 0
        
    def readchar(self, num):
        """
        This method reads the character from the input and checks if it is
        a valid value.
        Brainfuck character: ,
        """
        if int(num) < self.fieldsize and int(num) >= 0:
            self.array[self.pointer] = int(num)
            return True
        else:
            raise NumError()

    def printchar(self):
        """
        Prints the ASCII-Code for the field of self.array that self.pointer
        points at.
        Brainfuck character: .
        """
        return chr(self.array[self.pointer])
    
    def increase_field(self):
        """
        Increases the field of self.array that self.pointer points at by one.
        Brainfuck character: +
        """
        if self.array[self.pointer] < self.fieldsize - 1:
            self.array[self.pointer] += 1
        else:
            self.array[self.pointer] = 0

    def decrease_field(self):
        """
        Decreases the field of self.array that self.pointer points at by one.
        Brainfuck character: -
        """
        if self.array[self.pointer] > 0:
            self.array[self.pointer] -= 1
        else:
            self.array[self.pointer] = self.fieldsize - 1

    def increase_pointer(self):
        """
        Increases selt.pointer by one.
        Brainfuck character: >
        """
        if self.pointer < self.arraysize - 1:
            self.pointer += 1
        else:
            self.pointer = 0

    def decrease_pointer(self):
        """
        Decreases selt.pointer by one.
        Brainfuck character: <
        """
        if self.pointer > 0:
            self.pointer -= 1
        else:
            self.pointer = self.arraysize - 1

    def loop_begin(self, i):
        """
        This is called when a loop is starting (or not if the field is 0)
        Brainfuck character: [
        """
        if self.array[self.pointer] == 0:
            # this will find the matching loop-end for this loop-begin
            x = 0
            while i <= (len(self.code)):
                if self.code[i] == self.chars[4]:  # char 4 = [
                    x += 1
                elif self.code[i] == self.chars[5]:  # char 5 = ]
                    x -= 1
                    if x <= 0:
                        return i
                i += 1
        else:
            self.loops.append(i)
            return i
        

    def loop_end(self, i):
        """
        This is called when the endloop-character is found
        Brainfuck character: ]
        """
        if self.array[self.pointer] == 0:
            self.loops.pop()
            return i
        else:
            x = self.loops.pop()
            self.loops.append(x)
            return x
        

    def run(self):
        """
        This runs the Brainfuck-Code and returns it's output
        """
        output = ""
        i = 0
        while i < len(self.code):
            character = self.code[i]
            if character in self.char_handler:
                if character == self.chars[4]:
                    i = self.char_handler[self.chars[4]](i)
                elif character == self.chars[5]:
                    i = self.char_handler[self.chars[5]](i)
                elif character == self.chars[6]:
                    output += self.char_handler[self.chars[6]]()
                elif character == self.chars[7]:
                    while True:
                        try:
                            print "Input required"
                            self.char_handler[self.chars[7]](int(raw_input()))
                            break
                        except ValueError:
                            print "Please, enter a number!"
                        except NumError:
                            print "Number has to be between including 0 and " + str(self.fieldsize-1)
                else:  
                    self.char_handler[character]()
                        
            i += 1
        if output != "":
            print output

            


# Beispiel
if __name__ == '__main__': 
    bf = Brainfuck(30)
    while True:
        try:
            code = ""
            read = ""
            print "Enter brainfuck code"
            while not read == "/code":
                read = raw_input()
                code += read
            bf.code = code
            bf.check_syntax()
            break
        except BFSyntaxError:
            print "Your Code is incorrect, check the syntax"
    bf.run()
An's Ende hab ich mal eine simple UI geschrieben (auf die Schnelle gemacht), damit sich das besser benutzen und testen lässt.
Sobald ihr eine neue Zeile mit /code eingebt, ist die Codeeingabe beendet und der Code wird ausgeführt.

Edit: Code nach dem Vorschlag, ein Dictionary (self.handle_chars) für die Funktionsaufrufe in run() zu benutzen
Zuletzt geändert von Karl am Donnerstag 12. Juni 2008, 18:24, insgesamt 3-mal geändert.
Leonidas
Python-Forum Veteran
Beiträge: 16025
Registriert: Freitag 20. Juni 2003, 16:30
Kontaktdaten:

Zur Methode ``run`` fällt mir eines ein: Dictionaries existieren.
My god, it's full of CARs! | Leonidasvoice vs (former) Modvoice
Karl
User
Beiträge: 252
Registriert: Freitag 29. Juni 2007, 17:49

Leonidas hat geschrieben:Zur Methode ``run`` fällt mir eines ein: Dictionaries existieren.
Du meinst anstatt self.char[5] sollte ich self.char[']'] benutzen?
Auf die Idee bin ich komischerweise gar nicht gekommen.
Dann wäre der Code noch ein Stück selbsterklärender :)
rayo
User
Beiträge: 773
Registriert: Mittwoch 5. November 2003, 18:06
Wohnort: Schweiz
Kontaktdaten:

Nein er meint das nicht so.

Eher sowas:

Code: Alles auswählen

def set_chars(self):
    self.char_handler = {'+': self.increase_field, '-': self.decrease_field, ...}               
und dann bei der while i < len(self.code): anstatt der vielen Ifs einfach

Code: Alles auswählen

self.char_handler[character]()
Gruss
Karl
User
Beiträge: 252
Registriert: Freitag 29. Juni 2007, 17:49

Ahh! Das ist echt um einiges einfacher :)
Cool, wusste gar nicht, dass sowas geht.

Aber wie soll ich zB folgendes durch dieses Prinzip ersetzen:

Code: Alles auswählen

elif character == self.chars[4]:  # char 4 = [
                i = self.loop_begin(i)
?

Edit: Ich hab das jetzt mal so abgeändert, ich änder das auch gleich im 1. Post, aber viel übersichtlicher wird's dadurch auch nicht :p Kürzer aber schon ;)
Benutzeravatar
Hyperion
Moderator
Beiträge: 7478
Registriert: Freitag 4. August 2006, 14:56
Wohnort: Hamburg
Kontaktdaten:

Hallo,

Du könntest die ganzen decrease / increase Methoden zusammenfassen oder zumindest vereinfachen, indem Du den modulo-Operator nutzt:

Code: Alles auswählen

array_size = 10
def change_pointer(pointer, step):
    return (pointer + step) % array_size

pointer = 6
pointer = change_pointer(pointer, 1)
print pointer
pointer = change_pointer(pointer, 5)
print pointer
pointer = change_pointer(pointer, -13)
print pointer
Das sollte Deinen Code weiter entschlacken.
Y0Gi
User
Beiträge: 1454
Registriert: Freitag 22. September 2006, 23:05
Wohnort: ja

Bei den ersten beiden Klassen: Leerzeilen zwischen die Methoden!

In der Methode `readchar`: Warum `True` zurückgeben? Wenn sowieso sonst nichts zurückgegeben wird, brauchst du gar nichts zurückgeben und fängst im aufrufenden Code einfach nur eventuelle Exceptions ab.
Schattenbringer1
User
Beiträge: 9
Registriert: Mittwoch 4. Juni 2008, 16:34

Schön. Was du gemacht hast gefällt mir recht gut.

ich habe die tage auch mal ein BF interpreter geschrieben. Allerdings in c++. Also 99 Bottles of beer geht mit deinem schonmal Fehlerfrei.
Also hab ich mit diesem Programm einen Test gemacht, wie schnell das läuft. Dazu habe ich dein Programm so geändert, dass es aus einer Datein liest und das 30000 Zellen benutzt werden.

hier das Ergebnis:

Code: Alles auswählen

c++:
real	0m0.002s
user	0m0.001s
sys	0m0.000s

python:
real	0m0.351s
user	0m0.349s
sys	0m0.002s

python mit psyco:
real	0m0.090s
user	0m0.085s
sys	0m0.003s

um mir noch Feinde zu machen, der perl brainfuck interpreter von einen kumpel:
real	0m0.177s
user	0m0.117s
sys	0m0.005s

Dachte das interresiert dich vllt.
zu meinem c++ code muss man sagen, dass er schlicht HÄSSLICH ist, weil ich ihn recht heftig optimiert haben. Für den perlcode gilt gleiches.


Schlussfolgerung:
quäle dich mit c++ rum, oder wenn dir preformance recht egal ist, nutze psyco.


Nicht das das jetzt irgentwer als hassrede gegen python versteht. Ist nur das was ich herausgefunden habe. Falls interresse besteht kann ich alles bis auf den perl interpreter posten.
[/code]
Karl
User
Beiträge: 252
Registriert: Freitag 29. Juni 2007, 17:49

Hyperion hat geschrieben:Hallo,

Du könntest die ganzen decrease / increase Methoden zusammenfassen oder zumindest vereinfachen, indem Du den modulo-Operator nutzt:

Code: Alles auswählen

array_size = 10
def change_pointer(pointer, step):
    return (pointer + step) % array_size

pointer = 6
pointer = change_pointer(pointer, 1)
print pointer
pointer = change_pointer(pointer, 5)
print pointer
pointer = change_pointer(pointer, -13)
print pointer
Das sollte Deinen Code weiter entschlacken.
Okay, das ist ne Idee ;)
Ich weiß nicht, wenn ich alle eure Ideen umgesetzt hab, ist der Code wahrscheinlich so minimal, dass man gar nicht mehr sieht, was eigentlich gemacht wird :p
Ich hatte gar nicht darüber nachgedacht, die increament und decreament Methoden zusammenzufassen, weil ich nur "1 Befehl eine Methode" im Kopf hatte. Aber eigentlich schon sinnvoller als meine if-else Zweige da :)
Das ändere ich dann demnächst mal.
Y0Gi hat geschrieben:Bei den ersten beiden Klassen: Leerzeilen zwischen die Methoden!

In der Methode `readchar`: Warum `True` zurückgeben? Wenn sowieso sonst nichts zurückgegeben wird, brauchst du gar nichts zurückgeben und fängst im aufrufenden Code einfach nur eventuelle Exceptions ab.
Okay, die ersten beiden Klassen hab ich eigentlich nur hier irgendwo aus'm Forum kopiert und den Namen angepasst :p Du hast natürlich Recht, eine Leerzeile macht das ganze viel leichter zu lesen.
Warum ich True zurückgebe? Ist wohl Gewohnheit. Irgendwann hab ich mir mal in irgendeiner Sprache angewöhnt, immer irgendetwas zurückzugeben. Macht natürlich hier keinen Sinn :) Wobei es bei komplizierteren Funktionen auch irgendwo den Code übersichtlicher macht, wenn man sieht "Ah okay, dieser Zweig hier ist der 'richtige'". Naja, jedenfalls ist das return eigentlich Sinnlos :p
Schattenbringer1 hat geschrieben:Schön. Was du gemacht hast gefällt mir recht gut.

ich habe die tage auch mal ein BF interpreter geschrieben. Allerdings in c++. Also 99 Bottles of beer geht mit deinem schonmal Fehlerfrei.
Also hab ich mit diesem Programm einen Test gemacht, wie schnell das läuft. Dazu habe ich dein Programm so geändert, dass es aus einer Datein liest und das 30000 Zellen benutzt werden.

hier das Ergebnis:

Code: Alles auswählen


c++:
real    0m0.002s
user    0m0.001s
sys    0m0.000s

python:
real    0m0.351s
user    0m0.349s
sys    0m0.002s

python mit psyco:
real    0m0.090s
user    0m0.085s
sys    0m0.003s

um mir noch Feinde zu machen, der perl brainfuck interpreter von einen kumpel:
real    0m0.177s
user    0m0.117s
sys    0m0.005s
Dachte das interresiert dich vllt.
zu meinem c++ code muss man sagen, dass er schlicht HÄSSLICH ist, weil ich ihn recht heftig optimiert haben. Für den perlcode gilt gleiches.


Schlussfolgerung:
quäle dich mit c++ rum, oder wenn dir preformance recht egal ist, nutze psyco.


Nicht das das jetzt irgentwer als hassrede gegen python versteht. Ist nur das was ich herausgefunden habe. Falls interresse besteht kann ich alles bis auf den perl interpreter posten.
Sorry, aber ich finde deinen Post ist hier recht Fehl am Platz.
Jeder hier weiß, dass C++ schneller als Python ist. Jeder weiß, dass Python nicht auf Geschwindigkeit optimiert ist. Genau das soll Python ja auch sein: Du sagst, dein Code ist hässlich. Meiner ist schön ;) Auch wenn man das ganze bestimmt noch schöner gestalten kann :p
Deine Schlussfolgerung ist richtig, aber wenn jemand Python benutzt, ist er glaube ich auch schon zu dieser Schlussfolgerung gelangt :) Aber performance ist mir nicht nur "recht" egal sondern total egal, solange das ganze in einer annehmbaren Zeit abläuft. Und das tun Python Programme imo in fast jedem Gebiet.
Aber trotzdem finde ich deinen Test interessant, um den Vergleich zu sehen. Psyco scheint wohl ne gute Sache zu sein. Und dass C++ Keine-Ahnung-Wie-Viel schneller ist, war eh klar :D
sma
User
Beiträge: 3018
Registriert: Montag 19. November 2007, 19:57
Wohnort: Kiel

Das Posting hat mich inspiriert, einen kleinen Brainfuck-Compiler zu schreiben. Ich musste 2 Funktionen benutzen, weil es offenbar nicht möglich ist, `exec` in einer Funktion zu benutzen, die lokale Funktionen hat...

Code: Alles auswählen

def compile_brainfuck(src):
    program = ["def bf():", " import sys", " cells, ptr = [0] * 1000, 0"]
    indent = 1
    def emit(line): program.append(" " * indent + line)
    for s in src:
        if s == ">": emit("ptr += 1")
        elif s == "<": emit("ptr -= 1")
        elif s == "+": emit("cells[ptr] += 1")
        elif s == "-": emit("cells[ptr] -= 1")
        elif s == ".": emit("sys.stdout.write(chr(cells[ptr]))")
        elif s == ",": emit("cells[ptr] = ord(sys.stdin.read(1))")
        elif s == "[": emit("while cells[ptr]:"); indent += 1
        elif s == "]": emit("pass"); indent -= 1
    indent -= 1; emit("bf()")
    return "\n".join(program)
    
def run_brainfuck(src): exec compile_brainfuck(src)
Das Hallo-Welt-Beispiel aus der Wikipedia läuft bei mir in 0.03s.

Stefan
Karl
User
Beiträge: 252
Registriert: Freitag 29. Juni 2007, 17:49

@sma
Klar geht es kleiner :) Brainfuck wurde ja auch mit dem Ziel entwickelt, einen möglichst kleinen Compiler zu haben. Der originale (1.) Compiler ist irgendwas zwischen 200-300 Bytes groß, allerdings in C.
Aber kann's sein, dass dein Code nicht so 100%ig funktioniert?
Zum Beispiel dieser Brainfuckcode funktioniert nicht:

Code: Alles auswählen

,->,>+>>+<<<[>>>[<<<<+>>>>-]<<[-]<<[>>+<<-[>>>>+<<<<-]]>-]>[++++++.[-]]
Liegt wohl am read, also dem Komma. Wenn ich statt die Zeichen einzulesen manuell welche in den Code einbaue, funktioniert's ;) Also guck dir das einfach nochmal an.
sma
User
Beiträge: 3018
Registriert: Montag 19. November 2007, 19:57
Wohnort: Kiel

Karl, mir ging es nicht so sehr um die Größe, als um die Idee, das BF-Programm zu "kompilieren" statt es einfach zu interpretieren. Das mein Code kürzer war, ist nur ein angenehmer Seiteneffekt. Ein direkter Interpreter wäre noch kleiner.

Du sagst, dein Beispielprogramm läuft bei mir nicht. So wie ich den Wikipedia-Artikel verstehe, hast aber du den ","-Befehl falsch implementiert. Da steht ASCII-Wert speichern (also `ord`), nicht die Zahl, für die eine eingelesene Ziffernfolge steht (`int`) so wie du das implementiert hast. Was soll das Programm denn machen?

Ich biete an, dass diese 99-Bottles-of-Beer Version bei mir läuft, während dein Interpreter leider irgendwie hängt. Liegt es an den vielen Kommentaren zwischen dem Code? Um das Problem zu finden, fehlt mir ein guter Debugger. Das Programm hängt in einer Schleife, glaube ich.

Der Text wird in 130ms nach /dev/null gechrieben (1,6GHz Core Duo).

Stefan
mitsuhiko
User
Beiträge: 1790
Registriert: Donnerstag 28. Oktober 2004, 16:33
Wohnort: Graz, Steiermark - Österreich
Kontaktdaten:

sma hat geschrieben:Das Posting hat mich inspiriert, einen kleinen Brainfuck-Compiler zu schreiben. Ich musste 2 Funktionen benutzen, weil es offenbar nicht möglich ist, `exec` in einer Funktion zu benutzen, die lokale Funktionen hat...
Natürlich nicht. Python markiert Variablen, die in Closures verwendet werden, damit der GC/das Refcounting nicht verwendete aufräumen kann. Weil ein Scope, in dem du exec nutzt speziell markiert wird geht dort diese Fähigkeit verloren. In einem Scope mit einem exec Statement werden alle Namen mit LOAD_NAME geladen, im Gegensatz zu normalen Scopes wo es LOAD_FAST und LOAD_GLOBAL gibt, also zur compile-time feststeht, welcher Name von wo kommt.

Da dir der Namespace aber egal ist, mach doch sowas:

Code: Alles auswählen

import sys

def run_brainfuck(src):
    program = []
    indent = 0
    def emit(line): program.append(" " * indent + line)
    for s in src:
        if s == ">": emit("ptr += 1")
        elif s == "<": emit("ptr -= 1")
        elif s == "+": emit("cells[ptr] += 1")
        elif s == "-": emit("cells[ptr] -= 1")
        elif s == ".": emit("sys.stdout.write(chr(cells[ptr]))")
        elif s == ",": emit("cells[ptr] = ord(sys.stdin.read(1))")
        elif s == "[": emit("while cells[ptr]:"); indent += 1
        elif s == "]": emit("pass"); indent -= 1
    exec "\n".join(program) in {'sys': sys, 'cells': [*] * 1000, 'ptr': 0}
TUFKAB – the user formerly known as blackbird
Karl
User
Beiträge: 252
Registriert: Freitag 29. Juni 2007, 17:49

sma hat geschrieben:Karl, mir ging es nicht so sehr um die Größe, als um die Idee, das BF-Programm zu "kompilieren" statt es einfach zu interpretieren. Das mein Code kürzer war, ist nur ein angenehmer Seiteneffekt. Ein direkter Interpreter wäre noch kleiner.

Du sagst, dein Beispielprogramm läuft bei mir nicht. So wie ich den Wikipedia-Artikel verstehe, hast aber du den ","-Befehl falsch implementiert. Da steht ASCII-Wert speichern (also `ord`), nicht die Zahl, für die eine eingelesene Ziffernfolge steht (`int`) so wie du das implementiert hast. Was soll das Programm denn machen?

Ich biete an, dass diese 99-Bottles-of-Beer Version bei mir läuft, während dein Interpreter leider irgendwie hängt. Liegt es an den vielen Kommentaren zwischen dem Code? Um das Problem zu finden, fehlt mir ein guter Debugger. Das Programm hängt in einer Schleife, glaube ich.

Der Text wird in 130ms nach /dev/null gechrieben (1,6GHz Core Duo).

Stefan
Hmm, ich habe das Ganze so verstanden, dass der int-Wert des ASCII-Zeichens gespeichert wird (was in meinen Augen auch am meisten Sinn macht). Naja im Prinzip auch völlig egal, da es gleich ist, ob man den HEX-Wert, den ASCII-Wert oder sonst was speichert, kommt ja auf's selbe hinaus. Sind ja nur andere Schreibweisen ;)
Ich habe bei dir einfach mal 2 Zahlen getestet, die hätten eigentlich in jedem Fall (ob du jetzt den HEX-Wert, den ASCII-Wert, einen int-Wert, oder sonstwas einliest) funktionieren müssen. Vielleicht hab ich aber trotzdem irgendwas falsch gemacht, keine Ahnung. Ich hab auch gerade keinen PC mit einem Python Interpreter zur Hand um das nochmal zu testen.
Daher hab ich auch keine Ahnung, ob der 99 Bottles of beer Code läuft, aber bisher lief bei mir jeder Code korrekt, ob mit oder ohne Kommentare. Naja das schau ich mir heute Abend vielleicht nochmal an ;)
Wobei Schattenbringer1 in seinem Post sagte, er hätte 99 Bottles of beer getestet.
Muss ich heute Abend nochmal schaun :)
Karl
User
Beiträge: 252
Registriert: Freitag 29. Juni 2007, 17:49

Okay, bei dem Code scheint mein Programm echt in einer Schleife zu hängen.
Ich hatte jetzt keine Lust, das richtig zu debuggen, ich hab einfach mal i während der Schleife ausgegeben, womit ich festgestellt habe, dass immer von Zeichen 3127 zu 3128 (oder so) und zurück gesprungen wird, was bedeutet, dass mein Code einen Fehler hat :o Nur hab ich keine Ahnung welchen, da das ganze ansonsten einwandfrei funktioniert und auch mit verschachtelten Schleifen nie Probleme gehabt hat.
Da denkt man, man hat einen fehlerfreien Code und dann ... :(
sma
User
Beiträge: 3018
Registriert: Montag 19. November 2007, 19:57
Wohnort: Kiel

@mitsuhiko, jetzt habe ich endlich den Sinn von LOAD_NAME verstanden. Danke. Deine Lösung ist natürlich nochmal besser als meine.

Stefan
Antworten