Natural Language and Logic Programming

Veronica Dahl

Summary

• N.L. and L.P.: A natural alliance
• Historic Overview
• Some basic problems in NLP
• Computational Linguistic Approaches to long-distance dependencies: 1. unification-based, 2. logico-mathematical, 3. principles-and-parameters
• Some hard problems in NLP- Assumption Grammars
• Recent Applications, e.g. Controlling Virtual Worlds/Robots Through Natural Language
• Cross-fertilization with other disciplines

N.L. and L.P.: A natural alliance

• Expression of language knowledge (in many linguistic formalisms) as some sort of deduction from general principles
• Partial, incremental info- also typical in linguistics
• Aims of conciseness, generality, declarativeness

Using logic throughout implies minimal need for interfaces

Historic Overview

• First L.P. application = first language processing L.P. application (A system of man-machine communication in French- Colmerauer, Kanoui, Pasero, Roussel, 1973)
• Metamorphosis Grammars (Colmerauer 75); DCGs (F. Pereira and D.H.D. Warren)

Logic term rewriting formalism

Applications:

- A conversation system in French on social and kin relationships

- A Spanish, French and English front end to the first database system written in Prolog (compared favourably in efficiency to that of the Lunar System by Woods)

• Deviations from fixed strategy- e.g. tabular parsing, bottom up parsing.
• Evolving L.P. techniques also found application in language processing: higher order logics, partial execution, memoing, C.L.P., parallelism

In parallel: Developments in linguistics and computational linguistics

• Transformational (generative) paradigm: initial step towards computationally usable linguistic models. A base component generated sentences in "canonical" form (e.g. active voice), and a transformational component generated alternative forms (e.g. passive voice, interrogatives). Subsequent efforts aim at replacing the myriads of specific rules involved by brevity oriented frameworks.
• Lexical functional grammar (Bresnan, 82): replaces transformations by dealing with them in the lexicon
• Generalized Phrase Structure Grammars (Gazdar el al, 85): Higher level grammars are mechanically converted into context-free grammars
• Government-Binding/Barriers (Chosmky 81,86): Deductive interaction of a small number of principles and constraints
• Categorial grammars (Oerhle, Bach, Wheeler 88 overview): Analyse language expressions as the functional product of a functor applied to simpler argument expressions

Difficulties remain:

• Modern linguistics stresses competence over performance
• Results mostly obtained for language synthesis, rather than for analysis
• Formalizations of linguistics- relatively recent, and in constant evolution

