Uni-Logo

Projekte für die Vorlesung Konzepte von Programmiersprachen

Einleitung

In den letzten drei Wochen der Vorlesung Konzepte von Programmiersprachen sollen in einer Projektphase die erworbenen Kentnisse vertieft werden. Jeder Student soll in der Projektphase eines der unten aufgeführten Projekte durchführen, nach Rücksprache mit dem Assistenten der Vorlesung kann auch ein eigenes Projekt gewählt werden.

Die Ergebnisse der Projektphase werden am Donnerstag, 23.7.2009, 14 Uhr, Geb. 101, Raum 01-016 vorgestellt. Jeder Student muss dazu einen individuellen Vortrag von 10 Minuten Länge halten. Die Projekt selbst können in Teams von zwei bis drei Studenten bearbeitet werden; die individuellen Vorträge sollen dann verschiedene Aspekte der erarbeiteten Lösung beleuchten.

Bevor mit der eigentlichen Arbeit am Projekt begonnen wird, sollte mit dem Assistenten eine Diskussion über den Inhalt der Aufgabenstellung erfolgen. Während der Projektphase und bei Erstellung des Vortrags sind solche Diskussionen natürlich auch hilfreich.

Projekt 1: Parametrische Polymorphie

In der Vorlesung wurde die Sprache INFERRED vorgestellt. Diese Sprache unterstützt keine parametrische Polymorphie, wie folgendes Beispiel demonstriert: 

let f = proc (x : ?) x
in if (f zero?(0)) then (f 11) else (f 22)

Der Typinferenzalgorithmus weist obiges Beispiel zurück, da f einmal mit dem Typ int -> int und einmal mit dem Typ bool -> bool verwendet wird. Mit parametrischer Polymorphie hat f den Type forall a. a -> a, so dass durch Instanzierung von a einmal mit int und einmal mit bool das Programm typkorrekt ist.

In diesem Projekt soll ein Typinferenzalgorithmus für eine Sprache mit parametrischer Polymorphie implementiert werden. Außerdem soll die Sprache explizite Referenzen (ähnlich wie in der Sprache EXPLICIT-REFS) unterstützen. Als möglich Erweiterung bietet sich ad-hoc Polymorphie im Stile von Haskells Typklassenmechanismus an.

Resourcen:

  • Types and Programming Languages. Benjamin C. Pierce. MIT Press, Cambridge, Massachusetts. 2002. ISBN 0-262-16209-1 (Das Buch ist bei uns in der Bibliothek verfügbar.)
  • Principal Type-schemes for Functional Programs. Luis Damas and Robin Milner. In Proceedings of the 9th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages. ACM, New York, NY. 1982. http://doi.acm.org/10.1145/582153.582176
  • Qualified Types: Theory and Practice. Mark P. Jones. Cambridge University Press. 1994. ISBN 0 521 47253 9. (Das Buch ist bei uns in der Bibliothek verfügbar.)

Projekt 2: Software Transactional Memory

In der Vorlesung wurde explizite Locking als Synchronisationstechik für nebenläufige Programme vorgestellt. In diesem Projekt soll mit Software Transactional Memory (STM) eine andere Synchronisationstechnik implementiert werden.

Die Idee hinter STM ist einfach: gewisse Codebereiche können als atomar gekennzeichnet werden und der Interpreter (bzw. das Laufzeitsystem für eine kompilierte Sprache) garantiert dann, dass diese Bereiche auch atomar ablaufen. Um möglichst viel Nenbenläufigkeit zu ermöglich soll die Atomizität allerdings nicht mittels Locks sondern durch eine optimistische Auswertungsstrategie erreicht werden: atomare Blöcke werden, ohne jedes Locking, in einer gewissen Sandbox Umgebung ausgeführt. Beim Verlassen eines atomaren Blocks wird dann geprüft, ob die Sandbox Umgebung konsistent mit dem globalen Heap ist und ob es während der Ausführung des atomaren Blocks zu keinen Konflikten kam. Ist beides der Fall werden die in der Sandbox Umgebung vorgenommenen Änderung in den globalen Heap übertragen. Andernfalls wird der atomare Block in einer neuen Sandbox Umgebung nochmals ausgeführt.

In diesem Projekt soll ein Interpreter für eine Sprache mit Nebenläufigkeit und Unterstützung für STM implementiert werden. Eine mögliche Erweiterung ist der Entwurf eines einfachen Typsystems, welches sicherstellt, dass in atomaren Blöcken keine unerwünschten Seiteneffekt auftreten, die beim Wiederholen des atomaren Blocks fatale Folgen haben könnten.

Resourcen:

  • Beautiful concurrency. Simon Peyton Jones. Chapter for the book "Beautiful code", edited by Greg Wilson, O'Reilly 2007. PDF
  • A Semantic Framework for Designer Transactions. Jan Vitek, Suresh Jagannathan, Adam Welc, and Antony L. Hosking. In Proceedings of ESOP 2004. LNCS 2986, Springer Verlag, Heidelberg. ISNB 978-3-540-21313-0. PDF

Projekt 3: Datalog

Datalog ist eine Querysprache für deklarative Datenbanken, welche auf dem logischen Programmierparadigma basiert. Programme in Datalog sind auch syntaktisch gültige Prolog Programme. Hier ist ein einfaches Beispiel in Datalog: 

parent(bill,mary).
parent(mary,john).

Durch diese beiden Fakten wird die Relation parent definiert und festgelegt, dass bill ein Elternteil von mary und mary wiederum ein Elternteil von john ist.

Mit den folgenden Regeln definiert man nun die ancestor Relation:

ancestor(X,Y) :- parent(X,Y).
ancestor(X,Y) :- parent(X,Z),ancestor(Z,Y).

Stellt man jetzt die Anfrage ancestor(bill,X) erhält man als mögliche Belegungen von X sowohl mary als auch john

In diesem Projekt soll ein Interpreter für Datalog geschrieben werden. Eine Erweiterungmöglichkeit ist z.B. das Einführen von Negation.

Resourcen:

  • What You Always Wanted to Know About Datalog (And Never Dared to Ask). S. Ceri, G. Gottlob, and L. Tanca. IEEE Transactions on Knowledge and Data Engineering Volume 1, Issue 1. 1998. PDF
  • Foundations of databases. Serge Abiteboul, Richard Hull, Victor Vianu. Addison-Wesley. 1995. (Das Buch ist bei uns in der Bibliothek verfügbar.)
  • Datalog Educational System