08. – 12. Juni 1998, Dagstuhl-Seminar 98231

Programs: Improvements, Complexity, and Meanings


N. Jones (Copenhagen), O. de Moor (Oxford), J. Royer (Syracuse)

Auskunft zu diesem Dagstuhl-Seminar erteilt

Dagstuhl Service Team


Externe Homepage
Dagstuhl-Seminar-Report 213

Motivation to the Seminar 98231
"Programs: Improvements, Complexity, and Meanings"
Schloss Dagstuhl, 08.06.-12.06.98

Topic : the interface between Complexity Theory and Programming Languages. Much interest has been shown in recent results relating speed of imperative LISP to pure LISP (Pippenger), ,pointers versus ad dresses"(Ben-Amram and Galil), and a proof that ,constant time factors do matter" (Jones), but the field is far from well-developed. This seminar will bring together three communities:

  • Complexity theorists: precisely stated problems about time, space, language expressiveness, etc.
  • Program transformers and analysts: execution speed, limits to implementation efficiency, etc.
  • Semanticists: operational models, expressiveness, intensional properties, etc.

Our goal is fruitful interactions, leading to formulation and perhaps solving new questions that are both of theoretical interest and of practical relevance. A model question : Are functional or logic programs necessarily less efficient than equivalent imperative programs? Such questions need to be made more precise in order to be answered; and solution can be tricky indeed. A model answer by Nick Pippenger (POPL 1996) : ,Pure LISP" is provably less efficient, by a logarithmic time factor, than ,impure LISP" with list-modifying assign ments, when applied to solve a problem involving a series of online permutations.

Related workshops by the organizers: the 1996 DIMACS workshop Computational Complexity and Programming Languages ; 1991-1997 conferences on Partial Evaluation ; the 1994 IFIP miniworkshop Program Speedups in Theory and Practice ; and the 1995 workshop Higher Order Operational Techniques in Semantics . A bibliography of books and papers relevant to the seminar can be seen at:

Some relevant topics:

  • Automatic program improvement
  • Calculi for proving complexity results about programs
  • Capturing complexity classes by programs
  • Cost models for the untyped lambda calculus, ML, lazy languages,...
  • Examples and good sharp problems about efficiency, expressivity,...
  • Intensional program properties (time, memory, etc.)
  • Meanings, complexity and speed in query languages
  • Operationally defined program improvement relations
  • Optimality of program execution models
  • Principles for and limits to efficient compilation
  • Program analysis complexity
  • Programming paradigm effects on program efficiency
  • Program transformation by calculation
  • Strange program execution techniques (memoisation, magic sets,...)
  • Tools to reason about the efficiency and behavior of programs
  • Transformation: partial evaluation, supercompilation, Burstall-Darlington,...
  • Verification of compiler optimizations

Emphasis, nature of the meeting : Participants should be open to bridge-building, and are encouraged to bring draft papers for discussion (a preliminary proceedings will be printed). It will not be one long confer ence with hours of lecture-style presentations. Rather, there will be a mixture of session types, perhaps in cluding

  • presentation of new results (or overviews of old ones, for people ,from the other side")
  • problem statement sessions, trying to find good questions to ask
  • joint problem-solving sessions, based on a problem given in advance

Planning to come if possible : Thorsten Altenkirch, Amir Ben-Amram, Olivier Danvy, Oege de Moor, Andrew Gordon, Irene Guessarian, Yuri Gurevich, Martin Hofmann John Hughes, Neil Jones, Bruce Kapron, Harry Mairson, Yiannis Moschova kis, Bernhard Möller, Chris Okasaki, Luke Ong, Jens Palsberg, Holger Petersen, Jim Royer, Andre Scedrov, Arnold Schönhage, Helmut Schwichtenberg, Carolyn Talcott.


In der Reihe Dagstuhl Reports werden alle Dagstuhl-Seminare und Dagstuhl-Perspektiven-Workshops dokumentiert. Die Organisatoren stellen zusammen mit dem Collector des Seminars einen Bericht zusammen, der die Beiträge der Autoren zusammenfasst und um eine Zusammenfassung ergänzt.


Download Übersichtsflyer (PDF).


Es besteht weiterhin die Möglichkeit, eine umfassende Kollektion begutachteter Arbeiten in der Reihe Dagstuhl Follow-Ups zu publizieren.

Dagstuhl's Impact

Bitte informieren Sie uns, wenn eine Veröffentlichung ausgehend von
Ihrem Seminar entsteht. Derartige Veröffentlichungen werden von uns in der Rubrik Dagstuhl's Impact separat aufgelistet  und im Erdgeschoss der Bibliothek präsentiert.