A prototype tool to support the stepwise enhancement paradigm is discussed in (Sterling and Sitt Sen [SS93]). Users interact with the tool to construct an enhancement from one of several predefined skeletons. The discussion in this paper on higher order programming and shape suggests three tools to automate parts of the software development process. The first converts types (defined in some suitable syntax) into Horn clause definitions, the second converts Horn clause definitions into related higher order predicate definitions and the third optimises code to eliminate the overheads of higher order predicates (see Figure 0).
Considering only the work on shape and polytypism in functional languages it seems more natural go directly from types to higher order functions. However, splitting this into two separate stages has significant advantages. Having Horn clause definitions of types is useful in itself for runtime type checks, test data generation et cetera. These Horn clause definitions may also be refined by adding further constraints, for example, refining the definition of a binary tree to obtain the definition of a binary search tree. Most importantly, it allows higher order definitions to be derived from arbitrary Horn clause programs, significantly increasing flexibility.
:- type tree(T) ---> leaf(T); t(tree(T),tree(T)). :- skeleton tree_any/1 generates foldl, foldr. sum_tree(T, N) :- foldl_tree_any(plus, =, T, 0, N).Program 17: User input to tools
We have implemented prototypes of the first two tools and experimented with a previously developed optimisation tool. Program 17 gives a small example of the use of our tools. It contains the definition of the polymorphic type tree, a directive which states that versions of foldl and foldr should be generated for this type, and a use of foldl for this type. In a more tightly integrated system the need for explicit directives could be avoided by detecting such uses of higher order predicates and generating predicates based on usage. The first tool takes the type definition and generates Horn clause definitions of tree/2 (a higher order predicate corrresponding to the polymorphic type) and tree_any/1. The second tool takes the definition of tree_any/1 and produces Horn clause definitions of the higher order predicates foldl_tree_any/5 and foldr_tree_any/4. Existing tools/compilers can transform sum_tree so it is as efficient as hand-optimised code. We plan to implement a Web interface to the tools in the future.
Converting types into Horn clause definitions is conceptually straightforward. However, our implementation was made more complex by allowing type synonyms and undescriminated unions in type definitions, and the desire for the Horn clause definitions to be as simple as possible. The simplicity of the output is important for the subsequent generation of higher order predicates. Our prototype needs more work to ensure the simplest output is produced for all possible inputs. Optimisation of higher order code is also reasonably straightforward and has been done in several logic programming systems, such as the compilers for XSB-Prolog (Sagonas and Warren [SW95]) and Mercury (Somogyi et al. [SHC95]). Unfortunately, most Prolog compilers do not perform such optimisations and there are no available source to source optimisation tools which are guaranteed to work correctly for standard Prolog.
Converting Horn clause definitions into higher order predicates requires more innovation. One challenge is taking a known transformation from regular types to higher order functions and generalising it to Horn clause definitions which may not correspond to regular types. We have shown one way to do this for foldr and developed a new generalisation of foldl, but each transformation requires careful thought and there is not necessarily a unique ``best'' solution. Another challenge is determining a useful set of transformations or abstractions. An obvious starting point is the functions over lists which have been found useful in functional programming. However, the optimal set depends on the programming style and what programming patterns occur frequently. Although there are important programming patterns which lie in the intersection of what is coded in logic and functional languages, there are also patterns which are unique to each paradigm.
