Wie ich mir in Python einen Interpreter für Factor baue

Gute Links und Tutorials könnt ihr hier posten.
sma
User
Beiträge: 3018
Registriert: Montag 19. November 2007, 19:57
Wohnort: Kiel

Wie ich mir in Python einen Interpreter für Factor baue

Beitragvon sma » Sonntag 11. Januar 2009, 10:57

sma hat geschrieben:Ich hatte vor einigen Wochen eine Art Tutorial geschrieben, wie man einen Interpreter für die Programmiersprache Factor in Python bauen kann. Zu viel Codeabschnitte in einem Artikel töten ja bekanntlich dieses Forum, daher versuche ich als Workaround mal, das ganze in vielen kleinen Artikel zerteilen. Viel Spaß. Kommentare sind willkommen.


Factor ist eine Forth-artige Programmiersprache, die konkatenativ ist, d.h. man reiht Befehlswörter aneinander, die Daten auf einem Stack verarbeiten. Im Gegensatz zum klassischen sehr maschinennahen Forth unterstützt Factor (wie Joy, einem der Vorbilder) funktionale und objektorientierte Programmierung (die von CLOS, dem CommonLisp-Objektsystem, abgeschaut ist) und ist eine sehr ungewöhnliche und interessante Programmiersprache.

Factor-Programme bestehen aus Wörtern, die durch Leerzeichen getrennt sind: `3 4 + .`.

Dies addiert (`+`) die Zahlen 3 und 4 und gibt das Ergebnis aus (`.`). Operatoren folgen den Operanden.

Ich baue schrittweise einen Factor-Interpreter in Python, der obigen Code ausführen kann.

Ich beginne mit einem Objekt, das einen String in Wörter zerlegen kann:

Code: Alles auswählen

class Lexer(object):
    def __init__(self, s):
        self.s, self.t = s, None

    def skip(self):
        self.s = self.s.lstrip()

    def readuntil(self, end):
        self.t, self.s = self.s.split(end, 1) if end in self.s else (self.s, "")

    def next(self):
        self.skip()
        if self.s:
            self.readuntil(" ")
            return True

l = Lexer("3 4  + .")
while l.next():
    print l.t


Dies gibt `3`, `4`, `+` und `.` aus und erkennt somit die einzelnen Wörter.
sma
User
Beiträge: 3018
Registriert: Montag 19. November 2007, 19:57
Wohnort: Kiel

Beitragvon sma » Sonntag 11. Januar 2009, 10:59

Um das Beispielprogramm `3 4 + .` auszuführen, übersetze ich es in eine Folge von Python-Funktionen (einen so genannten "threaded code"), die ich dann der Reihe nach aufrufe. Ich suche dazu zu jedem Wort, das der `Lexer` erkennt hat, ein Funktionsobjekt aus einem Wörterbuch heraus. Finde ich nichts und sieht das Wort wie eine Zahl aus, dann sei das so.

Code: Alles auswählen

class Factor(object):
    def parseuntil(self, t):
        data = []
        while self.lexer.next() and self.lexer.t != t:
            try:
                func = self.vocab[self.lexer.t]
            except KeyError, ex:
                try:
                    func = int(self.lexer.t)
                except ValueError:
                    raise ex
            data.append(func)
        return data
   
    def parse(self, s):
        self.lexer = Lexer(s)
        return self.parseuntil("")

# some stubs to test the parser
Factor.vocab = {
    '+': "add",
    '.': "emit",
}
print Factor().parse("3 4 + .")


Dies gibt `[3, 4, 'add', 'emit']` aus.
sma
User
Beiträge: 3018
Registriert: Montag 19. November 2007, 19:57
Wohnort: Kiel

Beitragvon sma » Sonntag 11. Januar 2009, 11:02

Die Strings mit doppelten Anführungszeichen in `Factor.vocab` waren Platzhalter für die primitiven Operationen, die ich in Python schreiben muss. Hier kommt ein Mechanismus, wie ich sie automatisch registrieren kann:

Code: Alles auswählen

