Programmiersprachen und Übersetzer
05 - Semantische Analyse

Graphiken und Animationen

PreviousNext

Als erstes wollen wir uns die Baumtraversierung anschauen und mit dem Visitor/Besucher-Pattern ein Entwurfsmuster diskutieren, bei dem man die Attributgleichungen für S-Attribute übersichtlich formulieren kann. Generell fließen die Informationen bei S-Attributen von unten nach oben, wir müssen also zuerst alle Kinder eines Knotens besuchen, bevor wir daran gehen, das eigene Attribut auszurechnen. Dieses Berechnungsmuster entspricht einer Tiefensuche mit Post-Order Besuchsreihenfolge.

Das erste Codebeispiel zeigt eine rekursive Funktion, die diese Tiefensuche implementiert und das Höhenattribut ausrechnet. Im gesamten Verlauf wird die Funktion height(N) für jeden Knoten N des Baums einmal aufgerufen und der untere Teil der Funktion rechnet die Höhe aus. Der rekursive Besuch aller Knoten geschieht dadurch, dass wir height() mit dem Wurzelknoten aufrufen und wir bei jedem Knoten zuerst height(child) für alle Kinder auswerten. Beachten Sie hier, dass jeder Knotentyp unter dem Feld N.children eine Liste aller seiner Kinder bereitstelltFür plus: N.children = [N.lhs, N.rhs]. Auf einem Knoten stehend besucht height() also zuerst die Kinder, rechnet dort das Attribut child.h aus und erst danach wird der Code für den aktuellen Knoten ausgewertet und das Attribut gesetzt.

Der mittlere Teil berechnet, abhängig vom Typ des Knotens, den Wert für das Attribut h. Für literal-Knoten ist die Höhe 1, für Blätter hängt sie von den beiden Kindern ab. An dieser Stelle verwenden wir den dynamischen Typ des Knotens, um in Python eine Fallunterscheidung anhand der AST-Knotenklasse (isinstance()) zu machen.

Mit diesem Muster können wir alle S-Attribute für unseren AST ausrechnen. Allerdings geht die Formulierung der Attributgleichungen im Code für die Traversierung und der Fallunterscheidung für den dynamischen Typen (=dynamic dispatch) unter. Um dieses Problem noch deutlicher zu machen, habe ich auf der zweiten Folie die Traversierung noch kompakter formuliert, und den Rückgabewert von height() für die Propagation der Höhe verwendet. Der Besuch der Kinder ist jetzt spezifisch für den Knotentypen und seine Kinder geworden.

Hierdurch entstehen mehrere Probleme: Zum einen schreiben wir den Code für Traversierung und dynamischen Dispatch für jedes Attribut immer wieder, was zu einer unsäglichen Menge an Boilerplate-Code führt, und zum anderen ist die Lösung sehr fragil: Führen wir einen neuen Knotentypen ein, der Kinder besitzt, so müssen wir alle Baumtraversierungen unseres Übersetzer um diesen Knotentypen ergänzen. Vergessen wir dabei den rekursiven Abstieg für diesen Knotentypen richtig zu implementieren, so vergessen wir ganze Unterbäume bei der Baumtraversierung. Um dieses Problem zu lösen und besseren Code zu schreiben, faktorisieren wir jene Teile der Implementierung, die für alle Baumtraversierungen gleich sind, in eine generische Funktion aus. Wir wenden also das informatische Grundprinzip Trennung der Belange an.

Graphiken und Animationen

PreviousNext

Mit dem Visitor-Pattern bündeln wir nur den knotenspezifischen Code und geben für jede Knotenart eine visit()-Funktion an. Um dies generisch zu formulieren, können wir in C++ das Sprachfeature der überladenen Funktionen verwenden, welches wir in der letzten Vorlesung bereits diskutiert haben. Durch diese Überladung wird die visit()-Funktion zu einer Art komplexem Operator, der für jede Art von Knoten weiß, welcher Code ausgeführt werden soll. Indem wir die visit()-Methode virtuell machen, können wir von Visitor erben und Funktionen für einzelne Knotentypen überschreiben.

