https://www.dagstuhl.de/98231

### June 8 – 12 , 1998, Dagstuhl Seminar 98231

# Programs: Improvements, Complexity, and Meanings

## Organizer

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

## For support, please contact

## Documents

External Homepage

Dagstuhl-Seminar-Report 213

## Motivation

**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:

http://www.diku.dk/users/neil/DagstuhlBib.html.

**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.