class Factor...
    vocab = {}
   
    @classmethod
    def op(cls, name, parsing=False):
        def _(func):
            cls.vocab[name] = func
            func.parsing = parsing
            return func
        return _

@Factor.op("+")
def add(f): f.push(f.pop() + f.pop())

@Factor.op(".")
def emit(f): print f.pop()

print Factor().parse("3 4 + .")


Dies gibt `[3, 4, <function add at ...>, <function emit at ...>]` aus.
sma
User
Beiträge: 3018
Registriert: Montag 19. November 2007, 19:57
Wohnort: Kiel

Beitragvon sma » Sonntag 11. Januar 2009, 11:05

Der Interpreter hat einen Stack, der alle Zwischenergebnisse zur Berechnung speichert. Mit `push` schiebt Objekte auf den Stack, die mit `pop` in umgekehrter Reihenfolge wieder gelesen werden können.

`parse` erzeugt aus einem Factor-Programm eine Liste mit Zahlen und Funktionen. Ich führe das Programm aus, indem ich jede Funktion der Liste ausführe. Damit ich keine spezielle Behandlung der Zahlen vornehmen muss, "compiliere" ich diese mittels `literalize` in konstante Funktionen, die diese Zahlen auf den Stack schreiben.

Code: Alles auswählen

class Factor...
    def __init__(self):
        self.stack = []
   
    def push(self, value): self.stack.append(value)
   
    def pop(self): return self.stack.pop()
   
    def quotate(self, funcs):
        return [literize(func) for func in funcs]
   
    def execute(self, s):
        for func in self.quotate(self.parse(s)):
            func(self)

def literize(value):
    return value if callable(value) else lambda f: f.push(value)

Factor().execute("3 4  + .")


Führt man den Python-Code jetzt aus, sollte `7` ausgegeben werden.

Das erste Wort aus der Eingabe wird erst durch `parse` zu einem `int`, danach in `quotate` mit Hilfe von `literize` zu einer Funktion, die das Objekt 3 mittels `push` auf den Stack des Interpreters schiebt. Beim zweiten Wort passiert das selbe für 4. Zu `+` wird die Python-Funktion `add` gefunden, die dann zwei Zahlen vom Stack addiert und das Ergebnis wieder auf den Stack schreibt. Dies ist genau, was `.` erwartet, welches zu `emit` wird, was dann die Zahl vom Stack ausgibt.

Der Factor-Interpreter ist fertig... fast jedenfalls :)
sma
User
Beiträge: 3018
Registriert: Montag 19. November 2007, 19:57
Wohnort: Kiel

Beitragvon sma » Sonntag 11. Januar 2009, 11:10

Fügen wir eine neue Operation hinzu: `dup`.

Code: Alles auswählen

@Factor.op("dup")
def dup(f): f.push(f.stack[-1])

Factor().execute("3 4  + dup + .")


Dies gibt `14` aus.

`dup` hat den so genannten "stack effect" `( x -- x x )`, was bedeuten soll, dass vor dem Aufruf ein Element auf dem Stack erwartet wird und nach dem Aufruf der Operation dieses Element zweimal auf dem Stack steht. Derartige Kommentare (denn die Klammern sind eine Syntax für Kommentare in Factor) gelten als guter Stil bei eigenen Wörtern.

Der "stack effect" für `+` lautet `( y x -- x+y )`.

Schauen wir uns an, wie Kommentare in der Eingabe verarbeitet werden.

Lese ich die Eingabe `3 4 ( y x -- x+y ) +` Wort für Wort ein, komme ich auch zu `(` (daher ist das Leerzeichen hinter der öffnenden Klammer sehr wichtig), welches nun dazu führen soll, das alle Zeichen bis einschließlich `)` übersprungen werden sollen. Wie für `+` und `.` will ich eine Funktion für `(` im Wörterbuch registrieren.

Statt die Funktion einfach in `funcs` zu speichern, will ich diese aber sofort ausführen. `(` ist daher ein "parsing word", ein Wort, das während der Übersetzung ausgeführt wird.

So wird es definiert:

Code: Alles auswählen