Die traversal()-Funktion bündelt den nun generischen Teil der Baumtraversierung. Sie bekommt ein Visitor-Objekt und einen Baumknoten als Argument und kümmert sich um die Besuchsreihenfolge und den korrekten Aufruf der visit()-Funktionen. Für den rekursiven Abstieg verlässt sich die Traversierungsfunktion darauf, dass jeder Knotentyp eine Liste seiner Kinder bereitstellt. Nachdem diese besucht wurden, rufen wir die visit()-Funktion auf.

Leider ist das Codebeispiel, wie ich es auf der ersten Folie gezeugt habe, kaputt. Denn an der Aufrufstelle von visit() wird bei der Auflösung der Überladung nur der dynamische Typ von v, nicht aber der von t beachtet. Dieses Problem, dass virtuelle Methoden nur im ersten Argument dynamischen Dispatch anwenden, haben wir bereits im Kapitel über Namensauflösung diskutiert Siehe Dynamischer Dispatch.. Für das Visitor-Pattern brauchen wir allerdings nicht nur einen solchen single-dynamic dispatch, sondern einen double-dynamic dispatch. Wir wollen uns nun ansehen, wie wir diesen in einer statisch typisierten Sprache (C++) und einer dynamischen Skriptsprache (Python) emulieren können.

In der statischen C++-Variante erreichen wir den double-dynamic dispatch dadurch, dass wir zweimal hintereinander einen single-dynamic dispatch durchführen bzw. zwei virtuelle Methodenaufrufe hintereinander schalten. Der Startpunkt unseres Aufrufs ist die traversal()-Funktion: Hier rufen wir auf einem Tree-Objekt die virtuelle accept()-Methode auf, die uns als Trampolin für den double-dynamic dispatch dient (1. dynamic dispatch). Weil accept() virtuell ist, wird der Aufruf anhand des dynamischen Typen aufgelöst und wir landen in Codestücken, die spezifisch für den jeweiligen AST-Knotentyp sind; der statische Typ des this-Zeigers ist gleich dem dynamischen Typen des Objekts. Die accept()-Methoden bekommt ein Visitorobjekt (statischer Typ: Visitor, dynamischer Typ: divers) und ruft dort die virtuelle visit()-Funktion mit sich selbst auf (2. dynamic dispatch). Somit kommen wir mit dem zweiten virtuellen Methodenaufruf zu einer visit()-Funktion, die dynamisch abhängig ist vom Knoten und vom Visitortypen!

Man kann diese Aufrufkette traversal()-accept()-visit() so beschreiben, dass wir den statischen Typen der Argumente schrittweise an ihre dynamischen Typen anpassen. Am Anfang haben wir (Visitor, Tree), dann (Visitor, literal) und letztendlich (HeightVisitor, literal).

Für die Python-Variante des Visitor-Patterns wählen wir eine andere Technik, da wir in dieser Skriptsprache keine Überladung in den Parametertypen haben (keine statischen Typen!). Stattdessen verwenden wir Introspektion auf dem gegebenen Visitor-Objekt und dem AST-Knoten. In Python haben wir die Möglichkeit, uns den dynamischen Typen eines Objekts als ein eigenes Objekt geben zu lassen (type()). Aus diesem Typ-Objekt können wir den Typnamen (__qualname__Dieses Attribut gibt es erst seit Python 3. Es ist der qualified-name des Typen, der bei Klassen gleich dem Klassennamen ist.) extrahieren und einen Methodennamen ableiten. Würden wir den gegebenen Code mit einem literal-Knoten ausführen, so wäre M_name der String "visit_literal". Mit Hilfe von Introspektion mittels getattr(obj, name) kommen wir an die virtuelle Methode (selbst auch wieder ein Objekt), die wir aufrufen können. Diese Art einen double-dynamic dispatch durchzuführen ist nur möglich, wenn eine Sprache mittel zur Introspektion der Laufzeitumgebung (dynamische Typinspektion, Finden von Methoden) zur Verfügung stellt.

Mit all unserem Vorwissen, und zwei Implementierungsvarianten für das Visitor-Pattern im Rücken, ist es nun relativ einfach eine simple Typberechnung und -prüfung zu definieren. Dafür berechnen wir für jeden (relevanten) Knoten im AST einen statischen Rückgabetypen und prüfen an allen inneren Knoten, ob die Typen der Kinder zueinander und zum Knotentypen kompatibel sind. Zum Beispiel sollten wir nur zwei Ganzzahlen miteinander addieren, wobei das Ergebnis der Addition wiederum eine Ganzzahl ist.

