Wie man einen Python-Interpreter in Java bauen kann

[sma]

Ich hoffe, ich habe den folgenden Text nicht schon mal gepostet. Ich habe ihn schon vor einem Jahr oder so geschrieben und jetzt wiedergefunden und ein bisschen bearbeitet. Ich würde mich über Feedback freuen. Das Thema ist nicht einfach, aber ich habe mich bemüht, es knapp aber verständlich zu beschreiben. Schicker formatiert findet man's auch hier: https://gist.github.com/738236

Stefan

Ein Python-Interpreter

Dieser Text beschreibt theoretische Überlegungen, Python-Programme in Java zu präsentieren, um sie dann auszuführen. Auf welche Weise der Python-Quelltext übersetzt wird, ist nicht wichtig, nur das man zu jedem Python-Teilprogramm eindeutig ein Exemplar einer Java-Klasse zuordnen kann. Um den syntaktischen Ballast von Java zu reduzieren, lasse ich, wo nicht weiter wichtig, alle Sichtbarkeitsmodifikatoren und die offensichtlichen Konstruktoren zur Initialisierung der aufgeführten Exemplarvariablen weg.

Ich übersetze ein Python-Programm in zwei Arten von AST-Knoten:

Code: Alles auswählen

    abstract class Stmt {
        abstract void exec(Frame f);
    }
    
    abstract class Expr {
        abstract Obj eval(Frame f);
    }

Ein Programm ist eine Liste von Anweisungen (`Stmt`). Um es auszuführen, rufe ich jeweils `exec()` auf. Um Ausdrücke (`Expr`) als Teil der Anweisungen auszuwerten, benutze ich `eval()`. Was `Frame` ist, definiere ich später. `Obj` ist die abstrakte Oberklasse für alle Python-Objekte. Auch dazu später mehr.

Gegeben sei dieses Python-Programm:

Code: Alles auswählen

    for i in range(10):
        j = -i
        if i % 2:
            print j

Es besteht aus einer `for`-Anweisung, einem Funktionsaufruf der eingebauten Funktion `range`, einer Zuweisung-Anweisung, einer Negation, einer `if`-Anweisung, einer Modulo-Operation und einer `print`-Anweisung sowie mehreren Variablen-Referenzen.

Zur seiner Repräsentation brauche ich die folgenden AST-Knoten:

Code: Alles auswählen

    class ForStmt extends Stmt {
        Expr target;
        Expr items;
        Suite body;
    }
    
    class AssignStmt extends Stmt {
        Expr target;
        Expr value;
    }
    
    class IfStmt extends Stmt {
        Expr condition;
        Suite then;
    }
    
    class PrintStmt extends Stmt {
        Expr value;
    }
    
    class Suite extends Stmt {
        Stmt[] statements;
    }

    class Call extends Expr {
        Expr primary;
        Expr[] arguments;
    }
    
    class Lit extends Expr {
        Obj value;
    }
    
    class Var extends Expr {
        Str name;
    }
    
    class Neg extends Expr {
        Expr expr;
    }
    
    class Mod extends Expr {
        Expr left, right;
    }

Unter der Annahme, alle Java-Klassen haben passende Konstuktoren, kann ich mein Python-Beispiel wie folgt in Java nachbauen. Diese Aufgabe übernimmt normalerweise ein Parser:

Code: Alles auswählen

    new ForStmt(new Var("i"), new Call(new Var("range"), new Lit(10)), new Suite(
        new AssignStmt(new Var("j"), new Neg(new Var("i"))),
        new IfStmt(new Mod(new Var("i"), new Lit(2)), new Suite(
            new PrintStmt(new Var("j"))))))

Hinweis: Eine sinnvolle Optimierung wäre, zwischen lokalen und globalen Variablen zu unterscheiden. Alle Variablen, denen etwas zugewiesen wird (wobei es egal ist, wo das passiert) und die nicht als `global` deklariert wurden, sind lokal (`i` und `j`). Variablen wie `range`, denen nie etwas zugewiesen wird, gelten als global. Ich verzichte auf diese Optimierung.

Ich werte ein Programm durch einen rekursiven Interpreter aus. Dazu muss ich für alle Unterklassen von `Stmt` die Methode `exec` und für alle Unterklassen von `Expr` die Methode `eval` implementieren.

Eine `for`-Schleife iteriert über ihre Elemente `items`, wobei die Schleifenvariable `target` jeweils das aktuelle Element aufnimmt. Python erlaubt verschiedene Objekte als Elemente: Eine Liste, ein Tupel, ein Dict, ein Iterator, ein Generator oder ein Exemplar einer Klasse, das entweder eine `__getitem__`-Methode oder eine `__iter__`-Methode hat. Ich nehme an, dass die Methode `iter()` des Laufzeitsystems das alles jeweils in einen `java.util.Iterator<Obj>` verwandelt.

Code: Alles auswählen

    class ForStmt...
        void exec(Frame f) {
            for (Iterator<Obj> it = items.eval(f).iter(); it.hasNext();) {
                target.set(f, it.next());
                body.exec(f);
            }
        }

