Grundlagen von Programmiersprachen, Spezialvorlesung, SS2000

Administratives

• zehn Übungsblätter
• erstes Übungsblatt: 08.05.2000
• Scheinbedingung: 50% sinnvoll bearbeitet
• erstes Blatt am 9.5.00, Abgabe 15.5.00, musterlösung auf Papier zu bekommen
• zweites Blatt am 15.5.00, Abgabe 22.5.00, musterlösung
• drittes Blatt am 22.5.00, Abgabe 29.5.00, musterlösung
• viertes Blatt am 5.6.00, Abgabe 19.6.00, musterlösung
• Fünftes Blatt am 19.6.00, Abgabe 26.6.00, musterlösung auf Papier zu bekommen
• Sechtes Blatt am 26.6.00, Abgabe 3.7.00, musterlösung auf Papier zu bekommen
• Siebtes Blatt am 3.7.00, Abgabe 10.7.00, musterlösung
• Achtes Blatt am 10.7.00, Abgabe 17.7.00, musterlösung
• am 17.7.00 und 24.7.00, kein Blätter mehr! Schöne Sommerferien!

Inhalt

Die Vorlesung behandelt die grundlegenden Konzepte moderner Programmiersprachen und ihre Realisierung anhand von Beispielen. Eine zentrale Rolle dabei spielen Abstraktionsmittel, die uns in die Lage versetzen Softwareprobleme so zerlegen, dass jedes Teil von einer einzelnen Person verstanden, benutzt und verändert werden kann. Dies erleichtert die Entwicklung, die Wartung, sowie das Testen/Verifizieren von Programmen.

Die Vorlesung verwendet Beispiele unter anderem aus den Sprachen Haskell, ML, Scheme, Smalltalk, Java und Prolog. Der Umgang mit diesen Sprachen wird in der Übung vertieft.

Ziele

• Verständnis der Konzepte, ihrer Realisierung und ihrer Kosten in verschiedenen Programmiersprachen
• Anwendung der Konzepte
• Bewertung einer Sprache (ist sie für eine Problemstellung geeignet?)
• Verständnis von grundlegenden Problemen des Sprachentwurfs

Vorläufige Gliederung

1. Einführung
2. Funktionale Programmierung: Überblick (Lisp, Scheme, ML, Haskell)
3. Grundlagen und Eigenschaften am Beispiel von Haskell (Berechnung durch Termersetzung, Auswertungsstrategien, konkrete Datentypen) [18][9]
4. Funktionen als Daten, Lambdakalkül [2]
5. Überladung, Polymorphie, Typen, abstrakte Datentypen [4][14][3]
6. Fortgeschrittene Konzepte: Typklassen, Monaden, Ein-/Ausgabe [10][16][19]
7. Fortgeschrittene Konzepte: Exceptions, Continuations, Dynamic scope
8. Allgemeine Konzepte: Speicherbereinigung (garbage collection) [12][20], Modulsysteme [11][13][8], Nebenläufigkeit [15]
9. Objektorientierte Programmierung: Überblick (Simula, Smalltalk, C++, Java)
10. Grundlagen (Vererbung, Subtyping, dynamische Bindung, Cloning, Objektkalkül) [5][1]
11. Eigenschaften am Beispiel von Smalltalk [7]
12. Fortgeschrittene Konzepte: Metaklassen, generische Funktionen, Typen [6]
13. Logikprogrammierung: Prolog
14. Constraintprogrammierung: Oz [17]

Programmiersprachen Online

der folgende Liste gibt URLs an für die Sprachen die (warscheinlich) in die Übungen verwendet werden. Sie sind alle frei zum downloaden und existieren für die meist verwendete Platformen (Linux, Windows, Sun, etc.) :

• Hugs 98
• SML 110.06
• Ocaml 3.00
• Scheme 48
• Java 1.2
• Swi Prolog
• VW Smalltalk 5i.1

Online Ressourcen