Lassen wir alle Feinheiten, wie Namensauflösung und Polymorphie, außer Acht, so ist der Knotentyp ein S-Attribut, welches von unten nach oben propagiert wird. Wir müssen also für alle Blätter einen Typ angeben und für jeden inneren Knotentyp eine Berechnungsvorschrift für die Propagation von unten nach oben. Bei literalen Konstanten (z.B. 23, "foo") geben die Sprachregeln genau vor, welchen Typ diese Ausdrücke haben (z.B. int, string). Diese Sprachregeln lassen sich sehr klar in unserem TypeVisitor kodieren, indem wir das Typattribut in den Blättern entsprechend setzen. Bei manchen Knoten, wie dem address-of-Operator (&FOO), besteht die Typberechnung daraus, einen Typkonstruktor (pointer()) auf dem Typen des einzigen Kindes anzuwenden. Informeller gesagt ist der Ergebnistyp des address-of-Operators ein Pointertyp, der als Pointee-Typ den Typ des Kindes hat; &"foobar" hat den Typ pointer(string), wenn "foobar" den Typ string hat.

Bei komplexeren Knoten oder bei komplexeren Sprachregeln beinhaltet die entsprechende visit()-Methode nicht nur Typberechnung, sondern sie prüft auch, ob gewisse Sprachregeln eingehalten wurden. So müssen in einem strikt monomorphen Typsystem die beiden Operandentypen bei einer Addition übereinstimmen (L.equal(R)). Weiterhin wird überprüft, ob die Addition für diese Typen überhaupt definiert ist. In unserem Beispiel ist nur eine Addition von Ganzzahlen erlaubt (L.equal(int)).

Wir übergeben der traversal()-Funktion die Wurzel des ASTs und das Visitor-Objekt und die visit()-Methoden werden, in der richtigen Reihenfolge, von unten nach oben, aufgerufen, sodass die Typinformationen von unten nach oben berechnet wird. Dabei prüfen wir nicht nur die konsistente Verwendung der Typen, sondern befüllen auch für jeden Knoten das Typ-Attribut, welches wir im weiteren Verlauf der Übersetzung verwenden werden.

Graphiken und Animationen

PreviousNext

Aber nicht immer passen die an einem Knoten geforderten Typen zu den Typen der Operanden. Im Beispiel wollen wir eine Funktion, welche eine Fließkommazahl erwartet, mit einer Ganzzahl aufrufen. Wäre unsere Sprache ganz strikt, müssten wir an dieser Stelle die Übersetzung abbrechen und dem Programmierer die Aufgabe überlassen, eine explizite Umwandlung von Ganzzahl zu Fließkommazahl einzufügen. Eine solche explizite Typumwandlung heißt auch Cast ((char *) ....) oder Coercion und hat zweierlei Aspekte: Zum einen wird der angegebene Typausdruck anstatt der des Kindes als Rückgabetyp verwendet, zum anderen muss, unter Umständen, Code eingefügt werden, der das Objekt zur Laufzeit vom einen zum anderen Typen umwandelt. Allerdings prüft nicht jede Programmiersprache, ob die angegebene Typumwandlung überhaupt Sinn ergibt oder ob der Programmierer das Typsystem absichtlich umgehtBei C bieten Casts kaum bis keine Typsicherheit, was aber für systemnahe Programmierung mehr als Feature denn als Bug gesehen wird..

Da das manuelle einfügen von expliziten Typumwandlungen aufwendig ist und zu einer verschlechterten Lesbarkeit des Codes führt, haben viele Sprachen, zumindest einige, Regeln zur impliziten Typumwandlung. So wandeln viele Sprachen eine Ganzzahl automatisch in eine Fließkommazahl um. Technisch geschieht die implizite Typumwandlung während der Berechnung des Typattributs: Passt an einem Knoten der vorgefundene Typ eines Kindes nicht zum erwarteten Typ, so prüft der Übersetzer, ob die Sprachregeln es erlauben, eine implizite Umwandlung vorzunehmen. Ist dies möglich, so wird ein neuer AST-Knoten eingefügt, der die Typumwandlung durchführt.