Interesting mutual feedback: formal linguistics, computational linguistics and L.P.
A BinProlog grammar (AG) for analysing or generating English:
% N.B.you must have a blank before the 
% marker for a word (i.e., #)
% To give an input string, use "#<" 
% (e.g., call ? #<Input, sent(P),#>Rest.)
% To get an output string, use "#>"
% For instance, ?- #<[a,b,c], #X,#Y, #>Rest.
% should yield: X=a,
%               Y=b,
%               Rest=[c]
% Notation: Some BinPrologs use 
% "dcg_def([a,b,c])" instead of "#<[a,b,c]",
% and "dcg_val(X)" instead of "#>X".

sent(P) :- name(X), verb_phrase(X,P).

% Verb Phrases

verb_phrase(X,P):- verb(X,P,L), comps(L).

comps([]).
comps([H|T]) :- comp(H), comps(T).

comp([P,X]) :- P, name(X).


prep_phrase(W,Z) :- W, name(Z).

% Intransitive verbs

verb(X,smiles(X),[]) :- #smiles.

% Transitive verbs

verb(X,likes(X,Y),[[prep(dir),Y]]) :- #likes. 
verb(X,P,L) :- #is, adj(X,P,L). 

% Bitransitive verbs

verb(X,gives(X,Y,Z),[[prep(dir),Y],[prep(to),Z]]) :- #gives.

prep(to) :- #to.
prep(dir).

name(anne) :- #anne.
name(rover) :- #rover.
name(peter) :- #peter.
name(X) :- #who.

% Unary adjectives

adj(X,intelligent(X),[]) :- #intelligent.
adj(X,kind(X),[]) :- #kind.

% Binary adjectives

adj(X,angry_with(X,Y),[[prep(with),Y]]) :- #angry.
Retrieving the argument questioned on (sentences with "who")

% A question is a sentence in which some 
% name has been replaced by "who"
% (assumed as "answer" in the name rule, 
% to be consumed by the question rule)

question(X,P) :- sent(P), -answer(X).

sent(P) :- noun_phrase(X), verb_phrase(X,P).

% Noun Phrases

noun_phrase(X) :- name(X).

% Verb Phrases

verb_phrase(X,P):- verb(X,P,L), comps(L).

comps([]).
comps([H|T]) :- comp(H), comps(T).

comp([P,X]) :- P, name(X).


prep_phrase(W,Z) :- W, name(Z).

% Intransitive verbs

verb(X,smiles(X),[]) :- #smiles.

% Transitive verbs

verb(X,likes(X,Y),[[prep(dir),Y]]) :- #likes.
verb(X,P,L) :- #is, adj(X,P,L).  

% Bitransitive verbs

verb(X,gives(X,Y,Z),[[prep(dir),Y],[prep(to),Z]]) :- #gives.

prep(to) :- #to.
prep(dir).

name(anne) :- #anne.
name(rover) :- #rover.
name(peter) :- #peter.
name(X) :- #who, +answer(X).

% Unary adjectives

adj(X,intelligent(X),[]) :- #intelligent.
adj(X,kind(X),[]) :- #kind.

% Binary adjectives

adj(X,angry_with(X,Y),[[prep(with),Y]]) :- #angry.  

% Adjective Phrases

adj_phrase(X,P) :- adj(X,P,L), comps(L).

Quantified Noun Phrases

% N.B. Not yet embedded inside noun phrases 
% (i.e., complements are built around proper 
% names, not quantified noun phrases)
% Only relevant rules are shown, more complete
% grammar next

sent(S) :- noun_phrase(X,P,S), verb_phrase(X,P).

% Noun Phrases

noun_phrase(X,P,P) :- name(X).
noun_phrase(X,Predicate,Formula):- 
    quant(X,Subject,Predicate,Formula),
    noun(X,Subject,L), comps(L).

quant(X,S,P,the(X,S,P)) :- #the.
quant(X,S,P,a(X,S,P)) :- #a; #some.
quant(X,S,P,no(X,S,P)) :- #no.
quant(X,S,P,all(X,S,P)) :- #all; #every.

noun(X,dinosaur(X),[]):- #dinosaur.
noun(X,chair(X),[]):- #chair.

noun(X,mother_of(X,Y),[[prep(of),Y]]).
noun(X,father_of(X,Y),[[prep(of),Y]]).

Embedding Quantified Noun Phrases inside quantified noun phrases

% WARNING: WORKS FOR ANALYSIS ONLY
% Sentences
 
question(X,Q) :- sent(Q), -answer(X).

sent(S) :- noun_phrase(X,P,S), verb_phrase(X,P).

% Noun Phrases

noun_phrase(X,P,P) :- name(X).
noun_phrase(X,Predicate,Formula):- 
    quant(X,Subject,Predicate,Formula),
    noun(X,S,L), comps(L,S,Subject).

quant(X,S,P,the(X,S,P)) :- #the.
quant(X,S,P,a(X,S,P)) :- #a; #some.
quant(X,S,P,no(X,S,P)) :- #no.
quant(X,S,P,all(X,S,P)) :- #all; #every.

noun(X,dinosaur(X),[]):- #dinosaur.
noun(X,zoo(X),[]):- #zoo.
% noun(X,chair(X),[]):- #chair.

noun(X,mother_of(X,Y),[[of,Y]]):- #mother.
noun(X,father_of(X,Y),[[of,Y]]):- #father.

% Verb Phrases

% The verb phrase's representation is now obtained 
% incrementally: each complement contributes
% some more structure to the skeleton P

verb_phrase(X,P1):- verb(X,P,L), comps(L,P,P1).

comps([],P,P).
comps([[P,X]|L],S1,S) :- prep(P), 
    noun_phrase(X,S1,S2), comps(L,S2,S).

% Intransitive verbs

verb(X,smiles(X),[]) :- #smiles.

% Transitive verbs

verb(X,likes(X,Y),[[dir,Y]]) :- #likes. 
verb(X,P,L) :- #is, adj(X,P,L). 

% Bitransitive verbs

verb(X,gives(X,Y,Z),[[dir,Y],[to,Z]]) :- #gives.

prep(of) :- #of.
prep(to) :- #to.
prep(with):- #with.
prep(dir).

name(anne) :- #anne.
name(rover) :- #rover.
name(peter) :- #peter.
name(X) :- #who, +answer(X).

% Unary adjectives

adj(X,intelligent(X),[]) :- #intelligent.
adj(X,kind(X),[]) :- #kind.

% Binary adjectives

adj(X,angry_with(X,Y),[[with,Y]]) :- #angry. 

% Adjective Phrases

adj_phrase(X,P) :- adj(X,P1,L), comps(L,P1,P).

Some Basic Problems in NLP

The Parsing Problem: Given a grammar and a presumed sentence in the language defined by that grammar, obtain some representative structure(s) if the sentence is indeed in the language.

• infinite sentences, finite grammars: conciseness, regularity
• ambiguity that plagues natural language
• avoiding overgeneration
• obtaining semantic representations
• unbounded or long-distance dependency: e.g. Topicalization

"Logic, we love"
"Logic, I know we love"
"Logic, I suspected he knew we love"

L.P. Approaches to long-distance dependencies

• Through Extra Arguments:

  sentence --> s(complete).
  s(E) --> noun_phrase(complete), verb_phrase(E).

  noun_phrase(complete) --> determiner, noun, relative.
  noun_phrase(complete) --> name.
  noun_phrase(missing_np) --> [].

  verb_phrase (complete) --> verb.
  verb_phrase (E) --> verb, noun_phrase(E).

  relative --> pronoun, s(missing_np).
  relative --> pronoun, vp(complete).

• Through Multi-head rules

e.g. subject-verb inversion, as occurs in interrogative sentences in some romance languages, can be described by MG rules such as:

           marker, noun_phrase, verb --> verb, noun_phrase.

where ``marker'' has been introduced by rules such as:

          sentence(interrogative) --> marker, s, [?].
          sentence (affirmative) --> s.

e.g. relativization can be expressed in XGs through:

        relative --> rel_marker, sentence. 
        np --> trace(_).

        rel_marker(I), skip(X), trace(I) --> rel_pronoun(I), skip(X).

Linguistically principled approaches

• complex feature structures encode partial information about constraints (often in view of graph unification).
• features are given values only through unification

Feature structure unification as constraint enforcement

A Sample feature-based grammar fragment

S -->     NP       VP          
       [num:X,     [num:X]     
       case:nom]                

NP      -->   name            VP      -->      V
[num:X,      [num:X,          [num:X]        [num:X,
case:Y]      case:Y]                         subcat:1]

NP      --> Pronoun           VP      -->      V       NP
[num:X,     [num:X,           [num:X]         [num:X,  [case:acc]
case:Y]     case:Y]                           subcat:2]

Name    -->  Maria            V       -->  laughs
[num:sing]                                  [num:sing,
                                            subcat:1]

2. Logico-mathematical approaches

• Higher order logics (e.g. Linear and intuitionistic implication approach (Lolli, Assumption Grammars)

E. g. the relativization rule in lambda-Prolog:

              relative (that::L1) L2 :-  (np Z Z) => s L1 L2.

prevents empty noun phrases from being generated outside relative clauses.
• Categorial grammars embed info about all possible combinations of constituents in their categories. Based on the idea that language expressions can be analysed as the functional product of a functor applied to a suitable set of simpler argument expressions

3. Principle-and-Constraints approaches

• 3.1 Head-Driven Phrase Structure Grammar (HPSG): each phrase contains a lexical head, which determines many of the syntactic properties of that phrase (e.g. for a verb phrase, the verb; for a prepositional phrase, the preposition; etc.).

HPSG treats long-distance dependencies through transmitting a non overt category's feature specifications from arbitrary daughters (not just head daughters) to their mothers, until they can be unified with the appropriate dislocated constituent.

HPSG-inspired approaches: Constraint Logic Grammars, The Comprehensive Unification Formalism, CU-Prolog, Typed Unification Grammars

• 3.2 Chomskyan approaches

Government-Binding: three rule systems and a set of modules which define well-formedness conditions on each of four levels of representation

Some hard problems in NLP- Assumption Grammars

• assume each noun phrase as a potential referent of some pronoun appearing later
• let pronouns consume these assumptions when there is agreement in gender, number, etc.

Sample treatment of Anaphora

np(X,VP,VP):- proper_name(X),  *(specifier(X)). 
np(X,VP,R):- det(X,NP,VP,R), noun(X-F,NP), 
             *(specifier(X-F)).

pronoun(X-[masc,sing]):- #he.
pronoun(X-[fem,sing]):- #her.

anaphora(X):- pronoun(X).
noun(X-[fem,sing],woman(X)):- #woman.

• *(specifier(X)) keeps in X the noun phrase's relevant information.
• potential co-specifiers of an anaphora can then consume the most likely co-specifiers hypothesized (i.e., those agreeing in gender and number), through a third rule for noun phrase:

np(X,VP,VP):- anaphora(X), -(specifier(X)).

Timeless Assumptions

Backwards anaphora:

Near her, Alice saw a Bread-and-Butterfly.

• pronoun needs to consume a referent before it has been assumed

Tweedledum proposed, and Tweedledee agreed to, a battle.

• direct object needs to be consumed before having been assumed

Find-or-Wait Timeless Assumption

% The assumption being made was expected 
% by a previous consumption
=X :- -wait(X), !.

% if no previous expectation, assume it linearly
=X :- +X.


% uses an assumption, and deletes it if linear
=-X :- -X, !.

% if assumption not yet made, 
% adds its expectation
=-X :- +wait(X).

Simplified example for Coordination- using timeless assumptions

sent(and(S1,S2)):- s(S1), +and, s(S2). 
    % conjunction of two sentences assumes that
    % there will be an ``and'' between them.

s(S):- name(K), verb(K,P,S), np(P).

np(P):- det(X,P1,P), noun(X,P1), 
        =ref_np(P).    
             % keep it as potential 
             %referent for a missing np
np(P):- #and, -and,             
        =-ref_np(P).    
        
det(X,P,the(X,P)):- #the.
noun(X,cupboard(X)):- #cupboard.

name(tim):- #tim.
name(anne):- #anne.

verb(X,Y,built(X,Y)):- #built.
verb(X,Y,painted(X,Y)):- #painted.

test(In,Out):-  dcg_def(In), sent(Out), 
                dcg_val([]).

go:-example(X),test(X,Out),write(Out),nl,fail;   
    write('end'), nl.

example([tim,built,and,
         anne,painted,the,cupboard]).

we obtain the semantic representation:

and(built(tim,the(X,cupboard(X)),
painted(ann,the(X,cupboard(X)))

Controlling Virtual Worlds/Robots Through Natural Language

• imperative (subjectless) outermost sentences
• dynamic changes of the world driven by natural language utterances
• formula production inadequate: subformulas must be evaluated by consulting the world (e.g. "Craft a car, give it to Peter" must evaluate "it" to the new world object represented by the car that avatar crafted)
• interesting interactions between the parser and the world description

Sample LogiMOO consultation in Controlled English

==BEGIN COMMAND RESULTS== you are in the lobby SUCCEEDING(go(lobby)) user(veronica,none,'http://localhost'). user(paul,none,'http://localhost'). login(paul). online(veronica). online(paul). place(lobby). place(office). contains(lobby,veronica). contains(lobby,paul). SUCCEEDING(look)

==END COMMAND RESULTS==

TEST: Craft a cat. Where is the cat? Who has it? WORDS: [craft,a,cat,.,where,is,the,cat,?,who,has,it,?] SENTENCES: [craft,a,cat] [where,is,the,cat] [who,has,it]

==BEGIN COMMAND RESULTS== SUCCEEDING(craft(cat)) cat is in lobby SUCCEEDING(where(cat)) joe has cat SUCCEEDING(who(has,cat))

==END COMMAND RESULTS==

TEST: Dig the bedroom. Go there. Dig a kitchen, open a port south to the kitchen, go there, open a port north to the bedroom. Go there. Craft a song-au. Give it to the Wizard.

==BEGIN COMMAND RESULTS== SUCCEEDING(dig(bedroom)) you are in the bedroom SUCCEEDING(go(bedroom)) SUCCEEDING(dig(kitchen)) SUCCEEDING(open_port(south,kitchen)) you are in the kitchen SUCCEEDING(go(kitchen)) SUCCEEDING(open_port(north,bedroom)) you are in the bedroom SUCCEEDING(go(bedroom)) SUCCEEDING(craft(song.au)) logimoo:<joe># 'wizard:I give you song.au' SUCCEEDING(give(wizard,song.au))

==END COMMAND RESULTS==

TEST: Craft a Gnu. Who has it? Where is it? Where am I? WORDS: [craft,a,gnu,.,who,has,it,?,where,is,it,?,where,am,i,?] SENTENCES: [craft,a,gnu] [who,has,it] [where,is,it] [where,am,i]

==BEGIN COMMAND RESULTS== SUCCEEDING(craft(gnu)) joe has gnu SUCCEEDING(who(has,gnu)) gnu is in bedroom SUCCEEDING(where(gnu)) you are in the bedroom SUCCEEDING(whereami)

==END COMMAND RESULTS==

TEST: Give to the Wizard the Gnu that I crafted. Who has it? WORDS: [give,to,the,wizard,the,gnu,that,i,crafted,.,who,has,it,?] SENTENCES: [give,to,the,wizard,the,gnu,that,i,crafted] [who,has,it]

==BEGIN COMMAND RESULTS== logimoo:<joe># 'wizard:I give you gnu' SUCCEEDING(give(wizard,gnu)) wizard has gnu SUCCEEDING(who(has,gnu))

==END COMMAND RESULTS==

TEST: construya un gato. donde esta el gato? quien tiene lo? WORDS: [construya,un,gato,.,donde,esta,el,gato,?,quien,tiene,lo,?] SENTENCES: [construya,un,gato] [donde,esta,el,gato] [quien,tiene,lo]

==BEGIN COMMAND RESULTS== SUCCEEDING(craft(gato)) gato is in lobby SUCCEEDING(where(gato)) veronica has gato SUCCEEDING(who(has,gato))

==END COMMAND RESULTS==

Cross-fertilizations- Chart Parsing

• Kay (1967): Store substructures parsed in a chart which remains available even after failure and backtracking

e.g. for "Alan Robinson discovered the resolution principle in the sixties", the following two rules may be tried in order:

vp --> v, np.
vp --> v, np, pp.

• Earley (1970) Ingenious chart parsing algorithm : the chart can store unfinished constituents as well as completely parsed ones.
• David D. H. Warren (1975) proposed the transfer of the Earley algorithm ideas about parsing into logic programming proper. Memoization has since been investigated within ``Earley deduction" by David Scott Warren and incorporated into other logic programming settings.

Cross-fertilizations- Parametric L-systems and logic grammars (Pruzinkiewicz and Hanan 1992)

• developed for visual models of plant development
• generates strings that are sequences of commands for a LOGO-style turtle

References

• N. Chomsky. Lecture notes on government and binding, the pisa lectures, 2nd (revised) ed. Foris Publications, 1982.
• A. Colmerauer. Metamorphosis grammars. In Lecture Notes in Computer Science, New York, N. Y., 1978. Springer-Verlag.
• V. Dahl. Discontinuous grammars. Computational Intelligence, 5:161--179, 1989.
• V. Dahl and M. McCord. Treating coordination in logic grammars. In American Journal of Computational Linguistics 9, pages 69--91, 1983.
• V. Dahl, P. Tarau, and Y. N. Huang. Datalog Grammars. In Proc. 1994 Joint Conference on Declarative Programming, pages 268--282, Peniscola, Spain, September 1994.
• V. Dahl, P. Tarau, and J. Andrews. Extending Datalog Grammars. In Proc. of NLDB'95, Paris, May 1995
• Veronica Dahl, Paul Tarau, and Renwei Li. Assumption Grammars for Processing Natural Language. In Lee Naish, editor, Proceedings of the Fourteenth International Conference on Logic Programming, pages 256--270, MIT press, 1997.
• A. Fall, V. Dahl, and P. Tarau. Resolving co-specification in contexts. In Proc. of IJCAI Workshop on Context in Natural Language Processing, Montreal, Canada, 1995.
• J.-Y. Girard. Linear logic. Theoretical Computer Science, (50):1--102, 1987.
• Joshua S. Hodas and Dale Miller. Logic Programming in a Fragment of Intuitionistic Linear logic. Journal of Information and Computation, 110(2):327--365, May 1994.
• Paul Tarau. BinProlog 5.75 User Guide. Technical Report 97-1, Departement d'Informatique, Universite de Moncton, April 1997. Available from http://clement.info.umoncton.ca/BinProlog.
• Zaiane, Osmar; Fall, Andrew; Rochefort Stephen; Dahl Veronica and Tarau, Paul: On-line Resource Discovery Using Natural Language, Proceedings of RIAO'97, 1997, pp.336--355, "McGill University, Montreal"

About this document ...

This document was generated using the LaTeX2HTML translator Version 95.1 (Fri Jan 20 1995) Copyright © 1993, 1994, Nikos Drakos, Computer Based Learning Unit, University of Leeds.

The command line arguments were:
latex2html -split 0 -link 0 html.tex.

The translation was initiated by Veronica Dahl on Sat Dec 27 18:27:30 PST 1997