• Haskell (Sprachdefinition, Dokumentation zur Library, Implementierungen, weitere Infos)
• Scheme
• SML (Frequently Asked Questions, enthält auch Einführungen, etc.), OCaml
• Smalltalk
• Java
• Logic Programming
• Oz
• Paper of Cardelli on Type Systems

Extra Information

• Literaturhinweise
• Haskell syntax (core)
• SML syntax
• Scheme Report

References

 [1]

Martín Abadi and Luca Cardelli. A Theory of Objects. Springer-Verlag, 1996.

 [2]

Henk P. Barendregt. Functional programming and lambda calculus. In Jan van Leeuwen, editor, Handbook of Theoretical Computer Science--Formal Models and Semantics, volume B, chapter 7. Elsevier Science Publishers, 1990.

 [3]

Luca Cardelli. Type Systems, chapter 103, pages 2208-2236. CRC Press, 1997.

 [4]

Luca Cardelli and Peter Wegner. On understanding types, data abstraction, and polymorphism. ACM Computing Surveys, 17:471-522, December 1985.

 [5]

Kathleen Fisher and John C. Mitchell. What is an object-oriented programming language? Technical report, Stanford University, 1995.

 [6]

Daniel P. Friedman, Mitchell Wand, and Christopher T. Haynes. Essentials of Programming Languages. MIT Press and McGraw-Hill, 1992.

 [7]

Adele Goldberg and David Robson. Smalltalk-80: The Language and Its Implementation. Addison-Wesley, 1983.

 [8]

Robert Harper and Mark Lillibridge. A type-theoretic approach to higher-order modules with sharing. In Proc. 21st Annual ACM Symposium on Principles of Programming Languages, pages 123-137, Portland, OG, January 1994. ACM Press.

 [9]

Haskell 98, a non-strict, purely functional language. http://www.haskell.org/definition, December 1998.

 [10]

Mark P. Jones. Functional programming with overloading and higher-order polymorphism. In Advanced Functional Programming, volume 925 of Lecture Notes in Computer Science, pages 97-136. Springer-Verlag, May 1995.

 [11]

Mark P. Jones. First-class polymorphism with type inference. In Neil D. Jones, editor, Proc. 24th Annual ACM Symposium on Principles of Programming Languages, pages 483-496, Paris, France, January 1997. ACM Press.

 [12]

Richard Jones and Rafael Lins. Garbage Collection. John Wiley & Sons, 1996.

 [13]

David MacQueen. Modules for standard ML. Technical report, Bell Laboratories, Murray Hill, New Jersey, 1985.

 [14]

John C. Mitchell and Gordon D. Plotkin. Abstract types have existential types. ACM Transactions on Programming Languages and Systems, 10(3):470-502, July 1988.

 [15]

Simon Peyton Jones, Andrew Gordon, and Sigbjørn Finne. Concurrent Haskell. In Conference Record of POPL '96: The 23^rd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pages 295-308, St. Petersburg Beach, Florida, USA, January 1996.

 [16]

Simon L. Peyton Jones and Philip L. Wadler. Imperative functional programming. In Proc. 20th Annual ACM Symposium on Principles of Programming Languages, pages 71-84, Charleston, South Carolina, January 1993. ACM Press.

 [17]

Gert Smolka. The Oz programming model. In Jan van Leeuwen, editor, Computer Science Today, volume 1000 of Lecture Notes in Computer Science, pages 324-343. Springer-Verlag, Berlin, 1995.

 [18]

Peter Thiemann. Grundlagen der funktionalen Programmierung. Teubner Verlag, Stuttgart, 1994.

 [19]

Philip L. Wadler. The essence of functional programming. In Proc. 19th Annual ACM Symposium on Principles of Programming Languages, pages 1-14, Albuquerque, New Mexico, January 1992. ACM Press.

 [20]

Paul R. Wilson. Uniprocessor garbage collection techniques. Technical report, University of Texas, 1999.