In einem Sprachstandard werden normalerweise nur solche impliziten Typumwandlungen definiert, welche keine überraschende Semantik haben. So kennen viele Sprachen die Ganzzahlweitung, welche eine implizite Umwandlung von den kleinen (Bitbreite) zu den großen Ganzzahltypen erlaubt. Möglich ist dies, weil durch eine solche Weitung kein Informationsverlust entstehen kann; der größere Ganzzahltyp hat eine höhere Informationskapazität.

Wenn wir, für einen kurzen Augenblick, unsere sprachphilosophische Brille aufsetzen, so ist die implizite Typumwandlung oder Coercion eine Spielart des Polymorphismus, denn sie erlaubt es, dass ein Typ an Stelle eines anderen Typen treten kann; der implizit umwandelbare Typ hat eine weitere Gestalt. Dabei gehört die Coercion, ebenso wie die Überladung, zur Klasse der Ad-Hoc Polymorphie, da die konkrete Gestalt des Typens an der konkreten Stelle im Programm bzw. im AST festgestellt wird.

Vergleichen wir Coercion mit Überladung, so stellen wir fest, dass beide Ad-Hoc Mechanismen in der gleichen Problemlage angewendet werden, sie aber auf unterschiedlichen Seiten wirken. Die Überladung wählt anhand des Operandentypen die Operation aus; Bei der Coercion wandeln wir den Operanden anhand des Operators um. In manchen Sprachen interagieren beide Mechanismen an einer Stelle. So kann es in C++ passieren, dass ein Funktionsargument zuerst implizit umgewandelt wird, bevor die richtige Überladung ausgewählt wird. Solch eine Situation kann noch unübersichtlicher werden, da der Programmierer eigene Regeln zur impliziten Typumwandlung definieren kann.

Generell lässt sich sagen, dass implizite Typumwandlungen ein mächtiges, aber auch ein gefährliches Sprachmittel sind. Zum einen führen gut gewählte Coercion-Regeln zu Code, bei dem nicht beständig gegen das Typsystem gekämpft wird. Zum anderen können automatisch angewendete Typumwandlungen zu Situationen führen, bei denen man sich fragt: "Wieso funktioniert das? Und was wird hier eigentlich aufgerufen?"

Ein besonders schönes Beispiel für verwirrende Regeln zur impliziten Typumwandlung ist JavaScript. Dort gibt es viele Situationen, bei denen Zeichenketten automatisch zu einem "semantisch-äquivalenten Typen" umgewandelt werden. Verwendet man beispielsweise die Zeichenkette "23" in einem Ganzzahl-Kontext, so wird diese Zeichenkette als eine Ganzzahl zur Basis 10 geparst. Hier geschieht also nicht nur auf Ebene der Typen eine Umwandlung, sondern es wird eine Interpretation der Zeichenkette, unter der Annahme des Zehnersystems, durchgeführt.

So gut die Idee auf den ersten Blick erscheinen mag (sie spart eine Menge parseInt()-Aufrufe), so schlecht ist sie in der Praxis. Denn diese, und ähnliche semantische Interpretationen von leeren Arrays, führen dazu, dass der ==-Operator und der !=-Operator inkonsistent werden!Lassen Sie sich das noch einmal auf der Zunge zergehen! Inkonsistenz bei der Gleichheitsrelation! Um George Orwell zu zitieren: "Schwarz ist weiß, Freiheit ist Sklaverei". Nachdem diese Inkonsistenz auffiel, hat JavaScript einen ===-Operator bekommen, bei dem die impliziten Typumwandlungen ausgeschaltet werden, um "echte Gleichheit" abprüfen zu können.

Graphiken und Animationen

PreviousNext

Nachdem wir eine Idee davon bekommen haben, wie Typen in einem Übersetzer berechnet und geprüft werden, wollen wir uns der Namensauflösung zuwenden. Da wir diesem Thema schon eine ganze Vorlesung gewidmet haben, wollen wir hier nur diskutieren, wie sich diese in unserer Attribut-Sicht einordnet und jene Techniken kennenlernen, mit denen die entsprechenden Sprachregeln implementiert werden.

