Programs: Improvements, Complexity, and Meanings
Dagstuhl Seminar on
Programs: Improvements, Complexity, and Meanings
Schloß Dagstuhl
Wadern, Germany, June 8-12, 1998.
Topic: The interface between Programming Languages
and Complexity Theory.
Much interest has been shown in recent results relating
speed of imperative LISP to pure LISP (Pippenger), "pointers
versus addresses" (Ben-Amram and Galil), and a proof that "constant
time factors do matter" (Jones), but the field is far from
well-developed. This workshop will bring together three communities:
- Semanticists: interested in operational models of
programming languages, expressiveness, intensional properties, etc.
- Program transformers and analysts: interested in program
execution speed, limits to implementation efficiency, etc.
- Complexity theorists: interested in precisely stated
problems about computation time and space, language expressiveness,
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 logarithic time factor,
than "impure LISP" with list-modifying assignments, when applied
to solve a problem involving a series of online permutations.
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 optimisations
Emphases, 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 conference with hours of
lecture-style presentations. Rather, there will be a mixture of
session types, perhaps including
- 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
Meeting plan, titles and abstracts:
(evolving)
The organizers:
Related workshops by the organizers:
Bibliography
(under
construction!) of books and papers relevant to the workshop.
To the Dagstuhl Homepage