Go backward to Organizers
Go up to Top
Go forward to Participants
This statement, written by the organizers, was
included with the invitations to participants.
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
- 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
- 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:
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.
- A list of problems in generic programming. These include new
components, new kinds of abstractions, language extensions, tools.
- A process for extending the existing body of generic components, as
well as methods for their specification and verification and for
establishing their efficiency in actual programs.