A higher order reconstruction of stepwise enhancement

Lee Naish and Leon Sterling

In the last couple of years, there has been renewed interest in systematic methods for the construction of Prolog programs, for example (Gegg-Harrison, 1995), (Kirschenbaum et al., 1996), (Sterling and Yalcinalp, 1996), and (Vasconcelos and Fuchs, 1995). This paper loosely characterises the progression of approaches that have been offered for systematic construction of logic (usually Prolog) programs. There is a trade-off between what is accessible for practical programmers and what is clearly explained in theory.

We claim that both audiences can be addressed through stepwise enhancement. The method can be explained directly in term of programming techniques applied to simple programs, and also given a more theoretical basis in terms of higher order functions. We review stepwise enhancement, sketch how to capture an enhancement as a higher order function adapted from foldr, and then sketch how individual enhancements are specialisations of the particular foldr predicate. We show how this is closely related to the new ideas on shape and polytypism being discussed in the functional programming community (Jay and Cockett, 1994), (Jay, 1995), (Belle et al., 1996) (Jeuring and Jansson, 1996), (Jansson and Jeuring, 1997). We go on to generalise this work in several ways, utilising key features of logic programming such as nondeterminism and flexible modes, and show how foldl can also be adapted.