Topics on Programming Languages, Seminar, SS2001

Termin der Sitzungen nach Vereinbarung.

Betreuung

• Prof. Dr. Peter Thiemann
• Simon Helsen

Das Seminar findet auf Deutsch statt.

Goals

Programming Languages have come a long way since the invention of Cobol and Fortran in the early 50's. Powerful abstraction and control mechanisms have been introduced over the years to make the life of a software developer easier. However, these powerful features introduce more complexity and new problems of both theoretical and practical nature. The main goal of the seminar is to familiarise students with some modern techniques introduced in programming languages over the last few decades, many of which are slowly finding their way into mainstream languages. Topics range from compilation, e.g. type inference, runtime system issues, like garbage collection, to abstraction mechanisms, for instance macros, continuations, and mixins, as well as new programming idioms such as generative and constraint programming. The aim of the seminar is to increase the awareness of the potential of these techniques in programming language design and implementation.

Innovations are not always easily accepted in mainstream programming. This is evidenced by a funny column, dating from the early 80s, about an innovative (then!) programming language: "Real Programmers don't use Pascal".

Proposed topics and references

Note: Most of the papers referenced below are accessible on the Net. However, we already downloaded all Net-accessible papers on a local directory. Therefore, if you need a paper, just send me an e-mail, so you don't need to search yourself. Especially older papers may be hard to obtain, but in that case, we usually have a hardcopy around.

Type Inference

Hindley-Milner and beyond

Functional programming languages like Standard ML and Haskell use type inference to derive type information from expressions. The type inference process provides the user with a proof for partial correctness of her program.

• The first well-known and widely spread type inference algorithm is algorithm W and is based on the Hindley-Milner type system. It is part of the Standard ML programming language [29].
• The type system found in the Haskell programming language [16] is an extension of the Hindley-Milner system, adding type and constructor classes. Type inference becomes more difficult but remains fully automatic (i.e., it requires no user annotations).

Literature:

1. Louis Damas and Robin Milner, Principal Type-Schemes for Functional Programs [9]
2. Robin Milner, A theory of type polymorphism in programming [28]
3. Oukseh Lee and Kwangkeun Yi, Proofs about a Folklore Let-polymorphic Type Inference Algorithm [27]
4. Mark Jones, A System of Constructor Classes: Overloading and Implicit Higher-Order Polymorphism [21]
5. Fritz Henglein, Type inference with Polymorphic Recursion [20]
6. Tobias Nipkow and Christian Prehofer, Type checking type classes [33]
7. Mark Jones, Typing Haskell in Haskell [22]

 

Object inference

Although automatic type inference has usually been considered in the context of functional languages, recent research is focusing on automated type inference for object languages. The primary goal for object inference is to augment object-oriented languages with flow analysis that catch errors like method not understood and other exceptions which are not always caught at compile-time.

Literature:

1. Jens Palsberg and Michael Schwartzbach, Object Oriented Type Systems [35]
2. Jens Palsberg, Efficient Type Inference for Object Types [34]
3. Martin Abadi and Luca Cardelli, A theory of Objects [1]

Garbage Collection Techniques

Basic Garbage Collection Techniques

Memory management is one of the most notorious sources for bugs in programs. Especially dereferencing deallocated pointers can lead to exceptions or -worse- to unspecified and unpredictable program behaviour. Since the invention of Lisp in the 60's, garbage collection has been used as a technique to take the burden of manual memory management from the programmer. Garbage collection was long thought to be very inefficient even though many algorithms with different space/time properties have been proposed and developed. Thanks to Java, garbage collection has become widely accepted and this seminar should give the participants an idea of how and why it works.

Literature:

1. Paul Wilson, Uniprocessor Garbage Collection Techniques [48]
2. Richard Jones and Raphael Lins, Garbage Collection [23]

 

Generational and distributed GC

Garbage collectors have become very efficient over the last few years. A particular clever and fast technique is generational garbage collection. The underlying philosophy is that not all dynamically allocated objects have the same space behaviour: some are very short lived whereas others stay around for a long time, perhaps the whole life time of the program. Hot Java implements a variation of generational garbage collection, thereby improving drastically on earlier Java runtime systems.

Garbage collection is also possible and necessary in parallel and distributed environments, where more than one process can access and mutate the object space. This makes manual memory management horrendously difficult and error-prone. Especially since the advent of the Internet, a lot of attention has been paid to extend garbage collection algorithms in a distributed setting.

Literature:

1. The article of Wilson and the book of Jones and Lins (see above)
2. Andrew Appel, Simple Generational Garbage Collection and Fast Allocation [2]
3. David Plainfossé and Marc Shapiro, A survey of distributed Garbage Collection Techniques [36]

Continuations

Continuations and the CPS transformation

The term continuation covers a range of techniques and applications. Basically, the word continuation can be understood as context: the "rest" of the execution, the contents of the stack at some point during execution, a function expressing what comes after the current expression etc. etc.

Continuations can be captured as first-class function values, for instance, in the Scheme programming language [24]. In Scheme, it is possible at any point in the program to catch the continuation of the current execution, name it, move it around and run it at some other point. Continuations are also related to a style of programming where every computation passes its result to a continuation, which is represented explicitly as a function. This transformation from direct-style into so-called Continuation-passing Style (CPS) can be done automatically and is a useful compilation and program transformation technique since it makes the flow of execution more explicit. Generally, handling and using continuations requires higher-order functions.

Literature:

1. Daniel Friedman, Mitchell Wand and Christopher Haynes, Essentials of Programming Languages (chapters 8-10) [14]
2. John Hatcliff and Olivier Danvy, A Generic account of continuation-passing style [18]
3. Olivier Danvy and Andrzey Filinsky, Representing Control: a study of the CPS transformation [10]

 

Applications for continuations

Continuations are a powerful abstraction mechanism, but what can you do with them? Continuations have been proven extremely useful in implementing multi-processing, concurrency and threads. A multi-processing facility requires three features: elementary exclusion, data protection, and process saving. Continuations seem to be a good tool for implementing the latter two. The paper by Wand describes the implementation of a multi-processing facility in Scheme using continuations. Draves, Bershad, Rashid and Dean use continuations to implement threads in the Mach 3.0 operating system (the predecessor of Unix) and the paper by Olin Shivers discusses the relationship between continuations and threads.

Literature:

1. Mitchell Wand, Continuation-Based Multiprocessing [47]
2. Richard Draves, Brian Bershad, Richard Rashid and Randall Dean, Using Continuations to Implement Thread Management and Communication in Operating Systems [11]
3. Olin Shivers, Continuations and threads: Expressing machine concurrency directly in advanced languages [38]

Macro Languages

Everyone knows C's famous preprocessor that allows the C hacker to #define all sorts of "neat" and "cool" stuff, usually with the goal to improve efficiency. Another notable goal of macro languages is to provide a language extension facility. Unfortunately, the use macros in C is rather error-prone because the meaning of a use of the macro depends on its context of use, whereas the meaning of a function depends only on the context of its definition. This can give rise to subtle bugs. A lot of attention has been paid on how to design a proper macro language, i.e., what kind of features it may have and how its behaviour should be restricted with respect to the actual programming language it is built upon. Although most people agree on the necessity of macro languages, it is astonishing how its design and implementation in existing languages are still neglected.

Literature:

1. Luca Cardelli, Florian Matthes and Martin Abadi, Extensible Syntax with Lexical Scoping [6]
2. William Clinger and Jonathan Rees, Macros that work [7]
3. Eugene Kohlbecker, Daniel Friedman, Matthias Felleisen and Bruce Duba, Hygienic Macro Expansion[25]
4. Eugene Kohlbecker and Mitchell Wand, Macro-by-example: Deriving syntactic transformations from their specifications [26]
5. Claus Brabrand and Michael Schwartzbach, Growing Languages with Metamorphic Syntax Macros [4]

Parametrised Classes aka Mixins

Object-Oriented Programming, invented in the 60s, properly designed in the 70s and buzzed in the 80s, is usually associated with classes. Although all mainstream OO-languages are effectively built on the notion of class, it has been recognised that the class concept suffers from some inherent limits. One particular problem is the so-called extensibility problem. It turns out that classes are a perfect match if the data domain is to be extended (sub-classing), however, classes prove less practical when new functionality is to be added. Recently, the concept of parametrised classes or mixins has been proposed to solve exactly that problem. A mixin is simply a class that is parametrised over its superclass. Although relatively unproblematic in a dynamically typed setting, mixins pose some interesting problems when put in a statically typed context.

Literature:

1. Bruce Findler and Matthew Flatt, Modular Object Oriented Programming with units and mixins [12]
2. Matthew Flatt, Shriram Krishnamurthi and Matthias Felleisen, Classes and Mixins [13]
3. Gilad Bracha and William Cook, Mixin-based Inheritance [5]
4. Viviana Bono, Amit Patel and Vitaly Shmatikov, A core calculus of classes and mixins [3]

