Using Higher-Order Logic Programming for Semantic Interpretation of Coordinate Constructs

Using Higher-Order Logic Programming for Semantic Interpretation of Coordinate Constructs Seth Kulick University of Pennsylvania Computer and Information Science 200 South 33rd Street Philadelphia, PA 19104-6389 USA skulick@linc, cis. upenn, edu Abstract Many theories of semantic interpretation use A-term manipulation to composition- ally compute the meaning of a sentence. These theories are usually implemented in a language such as Prolog that can simulate A-term operations with first-order unifica- tion. However, for some interesting cases, such as a Combinatory Categorial Gram- mar account of coordination constructs, this can only be done by obscuring the un- derlying linguistic theory with the "tricks" needed for implementation. This paper shows how the use of abstract syntax per- mitted by higher-order logic programming allows an elegant implementation of the se- mantics of Combinatory Categorial Gram- mar, including its handling of coordination constructs. 1 Introduction Many theories of semantic interpretation use A-term manipulation to compositionally compute the mean- ing of a sentence. These theories are usually imple- mented in a language such as Prolog that can sim- ulate A-term operations with first-order unification. However, there are cases in which this can only be done by obscuring the underlying linguistic theory with the "tricks" needed for implementation. For example, Combinatory Categorial Grammar (CCG) (Steedman, 1990) is a theory of syntax and seman- tic interpretation that has the attractive character- istic of handling many coordination constructs that other theories cannot. While many aspects of CCG semantics can be reasonably simulated in first-order unification, the simulation breaks down on some of the most interesting cases that CCG can theoreti- cally handle. The problem in general, and for CCG in particular, is that the implementation language does not have sufficient expressive power to allow a more direct encoding. The solution given in this pa- per is to show how advances in logic programming allow the implementation of semantic theories in a very direct and natural way, using CCG as a case study. We begin by briefly illustrating why first-order unification is inadequate for some coordination con- structs, and then review two proposed solutions. The sentence in (la) usually has the logical form (LF) in (lb). (la) John and Bill run. (15) (and (run John) (run Bill)) CCG is one of several theories in which (lb) gets derived by raising John to be the LF AP.(P john), where P is a predicate that takes a NP as an argu- ment to return a sentence. Likewise, Bill gets the LF AP.(P bill), and coordination results in the fol- lowing LF for John and Bill: (2) AP.(and (P john) (P bill)) When (2) is applied to the predicate, (15) will re- sult after 13-reduction. However, under first-order unification, this needs to simulated by having the variable z in Az.run(z) unify both with Bill and John, and this is not possible. See (Jowsey, 1990) and (Moore, 1989) for a thorough discussion. (Moore, 1989) suggests that the way to overcome this problem is to use explicit A-terms and encode /~-reduction to perform the needed reduction. …

Content truncated to 500 words