@Factor.op("(", parsing=True)
def comment(f): f.lexer.readuntil(")")


Und so erweitere ich meinen Interpreter um die Verarbeitung von "parsing words":

Code: Alles auswählen

class Factor...
    def parseuntil(self, t):
        ...
                func = self.vocab[self.lexer.t]
                if func.parsing: func(self); continue
        ...

Factor().execute("3 4  ( y x -- x+y ) + ( print it).")

Wir sehen wie gewohnt `7`. Die Kommentare werden ignoriert.
sma
User
Beiträge: 3018
Registriert: Montag 19. November 2007, 19:57
Wohnort: Kiel

Beitragvon sma » Sonntag 11. Januar 2009, 11:14

Ein neues Wort definiert man so: `: twice ( x -- 2x ) dup + ;`.

Das Wort `:` leitet die Definition eines eigenen Worts ein. Es muss zur Übersetzungszeit ausgeführt werden. Beendet wird die Definition mit `;`. Dieses Wort erzeugt "freistehend" einen Fehler und begrenzt nur `:`.

Ich führe eine Klasse `Word` ein, die wie die primitiven Operationen (die ja Python-Funktionen sind) "callable" ist. Ein `Word` speichert die Liste der Funktionen, die `parseuntil` zusammenstellt als `code`:

Code: Alles auswählen

@Factor.op(":", parsing=True)
def define(f):
    f.lexer.next()
    f.vocab[f.lexer.t] = f.word = Word()
    f.word.code = f.quotate(f.parseuntil(";"))

class Word(object):
    parsing = False
    def __call__(self, f):
        for func in self.code: func(f)

Factor().execute(": twice ( x -- 2x ) dup + ; 9 12 + twice .")


Die letzte Zeile sollte `42` ausgegeben haben.
sma
User
Beiträge: 3018
Registriert: Montag 19. November 2007, 19:57
Wohnort: Kiel

Beitragvon sma » Sonntag 11. Januar 2009, 11:29

Ich kann auch eigene "parsing words" definieren (tatsächlich ist `:` und der gesamte Lexer und Parser, die ich hier in Python geschrieben habe, beim echten Factor in Factor selbst definiert), indem ich das `parsing` dem `;` folgen lasse:

Code: Alles auswählen

@Factor.op("parsing", parsing=True)
def parsing(f): f.word.parsing = True


So könnte `:` definiert sein:

Code: Alles auswählen

: : ( -- ) next create-word " ;" parseuntil >quotation define-word ; parsing

: next ( -- str ) P{{ f.lexer.next(); f.push(f.lexer.t) }} ;
: create-word ( str -- ) P{{ f.vocab[f.pop()] = f.word = Word() }} ;
: " ( -- str ) P{{ f.lexer.readuntil('"'); f.push(f.lexer.t) }} ; parsing
: parseuntil ( str -- seq ) P{{ f.push(f.lexer.parseuntil(f.pop())) }} ;
: >quotation ( seq -- quot ) P{{ f.push(f.quotate(f.pop())) }} ;
: define-word ( quot -- ) P{{ f.word.code = f.pop() }} ;


Problem hierbei: Wenn ich `:` definieren will, kann ich es nicht gleichzeitig dabei benutzen. Factor löst das Problem, dass man einen Factor-Interpeter braucht, der Factor-Quelltext in Maschinencode übersetzt und das dann einen neuen Factor-Interpreter erzeugt. Das habe ich leider nicht. Daher bleibe ich notgedrungen bei meiner Python-Implementierung von `:`.

Ansonsten würde ich aber schon gerne so viel wie möglich in Factor implementieren und möchte daher das "parsing word" `P{{` implementieren. Dieses Wort erlaubt es, eine primitive Operation mit dem entsprechenden Python-Code bis `}}` zu definieren.

Ich muss dazu an `data` von `parseuntil` herankommen, welches ich daher auf den Stack schiebe. Dann kann ich den Python-Code (der kein `}}` enthalten darf) zur Übersetzungszeit einlesen, zu einer Funktion machen und diese zur Liste der Funktionen bzw. Literale hinzufügen, die somit das oberste Stackelement ist:

Code: Alles auswählen

class Factor...
    def parseuntil(self, t):
        self.push([])
        ...
            self.stack[-1].append(func)
        return self.pop()

@Factor.op("P{{", parsing=True)
def python(f):
    f.lexer.readuntil("}}")
    exec "def primitive(f): %s" % f.lexer.t
    f.stack[-1].append(locals()['primitive'])
   
Factor().execute(": swap ( x y -- y x ) P{{ f.push(f.stack.pop(-2)) }} ; 3 4 swap . .")


Der Code gibt erst 3, dann 4 aus, nachdem die beiden Zahlen auf dem Stack vertauscht wurden.
sma
User
Beiträge: 3018
Registriert: Montag 19. November 2007, 19:57
Wohnort: Kiel

Beitragvon sma » Sonntag 11. Januar 2009, 11:36

Zurück zu der Beispielimplementierung von `:`:

Das Wort `next` liest das nächste Wort über den Lexer ein und schreibt es auf den Stack. Es berücksichtigt allerdings nicht, dass es kein solches Wort geben könnte. `next` wäre einfacher, wenn das Lexer-Objekt ebenfalls den Factor-Stack zur Rückgabe benutzen würde und nicht Pythons eigenen Mechanismus mit `return`. Es entspricht damit der ersten Zeile Python-Code von `define`.

`create-word` entspricht der zweiten Zeile von `define`. Es erzeugt ein neues Word-Objekt mit den Namen, der auf dem Stack steht (und dort von `next`) hingeschrieben wurde.

Das Wort `"` definiert eine String-Konstante. Zu beachten ist, dass hinter dem `"` ein Leerzeichen kommen muss, welches das `"` beendet bevor dann alles bis zum nächsten `"` als String gelesen und auf den Stack geschoben wird. Der leere String schreibt sich damit `" "`.

Mit `parseuntil` wird nun der Factor-Parser aufgerufen. Dies entspricht dem innersten Ausdruck der dritten Zeile von `define`. Auf dem Stack landet eine Liste mit Funktionsobjekten bzw. Zahlen oder anderen Konstanten, wenn man sie z.B. wie mit `"` definiert. Diese Liste wird mit `>quotation` nun derart bearbeitet, dass alle Konstanten zu Funktionen werden, die diese Konstanten auf den Stack schreiben. Dies entspricht dem äußeren Ausdruck in Zeile 3 von `define`.

Schließlich weist `define-word` die so erzeugte Liste dem `code`-Attribut des neu erzeugten Worts zu und definiert es auf diese Weise. Doch nun mehr zu den Listen.

Die Python-Funktionen der Klasse `Factor` sollten eigentlich alle in Factor definiert werden. Der Übergang von Python-Konvention, Objekte mittels `return` an den Aufrufer zurückzugeben und die Factor-Konvention, die Objekte auf dem einen Stack zu lagern, machen die oben definierten primitiven Operationen unnötig umständlich. Bislang kann ich aber keine Bedingungen oder Schleifen in Factor ausdrücken.
sma
User
Beiträge: 3018
Registriert: Montag 19. November 2007, 19:57
Wohnort: Kiel

Beitragvon sma » Sonntag 11. Januar 2009, 11:42

Factor kennt neben Worten, Zahlen und Zeichenketten noch zwei Mengentypen: Sequenzen und Quotations.

Sequenzen sind Literale in `{ ... }`, die dann als Liste auf den Stack geschoben werden:

Code: Alles auswählen

@Factor.op("{", parsing=True)
def sequence(f): f.stack[-1].append(f.parseuntil("}"))

Factor().execute("{ 1 2 3 } .")


Darauf kann man jetzt die üblichen primitiven Operationen implementieren:

Code: Alles auswählen