Generative Programming

When we program, we usually want to calculate a value of some kind, whether this results in interactive word-processing, playing Quake or calculating the particle stream in a supernova. Supposing appropriate extensions to the programming language, it is possible to generalise the concept of programming in such a way that it allows the user to calculate programs, not just values. In other words, the generative programming idiom adds code to its value domain.

MetaML

One particular approach to generative programming is present in the MetaML-system. It extends the Standard ML Programming Language [29] with annotation constructs that produce code when executed. Moreover, it does this in a type-safe manner, i.e., the generated code can be proven type-safe by the MetaML type checker. Meta-programming has a lot of applications, and it is often used to implement aggressive optimisation techniques.

Literature:

1. Walid Taha and Tim Sheard, MetaML and Multi-stage Programming with Explicit Annotations [45]
2. Walid Taha and Tim Sheard, Multi-stage Programming with Explicit Annotations [44]
3. Eugenio Moggi, Walid Taha, Zino Benaissa and Tim Sheard, Idealised MetaML: Simpler, and More Expressive [32]

 

Partial Evaluation

Although the MetaML-approach to generative programming is very flexible and allows extensive user control on program generation, it may be quite laborious to use as a general optimisation technique. Partial evaluation approaches the optimisation problem from a different angle. Instead of expecting manually inserted annotations in the input program, it simply tries to (partially) evaluate as much of the given program as possible when given some (usually not all) of its input. How the actual program is reduced depends on the partial evaluation (aka program specialisation) technique at hand. However, just like MetaML, the result of partial evaluation is a new program.

Literature:

