In the last few years, interest in systematic methods for the construction of Prolog programs has significantly increased, for example (Gegg-Harrison, [GH95]), (Power and Sterling, [PS90]), (Kirschenbaum et al., [KMS96]), (Sterling and Yalçinalp, [SY96]), and (Vasconcelos and Fuchs, [VF95]). These papers have built on previous less systematic approaches to Prolog programming, implicit in text books and shared code. The progression of approaches has been discussed in (Naish and Sterling [NS98]).
Two audiences can benefit from systematic approaches. First, novice programmers who need guidance to create code of reasonable quality. Second, experienced programmers who want to increase their productivity. The needs of these two groups are quite different. Novices can learn more easily from concrete examples and don't have the experience to recognise patterns and abstractions. Experienced programmers can benefit from using higher levels of abstraction in powerful tools.
We claim that both audiences can be addressed through the method
of stepwise enhancement.
It 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. In this paper 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, [JC94]), (Jay, [Jay95]),
(Bellé et al., [BJM96])
(Jeuring and Jansson, [JJ96]), (Jansson and Jeuring, [JJ97]).
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.
This leads to a proposal for a set of software tools to automatically
produce Prolog procedures from type definitions.
We describe a prototype implementation and
relate our initial experiences using these tools and using the higher order
programming style with Prolog.
The current work was sparked by the challenge to use the higher order approach to explain a ``complicated'' program, the rule interpreter described in Section 17.4 of the second edition of The Art of Prolog (Sterling and Shapiro, [SS94]). In explaining the program, a new method was formulated: the final program is built around an output type rather than an input type. In this paper we give another example of this technique, using a different interpreter.
What has emerged is a better understanding of how types can drive program development, and how Naish and Sterling's views of systematic program construction via stepwise enhancement are complementary. The work relates to recent, exciting work in the functional programming community concerning shape, which sets our views on program development in a broader context. These insights have prompted the development of prototype software tools for partially automating coding based on types and skeletons. This paper describes our experiences with higher order programming in Prolog and the use of these tools. The initial results show that a significant increase in programming productivity is possible.