Prev Up Next
Go backward to Polytypic Programming
Johan Jeuring

Go up to Foundations and Methodology Comparisons
Go forward to Using Genericity to Improve OO Designs
Karsten Weihe


Recasting Algorithms As Objects:
An Alternative to Iterators
Murali Sitaraman

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.


 

Prev Up Next