1. Torben Mogensen, Partial Evaluation: Concepts and Applications [30]
2. John Hatcliff, An Introduction to Online and Offline Partial Evaluation Using a Simple Flowchart Language [17]
3. Torben Mogensen and Peter Sestoft, Partial Evaluation (encyclopedia of computer science [31]
4. Charles Consel and Olivier Danvy, Tutorial Notes on Partial Evaluation [8]

 

Supercompilation

The kind of optimisations that can be performed by a partial evaluation system are limited. The power of a program specialiser actually depends on the level at which it makes decisions on whether to perform some static calculations or produce code. A very powerful program specialisation technique is supercompilation, developed in the ex-Soviet Union by Valentin Turchin long before partial evaluation was known in the West (the original article was in Russian!) A supercompiler starts from a global view of how the program is executed and then generalises just enough to make this supervising and code-generating process finite. A supercompiler is so powerful that it is capable of deriving the very efficient Knuth-Morrison-Pratt string matching algorithm automatically from the naive implementation! Needless to say, supercompilation is quite inefficient.

Literature:

1. Morten Sörensen and Robert Glück, Introduction to Supercompilation [42]
2. Morten Sörensen, Turchin's supercompiler revisited [43]
3. Robert Glück and Morten Sörensen, A road-map to metacomputation by supercompilation [15]
4. Valentin Turchin, The concept of a Supercompiler [46]

Constraint Programming in OZ

Another, perhaps somewhat unexpected, programming idiom is constraint programming. Next to "ordinary" programming, a constraint programming language allows to express computation in terms of constraints. Applications for constraint programming are to be found in natural language processing and combinatorial integer calculation. Another rather different application for constraints is the scheduling problem in high-level concurrent programming. The OZ programming language is a concurrent object-oriented programming language with constraints built-in to provide for communication and synchronisation of concurrent computations. The Oz/Mozart system (http://www.mozart-oz.org) is an implementation of the Oz language.

Literature:

1. Gert Smolka, Problem Solving with Constraints and Programming [40]
2. Gert Smolka, The Oz Programming Model [39]
3. Martin Henz, Gert Smolka and Jörg Würtz, Object-Oriented Concurrent Constraint Programming in Oz [41]

List of talks and speakers

The talks will be held at 14u ct. in Room SR 00-019, Geb. 079.

26/6/2001	:	Matthias Freiburghaus, Supercompilation
3/7/2001	:	Daniel Van Den Eijkel, Continuations and The CPS transformation

References

 [1]

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

 [2]

Andrew W. Appel. Simple generational garbage collection and fast allocation. Software--Practice & Experience, 19(2):171-183, February 1989.

 [3]

Viviana Bono, Amit Patel, and Vitaly Shmatikov. A core calculus of classes and mixins. In 13th European Conference on Object-Oriented Programming (ECOOP '99), pages 43-66, Lisbon, June 1999. Springer-Verlag.

 [4]

Claus Brabrand and Michael Schwartzbach. Growing languages with metamorphic syntax macros. Technical report, University of Aarhus, 2000. Available from http://www.brics.dk/bigwig/research/publications/macro.ps.

 [5]

Gilad Bracha and William Cook. Mixin-based inheritance. In OOPSLA'90, ACM SIGPLAN Fifth Annual Conference on Object-Oriented Programming Systems, Languages, and Applications. ACM, 1990. SIGPLAN Notices (25)10.

 [6]

Luca Cardelli, Florian Matthes, and Martín Abadi. Extensible grammars for language specialization. In Catriel Beeri, Atsushi Ohori, and Dennis Shasha, editors, Database Programming Languages, Proceedings of the Fourth International Workshop on Database Programming Languages -- Object Models and Languages, Workshops in Computing, pages 11-31, Manhattan, New York City, USA, August 1993 1994. Springer-Verlag.

 [7]

William Clinger and Jonathan Rees. Macros that work. In Proc. 18th Annual ACM Symposium on Principles of Programming Languages, pages 155-162, Orlando, Florida, January 1991. ACM Press.

 [8]

Charles Consel and Olivier Danvy. Tutorial notes on partial evaluation. In POPL1993 [37], pages 493-501.

 [9]

Luis Damas and Robin Milner. Principal type-schemes for functional programs. In Proc. 9th Annual ACM Symposium on Principles of Programming Languages, pages 207-212. ACM, 1982.

 [10]

Olivier Danvy and Andrzej Filinski. Representing control: A study of the CPS transformation. Mathematical Structures in Computer Science, 2:361-391, 1992.

 [11]

R. Draves, B. Bershad, R. Rashid, and R. Dean. Using continuations to implement thread management and communication in operating systems. Technical Report CMU-CD-91-115R, Carnegie Mellon University, October 1991.

 [12]

Robert Bruce Findler and Matthew Flatt. Modular object-oriented programming with units and mixins. In Paul Hudak, editor, Proc. International Conference on Functional Programming 1998, Baltimore, USA, September 1998. ACM Press, New York.

 [13]

Matthew Flatt, Shriram Krishnamurthi, and Matthias Felleisen. Classes and mixins. In Luca Cardelli, editor, Proc. 25th Annual ACM Symposium on Principles of Programming Languages, pages 171-183, San Diego, CA, USA, January 1998. ACM Press.

 [14]

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

 [15]

Robert Glück and Morten Heine Sørensen. A roadmap to metacomputation by supercompilation. In Olivier Danvy, Robert Glück, and Peter Thiemann, editors, Partial Evaluation, number 1110 in Lecture Notes in Computer Science, pages 137-160, Schloß Dagstuhl, Germany, February 1996. Springer-Verlag.

 [16]

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

 [17]

John Hatcliff. An introduction to online and offline partial evaluation using a simple flowchart language. In Hatcliff et al. [19], pages 20-82.

 [18]

John Hatcliff and Olivier Danvy. A generic account of continuation-passing styles. In Proc. 21st Annual ACM Symposium on Principles of Programming Languages, pages 458-471, Portland, OG, January 1994. ACM Press.

 [19]

John Hatcliff, Torben Æ. Mogensen, and Peter Thiemann, editors. Partial Evaluation--Practice and Theory. Proceedings of the 1998 DIKU International Summerschool, number 1706 in Lecture Notes in Computer Science, Copenhagen, Denmark, 1999. Springer-Verlag.

 [20]

Fritz Henglein. Type inference with polymorphic recursion. ACM Transactions on Programming Languages and Systems, 15(2):253-289, April 1993.

 [21]

Mark P. Jones. A system of constructor classes: Overloading and implicit higher-order polymorphism. In Arvind, editor, Proc. Functional Programming Languages and Computer Architecture 1993, pages 52-61, Copenhagen, Denmark, June 1993. ACM Press, New York.

 [22]

Mark P. Jones. Typing Haskell in Haskell. In Erik Meijer, editor, Proceedings of the 1999 Haskell Workshop, number UU-CS-1999-28 in Technical Reports, 1999. ftp://ftp.cs.uu.nl/pub/RUU/CS/techreps/CS-1999/1999-28.pdf.

 [23]

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

 [24]

Richard Kelsey, William Clinger, and Jonathan Rees. Revised⁵ report on the algorithmic language Scheme. Higher-Order and Symbolic Computation, 11(1):7-105, 1998. Also appears in ACM SIGPLAN Notices 33(9), September 1998.

 [25]

Eugene Kohlbecker, Daniel P. Friedman, Matthias Felleisen, and Bruce Duba. Hygienic macro expansion. In ACM Conference on LISP and Functional Programming, pages 151-161, 1986.

 [26]

Eugene Kohlbecker and Mitchell Wand. Macro-by-example: Deriving syntactic transformations from their specifications. In Proc. 14th Annual ACM Symposium on Principles of Programming Languages, pages 77-84. ACM, 1987.

 [27]

Oukseh Lee and Kwangkeun Yi. Proofs about a folklore let-polymorphic type inference algorithm. ACM Transactions on Programming Languages and Systems, 20(4):707-723, 1998.

 [28]

Robin Milner. A theory of type polymorphism in programming. Journal of Computer and System Sciences, 17:348-375, 1978.

 [29]

Robin Milner, Mads Tofte, Robert Harper, and Dave MacQueen. The Definition of Standard ML (Revised). MIT Press, 1997.

 [30]

Torben Æ. Mogensen. Partial evaluation: Concepts and applications. In Hatcliff et al. [19], pages 1-19.

 [31]

Torben Æ. Mogensen and Peter Sestoft. Partial evaluation. In Allen Kent and James G. Williams, editors, Encyclopedia of Computer Science and Technology, volume 37, pages 247-279. Marcel Dekker, 270 Madison Avenue, New York, New York 10016, 1997.

 [32]

Eugenio Moggi, Walid Taha, Zino El-Abidine Benaissa, and Tim Sheard. An idealized MetaML: Simpler, and more expressive. In S. Doaitse Swierstra, editor, Proc. 8th European Symposium on Programming, number 1576 in Lecture Notes in Computer Science, Amsterdam, The Netherlands, April 1999. Springer-Verlag.

 [33]

Tobias Nipkow and Christian Prehofer. Type checking type classes. In POPL1993 [37], pages 409-418.

 [34]

Jens Palsberg. Efficient inference of object types. Information and Computation, 123(2):198-209, 1995.

 [35]

Jens Palsberg and Michael I. Schwartzbach. Object-oriented type systems. John Wiley and Sons, 1994.

 [36]

David Plainfossé and Marc Shapiro. A survey of distributed garbage collection techniques. In Proc. Int. Workshop on Memory Management, Kinross, Scotland (UK), September 1995.

 [37]

Proc. 20th Annual ACM Symposium on Principles of Programming Languages, Charleston, South Carolina, January 1993. ACM Press.

 [38]

Olin Shivers. Continuations and threads: Expressing machine concurrency directly in advanced languages. In Olivier Danvy, editor, Proceedings of the Second ACM SIGPLAN Workshop on Continuations, number NS-96-13 in BRICS Notes, Paris, France, January 1997. Dept. of Computer Science, Aarhus, Denmark.

 [39]

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.

 [40]

Gert Smolka. Problem solving with constraints and programming. Computing Surveys, 28(4es), December 1996. Electronic Section.

 [41]

Gert Smolka, Martin Henz, and Jörg Würtz. Object-oriented concurrent constraint programming in Oz. In P. van Hentenryck and V. Saraswat, editors, Principles and Practice of Constraint Programming, pages 29-48. MIT Press, 1995.

 [42]

Morten Heine B. Sørensen and Robert Glück. Introduction to supercompilation. In Hatcliff et al. [19], pages 246-270.

 [43]

Morten Heine Sørensen. Turchin's supercompiler revisited. Master's thesis, DIKU, University of Copenhagen, March 1994.

 [44]

Walid Taha and Tim Sheard. Multi-stage programming with explicit annotations. In Charles Consel, editor, Proc.  ACM SIGPLAN Symposium on Partial Evaluation and Semantics-Based Program Manipulation PEPM '97, pages 203-217, Amsterdam, The Netherlands, June 1997. ACM Press.

 [45]

Walid Taha and Tim Sheard. MetaML and multi-stage programming with explicit annotations. Theoretical Computer Science, 2000.

 [46]

Valentin F. Turchin. The concept of a supercompiler. ACM Transactions on Programming Languages and Systems, 8(3):292-325, July 1986.

 [47]

Mitchell Wand. Continuation-based multiprocessing. Higher-Order and Symbolic Computation, 12(3):285-299, 1999.

 [48]

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