|
|
|
Recasting Algorithms: A New Generation of Objects
Typical problem solving techniques
-
separate selection of algorithms and data structures;
-
encapsulate algorithms as procedures; and
-
force expensive batch-style computation
Recasting differs in that it
-
encapsulates algorithms and data structures together as data abstractions
-
hides how and when computations take place
-
provides functional and performance flexibility through multiple implementations.
Introductory Article on the Topic
M. Sitaraman, B. W. Weide, T. J. Long, and W. F. Ogden, A Data Abstraction
Alternative to Data Structure Algorithm Modularization, Generic Programming,
Eds. D. Musser and M. Jazayeri, LNCS 1766, Springer-Verlag, 2000, 102-113.
Abstract
Typical techniques for problem solving separate the steps of choosing
data structures and algorithms. This separation and encaspulation
of
algorithms as procedures exposes representation details, and complicates
specification
and reasoning. In addition, a procedural encapsulation of algorithms
leads to computation of entire solutions in batch style, even for
problems where only partial solutions are needed and where partial
solutions can be computed efficiently in incremental fashion.
Recasting is an alternative approach in which data structures and
algorithms are encapsulated together to address a particular class
of
problems. Generic data abstractions that result from recasting
hide
both how and when computations take place, and provide both functional
and performance flexibility. When a data abstraction interface
is
suitably designed and specified, it permits alternative implementations
to be developed using different data structures and algorithms so that
there is at least one efficient implementation for each intended class
of application of the abstraction. Through recasting, for example,
the
problems of ordering a collection of items and sorting are unified
and
recast into a Prioritizer data abstraction, which provides an abstract
data type and operations to insert items to be priortized and to remove
a next
item in order. Instead of a procedure for finding a minimum
spanning forest of a graph (and other graph optimization problems),
recasting leads to data abstractions that permit edges on a solution
to
be extracted one at a time. Alternative implementations of these
abstractions may compute the solution either incrementally or in batch
style,
providing clients with a new degree of temporal flexibility.
Recasting is one of the key research results of the RESOLVE work on
component-based software engineering framework, discipline, and
language.
Examples of Recasting
-
Prioritizer_Template resulting from recasting "sorting" and related algorithms
-
Spanning_Forest_Machine_Template
-
Task_Scheduling_Template
-
Event-Sequencing Template
-
Other optimization problems
Other Publications |
|