https://www.dagstuhl.de/98171

April 27 – May 1 , 1998, Dagstuhl Seminar 98171

Generic Programming

Organizer

M. Jazayeri (Wien), R. Loos (Tübingen), D. Musser (Troy), A. Stepanov (SGI, Mountain View)

For support, please contact

Dagstuhl Service Team

Documents

Dagstuhl's Impact: Documents available
External Homepage
Dagstuhl-Seminar-Report 208


Motivation to Seminar 98171
Generic Programming
April 27 to 30, 1998
Schloss Dagstuhl, Wadern, Germany

Generic programming is a sub-discipline of computer science that deals with finding abstract representations of efficient algorithms, data structures, and other software concepts, and with their systematic organization. The goal of generic programming is to express algorithms and data structures in a broadly adaptable, interoperable form that allows their direct use in software construction.

Key ideas include:

  • Expressing algorithms with minimal assumptions about data abstractions, and vice versa, thus making them as interoperable as possible.
  • Lifting of a concrete algorithm to as general a level as possible without losing efficiency; i.e., the most abstract form such that when specialized back to the concrete case the result is just as efficient as the original algorithm.
  • When the result of lifting is not general enough to cover all uses of an algorithm, additionally providing a more general form, but ensuring that the most efficient specialized form is automatically chosen when applicable.
  • Providing more than one generic algorithm for the same purpose and at the same level of abstraction, when none dominates the others in efficiency for all inputs. This introduces the necessity to provide sufficiently precise characterizations of the domain for which each algorithm is the most efficient.

The intention in this seminar is to focus on generic programming techniques that can be used in practice, rather than to discuss purely theoretical issues. By the end of the seminar we would like to come up with the following results:

  1. A list of problems in generic programming. These include new components, new kinds of abstractions, language extensions, tools.
  2. A process for extending the existing body of generic components, as well as methods for their specification, verification and for establishing their efficiency in actual programs.

We think that to accomplish these goals we need to share a common vocabulary. Therefore, we will use the vocabulary established by the C++ Standard Template Library (STL) of fundamental data structures and algorithms. This is not intended to preclude discussion of generic programming issues that occur in other areas and that might be more easily illustrated with other libraries and languages. For example, topics might include language extensions to support generic programming in more recent languages such as Haskell or Java, or how generic programming goals intersect with design patterns or frameworks research.

Documentation

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

Publications

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

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.