Bei einer for-Schleife ist `target` immer ein `Var`, doch bei Zuweisungen kann der Ausdruck vor dem `=` komplizierter werden. Immer, wenn ich ein `Expr` als Ziel einer Zuweisung benutzen kann, benutze ich eine `set()`-Methode, die ich bislang unterschlagen hatte:

Code: Alles auswählen

    abstract class Expr...
        void set(Frame f, Obj value) {
            throw new UnsupportedOperationException();
        }
    }

Um das Zuweisen von Werten zu Variablen soll sich der bislang nicht weiter erläuterte `Frame` kümmern:

Code: Alles auswählen

    class Var...
        void set(Frame f, Obj value) {
            f.set(name, value);
        }

Die Zuweisung wird damit sehr einfach:

Code: Alles auswählen

    class AssignStmt...
        void exec(Frame f) {
            target.set(f, value.eval(f));
        }

Sie funktioniert insbesondere auch noch, wenn man Ausdrücke wie `a[0] = 1` oder `a.b = 2` oder `a, b = b, a` unterstützen will. Wenn die `[]`-Operation durch eine Klasse `Index` repräsentiert würde, könnte man wie folgt implementieren:

Code: Alles auswählen

    class Index extends Expr {
        Expr primary;
        Expr index;
        
        Obj eval(Frame f) {
            return primary.eval(f).getItem(index.eval(f));
        }
        
        void set(Frame f, Obj value) {
            primary.eval(f).setItem(index.eval(f), value);
        }
    }

Für parallele Zuweisungen würde der die repräsentierende Klasse `TupleCtr` annehmen, dass es eine passende Laufzeitklasse `Tuple extends Obj` gibt und bei `set()` etwas übergeben wird, auf dessen Element man mit `getItem()` zugreifen kann. Dies könnte ein anderes Tupel sein. Ich überprüfe nicht, ob auch die richtige Anzahl an Elementen vorhanden ist.

Code: Alles auswählen

    class TupleConstr extends Expr {
        Expr[] exprs;
        
        Obj eval(Frame f) {
            Obj[] values = new Obj[exprs.length];
            for (int i = 0; i < exprs.length; i++) {
                values[i] = exprs[i].eval(f);
            }
            return Tuple(values);
        }
        
        void set(Frame f, Obj value) {
            for (int i = 0; i < exprs.length; i++) {
                exprs[i].set(value.getItem(i));
            }
        }
    }

Doch zurück zu dem eigentlichen Problem. Wir haben bislang gesehen, wie das `for`, die Zuweisung und Variablen funktionieren. Variablen werden im `Frame` verwaltet. Dieser kennt ein `Dict extends Obj` zum Speichern der Werte unter den passenden Namen, repräsentiert durch Exemplare von `Str extends Obj`:

Code: Alles auswählen

    class Frame {
        Dict locals;
        
        void set(Str name, Obj value) {
            locals.setItem(name, value);
        }
    }

Schauen wir uns noch `if` und `print` an, bevor ich die `Expr`-Knoten und die restliche Implementierung von `Frame` zeige:

Code: Alles auswählen

    class IfStmt...
        void exec(Frame f) {
            if (condition.eval(f).truish()) {
                then.exec(f);
            }
        }

    class PrintStmt...
        void exec(Frame f) {
            System.out.println(value.eval(f).str());
        }

Die Methode `truish` prüft, ob ein Python-Objekt als wahr oder als falsch gilt. Die Methode `str` erstellt eine String-Repräsentation eines Python-Objekts als Java-String, den Java dann ausgeben kann.

Bei den `Expr`-Implementierungen beginne ich mit `Lit`, weil dieses trivial ist:

Code: Alles auswählen

    class Lit...
        Obj eval(Frame f) {
            return value;
        }

Um lesend auf eine Variable zuzugreifen, delegiere ich wieder an den Frame. Er hat ein zweites `Dict` für globale Variablen. Da Python auch noch eingebaute Funktionen aus einem `__builtins__` genannten Modul kennt, ist der Zugriff auf diese Variablen entsprechend komplex.

