June 8 – 12 , 1998, Dagstuhl Seminar 98231

Programs: Improvements, Complexity, and Meanings


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

For support, please contact

Dagstuhl Service Team


External Homepage
Dagstuhl-Seminar-Report 213


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 the series Dagstuhl Reports each Dagstuhl Seminar and Dagstuhl Perspectives Workshop is documented. The seminar organizers, in cooperation with the collector, prepare a report that includes contributions from the participants' talks together with a summary of the seminar.


Download overview leaflet (PDF).

Dagstuhl's Impact

Please inform us when a publication was published as a result from your seminar. These publications are listed in the category Dagstuhl's Impact and are presented on a special shelf on the ground floor of the library.


Furthermore, a comprehensive peer-reviewed collection of research papers can be published in the series Dagstuhl Follow-Ups.