A Software Engineering Perspective on Algorithmics.

1. INTRODUCTION

By a component we mean an encapsulated piece of code, which is not intended to be a stand-alone module, but to perform a specific task within a large software package or even within several distinct software packages. For example, every subroutine may be viewed as a component in this sense, because the functional details are encapsulated by the interface of the subroutine. Abstract data types (see Appendix B) are a more sophisticated example of components in this sense, because unlike subroutines, they are able to encapsulate state information in addition to the pure functionality.

We will discuss the problem of designing efficient, adaptable implementations of algorithm components. In practice, adaptability is important for several reasons:

--Throughout the lifetime of a project, the requirements on the functionality of a single component may change repeatedly. Reimplementing this component from scratch repeatedly is expensive and often infeasible. Extensive modifications of the core of the component are error-prone(1) and also often infeasible. In particular, extensive modifications of sophisticated algorithmic codes are error-prone. Ideally, adapting an algorithm component to changing requirements should amount to straightforward "error-proof" modifications of a few small, nonalgorithmic pieces of customization code (see Appendix A for the exact usage of this term in this paper).

--Often, software is implemented in a prototypical fashion. This means that first a raw prototype is implemented, which is then refined step-by-step throughout several development cycles. An example is the experimental development of algorithms. In larger projects, such a prototypical approach is feasible only if all components are easily customizable to new, revised versions of the software package.

--Implementing complex components (e.g. sophisticated algorithms) is expensive and requires special expertise. In this respect, it is desirable to have (in-house or third-party) repositories of complex components, which are reusable in many different contexts. However, to be widely reusable, a component must be adaptable to a large range of possible requirements, which are potentially unforeseen in the design phase of this component.

Many libraries offer efficient data structures and algorithms for various algorithmic problem domains. However, an implementation of an algorithm in a library need not fit seamlessly into every application. The integration may enforce significant overhead both in development/maintenance and in run-time efficiency. In some cases, this overhead may be so large that reimplementing an algorithm from scratch might be more practical than reusing an existing implementation.