Algebraic Methods in Prolog Programming

Abstract

We discuss some difficulties of coding and invoking functions implemented by predicates and we propose a number of conceptual tools for overcoming these difficulties. We use an algebraic model which supports strategies for designing complete, parsimonious, and terminating functions. We describe a translation scheme for converting these functions into predicates and we prove a number of properties of this transformation. Our investigation provides an algebraic interpretation of the cut and raises two issues of lack of orthogonality in the Prolog programming languages. We outline practical tools, based on our ideas, which simplify substantially some significant steps of the design and use of certain Prolog predicates. We extend current work on the translation from algebraic specifications and term rewriting systems to logic programs along two