Zusammenfassung. Dieser Erfahrungsbericht beschreibt zum einen ein studentisches Projekt an der Universitat Bremen, in dem eine Programmiersprache namens Monty entworfen und implementiert wurde. Des Weiteren wird auch die Sprache selbst anhand einiger Beispiele vorgestellt. Monty soll die Vorteile von klassischen Programmiersprachen wie C++ und Java mit denen von Skriptsprachen wie Ruby und Python kombinieren. Das Informatikstudium an der Universitat Bremen ist schon seit seinen Anfangen in den 1980er Jahren projektorientiert. In den viersemestrigen Projekten des Diplomstudiengangs haben die Studierenden den kompletten Softwareentwicklungskreislauf von Spezi kation der Anforderungen, Entwurf der Architektur uber Implementierung bis hin zu Test und Dokumentation durchlaufen. Diese Projekte sind im jetzigen Bachelor- und Masterstudium aufgeteilt worden in zweisemestrige Bachelorprojekte (mit 18 Credit Points ) und zweisemestrige Masterprojekte (mit 24 Credit Points ), wobei Masterprojekte oft als Fortsetzungen von Bachelorprojekten konzipiert werden. Beim Masterprojekt Monty's Coconut ist besonders, dass es von Studierenden selbst initiiert wurde: Zwei Studenten gewannen Marcus Ermler und Berthold Ho mann als Betreuer fur ihre Projektidee und erarbeiteten gemeinsam einen Projektvorschlag, fur den sie dann zwolf weitere Studierende begeistern konnten. Sonst entstehen die meisten Projektvorschlage aus Forschungsthemen der Arbeitsgruppen, unter denen die Studierenden dann auswahlen. Im Projekt Monty's Coconut sollte mit dem Entwurf der Sprache Monty ein Versuch unternommen werden, die Lucke zwischen klassischen Programmiersprachen und Skriptsprachen zu schlie en. Einen Referenzpunkt stellte die von David Watt (Universitat Glasgow) in [Wat05] vorgeschlagene Sprache dar, die ebenfalls Monty hei t, wobei in dieser Studie jedoch das Zusammenfuhren von dynamischer und statischer Typisierung im Mittelpunkt stand. Vor dem eigentlichen Projektbeginn haben sich die Studierenden inhaltlich im Kurs Ubersetzerbau, im Seminar Skriptsprachen und im Praktikum Ubersetzerwerkzeuge auf das Projekt vorbereitet und projektbegleitend in Kursen der Studierwerkstatt Methoden zum Projektmanagement und zur Kon iktbehandlung angeeignet. Von Oktober 2013 bis September 2014 wurden in wochentlichen vierstundigen Plenumstre en jeweils die Ergebnisse der vergangenen Woche diskutiert und Aufgaben fur die Arbeit von Untergruppen in der nachsten Woche verteilt. Die Arbeit im Projekt lasst sich grob in zwei Phasen untergliedern: (1) Diskussion und Entwicklung von Sprachkonzepten und (2) Erstellung der Sprachde nition mit paralleler Entwicklung des Compilers. Am Ende der ersten Phase wurde die bis dahin entwickelte Konzeption der Sprache auf einem selbst organisierten Workshop mit David Watt diskutiert. In Phase (2) wurde auf dem Projekttag des Fachbereichs Mathematik/Informatik der Zwischenstand des Projekts den Studierenden, Mitarbeiterinnen und Mitarbeitern prasentiert. Zum Abschluss wurden die Ergebnisse dann in einem o entlichen Vortrag auch Interessierten aus anderen Fachbereichen vorgestellt.
Dieses Papier ist einerseits ein Erfahrungsbericht, der den Projektverlauf und die gro ten Herausforderungen im Sprachentwurf zusammenfassen soll. Daruber hinaus wird auch die Sprache Monty selbst vorgestellt und anhand von Beispielen erlautert.
Die restlichen Abschnitte sind daher folgenderma en gegliedert: In Abschnitt 2 wird auf den Entwurf von Monty eingegangen, d.h. die Zielsetzung beim Sprachentwurf und die darin umgesetzten Konzepte. Abschnitt 3 stellt den implementierten Compiler vor. In Abschnitt 4 ziehen wir ein Fazit des Projekts und wagen uns an eine vorlau ge Bewertung von Monty. 2
Klassische Programmiersprachen wie C++ [Str13] und Java [GJS+14] haben ein statisches Typsystem und werden mit Compilern implementiert. Ihre Programme sind vielleicht etwas aufwandig zu schreiben, konnen dafur aber auf Typfehler uberpruft und e zient ausgefuhrt werden. Dagegen werden Skriptsprachen wie Ruby [FM08] und Python [vRD11] meist interpretiert. Mit ihrer knappen Syntax und ihrer dynamischen Typisierung sind sie auf schnelles und bequemes Schreiben ausgerichtet, wobei Geschwindigkeitseinbu en bei der Ausfuhrung in Kauf genommen werden. Die Sprache Monty wurde mit dem Ziel entwickelt, die Lucke zwischen Programmiersprachen und Skriptsprachen zu uberbrucken (siehe Abbildung 1). Eine einfach zu erlernende Syntax und eine vorwiegend statische, aber exible Typisierung soll weiterhin vergleichsweise hohen Entwicklungskomfort bieten, ohne Abstriche bei der E zienz machen zu mussen, denn die Sprache wird kompiliert. Die Objektorientierung ist klassenbasiert, wobei { im Gegensatz zu Java und C++ { in Monty alle Werte Objekte sind, auch Wahrheitswerte und Zahlen.
+ C+ a v a J
Monty
y Rub n o h t y P klassische Programmiersprachen Skriptsprachen Abbildung 1: Die Sprache Monty soll die Lucke zwischen Programmier- und Skriptsprachen uberbrucken Schon im Semester vor dem eigentlichen Projektbeginn wurden im Seminar Skriptsprachen viele altere und neuere Sprachen in Hinblick auf die von ihnen unterstutzten Konzepte und die Qualitat ihres Entwurfs analysiert. In der ersten Phase des Projekts wurde dann intensiv diskutiert, welche Konzepte in Monty unterstutzt werden sollen. Bei der Vererbung standen beispielsweise die Einfachvererbung mit Interfaces wie in Java, mit traits wie in Scala [OSV10] und allgemeine Mehrfachvererbung wie in C++ zur Debatte. So wurde die Grundlage fur einen detaillierten Anforderungskatalog an Konzepten und Eigenschaften der Sprache gelegt. Im Rahmen eines zweitagigen Workshops wurden diese Uberlegungen einem externen Berater vorgestellt und mit ihm diskutiert: David Watt von der Universitat Glasgow hatte zuvor ebenfalls eine Sprache mit dem Namen Monty konzipiert [Wat05], die ahnliche Ziele verfolgte und eine wichtige Inspiration fur die hier vorgestellte Sprache war. (Auf die Unterschiede zwischen David Watts Monty und unserer Sprache gehen wir am Ende dieses Abschnitts ein.)
Syntaktisch erinnert Monty stark an Python, was vor allem dadurch deutlich wird, dass Blocke nicht durch geschweifte Klammern oder Schlusselworter begrenzt, sondern eingeruckt werden. Beispiel 1 zeigt ein einfaches Monty-Programm. Anweisungen konnen wie in einer Skriptsprache als Sequenz aneinandergereiht werden, ohne dass zusatzliche Konstrukte wie main-Funktionen oder Klassen eingefuhrt werden mussen. Array<Int> numbers := [45, -13, 18, -5, -9, 0, 16] Bool positive(Int x):
return x > 0 print(numbers.filter(positive)) // [45, 18, 16]
Das Beispiel de niert ein Array von Int -Objekten und eine Funktion, die auf die Elemente des Arrays angewendet werden kann. Die Klasse Array ist generisch: sie kann fur beliebige andere Elementtypen instantiiert werden. Daruber hinaus ist sie eine Implementierung der abstrakten Klasse Sequence, von der auch Typen wie List und String erben. Die Zuweisung wird in Monty im Gegensatz zu den anderen oben genannten Sprachen durch ein \:=" ausgedruckt, da diese Schreibweise mathematisch plausibler ist. Somit kann das einfache Gleichheitszeichen \=" fur das Gleichheitspradikat benutzt werden.
In der letzten Zeile des Beispiels wird die Methode lter aufgerufen, die ebenfalls auf Sequence de niert ist. Sie erhalt als Parameter die Funktion positive, die als Pradikat fur das Filtern verwendet wird. Dies ist moglich, da Funktionen und Prozeduren ebenfalls Objekte sind und somit als Parameter oder Ruckgabewerte fur Funktionen verwendet werden konnen.
Beispiel 2 zeigt die De nition einer Klasse Vector2 fur Vektoren im Vektorraum R2. Die Klasse besitzt zwei Attribute vom Typ Float. Die Sichtbarkeit von Attributen und Methoden wird mit Symbolen ausgedruckt, wie sie auch in UML-Klassendiagrammen [RJB04] verwendet werden. Dabei steht + fur public, # fur protected, - fur private und ~ fur package. Die Methode initializer wird bei der Instantiierung aufgerufen.
Die Klasse Vector2 implementiert au erdem drei spezielle Methoden, die Operatoren uberladen: Die Addition mit einem anderen Vektor, die Multiplikation mit einem Skalar und das Skalarprodukt. Bei einem Aufruf der Form a + b wird die Methode operator + auf dem Objekt a aufgerufen und b als Parameter ubergeben. Dies erlaubt eine intuitive Notation von Operationen auf Vektoren, was in den letzten Zeilen des Code-Beispiels deutlich wird. class Vector2: # Float x # Float y + initializer(Float x, Float y): self.x := x self.y := y + Vector2 operator +(Vector2 other): // vector addition
return Vector2(self.x + other.x, self.y + other.y) + Vector2 operator *(Float other): // multiplication with a scalar
return Vector2(self.x * other, self.y * other) + Float operator *(Vector2 other): // scalar product
return self.x * other.x + self.y * other.y Vector2 p := Vector2(2.5, 3.75) Vector2 q := Vector2(1.75, 6.89) Vector2 r := (p*2.0)+q // Vector2(6.75, 14.39) Float f := p*q // 30.2125
Beispiel 2: De nition und Benutzung von Klassen in Monty (2D-Vektoren)
Monty besitzt ein statisches Typsystem, um eine schnelle Ausfuhrung der Programme zu ermoglichen. Um dem Komfort von Skriptsprachen naher zu kommen, erlaubt das Typsystem die dynamische Erweiterung von Objekten. Dies wird in Beispiel 3 benutzt, um fur ein Objekt zusatzliche Attribute zu de nieren. Angenommen, es gabe eine Funktion normalize, die einen Vektor als Parameter erwartet und den normalisierten Vektor zuruckliefert (d.h. einen Vektor, der in die gleiche Richtung zeigt, aber die Lange 1 hat). Die Klasse Vector2 besitzt kein Attribut, das angibt, ob ein Vektor normalisiert ist oder nicht. Mit dem Operator \->" kann fur das Vector2-Objekt q ein dynamisches Attribut isNormalized vom Typ Object de niert werden. In der Bedingung \q->isNormalized as Bool" wird darauf dynamisch zugegri en. Dabei muss zur Laufzeit uberpruft werden, ob das Attribut vorhanden ist und den richtigen Typ hat. Das Schlusselwort \as" stellt einen Typcast dar. Ein Ausdruck der Form exp as type wandelt den Wert des Ausdrucks exp in den Typ type um, sofern dies nach den Regeln des Typsystems moglich ist. Zugunsten des Entwicklungskomforts kann also explizit auf die Typsicherheit und Performanz statischer Typisierung verzichtet werden, um eine Art Duck Typing zu erreichen [CRJ12]. Vector2 p := Vector2(2.5, 3.75) Vector2 q := normalize(Vector2(1.75, 6.89)) q->isNormalized := true // introducing a dynamic attribute if q->isNormalized as Bool: // accessing a dynamic attribute print("The vector is normalized!")
Attribute, die nicht dynamisch zu einer Klasse hinzugefugt werden, mussen zum Zeitpunkt der Instantiierung initialisiert sein, da es in Monty keine Null-Referenzen gibt. Dies kann entweder bei der Deklaration der Attribute oder in der Initialisierungsmethode geschehen. Beispiel 4 illustriert, wie ohne Null-Referenzen ein Binarbaum implementiert werden kann. Fur den trivialen Fall (in diesem Fall die Blatter des Baumes) muss explizit ein Typ eingefuhrt werden. Dies stellt zwar auf der einen Seite einen geringen Overhead dar, auf der anderen Seite bietet es aber den Vorteil, dass stets Gewissheit uber den Typen eines Knoten besteht. class Branch<T> inherits BinaryTree:
BinaryTree<T> left T value BinaryTree<T> right + initializer(BinaryTree<T> left, T value, BinaryTree<T> right): self.left = left self.value = value self.right = right + height():
return 1+max(self.left.height(), self.right.height) class Leaf<T> inherits BinaryTree: + height(): return 0
Die vollstandige De nition der Sprache [Mon14b] enthalt noch einige weitere Konzepte, die in diesem Papier aus Platzmangel nicht beschrieben werden konnen. Dazu zahlen eine nahere Beschreibung abstrakter Klassen, allgemeiner Mehrfachvererbung, von Modulen und Paketen. Daruber hinaus sind weitere Konzepte in der gegenwartigen Fassung der Sprache noch nicht enthalten: lokale Typinferenz, Lambda-Funktionen, eingeschrankt generische Parameter und die explizite Verwendung von Mutability und Immutability. Solche zukunftigen Erweiterungen von Monty sind im Bericht [Mon14a] beschrieben.
Auch die von David Watt in [Wat05] vorgeschlagene Sprache Monty (die nie implementiert wurde) hat sich syntaktisch an Python orientiert und dynamische Typisierung erlaubt. Der Schwerpunkt dieser Studie liegt in Uberlegungen zur Unterscheidung von Klassen mit und ohne veranderlichen Attributen (mutable und immutable) und zur Varianz bei den Typparametern generischer Klassen. Syntaktisch und auch in Hinblick auf die Objektorientierung (Werte als Objekte, allgemeine Mehrfachvererbung) orientiert sich unser Monty aber eher an Python als an Java. 3
Der Compiler fur Monty wurde in Java implementiert. Damit wurde schon wahrend der Arbeit an der Sprachde nition begonnen. Im Folgenden soll ein Einblick in die Architektur und Funktionsweise des Compilers gegeben werden (vgl. Abbildung 2).
Syntaxanalyse Monty-Compiler Kontextanalyse Codegenerierung
LLVM Compiler nativer Code
Interpreter Prozessor
Wird der Compiler ausgefuhrt, so erwartet er eine Datei mit Monty -Code. Eine mit dem ANTLR-Framework [Par14a] generierte und in den Compiler eingebundene Syntaxanalyse generiert aus der eingelesenen Datei einen Ableitungsbaum. In den folgenden Schritten werden einige Entwurfsmuster (Design Patterns ) eingesetzt1. Hervorzuheben ist hier das External Tree Visitor-Pattern 2. Auf Grundlage des Ableitungsbaumes wird zuerst ein abstrakter Syntaxbaum (AST) erstellt, auf dessen Basis alle weiteren Operationen ausgefuhrt werden. Mehrere Visitors laufen dabei uber den AST, wobei verschiedene Aktionen auf den besuchten Knoten ausgelost werden. Die Visitors ubernehmen dabei Aufgaben wie:
Identi kation: Welche Deklaration ist in dem aktuellen Kontext diesem Bezeichner zugeordnet? Typuberprufung : Passen die Typen zueinander, etwa in Zuweisungen oder bei Funktionsaufrufen, oder ist mit Fehlern zu rechnen? Kontroll ussvalidierungen : Kommen break- und skip-Befehle nur in Schleifenrumpfen vor? Wird der returnBefehl nur innerhalb von Funktionsrumpfen verwendet und dort auf allen Verzweigungen erreicht? Der letzte Visitor, der uber den AST lauft, generiert LLVM -Code. LLVM [LA04] ist eine Architektur und Sammlung von Werkzeugen fur die Codeoptimierung und Codeerzeugung in Compilern. Der generierte Code liegt dabei in einer speziellen Zwischenreprasentationssprache vor, die Bestandteil dieser LLVM -Werkzeugsammlung ist. Das Ergebnis des Monty -Compilers ist also ein in LLVM -Code ubersetztes Monty -Programm. Dieses kann anschlie end dank der LLVM -Architektur sowohl direkt interpretiert als auch erst kompiliert und dann ausgefuhrt werden. Die Verwendung von LLVM ermoglicht es ebenso, Monty -Programme zu optimieren und fur eine Vielzahl von Plattformen zu ubersetzen. 4
Im Projekt Monty's Coconut wurde die Programmiersprache Monty entworfen, de niert und ein Compiler fur einen Gro teil der Sprache implementiert. Wir wollen hier zunachst zusammenfassen, welche Erfahrungen wahrend des Projekts gewonnen wurden, sowie anschlie end die Sprache und den Compiler bewerten. Der Entwurf einer Programmiersprache ist zeitaufwandig. Es dauerte drei Monate, um einen Katalog von Konzepten fur Monty zu erstellen. In langen wochentlichen Plenumssitzungen, deren Themen in jeweils wechselnden Kleingruppen vorbereitet wurden, haben die Teilnehmerinnen und Teilnehmer sehr engagiert den Entwurf der Sprache diskutiert. Wegen unterschiedlicher Vorkenntnisse und verschiedener Lieblingssprachen waren die Diskussionen oft kontrovers und langwierig. Gelegentlich entstand so der Eindruck, man kame kaum voran oder drehe sich sogar im Kreis. Gleichzeitig wuchs die Besorgnis, Zeit zu vergeuden, und der Wunsch, endlich konkreter an sichtbaren \Produkten" zu arbeiten. Diesen Prozess hatte man potenziell rationalisieren konnen, ware schon gleich zu Projektbeginn ein Interpreter fur eine elementare objektorientierte Sprache implementiert worden. Anhand dieser Implementierung hatte man vermutlich zielgerichteter diskutieren konnen, welche Auswirkungen bestimmte Erweiterungswunsche auf De nition und Implementierung der Sprache haben. Zur Strukturierung der Diskussion ware es auch nutzlich gewesen, Teilnehmerinnen und Teilnehmer zu \Fachleuten" fur Sprachen wie Python und Ruby oder fur Konzepte wie Mehrfachvererbung und Typinferenz zu ernennen, damit sie ihr Detailwissen jederzeit in die Diskussion einbringen konnen.
Die De nition einer Programmiersprache ist schwierig. Manche Probleme mit Konzepten { und speziell mit deren Kombination { haben sich erst gezeigt, als man die Sprache in sich schlussig, prazise und gleichzeitig 1Terence Parr, der Entwickler von ANTLR, schlagt diese Patterns in Kombination mit ANTLR vor [Par14b]. 2Bei dem External Tree Visitor handelt es sich um eine Variante des Visitors von Gamma et al. [GHJV95]. verstandlich beschreiben musste. Hilfreich ware wohl gewesen, zunachst nur eine elementare Kernsprache zu de nieren, um sie dann schrittweise zu erweitern. Ein weiteres, organisatorisches Problem lag darin, dass die Arbeit an der De nition nur wenig Vorsprung vor der Implementierung hatte, so dass die Reihenfolge, in der Konzepte de niert werden mussten, aufwandig mit der Compilergruppe synchronisiert werden musste. Auch hier hatte womoglich der Entwurf einer erweiterbaren Kernsprache die Abhangigkeiten zwischen den Gruppen reduzieren konnen, um so den Fokus von der Organisation auf die Konzepte zu verlagern. Die Entwicklung eines Compilers ist sehr anspruchsvoll. Das kann in einem Jahr kaum bewaltigt werden. Glucklicherweise standen Werkzeuge zur Verfugung: ANTLR fur die Syntaxanalyse, und LLVM fur die Codererzeugung. Durch Aufteilung in mehrere Visitors, die voneinander unabhangige Teilaufgaben ubernehmen, konnte der Compiler gut im Team entwickelt und die Arbeit parallelisiert werden, so dass wahrend der Implementierung nur selten Engpasse entstanden. Testgetriebene Entwicklung trug zur Qualitatssicherung bei, und ein diszipliniertes Vorgehensmodell { umgesetzt mit Hilfe von Git { sorgte dafur, dass es immer eine stabile Fassung des Compilers gab.
Monty ist ein erster Schritt in die richtige Richtung. Im Rahmen des Projekts konnten nicht alle Ideen umgesetzt werden. So wurden einige Aspekte wie die Typinferenz oder Lambda-Funktionen in der Spezi kation und folglich im Compiler gar nicht berucksichtigt und haben nur uber das Enhancement Proposal [Mon14a] ihren Weg in die Sprache gefunden. Daher kann wohl nicht davon gesprochen werden, dass die Lucke zwischen den gegenwartigen Sprachkonzepten tatsachlich geschlossen wurde, da noch viel Verbesserungspotential besteht. Grundsatzlich sind wir unserem Ziel aber schon nahe gekommen, da Monty sich zumindest innerhalb dieser Lucke positioniert. In Monty konnten eine leichtgewichtige Syntax und ein einheitliches Objektsystem mit einem statischen Typsystem in einer kompilierten Sprache vereint werden. Daruber hinaus enthalt Monty den SDA, der { wenngleich mit Einschrankungen { dynamische Typisierung in direkter Kombination mit statischer Typisierung ermoglicht. Der Compiler ist nur ein Prototyp. Er ubersetzt eine Teilsprache von Monty, produziert aber noch keinen guten Code. Optimierungen zu implementieren erscheint uns erst sinnvoll, wenn die Implementierung ansonsten vollstandig und stabil ist. Eine Standardbibliothek wurde auch noch nicht bereitgestellt, denn dies erfordert viel Routinearbeit, die spater nachgeholt werden kann.
Auch wenn die Arbeit an der Sprache und am Compiler bis zum Projektende nicht ganz abgeschlossen werden konnte, haben die Studierenden sehr viel gelernt uber Programmiersprachen und ihre Ubersetzer, auch uber die Schwierigkeiten der selbststandigen Arbeit in einem gro eren Team.
Im Ubrigen geht die Arbeit auch nach o ziellem Projektende weiter: Die Sprachde nition ist fertig, und am Compiler wird weiter gearbeitet. Umfangreichere Erweiterungen der Sprache und Verbesserung des Compilers sind Gegenstand von mehreren Abschlussarbeiten zu Themen wie beschrankten generischen Typparametern, automatischer Speicherbereinigung (garbage collection) und lokaler Typinferenz. Der aktuelle Stand des Projekts Monty's Coconut kann auf der Webseite http://www.informatik.uni-bremen.de/monty/ eingesehen werden. Danksagung. Die Autoren mochten sich bei David Watt dafur bedanken, dass sie den Namen Monty fur ihre Sprache verwenden durfen. Des Weiteren gilt unser Dank allen Teilnehmerinnen und Teilnehmern des Projekts Monty's Coconut fur ihre aktive Mitwirkung an der Entwicklung der Sprachspezi kation und des Compilers.
[CRJ12] Ravi Chugh, Patrick M. Rondon und Ranjit Jhala. Nested Re nements: A Logic for Duck Typing. In Proceedings of the 39th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL '12, Seiten 231{244, New York, NY, USA, 2012. ACM.
David Flanagan und Yukihiro Matsumoto. The Ruby Programming Language. O'Reilly, 2008. [GHJV95] Erich Gamma, Richard Helm, Ralph Johnson und John Vlissides. Design Patterns: Elements of Reusable Object-oriented Software. Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA, 1995. [GJS+14] James Gosling, Bill Joy, Guy Steele, Gilad Bracha und Alex Buckley. The Java Language Speci cation.
Addison-Wesley, 2014. 8. Au age. [OSV10] Martin Odersky, Lex Spoo und Bill Venners. Programming in Scala. Artima developer, 2010. 2.
Au age. [Par14b] Terrence Parr. Language Implementation Patterns. The Pragmatic Programmers, LLC, September 2014. Version 5.0. [Str13] [vRD11] Guido van Rossum und Fred L. Drake. Python Language Reference Manual. Network Theory Ltd,
Boston, March 2011. Release 3.2. [Wat05]
David A. Watt. The Design of Monty: a Programming/Scripting Language. Electronic Notes in Theoretical Computer Science, 141(4):5{28, 2005.