Factor.execute("""
: nth ( n seq -- elt ) P{{ seq, n = f.pop(), f.pop(); f.push(seq[n]) }} ;
: set-nth ( elt n seq -- ) P{{ seq, n = f.pop(), f.pop(); seq[n] = f.pop() }} ;
: subseq ( frm to seq -- subseq ) P{{ seq, to, frm = f.pop(), f.pop(), f.pop(); f.push(seq[frm:to]) }} ;
: length ( seq -- n ) P{{ f.push(len(f.pop())) }} ;
: push ( elt seq -- ) P{{ f.pop().append(f.pop()) }} ;
: pop ( seq -- elt ) P{{ f.push(f.pop().pop()) }} ;
: first ( seq -- elt ) 0 swap nth ;
: rest ( seq -- subseq ) 1 swap dup length swap subseq ;
""")


Dies überlasse ich dem Leser. Auch `f.stack[-1].append` könnte man besser abstrahieren. Eine alternative Implementierung von `{` wäre dann diese:

Code: Alles auswählen

: { ( -- seq ) " }" parseuntil >code ; parsing
: >code P{{ f.stack[-2].append(f.pop()) }} ;
sma
User
Beiträge: 3018
Registriert: Montag 19. November 2007, 19:57
Wohnort: Kiel

Beitragvon sma » Sonntag 11. Januar 2009, 12:00

Kommen wir zu Quotations. Das sind in `[ ... ]` eingeschlossene Wörter, die erst dann ausgeführt werden, wenn `call` für so ein Objekt auf dem Stack aufgerufen wird. Beispiel: `[ 3 4 + ] call .` Sie entsprechen einem "lambda" oder "block" anderer Programmiersprachen.

Ich repräsentiere sie wie Sequenzen als eigene Klasse:

Code: Alles auswählen

class Quotation(list):
    def call(self, f):
        for func in self: func(f)
       
Factor().execute("""
: [ ( -- quot ) P{{ f.stack[-1].append(Quotation(f.quotate(f.parseuntil("]")))) }} ; parsing
: call ( quot -- ) P{{ f.pop().call(f) }} ;
[ 3 4 + ] call .
""")


Zusammen mit den Wörtern von `:` könnte man `[` auch direkt in Factor implementieren - wie es im Original natürlich auch passiert. Erneut sieht man, dass der Kern der Sprache extrem kompakt ist und keine feste Syntax hat, nur Konventionen, und daher extrem erweiterbar ist.

Code: Alles auswählen

: [ ( -- quot ) " ]" parseuntil >quotation ; parsing


Das `call` ist leider nicht generisch wie es sein könnte, da `literalize` aus einem der ersten Teile die falsche Semantik hat. Das will ich jetzt aber nicht nochmal ändern. Eigentlich sollte eine `Quotation` einfach callable sein und `call` kann dann mit allem, was "callable" ist, umgehen.
sma
User
Beiträge: 3018
Registriert: Montag 19. November 2007, 19:57
Wohnort: Kiel

Beitragvon sma » Sonntag 11. Januar 2009, 12:02

Zusammen mit Quotations kann ich jetzt Kontrollstrukturen definieren. Ich beginne mit der folgenden primitiven Operation `?`, die abhängig von einem Objekt und dessen Wahrheitswert eines von zwei anderen Objekten auswählt:

Code: Alles auswählen

Factor().execute(": ? ( x t f -- t/f ) P{{ q2, q1 = f.pop(), f.pop(); f.push(q1 if f.pop() else q2) }} ;")


Nun sind `if`, `when` und `unless` einfach:

Code: Alles auswählen

Factor().execute("""
: if ( ? tq fq -- ) ? call ;
: drop ( x -- ) P{{ f.pop() }} ;
: when ( ? tq -- ) swap [ call ] [ drop ] if ;
: unless ( ? fq -- ) swap [ drop ] [ call ] if ;

{ } [ 3 4 + ] [ 3 twice ] if .
{ 1 2 } [ 3 4 + ] [ 3 twice ] if .
""")


Dies gibt 6 und 7 aus. Ich nutze hier aus, dass die leere Sequenz den Wahrheitswert "falsch" hat, während eine Sequenz mit zwei Elementen als "wahr" gilt.

Wer ist online?

Mitglieder in diesem Forum: 0 Mitglieder