Bislang habe ich Go geflissentlich ignoriert. Doch nun ist die stabile Version Go 1 erschienen. Da Go eine System-Programmiersprache wie C sein will, müsste man damit auch bequem einen Python-Interpreter schreiben können, der genauso gut wie CPython ist, oder?
Wie das prinzipiell funktioniert, ist mir bekannt. Die Semantik von Python ist mir auch bekannt.
Zeit für ein paar Experimente mit Go.
Auf dem Mac war es schnell mit brew install go installiert. Mit gefällt spontan, dass ich Code wie diesen hier, einfach mit go run hello.go in einem Schritt übersetzen und ausführen kann:
package main
import "fmt"
func main() {
fmt.Printf("Hello, Python!")
}
Ich muss kein Makefile und keine pom.xml schreiben oder komplizierte Kommandozeilenparameter auswendig lernen. Was der Befehl go sonst noch kann, habe ich mir noch nicht die Mühe gemacht herauszufinden. Auch das package-Konzept ist noch ein versiegeltes Buch für mich. Aber Go fühlt sich ausreichend dynamisch an, um mich nicht sofort abzuschrecken.
Allgemein gehe ich in dieses Projekt mit gesundem Halbwissen und ohne die Sprachspezifikation gelesen zu haben.
Das erste Problem ist der Editor. Es soll wohl ein Plug-in für Eclipse geben, doch ich möchte erst einmal bei TextMate bleiben und da das einzige Bundle für Go, dass ich ergoogelt hatte, über 1 Jahr alt war, habe ich erst einmal selbst ein Bundle gebaut. Nun funktioniert "Run", "Format", ein paar Snippets und das Einfärben von Schlüsselwörtern und Kommentaren und der erste Abend ist vorbei, ohne das ich etwas produktives geschafft habe. Na toll.
Mein Plan am nächsten Abend ist, Python-Objekte mit Hilfe von passenden Go-Typen abzubilden. Dann definiere ich Knoten für einen abstrakten Syntaxbaum, mit dem ich ein Python-Programm repräsentieren könnte und einen rekursiven Interpreter, der eine Kette von Frame-Objekten benutzt, um seinen Zustand zu verwalten.
Spannend bei Go finde ich deren Objektorientierung ohne Klassen. Ich weiß leider nicht, ob und wie eine Typhierarchie unterstützt wird. Ich glaube nicht. Ich würde sonst alle Typen von PyValue erben lassen. Ich nutze jetzt erst einmal ein leeres Interface. Welche Methoden so ein PyValue hat, habe ich mir noch nicht überlegt.
So sieht das in Go aus:
type (
PyValue interface{}
PyInt int
PyStr string
PyList []PyValue
PyDict map[PyValue]PyValue
PyFunc func(*PyFrame, PyList) PyValue
)
PyInt steht für int, der einzige Zahlentyp, den ich unterstützen werde. PyStr steht für str, wobei ich die Semantik von Go benutzen werde, die irgendwo zwischen Byte-Array und UTF-8-Kodierung liegt. PyList soll für list und tuple stehen, PyDict dementsprechend für dict. Mit PyFunc repräsentiere ich Funktionen, denen jeweils ein PyFrame als Kontext und die Liste der Argumente übergeben wird. Auf Schlüsselwort-Parameter verzichte ich erst einmal.
Ein PyFrame ist eine Struktur, die erst einmal so aussieht:
type PyFrame struct {
back *PyFrame
locals PyDict
globals PyDict
}
Um Exemplare von Typen zu erzeugen, soll man eine Konstruktor-Funktion schreiben, deren Namen mit New beginnt, also NewPyFrame. Meinetwegen. Damit ich Frames nicht bei jedem Funktionsaufruf kopiere und als Wert übergebe, muss ich hier mit Zeigern arbeiten, daher * und &:
func NewFrame(back *PyFrame, locals, globals PyDict) *PyFrame {
return &PyFrame{back, locals, globals}
}
Mir erscheint diese Funktion etwas redundant, aber sei es drum.
Ich überlege gerade, ob PyList und PyDict nicht auch Zeiger auf entsprechende Objekte sein müssten. Ich weiß es nicht. Hier aber zwei passende Konstruktor-Funktionen:
func NewList(values ...PyValue) PyList {
return values
}
func NewDict(values ...PyValue) PyDict {
dict := make(PyDict)
for i := 0; i < len(values); i += 2 {
dict[values[i]] = values[i + 1]
}
return dict
}
Kommen wir zum abstrakten Syntaxbaum. Bei Python habe ich zwei Arten von Knoten: Ausdrücke (Expr) und Anweisungen (Stmt). Einige Ausdrücke können zudem auf der linken Seite einer Zuweisung stehen und ein Target sein. Eine Folge von Anweisungen nenne ich Suite.
Oder in Go:
type (
Expr interface {
Eval(*PyFrame) PyValue
}
Stmt interface {
Exec(*PyFrame)
}
Suite []Stmt
Target interface {
Set(*PyFrame, PyValue)
}
)
Übrigens: Groß geschriebene Namen sind öffentlich, klein geschriebene Namen sind privat.
Ich möchte das folgende Python-Beispiel als AST repräsentieren:
for i in range(10):
j = i + i
print j
Ich benötige AST-Knoten für for, für Namen wie i, den Aufruf von range, die Zahl 10, die Zuweisung an j, die Addition und den print-Befehl.
AST-Knoten implementiere ich als Strukturen in Go:
type (
astLiteral struct {
value PyValue
}
astName struct {
name PyStr
}
astCall struct {
fun Expr
args []Expr
}
astFor struct {
target Target
items Expr
body Suite
}
astAssigment struct {
target Target
value Expr
}
astAdd struct {
left, right Expr
}
astPrint struct {
value Expr
}
)
Um die AST-Knoten zu Exemplaren der Interface-Typen Expr bzw. Stmt zu machen, muss ich nun Eval bzw. Exec implementieren (bzw. Set für Target). Ähnlich wie Python macht Go dabei den Empfänger explizit. Als Hommage an Python nenne ich den Empfänger immer self.
Ein astLiteral liefert einfach den Wert:
func (self *astLiteral) Eval(f *PyFrame) PyValue {
return self.value;
}
Hier ist ein triviales Testprogramm, das 1 ausgibt:
func main() {
frame := NewFrame(nil, NewDict(), NewDict())
ast1 := &astLiteral{PyInt(1)} // 1
println(ast1.Eval(frame).(PyInt))
}
In der ersten Zeile erzeuge ich einen neuen PyFrame mit Hilfe meiner Konstruktor-Funktionen. In der zweiten Zeile erzeuge ich (ohne Konstruktor-Funktion) einen AST-Knoten für eine 1. Da meine 1 vom Typ PyInt sein muss, muss ich sie aus der normalen 1 von Go erst erzeugen. Dann kann ich in der dritten Zeile meine triviale Eval-Methode aufrufen. Damit ich nicht nur eine Adresse sehe, sondern die Zahl 1, muss ich mit dem Cast-Operator .(PyInt) das Ergebnis zu einem PyInt erklären, der dann wie ein int dargestellt werden kann. Warum das nicht direkt funktioniert, erschließt sich mir nicht.
Ein Name liefert den gebundenen Wert. Dazu nutze ich eine Get-Methode in PyFrame, die ich natürlich auch implementieren muss. Um festzustellen, ob ein Dictionary einen Wert enthält, nutzt Go eine doppelte Zuweisung, die nicht nur den Wert selbst, sondern auch einen Boolschen Wert liefert, der sagt, ob ein Wert existiert:
func (self *astName) Eval(f *PyFrame) PyValue {
return f.Get(self.name)
}
func (self *PyFrame) Get(name PyStr) PyValue {
value, present := self.locals[name]
if present {
return value;
}
value, present = self.globals[name]
if present {
return value;
}
panic("unknown name '" + name + "'")
}
Mit panic kann ich einen Laufzeitfehler erzeugen. Wie Exceptions funktionieren, habe ich mir noch nicht überlegt, da dies die Möglichkeiten meines rekursiven Interpreters übersteigt und Go selbst keine Exceptions kennt.
Hier ist ein Test, der 2 und 3 ausgibt:
func main() {
frame := NewFrame(nil, NewDict(PyStr("a"), PyInt(2)), NewDict(PyStr("b"), PyInt(3)))
println((&astName{PyStr("a")}).Eval(frame).(PyInt)) // a
println((&astName{PyStr("b")}).Eval(frame).(PyInt)) // b
}
Einem Namen kann ich auch etwas zuweisen. Auch hier delegiere ich die Funktion wieder an PyFrame, wo eine Methode Set eine lokale Variable setzen kann. Das Ändern von globalen Variablen unterstütze ich nicht.
func (self *astName) Set(f *PyFrame, value PyValue) {
f.Set(self.name, value)
}
func (self *PyFrame) Set(name PyStr, value PyValue) {
self.locals[name] = value
}
Um dies zu testen, implementiere ich noch die Zuweisung:
func (self *astAssigment) Exec(f *PyFrame) {
self.target.Set(f, self.value.Eval(f))
}
Ich muss sagen, ich mag die Freiheit, wie ich Methoden zu verschiedenen "Klassen" definieren kann und wie einfach die "Mehrfachvererbung" von astName zu implementieren ist, welches sowohl ein Expr als auch ein Target ist. Das Entwurfsmuster selbst habe ich so auch schon mehrfach in Java und anderen Sprachen umgesetzt, aber es war immer lästig, dass ich in abstrakten Oberklassen grundsätzlich Standard-Implementierungen, die dann Laufzeitfehler werfen, implementieren musste. Noch immer fühlt sich Go wie eine Skriptsprache an, was auch durch die lokale Typinferenz in den Funktionen unterstützt wird. Bislang musste ich nur dort, wo es aus Dokumentationsgründen auch sinnvoll ist, den Signaturen, Typen deklarieren. Das gefällt.
Hier ist übrigens der Test für die Zuweisung:
func main() {
frame := NewFrame(nil, NewDict(), NewDict())
ast2 := &astAssigment{&astName{PyStr("c")}, &astLiteral{PyInt(4)}} // c = 4
ast2.Exec(frame)
println(frame.Get(PyStr("c")).(PyInt))
}
Als nächstes möchte ich die Addition implementieren. Ich kann Zahlen, Zeichenketten oder Listen addieren. Den Typ kann ich über einen switch mit dem speziellen Operator .(type) herausfinden. Dennoch muss ich ihn später noch mit .() zusichern. Man beachte, wie auch hier die doppelte Zuweisung mit einem Boolschen Wert als zweiten Parameter genutzt werden kann, um den Typ zu prüfen. Für Zahlen und Zeichenketten kann ich einfach das + von Go benutzen, doch Listen muss ich selbst kopieren.
func (self *astAdd) Eval(f *PyFrame) PyValue {
left := self.left.Eval(f)
right := self.right.Eval(f)
switch left.(type) {
case PyInt:
r, ok := right.(PyInt)
if ok {
return left.(PyInt) + r
}
case PyStr:
r, ok := right.(PyStr)
if ok {
return left.(PyStr) + r
}
case PyList:
l := left.(PyList)
r, ok := right.(PyList)
if ok {
value := make(PyList, len(l) + len(r))
copy(value, l)
copy(value, r)
return value
}
}
panic("type error")
}
Der Umgang mit den Typen fühlt sich ungewohnt und ein bisschen umständlich an, allerdings auch nicht wieder so schlimm, wie es bei Java wäre, wo einem schnell eine ClassCastException um die Ohren fliegt. Die Lösung, mit einem zweiten Wert zu melden, ob die Umwandlung geklappt hat, ist eigentlich ganz pfiffig.
Auch der print-Befehl ist schnell umgesetzt, er liefert allerdings ohne .()-Cast keine schönen Ausgaben und ich kann gerade im Zug nicht nachschauen, welche Methode meine Laufzeittypen implementieren müssen, um das zu überschreiben. Das überlasse ich als Übung dem Leser.
func (self *astPrint) Exec(f *PyFrame) {
println(self.value.Eval(f))
}
Jetzt sehe ich immer ein Paar bestehend aus einer Adresse im Hex-Format (ich rate mal einem Zeiger auf den Typ) und dem Wert, der ein gesetztes oberstes Bit hat, wahrscheinlich um anzuzeigen, dass es ein geboxter int ist. Was auch immer...
Spannender ist der for-Befehl. Ich werde ihn zunächst so implementieren, dass er eine PyList als Argument erwartet, nicht ein beliebiges aufzählbares Objekt. Dann kann ich die for-Schleife von Go benutzen, die mit dem Schlüsselwort range so funktioniert wie Pythons for zusammen mit enumerate. Da ich den Index nicht brauche, nutze ich _ als Variablenname (eine Konvention von Go):
func (self *astFor) Exec(f *PyFrame) {
items, ok := self.items.Eval(f).(PyList)
if ok {
for _, value := range items {
self.target.Set(f, value)
self.body.Exec(f)
}
return
}
panic("type error")
}
func (self Suite) Exec(f *PyFrame) {
for _, value := range self {
value.Exec(f)
}
}
Nun kann ich mein Beispiel testen, zunächst noch mit einer festen Liste:
func main() {
frame := NewFrame(nil, NewDict(), NewDict())
items := &astLiteral{PyList{PyInt(6), PyInt(7), PyInt(8)}} // [6, 7, 8]
ast4 := &astFor{&astName{PyStr("i")}, items, Suite{ // for i in [6, 7, 8]:
&astAssigment{&astName{PyStr("j")},
&astAdd{&astName{PyStr("i")}, &astLiteral{PyInt(1)}}}, // j = i + 1
&astPrint{&astName{PyStr("j")}}, // print j
}}
ast4.Exec(frame)
}
Das gibt die Zahlen 7, 8 und 9 aus.
Was nun noch fehlt, ist ein Aufruf von range(10). Dazu definiere ich zunächst die eingebaute Funktion range, die wir dann an den Namen range in frame.globals binden:
func pyRange(f *PyFrame, args PyList) PyValue {
len, ok := args[0].(PyInt)
if ok {
value := make(PyList, int(len))
for i := PyInt(0); i < len; i++ {
value[i] = i
}
return value
}
panic("type error")
}
...
frame.globals[PyStr("range")] = pyRange
Diese Funktion hat das gleiche Format wie PyFunc. Ich hätte daher gedacht, ich könnte sie überall dort benutzen, wo ich PyFunc erwarte. Das funktioniert leider nicht. Warum, muss ich noch recherchieren. Damit astCall funktioniert, muss ich dort leider auf den konkreten Typ "casten", nicht auf PyFunc:
func (self *astCall) Eval(f *PyFrame) PyValue {
fun, ok := self.fun.Eval(f).(func(*PyFrame, PyList) PyValue)
if ok {
args := make(PyList, len(self.args))
for i, arg := range self.args {
args[i] = arg.Eval(f)
}
return fun(f, args)
}
panic("type error")
}
Ersetze ich die Zeile items := ... mit der folgenden, funktioniert mein Beispiel:
items := &astCall{&astName{PyStr("range")}, []Expr{&astLiteral{PyInt(10)}}}
So weit so gut. Ich kann nicht abschätzen, wie effizient das ganze ist. Würde der selbe AST-Interpreter in C die Go-Version schlagen? Kopiere ich irgendwo Wert-Typen, die ich besser als Zeiger übergeben sollte? War die Entscheidung, PyInt und die anderen Laufzeit-Typen zu definieren eine gute? Oder sind diese überflüssig, solange ich dafür keine eigenen Methoden definieren will. Welchen Overhead zur Laufzeit hat eigentlich der Aufruf von Methoden oder ein Typtest? Kann Go als junge Sprache hier Java mit mehr als 10 Jahren Zeit für Optimierungen schlagen? Jedenfalls kann ich von 1 bis 10 zählen...
Es ist dritte Abend und ich möchte untersuchen, wie ich eigene Python-Programme einlesen und in einen AST verwandeln kann. Da es bei Python nicht trivial ist, die Einrückung zu parsen, werde ich die Todsünde begehen und Blöcke mit einem Schlüsselwort end beenden. Dann geht's einfach. Den Anfang eines Blocks erkenne ich ja an einem :.
Außerdem werde ich die Grammatik der Sprache auf das einschränken, was ich auch abbilden kann:
suite = stmt+
stmt = for | print | assignment
for = "for" target "in" expr ":" suite "end"
print = "print" expr
assignment = target "=" expr
target = NAME
expr = term ["+" term]
term = prim ["(" expr ")"]
prim = NAME | INT
Wie man eine Datei in einen String einliest überfordert mich. Es scheint keinen direkten Weg zu geben. Für einen regulären Ausdruck bräuchte ich einen String. Doch eine Datei lese ich erst einmal als []byte ein. In io/iotuil habe ich eine Funktion ReadFile gefunden. Fühlt sich alles kompliziert an. Ich werde einen String benutzen, nein, eigentlich ein []byte, den ich aus einem String erzeugen kann und den ganzen Encoding-Kram erst einmal vergessen.
Im bytes-Paket finde ich NewBuffer und so ein Objekt hat eine Methode String. Ich erzeuge es auf einem []byte. Das passt. Ich frage mich nur, warum ich überhaupt string als Datentyp habe. Mit der Methode ReadRune kann ich ein Zeichen einlesen wobei eine UTF-8-Kodierung angenommen wird. WriteRune macht das Gegenteil.
Der folgende Code funktioniert, erscheint mir aber immer noch übermäßig kompliziert:
import (
"bytes"
"unicode"
)
type Scanner struct {
inbuf *bytes.Buffer
outbuf *bytes.Buffer
Token string
}
func NewScanner(buf []byte) *Scanner {
scanner := &Scanner{bytes.NewBuffer(buf), bytes.NewBuffer(make([]byte, 0)), ""}
scanner.Advance()
return scanner
}
func (self *Scanner) read() rune {
r, _, err := self.inbuf.ReadRune()
if err != nil {
r = 0
}
return r
}
func (self *Scanner) Advance() {
// skip spaces
r := self.read()
for unicode.IsSpace(r) {
r = self.read()
}
// signal EOF if we reach the end of the input buffer
if r == 0 {
self.Token = ""
return
}
// read an int if it starts with a digit
if unicode.IsDigit(r) {
for unicode.IsDigit(r) {
self.outbuf.WriteRune(r)
r = self.read()
}
self.inbuf.UnreadRune()
self.Token = self.outbuf.String()
self.outbuf.Reset()
return
}
// read a name or keyword if it starts with a letter
if unicode.IsLetter(r) || r == '_' {
for unicode.IsLetter(r) || unicode.IsNumber(r) || r == '_' {
self.outbuf.WriteRune(r)
r = self.read()
}
self.inbuf.UnreadRune()
self.Token = self.outbuf.String()
self.outbuf.Reset()
return
}
// one character of syntax
self.outbuf.WriteRune(r)
self.Token = self.outbuf.String()
self.outbuf.Reset()
return
}
Diese import-Anweisung muss am Dateianfang hinter package stehen, sonst gibt es einen Fehler. Und ich darf auch nur das importieren, was ich wirklich nutze.
Mein Scanner nutzt zwei Buffer, einen zum Einlesen des in Strings zu zerlegenden Byte-Arrays und einen, mit dem ich mangels einer besseren Alternative die Strings erzeuge. Auch das Erzeugen eines leeren Buffer zum schreiben muss doch einfacher gehen.
Mit der Methode read vereinfache ich das Einlesen eines Zeichens. Die Länge ist mir egal und ein Fehler muss ein EOF sein, das ich einfacher als Wert 0 anzeige als durch einen zweiten Wert.
Die Methode Advance macht die eigentliche Arbeit und trägt das nächste Token in Token ein.
Das folgende Beispiel zeigt, das ich mein Beispiel damit zerlegen kann:
scanner := NewScanner([]byte("for i in range(10):\nj = i + 1\nprint j\nend"))
for scanner.Token != "" {
println(scanner.Token)
scanner.Advance()
}
Ich muss sagen, den Umgang mit Runen und Buffern finde ich doch recht umständlich im Vergleich zu Python.
Der eigentliche Parser ist hoffentlich einfacher umzusetzen. Ich entwerfe ihn analog zur Grammatik. Mit einer Funktion Parse geht es los:
func Parse(source []byte) Suite {
return parseSuite(NewScanner(source))
}
Eine suite bestehe aus Anweisungen und endet mit dem Ende des Programms oder einem end-Token:
func parseSuite(s *Scanner) Suite {
suite := make(Suite, 0)
for s.Token != "" && s.Token != "end" {
suite = append(suite, parseStmt(s))
}
return suite
}
Ein stmt kann entweder ein for oder ein print oder eine Zuweisung sein:
func parseStmt(s *Scanner) Stmt {
if s.match("for") {
target := parseTarget(s)
s.expect("in")
items := parseExpr(s)
s.expect(":")
body := parseSuite(s)
s.expect("end")
return &astFor{target, items, body}
}
if s.match("print") {
return &astPrint{parseExpr(s)}
}
target := parseTarget(s)
s.expect("=")
return &astAssigment{target, parseExpr(s)}
}
func (s *Scanner) match(token string) bool {
if (s.Token == token) {
s.Advance()
return true
}
return false
}
func (s *Scanner) expect(token string) {
if !s.match(token) {
panic("expected " + token + " but found " + s.Token)
}
}
Ein target ist in meiner eingeschränkten Grammatik einfach ein Name, aber ich möchte es etwas allgemeiner Formulieren und einen Ausdruck parsen, bei dem ich dann prüfe, ob er das Interface Target erfüllt:
func parseTarget(s *Scanner) Target {
target, ok := parseExpr(s).(Target)
if (ok) {
return target
}
panic("target expected")
}
Kommen wir zu epxr, welches eine Addition oder eine Zahl oder ein Name ist, dem optional ein call folgt. Hier erlaube ich nur einen Parameter, was die Sache sehr einfach macht.
func parseExpr(s *Scanner) Expr {
expr := parseTerm(s)
if s.match("+") {
expr := &astAdd{expr, parseTerm(s)}
}
return expr
}
Sowie:
func parseTerm(s *Scanner) Expr {
var expr Expr
if unicode.IsDigit(rune(s.Token[0])) {
i, _ := strconv.Atoi(s.Token)
expr = &astLiteral{PyInt(i)}
s.Advance()
} else if unicode.IsLetter(rune(s.Token[0])) || s.Token[0] == '_' {
expr = &astName{PyStr(s.Token)}
s.Advance()
}
if expr != nil {
if s.match("(") {
arg := parseExpr(s)
s.expect(")")
expr = &astCall{expr, []Expr{arg}}
}
}
return expr
}
Ein bisschen umständlich ist es, herauszufinden, ob ein Token wohl eine Zahl oder ein Name ist. Ich greife mir dazu das 1. Byte, was für Zahlen gut geht, aber für Namen nur im ASCII-Bereich funktioniert. Wäre das erste Zeichen ein Ä, wäre dessen UTF-8-Kodierung kein Buchstabe. Wahrscheinlich müsste ich mir im Scanner den Typ merken, denn dort weiß ich ihn ja schon. Um sauber an das erste Zeichen eines Strings zu kommen, muss ich anscheinend wieder über einen Buffer gehen:
rune first = bytes.NewBufferString(s.Token).ReadRune()
Nun kann ich aber mein Programm ausführen:
frame := NewFrame(nil, NewDict(), NewDict(PyStr("range"), pyRange))
Parse([]byte("for i in range(10):\nj = i + 1\nprint j\nend")).Exec(frame)
Der letzte Baustein, um das ganze einen Python-Interpreter nennen zu können, ist das Einlesen einer Python-Datei und das Ausführen derselben. Dazu muss ich das os-Paket importieren und kann dann os.Args benutzen. Ungefähr so:
func main() {
if len(os.Args) != 2 {
panic("usage: gopython file")
} else {
frame := NewFrame(nil, NewDict(), NewDict(PyStr("range"), pyRange))
Parse(ioutil.ReadFile(os.Args[1])).Exec(frame)
}
}
Mein Python-Interpreter ist fertig. Weitere Funktionen und AST-Knoten wären jetzt Fleißarbeit. Kompliziertere Funktionsaufrufe ebenfalls. Was so nicht funktioniert, sind Exceptions oder Generatoren. In beiden Fällen wäre es aber einfacher, zunächst auf eine Bytecode-VM umzusteigen und nicht direkt AST-Knoten zu evaluieren.
Dies soll mein Thema für den nächsten Abend sein.
Mein Beispielprogramm könnte man wie folgt in Bytecode-Instruktionen übersetzen:
LOAD_NAME range
LOAD_CONST 10
CALL 1
MAKE_ITER
LOOP:
GET_ITER >END
STORE_NAME i
LOAD_NAME i
LOAD_CONST 1
ADD
STORE_NAME j
LOAD_NAME j
PRINT
GOTO >LOOP
END:
LOAD_CONST None
RETURN
Die VM ist eine Stack-Maschine, d.h. alle Zwischenergebnisse werden über einen Werte-Stapel verarbeitet. Mit LOAD_NAME wird der Wert einer Variable auf den Stack geschrieben, mit STORE_NAME wird ein Wert vom Stack genommen und in eine Variable geschrieben. LOAD_CONST schreibt eine Konstante auf den Stack. Mit CALL kann ich eine Funktion mit der angegebenen Anzahl von Argumenten aufrufen. ADD nimmt zwei Werte vom Stack, addiert sie und schreibt das Ergebnis wieder auf den Stack. PRINT nimmt einen Wert vom Stack und gibt ihn aus. Mit MAKE_ITER mache ich aus dem obersten Element auf dem Stack einen Iterator, indem ich noch einen Index hinzufüge, der dann von GET_ITER jedes Mal erhöht wird. Diese Instruktion schiebt solange das nächste Element der Liste auf den Stack, bis es keine mehr gibt und springt dann zu der angegebenen Stelle. Mit GOTO kann ich ebenfalls zu einer anderen Stelle im Bytecode springen und RETURN beendet die Ausführung.
So ein Programm kann ich als code-Objekt repräsentieren, welches aus einem Byte-Array mit den Befehlen, ein PyValue-Array mit den Konstanten und ein String-Array mit den Namen besteht.
type PyCode struct {
codes []byte
names []PyStr
consts []PyValue
}
So ein Objekt kann ich im Kontext eines PyFrame ausführen, der nun aber noch einen Stack benötigt und einen index, der die nächste auszuführende Instruktion in codes bezeichnet:
type PyFrame struct {
back *PyFrame
locals PyDict
globals PyDict
index uint
stack []PyValue
code *PyCode
}
func NewFrame(back *PyFrame, locals, globals PyDict, code *PyCode) {
return &PyFrame{back, locals, globals, 0, make([]PyValue, 0, 10), code}
}
Nun kann ich eine Methode Execute definieren. Sie ist meine VM:
func (f *PyFrame) Execute() PyValue {
for {
switch f.nexti() {
case LOAD_CONST:
f.push(f.code.consts[f.nexta()])
case LOAD_NAME:
f.push(f.Get(f.code.names[f.nexta()]))
case STORE_NAME:
f.Set(f.code.names[f.nexta()], f.pop())
case CALL:
n := f.nexta()
a := make([]PyValue, n)
for n > 0 {
n -= 1
a[n] := f.pop()
}
f.push(f.pop().(func(*PyFrame, PyList)PyValue)(f, a))
case MAKE_ITER:
f.push(PyInt(0))
case GET_ITER:
index := f.pop().(PyInt)
list := f.pop().(PyList)
if int(index) < len(list) {
value := list[index]
index += 1
f.push(list)
f.push(index)
f.push(value)
f.index += 1
} else {
f.index = f.nexta()
}
case PRINT:
println(f.pop())
case GOTO:
f.index = f.nexta()
case RETURN:
return f.pop()
}
}
}
Ich brauche ein paar Hilfsmethoden:
func (f *PyFrame) nexti() byte {
c := f.code.codes[f.index]
f.index += 1
return c
}
func (f *PyFrame) nexta() uint {
return uint(f.nexti())
}
func (f *PyFrame) push(value PyValue) {
f.stack = append(f.stack, value)
}
func (f *PyFrame) pop() PyValue {
index := len(f.stack) - 1
value := f.stack[index]
f.stack = f.stack[:index]
return value
}
Und ein paar Konstanten:
const (
LOAD_CONST = 0
LOAD_NAME = 1
STORE_NAME = 2
CALL = 3
MAKE_ITER = 4
GET_ITER = 5
PRINT = 6
GOTO = 7
RETURN = 8
)
So definiere ich mir dann mein Beispiel:
code := &PyCode{
[]byte{
LOAD_NAME, 0,
LOAD_CONST, 1,
CALL, 1,
MAKE_ITER,
GET_ITER, 23,
STORE_NAME, 1,
LOAD_NAME, 1,
LOAD_CONST, 2,
ADD,
STORE_NAME, 2,
LOAD_NAME, 2,
PRINT,
GOTO, 7,
LOAD_CONST, 0
RETURN,
},
[]PyStr{PyStr("range"), PyStr("i"), PyStr("j")},
[]PyValue{nil, PyInt(10), PyInt(1)},
}
NewFrame(nil, PyDict(), PyDict(PyStr("range"), pyRange), code).Execute()
Natürlich will ich code-Objekte nicht per Hand bauen, sondern aus dem AST generieren. Dazu definiere ich eine Reihe von Compile-Methoden, denen ich ein PyCode-Objekt übergebe, das gebaut werden soll.
Konstanten:
func (self *astLiteral) compile(c *PyCode) {
c.addCode(LOAD_CONST)
c.addCode(c.addConst(self.value))
}
func (c *PyCode) addCode(code byte) {
c.codes = append(c.codes, code)
}
func (c *PyCode) addConst(value PyValue) byte {
for i, v := range c.consts {
if v == value {
return i
}
}
c.consts = append(c.consts, value)
return len(c.consts) - 1
}
Namen:
func (self *astName) compile(c *PyCode) {
c.addCode(LOAD_NAME)
c.addCode(c.addName(self.name))
}
func (c *PyCode) addName(name PyStr) byte {
for i, n := range c.names {
if n == name {
return i
}
}
c.names = append(c.names, name)
return len(c.names) - 1
}
for-Schleife:
func (self *astFor) compile(c *PyCode) {
self.items.compile(c)
c.addCode(MAKE_ITER)
index := len(c.codes)
c.addCode(GET_ITER)
c.addCode(0) // fix later
self.target.compileAsTarget(c)
self.body.compile(c)
c.addCode(GOTO)
c.addCode(index)
c.codes[index + 1] = len(c.codes)
}
func (self *astName) compileAsTarget(c *PyCode) {
c.addCode(STORE_NAME)
c.addCode(c.addName(self.name))
}
func (self Suite) compile(c *PyCode) {
for _, stmt := range self.stmts {
stmt.compile(c)
}
}
print-Befehl:
func (self *astPrint) compile(c *PyCode) {
self.expr.compile(c)
c.addCode(PRINT)
}
+-Operation:
func (self *astAdd) compile(c *PyCode) {
self.left.compile(c)
self.right.compile(c)
c.addCode(ADD)
}
Call:
func (self *astCall) compile(c *PyCode) {
self.fun.compile(c)
for _, arg := range self.args {
arg.compile(c)
}
c.addCode(CALL)
c.addCode(len(self.args))
}
Das war's. Der letzte Teil ist ungetestet, aber ich bin zuversichtlich, dass das so oder so ähnlich kompilieren und funktionieren wird.
Ich denke inzwischen, die Idee mit PyValue war keine gute und ich sollte direkt int, string, []interface{} und map[interface{}]interface{} sowie func(*Frame) als Typen benutzen. Letzteres reicht, wenn ich lokale Variablen nicht als dict verwalte, sondern als Liste. Zusammen mit dem Bytecode-Interpreter darf eine Funktion auch keinen Wert liefert, sondern sie schreibt ihr Ergebnis auf den Stack. Die eingebaute Funktion range sähe dann so aus:
func builtinRange(f *Frame) {
if len(f.args) == 1 {
n, ok := f.args[0].(int)
if ok {
list := make([]interface{}, n)
for i := 0; i < n; i++ {
list[i] = i
}
f.push(list)
}
}
panic("type error")
}
Ich denke auch, ich kann einen effizienteren Scanner schreiben, indem ich auf Buffer verzichte und selbst die Strings aus dem Byte-Array herausschneide. Ich muss dabei aber darauf achten, dass ich dadurch nicht das gesamte Byte-Array festhalte, sondern ein Set von Token verwalte. Dazu aber ein anderes Mal mehr.
Stefan