Constraint satisfaction - an alternate approach to unification in Prolog

Prolog is a linear resolution theorem prover with restrictions on the form of the clauses to prune the search space. Although Prolog has been widely used for implementing natural language systems, database systems, knowledge based expert systems and other A.I tasks, it has many limitations. The inferencing is symbolic and all the computations are performed in the Herbrand universe. Prolog has no notion of function evaluation. The uniform parameter passing mechanism, viz unification, is syntactic and too restrictive in nature. Moreover, Prolog uses a depth first search strategy combined with chronological backtracking which renders the SLD-Resolution incomplete. In this thesis, we study the incorporation of a constraints solver into Prolog. The generalization of unification into a constraints satisfaction algorithm allows the incorporation of function evaluation into unification. Constraint satisfaction is used to replace unification thus enhancing the power of Prolog. This idea could possibly be extended to other contexts where unification is used. Constraints can also appear as goals in the body of a rule. We discuss the enhancement in expressive power leading to an efficient solution of a larger class of problems. We also discuss ways of compiling the constraint solver and the modifications that are needed to be made in the Warren abstract machine for Prolog. An interpreter for the extended Prolog (written in Prolog) incorporating a constraint solver is presented along with examples illustrating its power.