In this chapter we briefly show how definite clause logic programs fall out as a particular instance of unification-based phrase structure grammars. The analysis is based on the realization that parse trees for unification-based grammars bear a striking resemblance to proof trees for logic programs. More significantly, the top-down analysis of unification-based grammars generalizes the notion of SLD-resolution as it is applied in definite clause logic programming, whereas the bottom-up analysis generalizes the standard notion of denotational semantics for logic programs. The results in this chapter can be taken as a generalization of the Prolog family of programming languages (though as we have said before, we put off the analysis of inequations in grammars and hence in definite clause programs until the next chapter on constraint-resolution).

It has been noted in the past, most notably by Mukai (1985, 1987, Mukai and Yasukawa 1985), Aït-Kaci and Nasr (1986), and Höhfeld and Smolka (1988), that the idea of definite clause programming can be extended to domains other than first-order terms. In particular, the systems developed by Mukai and Yasukawa, Aït-Kaci and Nasr, and Hohfeld and Smolka employ a more or less standard notion of definite clauses with the simple modification of replacing first-order terms with various notions of feature structure. Of course, this move was preceded by extensions to Prolog from within the Prolog community itself by Colmerauer (1984), who developed Prolog II, a language based on definite clauses that allowed terms to contain cycles and also inequations. In this chapter, we generalize all of these systems by showing how any of our systems of feature structures can be used as the basis for defining a definite clause programming language.