Typical techniques for problem solving separate the steps of choosing data structures and algorithms. This separation and encapsulation 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 prioritized 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.
For more information see: http://www.csee.wvu.edu/~resolve
References
B. W. Weide, W. F. Odgen, and M. Sitaraman, "Recasting Algorithms to
Encourage Reuse," IEEE Software, Vol. 11, No. 5, September 1994, 80-88.
S. Sreerama, D. Fleming, and M. Sitaraman, "Graceful Object-Based
Performance Evolution," Software - Practice and Experience, Vol. 27, No.
1, January 1997, 111-122.
M. Sitaraman, B. W. Weide, and W. F. Odgen, "Using Abstraction Relations to Verify Abstract Data Type Representations," IEEE Transactions on Software Engineering, March 1997, 157-170.