Namen verbinden Deklaration und Referenz quer zum AST. Daher ist es nicht möglich, diese Verbindung als S-Attribut zu formulieren, sondern wir müssen eine mächtigere Klasse von Attributen verwenden. Wenn eine Deklaration immer vor einer Verwendung stattfinden muss, so können wir die Namensauflösung als Berechnung eines L-Attribut auffassen ("die Deklaration steht im AST links"). Der gesuchte Attributwert ist dabei ein Zeiger an der Namensreferenz, welche auf den deklarierenden AST-Knoten zeigt. Um ein solches L-Attribut zu berechnen, erweitern wir den Visitor um eine Zustandsvariable, die es erlaubt, Daten während der Traversierung von links nach rechts zu transportieren. Für die Namensauflösung ist die Symboltabelle die kanonische Datenstruktur, um Informationen über die aktuell deklarierten Namen zu transportieren.

Die Symboltabelle ist eine Datenstruktur, mit der wir einen hierarchischen Namensraum während der Baumtraversierung verwalten können. Im Minimum erlaubt eine Symboltabelle, einen neuen Namensraum zu öffnen (openNamespace()), einen neuen Namen zu deklarieren (createName()), einen Namen aufzulösen (findName()) und den zuletzt geöffneten Namensraum wieder zu schließen (closeNamespace()). Dabei kann die Symboltabelle nicht nur die clostest-nested scope rule (CNSR), sondern auch komplexere Namensraumoperationen (wie Import von Namen), kapseln.

Zuerst wollen wir uns ansehen, wie die Symboltabelle bei einer Baumtraversierung verwendet wird, bevor wir uns ihrer Implementierung zuwenden. Um eine mit Zustand behaftete Traversierung durchzuführen, geben wir unserer Visitor-Klasse, welche bisher keinen eigenen Zustand hatte, ein Objekt-Attribut self.ST, welches im Konstruktor mit einer leeren Symboltabelle initialisiert wird. Mit dieser Symboltabelle iterieren wir nun über alle Knoten des ASTs.

Um Namensräume korrekt öffnen und schließen zu können, müssen wir unseren Visitor noch um eine weitere Funktionalität erweitern: Pre-Order-Besuchsreihenfolge. Bisher haben wir, an einem Knoten, die visit()-Funktionen aufgerufen, nachdem alle Kinder besucht worden sind (Post-Order). Nun wollen wir zusätzlich auch noch vor dem Besuch der Kinder eine Funktion aufrufen. Dazu führen wir in der traversal()-Funktion vor und nach der Schleife über die Kinder einen double-dynamic dispatch mit Hilfe des Visitor-Objekts durch. Wir rufen die pre()-Funktionen vor, und die post()-Funktionen nach dem rekursivem Abstieg auf. Auf diese Weise, können wir einen Namensraum beim Besuch einer Namensraum-Deklaration öffnen, bevor wir alle enthaltenen Elemente abarbeiten. Nach der Abarbeitung wird der entsprechende Namensraum wieder geschlossen.

Beim Besuch einer benannten Deklaration erzeugen wir einen neuen Namen (self.ST.createName()) und richten so eine Abbildung vom entsprechenden Namen auf den deklarierenden AST-Knoten ein. In einer Sprache mit statischen Typen hätten wir die Signatur createName(string, Decl).

An Stellen, an denen wir eine Namensreferenz auflösen wollen, fragen wir die Symboltabelle nach dem referenzierten Namen und bekommen den vorher verknüpften AST-Knoten als Rückgabewert von findName(string). Diese Deklaration können wir nun (als Zeiger/Referenz) in einem AST-Attribut der DeclRefExpr speichern.

Graphiken und Animationen

PreviousNext

Wir wollen uns nun damit beschäftigen, wie die Symboltabelle implementiert ist und wie wir CNSR-Namensauflösung implementieren können. Dabei sei gesagt, dass die hier gezeigte Methode nicht unbedingt die effizienteste Variante ist, aber sie ist gut geeignet, das Prinzip der Symboltabelle zu vermitteln.

Wir implementieren die Symboltabelle als einen Stack von Namensräumen. Am Beginn der Namensauflösung ist unsere Symboltabelle leer, das heißt, es ist kein Namensraum auf dem Stack gespeichert. Bei Besuch der AST-Wurzel legen wir den Wurzelnamensraum an und speichern eine Referenz auf denjenigen AST-Knoten, der diesen Namensraum geöffnet hat (A). Auf den Folien ist der aktuell besuchte Knoten rot umrandet und ich habe für Sie annotiert, ob wir gerade in der Pre-Order- oder in der Post-Order-Visitor-Funktion sind.