Code: Alles auswählen

    class Var...
        Obj eval(Frame f) {
            return f.get(name);
        }
    
    class Frame...
        Dict globals;
        ...
        Obj get(Str name) {
            Obj value = locals.getItem(name);
            if (value != null) {
                return value;
            }
            return getGlobal(name);
        }
        
        Obj getGlobal(Str name) {
            value = globals.getItem(name);
            if (value != null) {
                return value;
            value = globals.getItem(Str.__builtins__);
            if (value != null) {
                if (value instanceof Module) {
                    value = ((Module) value).dict;
                }
                value = value.getItem(name);
                if (value != null) {
                    return value;
                }
            }
            throw nameError(name);
        }
    
    class Str...
        static Str __builtins__ = new Str("__builtins__");

Um globale Variablen zu verändern, gibt es in Python eine speziellen Anweisung `global` um derartige Variablen zu kennzeichnen. Die "builtin"-Variablen kann man nicht direkt ändern, sondern muss das `Dict` des gleichnamigen Moduls ändern. Auf ein `Dict` kann ich mittels `getItem()` und `setItem()` zugreifen. Python 1.x und Python 2.x verhalten sich übrigens unterschiedlich, wenn `__builtins__` kein Dict enthält -- das sei hier egal.

Der Vollständigkeit halber hier noch die Methode um eine globale Variable zu setzen:

Code: Alles auswählen

    class Frame...
        void setGlobal(Str name, Obj value) {
            globals.setItem(name, value);
        }

Kann ich eine globale Variable bereits beim Parsen erkennen, kann ich sofort einen AST-Knoten als Exemplar von `GlobalVar` statt von `Var` anlegen:

Code: Alles auswählen

    class GlobalVar extends Expr {
        Str name;
        
        Obj eval(Frame f) {
            return f.getGlobal(name);
        }
        
        void set(Frame f, Obj value) {
            f.setGlobal(f, value);
        }
    }

Hinweis: Man könnte auch Zuweisungen an `__builtins__` erkennen und das Modul cachen, damit man nicht jedes Mal danach suchen muss. Dort stecken alle eingebauten Funktionen, Typen und Konstanten.

Das war jetzt aber gleich ein Sprung in Semantik der Variablen. Zurück zu den Operationen, die wieder einfach sind. Die `eval`-Methoden delegieren an entsprechende Methoden von `Obj`, die für Datentypen für Zahlen passend überschrieben werden.

Code: Alles auswählen

    class Neg...
        Obj eval(Frame f) {
            return expr.eval(f).neg();
        }

    class Mod...
        Obj eval(Frame f) {
            return left.eval(f).mod(right.eval(f));
        }

Bevor ich zum letzten AST-Knoten `Call` komme, möchte ich die Laufzeitklassen (vereinfacht) vorstellen.

Alles erbt von `Obj`, meiner abstrakten Oberklasse für alle Python-Objekte, die alle aufrufbaren Java-Methoden (und davon gibt es viele) definiert. Damit spare ich mir die meisten Cast-Operationen im Code:

Code: Alles auswählen

    abstract class Obj {
        java.util.Iterator<Obj> iter() { ... }
        boolean truish() { ... }
        Str str() { ... }
        Obj getItem(Obj key) { ... }
        void setItem(Obj key, Obj value) { ... }
        Obj getAttr(Str name) { ... }
        Obj neg() { ... }
        Obj mod(Obj other) { ... }
        Obj call(Obj... args) { ... }
        ...
    }

Zahlen werden durch `Int` repräsentiert:

Code: Alles auswählen

    class Int extends Obj {
        int value;
        
        Str str() { return new Str(String.valueOf(value)); }
    }

Strings werden durch `Str` repräsentiert:

Code: Alles auswählen

    class Str extends Obj {
        String value;
        
        Str str() { return this; }
        String toString() { return value; }
    }

`Dict` steht für Dictionary:

Code: Alles auswählen

    class Dict extends Obj {
        HashMap<Obj, Obj> values;
        
        Obj getItem(Obj key) { return values.get(key); }
        void setItem(Obj key, Obj value) { values.put(key, value); }
    }

`List` entspricht einem dynamischen Array. Daneben gibt es noch `Tupel` als ein nicht veränderbares Array, was ich aber in meinen Beispielen nicht brauche.

Code: Alles auswählen

    class List extends Obj {
        ArrayList<Obj> values;

        Obj getItem(Obj key) { return values.get(((Int) key).value); }
        void setItem(Obj key, Obj value) { values.set(((Int) key).value, value); }
    }

Klassen werden durch `Class` repräsentiert und ich definiere sie hier, um beispielhaft das Überschreiben von `neg()` mit einer Python-Implementierung zu zeigen. Ich unterschlage die Tatsache, dass Python Mehrfachvererbung hat.

Code: Alles auswählen

    class Class extends Obj {
        Str name;
        Class base;
        Dict dict;
    }

Python 1.x bezeichnet zwar alle Werte aller Datentypen als Objekte, aber nur Objekte vom Typ `Instance` sind Exemplare einer Klasse und somit Objekte im Java-Sinn:

Code: Alles auswählen

    class Instance extends Obj {
        Class cls;
        Dict dict;
    }

Klassen, Exemplare und Funktionen sind in Python "callable". Sie haben eine Methode `call(Obj... args)`. `Func` steht für benutzerdefinierte Python-Funktionen. Neben den Namen der Parametern `params`, die dann zu lokalen Variablen in dem Frame werden in dessen Kontext der Rumpf der Funktion `body` werden, kennt eine Funktion auch die globalen Variablen `globals`, die zum Zeitpunkt ihrer Definition gültig waren, d.h. in dem dort aktuellen Frame standen.

Code: Alles auswählen

    class Func extends Obj {
        Str[] params;
        Suite body;
        Dict globals;
    }

Funktionen, die in einer Klasse abgelegt sind, sind Methoden. Steckt eine `Func` in dem `Dict` einer Klasse, wird sie beim Zugriff automatisch in eine `Method` gekapselt (hier die Vereinfachung seit Python 3.x):

Code: Alles auswählen

    class Method extends Obj {
        Func func;
        Instance self;
    }

Und es gibt eingebaute Funktionen (und Methoden):

Code: Alles auswählen

    abstract class Builtin extends Obj {
    }

Schließlich gibt es noch Module, die in ihrem Dict die globalen Variablen halten. Python-Code wird immer im Kontext eines Moduls ausgeführt. In der interaktiven Kommandozeile oder wenn ein Python-Programm ausgeführt wird, heißt dieses Modul `__main__`.

Code: Alles auswählen

    class Module extends Obj {
        Str name;
        Dict dict;
    }

So könnte das System initialisiert werden, unter der Annahme, das auszuführende Programm in Form von Exemplaren der AST-Knoten-Klassen steckt in der Variablen `program`:

Code: Alles auswählen

    Module __builtins__ = new Module(Str.__builtins__, new Dict());
    __builtins__.dict.setItem(Str.range, new Builtin() { ... });
    Module __main__ = new Module(Str.__main__, new Dict());
    __main__.dict.setItem(__builtins__.name, __builtins__);
    __main__.dict.setItem(Str.__name__, __main__.name);
    program.exec(new Frame(new Dict(), __main__.dict));

So ist `neg()` in der Klassenhierarchie implementiert.

Prinzipiell ist es erst mal ein Fehler:

Code: Alles auswählen

    class Obj...
        Obj neg() {
            throw typeError("bad operand type for unary -");
        }

Für `Int` ist es allerdings möglich:

Code: Alles auswählen

   class Int...
        Obj neg() {
            return new Int(-value);
        }

Und es ist für Exemplare von Klassen möglich, die eine `__neg__`-Methode haben.

Code: Alles auswählen

    class Instance...
        Obj neg() {
            return findMethod(new Str("__neg__")).call();
        }

Mit `findMethod()` suche ich in der Klassenhierarchie ein Funktionsobjekt, das ich dann mit `bind()` in eine Methode verwandle.

Code: Alles auswählen

    class Instance...
        private Obj findMethod(Str name) {
            Obj func = cls.getAttr(name);
            if (func != null) {
                return func.bind(this);
            }
            throw attributeError(name);
        }

Finde ich kein passendes Attribut, wird ein Fehler geworfen, den `neg` noch abfangen muss. Es kann passieren, dass es das Attribut gibt, es aber keine Funktion enthält. Wie das zu einem Fehler führt, sehen wir gleich. Zunächst die Verfeinerung von `neg`:

Code: Alles auswählen

    class Instance...
        Obj neg() {
            Obj meth;
            try {
                meth = findMethod(new Str("__neg__"));
            } catch (AttributeError e) {
                return super.neg();
            }
            return meth.call();
        }

Zurück zu `findMethod`, welches zum Klassen-Objekt delegiert, welches zunächst sein Dict durchsucht und falls dort nichts gefunden wird, die Aufgabe an seine Superklasse delegiert. Statt Exceptions zu werfen, nutze ich hier `null` als Marker, das nichts gefunden wurde. Dieser Wert wird in Python nicht benutzt, das `None` aus Python wird in diesem Laufzeitsystem als einziges Exemplar der Klasse `None extends Obj` repräsentiert und ist damit nicht identisch mit `null` in Java:

Code: Alles auswählen

    class Class...
        Obj getAttr(Str name) {
            Obj value = dict.getItem(name);
            if (value != null) {
                return value;
            }
            if (base != null) {
                return base.getAttr(name);
            }
            return null;
        }

Die Verwandlung einer Funktion in eine Methode erledigt `bind`. Für normale Objekte passiert da gar nichts. Sie werden unverändert zurückgeliefert. Funktionen hingegen kapseln sich selbst in einem `Method`-Exemplar.

Code: Alles auswählen

    class Obj...
        Obj bind(Instance self) {
            return this;
        }
        
    class Func...
        Obj bind(Instance self) {
            return new Method(this, self);
        }

Das nächste Puzzlestück ist der Funktionsaufruf.

Prinzipiell geht es nicht:

Code: Alles auswählen

   class Obj...
        Obj call(Obj... args) {
            throw typeError("call of non-function");
        }

Funktionen kann man jedoch aufrufen. Der Rumpf der Funktion wird in einem neuen `Frame` ausgeführt, der die Argumente des Funktionsaufrufs an die Parameter der Funktion bindet und die richtigen globalen Variablen wählt. Jede Funktion bekommt bei ihrer Definition dieses Dict zugewiesen, damit sie auf die globalen Variablen ihres Moduls zugreifen kann und nicht auf die globalen Variablen an der Aufrufstelle:

Code: Alles auswählen

    class Func...
        Obj call(Obj... args) {
            Dict locals = new Dict();
            for (int i = 0; i < params.length; i++) {
                locals.setItem(params[i], args[i]);
            }
            body.exec(new Frame(locals, globals));
            return None;
        }

Bleibt noch die Methode:

Code: Alles auswählen

    class Method...
        Obj call(Obj... args) {
            return func.call(prepend(self, args));
        }
        
        static Obj[] prepend(Obj first, Obj[] rest) {
            Obj[] objs = new Obj[rest.length + 1];
            objs[0] = first;
            System.arraycopy(rest, 0, objs, 1, rest.length);
            return objs;
        }

Eine Klasse ist ebenfalls "callable". Dies erzeugt neue Exemplare der Klasse.

Ungefähr so:

Code: Alles auswählen

    class Class...
        Obj call(Obj... args) {
            Instance i = new Instance(this, Dict());
            i.findMethod(new Str("__init__")).call(args);
            return i;
        }

Ein Exemplar kann man wie eine Funktion aufrufen, wenn seine Klasse eine Methode `__call__` definiert:

Code: Alles auswählen

    class Instance...
        Obj call(Obj... args) {
            Obj meth;
            try {
                meth = findMethod(new Str("__call__"));
            } catch (AttributeError e) {
                return super.call(args);
            }
            return meth.call(args);
        }

Schließlich kann man auch eingebaute Funktionen aufrufen. Für `range` ist die Implementierung einfach. Man muss `call()` überschreiben:

Code: Alles auswählen

   class BuiltinRange extends Builtin {
        Obj call(Obj... args) {
            if (args.length != 1) {
                throw typeError("range takes exactly 1 parameter");
            }
            if (!(args[0] instanceof Int)) {
                throw typeError("illegal argument type");
            }
            int n = ((Int) args[0]).value;
            List list = new List(n);
            for (int i = 0; i < n; i++) {
                list.append(new Int(i));
            }
            return list;
        }

Ein Exemplar der Java-Klasse `BuiltinRange` muss dann im Modul `__builtins__` registriert werden. Das haben wir schon weiter oben gesehen.

Hinweis: Leider sind Parameterlisten in Python nicht so einfach aufgebaut, wie ich bislang behauptet habe, aber das ändern nichts am Prinzip der Aufrufe, sondern macht sie nur im Detail komplizierter, indem für fehlende Argumente Ersatzwerte gesetzt werden müssen, Schlüsselwortargumente ausgewertet und zugeordnet werden müssen, Restlisten für normale Argumente in Form eines Tupel und für Schlüsselwortargumente in Form eines Dict berechnet werden müssen und Tupel oder Dicts eventuell zu einer Parameterliste ausgepackt werden müssen. Dazu kommen vor Python 3.0 noch Tupel-Parameter und ab Python 3.0 keyword-only-Parameter für primitive Funktionen.

Nachdem wir jetzt wissen, wie ein Funktionsaufruf funktioniert, können wir den letzten Baustein einfügen und den `Call`-Knoten implementieren. Zunächst wird das Objekt vor den Klammern ausgewertet. Es sollte ein "callable" sein, also etwas, dass eine `call`-Methode sinnvoll implementiert. Dann werden alle Argumente rekursiv ausgewertet und die Funktion (bzw. das "callable") aufgerufen.

Code: Alles auswählen

    class Call...
        Obj eval(Frame f) {
            Obj func = primary.eval(f);
            Obj[] args = new Obj[arguments.length];
            for (int i = 0; i < arguments.length; i++) {
                args[i] = arguments[i].eval(f);
            }
            return func.call(args);
        }

Ich möchte noch einmal beschreiben, was beim Aufruf von `range` passiert. Zunächst wird der Wert für die Variable `range` bestimmt. Er wird zunächst in den lokalen Variablen des aktuellen Frame, danach in den globalen Variablen und da auch dort nicht zu finden, in dem Modul, das unter dem globalen Namen `__builtins__` abgelegt ist, gesucht und gefunden. Dies ist ein Exemplar der Java-Klasse `RangeBuiltin`. Dann wird das Argument wie gewohnt ausgewertet. Als nächstes wird die Methode `call` aufgerufen, das die Liste baut. `Func`, `Method`, `Instance` und `Class` kommen hier nicht vor, die Ausführungen sollten aber zeigen, wie sich diese Konzepte in das Laufzeitsystem einfügen.

Anweisungen werden zu einer `Suite` zusammengefasst und diese wird dann der Reihe nach ausgewertet. Damit kennen wir jetzt alle Methoden des rekursiven Interpreters:

Code: Alles auswählen

    class Suite...
        void exec(Frame f) {
            for (Stmt stmt : statements) {
                stmt.exec(f);
            }
        }

Eigentlich müsste ich in das `call` das `f` hinein reichen. In Python kann man mit den Systemfunktionen `locals` und `globals` auf die aktuellen lokalen bzw. globalen Variablen zugreifen.

Code: Alles auswählen

    class BuiltinLocals extends Builtin {
        Obj call(Frame f, Obj... args) {
            return f.locals;
        }
    }

Mit diesem Grundkonzept lässt sich die Semantik von Python fast vollständig abbilden. Generatoren funktioniert in einem rekursiven Interpreter nicht. Der Einsatz von Exceptions direkt wie in Python wäre sehr ineffizient in Java. Hier ist es besser, häufiger `null` zu benutzen, um zu signalisieren, das etwas nicht gefunden wurde.

[mkesper]

Beschreibe vielleicht noch kurz, was deinen Ansatz von Jython unterscheidet.

[cofi]

Jython ist eine komplette Laufzeitumgebung, sma stellt hier nur eine mögliche interne Repraesentation von Pythoncode vor, mit der man aufbereiteten Pythoncode interpretieren koennte. Insofern sind das Apfel und Apfelstrudel mit Sahne.

@sma: Danke für den Post.

[sma]

Jython ist ein recht vollständiges Python 2.5. Mein Ansatz irgendetwas zwischen Python 1.x und 3.x ohne Laufzeitbibliothek, der einzig das Prinzip eines rekursiven Interpreters zeigt. Ich denke, man könnte das ganze mit viel Fleiß ausbauen, hätte aber keine Generatoren.

Und Geschwindigkeitsrekorde gewinnt mein Ansatz leider auch nicht. Prinzipiell (Ausnahmen bestätigen die Regel) gilt, dass ein AST-Walker die langsamste Form eines Interpreters ist. Danach kommt ein klassischer Bytecode-Interpreter, der irgendwo ein großes switch-case hat, dann kommen Threaded Code-Interpreter (Forth-Systeme funktionieren klassischer Weise so, lässt sich in einer Hochsprache wie Java nicht effektiv simulieren) und dann JIT-Techniken.

Jython kompiliert Python-Quelltext in Java-Bytecode und nutzt damit einen JIT-Compiler. Das es dennoch meist nicht viel schneller ist als CPython liegt daran, dass bei Python allgegenwärtige Grundoperationen (Funktionsaufrufe und Attributzugriffe) so komplex sind, dass es völlig egal ist, was für eine Interpreter-Technologie man benutzt. Geschwindigkeit gewinnt man nur dadurch, dass man schummelt, d.h. Spezialfälle erkennt oder heimlich selten benutzte Funktionen weglässt.

Stefan

[sma]

Statt rekursiver `exec`- bzw. `eval`-Methoden kann man aus einem AST auch Befehle (sprich Maschinencode) für eine ausgedachte (sprich virtuelle) Maschine erzeugen, dann diese Maschine implementieren und so das Programm ausführen. Das ist in der Regel einfacher als echten Maschinencode für einen echten Prozessor zu erzeugen und theoretisch effizienter, als ein direkter AST-Interpreter.

So sieht das ursprüngliche Python-Programm als "Maschinencode" aus:

Code: Alles auswählen

    Code[] program = {
        new CodeVar("range"),
        new CodeLit(10),
        new CodeCall(1),
        new CodeIter(),
        new CodeNext(16),
        new CodeSet("i"),
        new CodeVar("i"),
        new CodeNeg(),
        new CodeSet("j"),
        new CodeVar("i"),
        new CodeLit(2),
        new CodeMod(),
        new CodeIfFalse(15),
        new CodeVar("j"),
        new CodePrint(),
        new CodeJump(4),
    }

Wie es aus dem AST erzeugt werden kann, möchte ich zurückstellen und damit beginnen, die virtuelle Maschine und ihre Befehle zu beschreiben. Ich repräsentiere (strikt objektorientiert) jeden Befehl als Unterklasse der abstrakten Klasse `Code`. Die Methode `step`, der eine virtuelle Maschine übergeben wird, führt einen Befehl aus:

Code: Alles auswählen

    abstract class Code {
        abstract void step(VM vm);
    }

Die Klasse `VM` repräsentiert die virtuelle Maschine. Sie kennt den `Frame` für die lokalen und globalen Variablen, natürlich das Programm, hat einen Stack für die Zwischenergebnisse und einen Index für den aktuellen Befehl:

Code: Alles auswählen

    class VM {
        Code[] code;    // instructions
        int ip;         // instruction pointer a.k.a. index into code
        Obj[] stack;    // intermediate values
        int sp;         // stack pointer a.k.a. index into stack
        Frame f;        // frame with local and global variables
        
        Obj push(Obj value) { return stack[sp++] = value; }
        
        Obj pop() { return stack[--sp]; }
        
        void run() {
            while (ip < code.length) {
                code[ip++].step(this);
            }
        }
    }

Die Methode `run` führt in einer `while`-Schleife jeweils den nächsten Befehl von `code` aus und stoppt, wenn das Ende des Arrays erreicht wurde. Die Befehle können nun Werte des Laufzeitsystems (Exemplare von Unterklassen der abstrakten Klasse `Obj`) auf den Stapel schieben (`push`), dort verarbeiten oder wieder entfernen (`pop`). Sie können außerdem den `Frame` verändern oder den Index `ip` des nächsten Befehls manipulieren, was Sprünge im Programm auslöst.

Der Befehl `CodeVar` lädt eine Variable und schiebt den Wert als Zwischenergebnis auf den Stack:

Code: Alles auswählen

    class CodeVar extends Code {
        Str name;
        void step(VM vm) { vm.push(vm.f.get(name)); }
    }

`CodeLit` macht das selbe mit einer Konstanten:

Code: Alles auswählen

    class CodeLit extends Code {
        Obj value;
        void step(VM vm) { vm.push(value); }
    }

`CodeCall` holt eine Liste von Argumente und ein Funktionsobjekt vom Stack und ruft dann die Funktion mit den Argumenten auf. Zu beachten ist, dass ich hier noch mehr tun müsste, wenn ich weitere benutzerdefinierte Funktionen aufrufen wollte, deren Programm-Code ebenfalls in einer (vielleicht sogar der selben) virtuellen Maschine ausgeführt werden soll. Sollte mein Ziel sein, die Rekursion, die einem AST-Interpreter innewohnt, aus dem System zu entfernen, habe ich es bislang noch verfehlt. Da es in diesem Beispiel aber nur um den Aufruf der eingebauten Funktion `range` geht und ich mir über eigene Funktionen noch keine Gedanken gemacht habe, ignoriere ich das Problem hier:

Code: Alles auswählen

    class CodeCall extends Code {
        int nargs;
        void step(VM vm) {
            Obj[] args = vm.pop(nargs);
            vm.push(vm.pop().call(args));
        }
    }

    class VM...
        Obj[] pop(int n) {
            Obj[] result = new Obj[n];
            sp -= n;
            System.arraycopy(stack, sp, result, 0, n);
            return result;
        }

Der Befehl `CodeIter` nimmt ein Objekt vom Stack und schiebt einen Iterator für das Objekt auf den Stack. Im ersten Teil war dies ein `java.util.Iterator<Obj>`. Hier beißt mich die statische Typisierung von Java, denn das ist natürlich keine Unterklasse von `Obj`. Ich brauche daher ein Exemplar einer Klasse `Iter extends Obj` als "Wrapper" für den Java-Iterator. Dies ist die Vorbereitung für die `for`-Schleife.

Code: Alles auswählen

    class CodeIter extends Code {
        void step(VM vm) { vm.push(vm.pop().iter()); }
    }
    
    class Iter extends Obj {
        java.util.Iterator<Obj> iter;
        Obj next() {
            return iter.hasNext() ? iter.next() : null;
        }
    }

`CodeNext` ist der zweite Befehl, der zusammen mit `CodeIter` eine `for`-Schleife implementiert. Er erwartet einen Iterator als oberstes Element auf dem Stack und schiebt dann den nächsten Wert aus dem Iterator auf den Stack -- oder nimmt den Iterator vom Stack und springt zu einem neuen Befehl, falls der Iterator sein Ende erreicht hat.

Code: Alles auswählen

    class CodeNext extends Code {
        int endIndex;
        void step(VM vm) {
            Iter it = (Iter) vm.pop();
            Obj obj = it.next();
            if (obj != null) {
                vm.push(it);
                vm.push(obj);
            } else {
                vm.ip = endIndex;
            }
        }
    }

Dies war der komplizierteste Befehl. Beim Rest gibt es keine Überraschungen mehr.

Eine lokale Variable wird mit `CodeSet` gesetzt:

Code: Alles auswählen

    class CodeSet extends Code {
        Str name;
        void step(VM vm) { vm.f.set(name, vm.pop()); }
    }

`CodeNeg` ruft `neg()` für das oberste Stack-Element auf und ersetzt es durch das Ergebnis des Methodenaufrufs:

Code: Alles auswählen

    class CodeNeg extends Code {
        void step(VM vm) { vm.push(vm.pop().neg()); }
    }

`CodeMod` ruft `mod()` für die obersten beiden Stack-Elemente auf und ersetzt sie durch das Ergebnis des Methodenaufrufs. Zu beachten ist, dass die Werte "rückwärts" auf dem Stack stehen:

Code: Alles auswählen

    class CodeMod extends Code {
        void step(VM vm) { Obj other = vm.pop(); vm.push(vm.pop().mod(other)); }
    }

Einen Sprung abhängig vom Wahrheitswert des obersten Stack-Elements implementiert `CodeIfFalse`. Das Stack-Element wird dabei entfernt.

Code: Alles auswählen

    class CodeIfFalse extends Code {
        int index;
        void step(VM vm) { if (!vm.pop().truish()) { vm.ip = index; } }
    }

Einen unbedingten Sprung zu einem anderen Befehl bietet `CodeJump`:

Code: Alles auswählen

    class CodeJump extends Code {
        int index;
        void step(VM vm) { vm.ip = index; }
    }

Und, schlussendlich, kann ich mit `CodePrint` ein Objekt ausgeben:

Code: Alles auswählen

    class CodePrint extends Code {
        void step(VM vm) { System.out.println(vm.pop().str()); }
    }

Das waren alle Befehle. Initialisiert man ein Exemplar der Klasse VM mit einem passenden `Frame`-Objekt, kann das Programm ausgeführt werden und sollte genauso funktionieren, wie zuvor mit dem AST-Interpreter. Theoretisch, aber auch nur theoretisch, läuft das Programm sogar schneller ab als zuvor. In der Praxis haben meine als Java-Objekte repräsentierten Befehle mit ihren Methodenaufrufen einen so großen Overhead, dass die `exec`- und `eval`-Aufrufe des AST gar nicht ins Gewicht fallen würden. Dafür ist meine virtuelle Maschine auf diese Weise um neue Befehle erweiterbar und sie hat das Potential, "stackless" zu werden. Dies meint, dass niemals der Stack der Sprache des Interpreters (im Gegensatz zur interpretierten Sprache) für rekursive Aufrufe der Interpreter-Funktion genutzt wird. CPython ist nicht "stackless", dort wird der System-Stack wie üblich bei C, benutzt, wenn eine Python-Funktion eine andere aufruft.

Das passiert bei mir jetzt auch - aber das soll ein Thema für ein anderes Mal sein. Noch muss ich zeigen, wie man aus dem AST den Maschinencode erzeugt. Dies macht eine einfache rekursiv auf allen Knoten des AST definierte Methode namens `build`, der ein wie folgt definierter `CodeBuilder` übergeben wird:

Code: Alles auswählen

    abstract class Node {
        abstract void build(CodeBuilder b);
    }
    
    class CodeBuilder {
        List<Code> code = new ArrayList<Code>();
        void add(Code c) { code.add(c); }
        int here() { return code.size(); }
        int skip() { add(null); return here() - 1; }
        void fix(int i, Code c) { code.set(i, c); }
    }

Zur Erinnerung hier noch einmal die Liste der AST-Klassen: `ForStmt`, `AssignStmt`, `IfStmt`, `PrintStmt`, `Suite`, `Call`, `Lit`, `Var`, `Neg`, `Mod`. Los gehen soll es mit `ForStmt`:

Code: Alles auswählen

    class ForStmt...
        void build(CodeBuilder b) {
            items.build(b);
            b.add(new CodeIter());
            int i = b.skip();
            target.buildAsTarget(b);
            body.build(b);
            b.fix(i, new CodeNext(b.here()));
        }

Zunächst wird rekursiv die Liste `items` gebaut. Dann wird ein `CodeIter`-Befehl erzeugt. Dann käme `CodeNext`. Doch noch kennen wir nicht `endIndex`, also wohin beim Ende der Aufzählung gesprungen werden soll. Daher kann dieser Befehl erst später eingetragen werden und ich merke mir seinen Index. Weiter geht es dann damit, das Element aus der Aufzählung in einer Variablen zu speichern. Wie üblich brauche ich für einige AST-Knoten wieder eine schreibende Variante, hier `buildAsTarget` genannt:

Code: Alles auswählen

    abstract class Node...
        void buildAsTarget(CodeBuilder b) { throw new UnsupportedOperationException(); }
    
    class Var...
        void buildAsTarget(CodeBuilder b) { b.add(new CodeSet(name)); }

Danach kann der Rumpf der Schleife erzeugt werden und schließlich kann ich den fehlenden Befehl mit dem nun bekannten Index nachtragen. Auf diese Weise kann ich in einem Schritt den Maschinencode erzeugen.

In das Erzeugen des Codes für die Liste waren folgenden AST-Knoten involviert:

Code: Alles auswählen

    class Var...
        void build(CodeBuilder b) { b.add(new CodeVar(name)); }
    
    class Lit...
        void build(CodeBuilder b) { b.add(new CodeLit(value)); }

    class Call...
        void build(CodeBuilder b) {
            primary.build(b);
            for (Expr argument : arguments) {
                argument.build(b);
            }
            b.add(new CodeCall(arguments.length)); 
        }

Die Zuweisung bringt auch keine Überraschungen:

Code: Alles auswählen

    class AssignStmt...
        void build(CodeBuilder b) {
            value.build(b);
            target.buildAsTarget(b);
        }

Bei `if` sieht es wieder etwas komplizierter aus, da auch hier erst später die Sprungadresse bekannt ist:

Code: Alles auswählen

    class IfStmt...
        void build(CodeBuilder b) {
            condition.build(b);
            int i = b.skip();
            then.build(b);
            b.fix(i, new CodeIfFalse(b.here()));
        }

Es folgenden die letzten `build`-Methoden ohne weitere Worte:

Code: Alles auswählen

    class Neg...
        void build(CodeBuilder b) { 
            expr.build(b);
            b.add(new CodeNeg());
        }

    class Mod...
        void build(CodeBuilder b) {
            left.build(b);
            right.build(b);
            b.add(new CodeMod()); 
        }
    
    class Suite...
        void build(CodeBuilder b) {
            for (Stmt stmt : statements) {
                stmt.build(b);
            }
        }
        
    class PrintStmt...
        void build(CodeBuilder b) {
            value.build(b);
            b.add(new CodePrint());
        }

Hat man einen AST, kann man daraus nun ein Maschinenprogramm erzeugen und mit einer virtuellen Maschinen ausführen. Vorhin erwähnte ich noch Funktionsaufrufe. Die Methode `call` der Klasse `Func` müsste man wie folgt ändern:

Code: Alles auswählen

    class Func extends Obj {
        Str[] params;
        Code[] body; // instead of Suite
        Dict globals;

        Obj call(Obj... args) {
            Dict locals = new Dict();
            for (int i = 0; i < params.length; i++) {
                locals.setItem(params[i], args[i]);
            }
            Frame frame = new Frame(locals, globals);
            new VM(body, frame).run(); // instead of body.exec(frame);
            return None;
        }
    }

Doch brauche ich wirklich für jede Funktion eine neue VM? So wie ich sie modelliert habe, ja. Jede Funktion braucht einen eigenen Befehlszeiger. Zwischenergebnisse könnte man auf einem zentralen Stack verwalten, doch dann wäre es schwerer, bei Exceptions den Stapel sauber aufzuräumen. Daher ist es auch hier einfacher, wenn jede Funktion ihren eigenen Stapel mit Zwischenergebnissen hat. Tatsächlich könnten VM und Frame zusammenfallen.

[mkesper]

(natürlich warmer) Apfelstrudel mit Sahne... *schwelg*
SCNR!