Contextual indices have been used for many years. For example, Biblical concordances have approximately this form, except for the rotations. The usual source for the problem as now known, however, is the Parnas definition.
In his paper of 1972, Parnas used the problem to contrast different criteria for decomposing a system into modules [Parnas72]. He describes two solutions, one based on functional decomposition with shared access to data representations, and a second based on a decomposition that hides design decisions. The latter was used to promote information hiding, a principle that underpins the use of abstract data types and of object-oriented design. Since its introduction, the problem has become well-known and is widely used as a teaching device in software engineering. Garlan, Kaiser, and Notkin also use the problem to illustrate modularization schemes based on data-driven tool invocation [Garlan92]--sometimes referred to as reactive integration.
While KWIC can be implemented as a relatively small system it is not simply of pedagogical interest. Practical instances of it are widely used by computer scientists. For example, the "permuted" [sic] index for the Unix Man pages is essentially such a system.
We use the problem in a course on software architecture to give students experience with software development in different architectural styles [GarlanShaw94]. We give three separate assignments. Each starts with a simple KWIC indexer, for which we supply code, and asks for modifications. By providing an initial implementation, we give them an example of a small system in the style of interest and get them started in the right way. Each exercise requires the modifications to be done in a way that preserves the style. As part of the assignments, students analyze the suitability of different styles for different variants on the basic problem.
Updated Halloween 95 by
Mary Shaw
Comments to maintainer