Beim Besuch einer Deklaration legen wir in dem Namensraum, der ganz oben auf dem Stack liegt, ein entsprechendes Mapping an. Zum Beispiel: tmp -> B oder fib -> D. Wenn wir einen benannten Namensraum besuchen (math), legen wir zuerst ein Mapping im aktuellen Namensraum an (math->C) und legen erst danach einen neuen, leeren Namensraum auf den Stack.

Treffen wir auf eine Namensreferenz, so führt die findName()-Funktion die CNSR-Namensauflösung durch: Beginnend beim obersten Namensraum auf dem Stack suchen wir nach dem referenzierten Namen. Finden wir den Namen nicht, so gehen wir immer eine Ebene in unserem Stack nach unten. Erst, wenn wir auch im Wurzelnamensraum keine Deklaration finden, geben wir einen Übersetzungsfehler aus; es wurde ein Name verwendet, der niemals deklariert wurde. Die gefundene Deklaration speichern wir als Referenz in einem Attribut (gestrichelte Linien).

Beim Aufsteigen aus dem rekursiven Abstieg bauen wir die aufgestapelten Namensräume wieder ab. Um sie im weiteren noch verfügbar zu haben, können wir die befüllten Namensräume aber auch als AST-Attribut an die Knoten hängen (nicht gezeigt).

Im Folgenden sehen Sie eine minimale Implementierung einer Symboltabelle. Zum Experimentieren habe ich alle AST-Knoten durch entsprechende Strings ersetzt und die einzelnen API-Aufrufe selbst getätigt. Spielen Sie damit herum! Benennen Sie, beispielsweise, die zweite Deklaration von tmp um und beobachten Sie, wie sich die Ausgabe ändert.

class Namespace:
    def __init__(self, decl):
        # str -> decl
        self.names = {}
        # Verzeigerung von Deklaration und Namespace
        self.decl = decl

    def createName(self, name, decl):
        self.names[name] = decl

    def findName(self, name):
        if name in self.names:
            return self.names[name]
        else:
            return None

    def __repr__(self):
        return "[%s: %s]" %(self.decl, self.names)

class SymbolTable:
    def __init__(self):
        self.namespaces = []

    def openNamespace(self, decl):
        NS = Namespace(decl)
        self.namespaces.append(NS)

    def closeNamespace(self, decl):
        NS = self.namespaces.pop()
        assert NS.decl == decl

    def createName(self, name, decl):
        # self.namespace[-1] ist das letzte Element der Liste!
        self.namespaces[-1].createName(name, decl)

    def findName(self, name):
        i = len(self.namespaces)
        while i > 0:
            i = i - 1
            decl = self.namespaces[i].findName(name)
            if decl != None:
                return decl
        raise RuntimeError("Name %s not found" % name)

    def __repr__(self):
        return "\n".join([repr(x) for x in self.namespaces])



ST = SymbolTable()

# pre_Namespace(A)
ST.openNamespace("A")

# pre_VarDecl(B)
ST.createName("tmp", "B")

# pre_Namespace(C)
ST.createName("math", "C")
ST.openNamespace("C")

# pre_Namespace(D)
ST.createName("fib", "D")
ST.openNamespace("D")

# pre_VarDecl(E)
ST.createName("tmp", "E")

# pre_DeclRef(F)
decl = ST.findName("tmp")
print("Decl: " + decl)
print("Symbol Table:")
print(repr(ST))

Graphiken und Animationen

PreviousNext

Das gezeigte Muster zur Namensauflösung funktioniert hervorragend, solange die Deklarationen in strikter Ordnung vor ihren Referenzen auftauchen müssen. Dies ist zum Beispiel bei C der Fall. Wollen wir diese Regel etwas aufweichen, indem wir erlauben, dass innerhalb eines Namensraums Referenzen vor ihren Deklarationen auftauchen können (wie dies bei Methoden in Java der Fall ist), so müssen wir zweimal über den AST traversieren: Beim ersten Mal sammeln wir alle Deklarationen ein und stecken sie in die Namensräume, welche wir an die AST-Knoten hängen. Beim zweiten Mal lösen wir alle Namensräume wieder auf.

