TOP
Search the Dagstuhl Website
Looking for information on the websites of the individual seminars? - Then please:
Not found what you are looking for? - Some of our services have separate websites, each with its own search option. Please check the following list:
Schloss Dagstuhl - LZI - Logo
Schloss Dagstuhl Services
Seminars
Within this website:
External resources:
  • DOOR (for registering your stay at Dagstuhl)
  • DOSA (for proposing future Dagstuhl Seminars or Dagstuhl Perspectives Workshops)
Publishing
Within this website:
External resources:
dblp
Within this website:
External resources:
  • the dblp Computer Science Bibliography


Dagstuhl Seminar 98171

Generic Programming

( Apr 27 – May 01, 1998 )

(Click in the middle of the image to enlarge)

Permalink
Please use the following short url to reference this page: https://www.dagstuhl.de/98171

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





Motivation

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.


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