Several years ago the first author implemented some higher order predicates for his own use in programming. The initial set was a Prolog version of the Miranda1 standard library. Some functions were not implemented because they rely on lazy evaluation. This was the first divergence between the higher order primitives used in Prolog and functional programming. The set of higher order predicates was expanded as new code was developed and patterns were noted, resulting in further divergence. The usage pattern of higher order primitives reported below is based on around 1400 lines of recently developed code (comments and blank lines excluded) for program analysis and transformation. The coding style was ``pure'', avoiding non-logical primitives where possible, and efficiency was generally ignored. Analysis of a larger body of code would obviously be desirable.
More recently we implemented the prototype transformation tools for foldr and foldl and implemented extra transformations as it became evident they were useful. The main application to date is a program analysis system which manipulates systems of constraints. The task was to change the representation of constraints to allow greater flexibility (such as adding disjunctive constraints which were previously not supported). The transformation tools proved to be very useful.
The new data structure for constraints was quite complicated, one type having fifteen different constructors. In addition, the design took advantage of Prolog's flexibility with respect to types and used overloading of representations (multisets and conjunctions used the same representation) and subtypes (at different program points several different sub-types of the constraint type were used). Partly because of this we edited the output of the transformation tools in several instances. Although the tools were designed with the higher order coding style in mind, we used a mixture of the higher order style and the stepwise enhancement style. With a more disciplined use of types, which would have required more explicit type definitions and type conversions, it is likely that fewer modifications to the output of the tools would have been required. However, editing the output of the tools would still have been useful in cases where the program pattern was similar but not identical to an instance of one of the abstractions supported by the tools. Around 500 lines of generated code were used in the final system (more than the number of lines of code used to implement the tools). We believe the tools significantly improved productivity.