Die andere Interaktion, die wir bereits im Kapitel zur Namensauflösung besprochen haben, sind überladene Funktionen. An dieser Stelle schauen wir uns nur die Einbindung der dort besprochenen Strategie (die Parametertypen werden Teil des Namens) an. Hierfür erzeugt der Code ein signatur-Objekt, welches als "Name" verwendet wird. Dort fügen wir, neben dem aufgerufenen Funktionsnamen auch noch die Parametertypen an und suchen nach der Deklaration. Haben wir diese gefunden, so speichern wir sie als Attribut (call.decl) und verwenden den Rückgabetyp als Typen des CallExpr-Knoten (call.Type = ...).

Mit der Baumtraversierung haben wir eine Technik bekommen, um S-Attribute auszurechnen. Die Symboltabelle hat uns dazu befähigt, Namensauflösung als ein L-Attribut zu berechnen. Aber was tun wir, wenn wir einen Zyklus in unseren Attributabhängigkeiten haben. Also wie berechnen wir eine Attributgleichung, bei der ein Attribut über Umwege von seinem eigenen Attributwert abhängt. Oder, wenn die Abhängigkeiten komplexer sind als einfach von unten nach oben oder von links nach rechts.

Im Beispiel habe ich eine solche Attributabhängigkeit mit zwei Knoten gezeigt. Zum einen sollen dort die beiden Attributwerte x.h und y.h aufeinander folgende Ganzzahlen sein, und zum anderen soll y.h genau doppelt so groß sein wie x.h. Diese Bedingungen sind zyklisch und können nur von x.h=1 und y.h=2 erfüllt werden. Ich habe diese Beispiel absichtlich so gestaltet, dass es nichts mit Programmiersprachen zu tun hat, sondern es soll nur klar werden, was es bedeutet, eine zyklische Attributabhängigkeit in einem AST zu haben.

Ein solch komplexes, unter Umständen zyklisches, System von Attributabhängigkeiten kann aber auch bei Programmiersprachen nützlich sein: Lange Zeit haben Informatiker versucht, Sprachregeln so zu gestalten, dass die semantische Analyse alleine mit S- und L-Attributen dargestellt werden kann. Dies führt aber dazu, dass häufig mehr Annotationen durch den Programmierer notwendig waren, da alles vor seiner Verwendung explizit angegeben werden musste (z.B. Namensdeklarationen oder Typannotationen). Häufig kommt man als Programmierer bei solch expliziten Sprachen auf den Gedanken: "Eigentlich müsste der Übersetzer das doch sehen. Das ist doch super offensichtlich!".

Dieses Gefühl entsteht beispielsweise häufig bei expliziter statischer Typisierung: Eigentlich verwenden wir eine Variable so, dass doch, aus dem Kontext(!), klar ist, welcher Typ gemeint ist. Mit Hilfe der Typinferenz können wir den Übersetzer dazu befähigen den Typen in solchen Situationen zu berechnen. Dabei leitet der Übersetzer die statischen Variablentypen aus der konkreten Verwendung der Variablen automatisch ab. Der formale Hintergrund und die häufigst eingesetzte Variante ist die Hindley-Milner-TypinferenzWikipedia: Typinferenz_nachHindley-Milner.

Nachteil an dieser komplexen Typinferenz ist, dass die Typattribute nun ein zyklisches Gleichungssystem bilden können, welches wir nicht mehr mit einfacher Baumtraversierung berechnen können. Wir brauchen eine mächtigere Technik, welche ich im Folgenden, überblickshalber, vorstellen werde: Die (syntaktische) Unifikation.

Graphiken und Animationen

PreviousNext

Typinferenz und Unifikation kommen insbesondere bei funktionalen Programmiersprachen, die generische TypenSiehe Polymorphismus. verwenden (z.B. Haskell), zum Einsatz. Wir wollen nun schrittweise durchgehen, wie die Typinferenz in diesen Sprachen funktioniert und wie wir Unifikation zur Auflösung zyklischer Attribute verwenden.

Zunächst stellen wir, wie gewohnt, die Attributgleichungen auf. In unserem Beispiel betrachten wir einen Funktionsaufruf append(p1, p2), für den wir zwei Dinge wissen: Zum einen wissen wir, dass append() als erstes Argument eine Liste mit beliebigen Elementtypen bekommt und das zweite Argument an diese Liste anhängt, bevor sie zurückgegeben wird. Dabei muss der zweite Parameter den selben Typen haben wie die ListenelementeIn kurz: append() fügt ein Element, typsicher, an eine homogene Liste an.. Zum zweiten wissen wir, dass p2 vom Typ int ist.

