development reuse and the logic program derivation of two string-matching algorithms
Program transformation advocates the development of programs by applying a sequence of meaning-preserving rules to a specification, thereby obtaining an implementation. The cost of program development and maintenance decreases if previous, similar derivations can be reused conveniently Through the string-matching problem, we study the reuse of complete parts of the derivation of an algorithm, in the deriv ation of another, "similar" algorithm. In particular, we first derive the search stage of a variant of the Boyer--Moore algorithm, and then reuse some "dev elopments" in a derivation of the search stage of the Knuth-Morris-Pratt algorithm. Several advantages result from employing logic programming. First, we get the semantic benefit of having a logical basis. Second, we can easily exploit nondeterminism. Third, we link both deriv ations by observing that repetitive "deterministic" unfolding (i.e. sequences of unfolding steps that halt when more than one clause would be inferred) is closely related to the preprocessing stage of both algorithms.
program derivation knuth-morris-pratt boyer-moore