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:
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:
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:
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:
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.
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:
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:
class Var...
void set(Frame f, Obj value) {
f.set(name, value);
}
Die Zuweisung wird damit sehr einfach:
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:
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.
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:
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:
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:
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.
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) {
Obj 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:
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:
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.
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:
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:
class Int extends Obj {
int value;
Str str() { return new Str(String.valueOf(value)); }
}
Strings werden durch Str repräsentiert:
class Str extends Obj {
String value;
Str str() { return this; }
String toString() { return value; }
}
Dict steht für Dictionary:
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); }
void append(Obj value) { values.add(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.
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.
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:
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.
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):
class Method extends Obj {
Func func;
Instance self;
}
Und es gibt eingebaute Funktionen (und Methoden):
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__.
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:
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:
class Obj...
Obj neg() {
throw typeError("bad operand type for unary -");
}
Für Int ist es allerdings möglich:
class Int...
Obj neg() {
return new Int(-value);
}
Und es ist für Exemplare von Klassen möglich, die eine __neg__-Methode haben.
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.
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:
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:
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.
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:
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:
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:
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:
class Class...
Obj call(Obj... args) {
Instance i = new Instance(this, new 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:
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:
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.
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.
Die Operation mod könnte ähnlich implementiert werden, denn auch sie kann in eigenen Klassen in Python überschrieben werden. Außerdem muss ich noch implementieren, dass alle Zahlen außer 0 als "wahr" angesehen werden:
class Int...
Obj mod(Obj other) {
return new Int(value % ((Int) other).value);
}
boolean truish() {
return value != 0;
}
Anweisungen werden zu einer Suite zusammengefasst und diese wird dann der Reihe nach ausgewertet. Damit kennen wir jetzt alle Methoden des rekursiven Interpreters:
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.
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.