Allerdings wissen wir, zu diesem Zeitpunkt, einige Dinge noch nicht: Welchen Typ hat p1? Welchen Rückgabetypen hat die gesamte CallExpr? Was ist die konkrete Aufrufsignatur für append()? Alle Typen, die wir noch nicht kennen, ersetzen wir in den Attributgleichungen durch Typvariablen. Konkrete Werte für diese Variablen zu finden, ist nun unser Ziel für die Typinferenz.

Mit diesem Typvariablen können wir nun die semantischen Sprachregeln als Gleichheitsbedingung formulieren. Im Beispiel ist die relevante Sprachregel: "Bei einem Funktionsaufruf müssen Parametertypen und Argumenttypen gleich sein. Der Rückgabetyp ergibt sich aus der Funktionssignatur". Ersetzen wir alle Attributreferenzen in dieser Bedingung durch die entsprechenden Gleichungen mit den freien Typvariablen, so erhalten wir die Bedingung: Der Term ([Gamma], Gamma)->[Gamma] soll gleich sein mit dem Term (Beta, int)->Alpha! Um diese Bedingung zu erfüllen, müssen wir die freien Typvariablen geschickt durch entsprechende Typausdrücke ersetzen. Der Prozess eine solche Ersetzung zu finden heißt Unifikation.

Im Beispiel führe ich, nacheinander, drei Ersetzungen durch, für die drei freien Typvariablen durch. Am Ende dieser Sequenz von Ersetzungen sind beide Terme an dem Funktionsaufruf gleich und wir haben erfolgreich eine Typinferenz durchgeführt. Hätten wir keine unifizierende Ersetzung gefunden, so hätten wir einen Übersetzungsfehler signalisieren müssen. Aber in unserem Fall hat alles geklappt: Wir wissen nun, dass p1 eine Liste von Ganzzahlen ist, dass der Rückgabetyp des Funktionsaufrufs ebenfalls eine Ganzzahlliste ist, und dass append() auf Ganzzahllisten operiert.

Die zentrale Technik der Typinferenz ist die Unifikation. Wir wollen ganz kurz definieren, was die Unifikation im Rahmen der Typinferenz leistet. Die Unifikation arbeitet auf mehreren geschachtelten Termen, die freie Variablen enthalten. In unserem Fall sind Typausdrücke mit freien Typvariablen die Terme, welche verarbeitet werden sollen (T1, T2). Dabei können die Typvariablen mehrfach in einem Term oder in mehreren Termen vorkommen, müssen aber in jedem Fall durch den selben Typausdruck ersetzt werden. Dieses mehrfache Auftreten einer Variable erlaubt es uns, die zyklischen Abhängigkeiten zu notieren.

Die Unifikation berechnet für die gegebenen Terme eine Sequenz von Ersetzungen, bei denen immer eine Typvariable durch einen konkreten Typausdruck ersetzt wird. Dabei ist die Reihenfolge der Ersetzungen relevant! Im Beispiel sehen wir, dass ich für die selben zu unifizierenden Typausdrücke eine andere unifizierende Ersetzungssequenz angegeben habe, die allerdings zum selben Ergebnis führt.

Für zwei unifizierbare Terme gibt es immer unendlich viele unifizierende Ersetzungen, denn wir können immer noch eine weitere nutzlose Unifikation hinzufügen (z.B. Alpha->Beta, Beta->Alpha, Alpha->Beta, Beta->list(Gamma),....). Daher suchen wir nicht nur irgendeine Unifikation, sondern den allgemeinsten Unifikator, welcher beide Terme angleicht und nur die wirklich notwendigen Ersetzungen vornimmt.

In der Literatur gibt es mehrere Verfahren, um die Unifikation effizient durchzuführen. Dabei wurde der erste Algorithmus von Robinson, welcher im schlimmsten Fall noch exponentielle Laufzeit hat, verbessert, sodass heute Unifikation in linearer Laufzeit möglich ist. Wir wollen die konkreten Algorithmen an dieser Stelle nicht diskutieren. Sollten Sie sich für die algorithmischen Details dennoch interessieren, seien Sie auf den Blogeintrag von Eli Bendesky verwiesen. Dort finden Sie eine Implementierung des Robinson-Algorithmus in Python.