Denitional Programming in GCLA Techniques, Functions, and Predicates
Olof Torgersson · 1996
When a new programming language or programming paradigm is devised, it is essential to investigate its possibilities and give guide-lines for how it can best be used. In this thesis we describe some of the possibilities of the declarative programming paradigm definitional programming. We discuss both general programming methodology and delve further into the subject of combining functional and logic programming within the definitional framework. Furthermore, we investigate the relationship between functional and definitional programming by translating functional programs to the definitional programming language GCLA. The thesis consists of three separate parts. In the first we discuss general programming methodology in GCLA. A program in GCLA consists of two parts, the definition and the rule definition, where the definition is used to give the declarative content of an application and the rule definition is used to give a procedural interpretation of the definition. We present and discuss three different ways to write the rule definition to a given definition. The first is a stepwise refinement strategy, similar to the usual way to give control information in Prolog where cuts are added in a rather ad-hoc fashion. The second is to split the set of conditions in the definition in a number of different classes and to give control information for each class. The third alternative is a local approach where we give a procedural interpretation to each atom in the definition. The second part of the thesis concerns the integration of functional and logic programming. We show how GCLA can be used to amalgamate first order functional and logic programming. A number of different rule definitions developed for this purpose are presented as well as a rule generator for functional logic programs. The rule generator creates rule definitions according to the third method described in the first part of the thesis. We also compare our approach with other existing and proposed integrations of functional logic programming. Even though all examples are given in GCLA the described ideas could just as well serve as a basis for a specialized functional logic programming language based on the theory of partial inductive definitions. In the third part we report on an experiment where we translated a subset of the lazy functional language LML to GCLA. This work has a close connection to different attempts to integrate functions and lazy evaluation into logic programming. The basic idea in the translation is that we use ordinary techniques from compilers for lazy functional languages to transform the functional program into a set of supercombinators. These supercombinators can then easily be mapped into GCLA definitions.