Logic languages based on functions: semantics and implementation
Uday S. Reddy · 1986
This dissertation aims at relating the well-developed field of functional programming with the newly emerging logic programming. Functional programming is based on the computational notion of reducing expressions to other semantically equivalent expressions. In particular, a successful reduction of a variable-free expression reduces it to its value. Logic programming, on the other hand, is based on the computational notion of solving statements with free variables to find valid instantiations of the variables. This richer notion of computation endows logic languages with more expressive power than functional languages. However, conventional logic languages are based on predicates specified by Horn clauses and lack the input-output directionality present in functional languages. In addition to providing convenient human-oriented syntax, directionality is useful for specifying control information (a requirement for the development of parallel implementations) and for lazy evaluation. It is shown that logic programming--the ability to solve statements--can be obtained in functional languages. This involves using an operational mechanism called narrowing instead of the conventional reduction. Narrowing, then, transforms a functional language into a logic language based on functions. Moreover, such a logic language subsumes Horn clause logic languages and thus provides all the expressive power of logic programming, while retaining the notion of input-output directionality. This dissertation presents the semantic foundations and the implementation methods for functional logic languages.