Natural Language and Logic Programming

Veronica Dahl
Simon Fraser University
veronica@cs.sfu.ca

Summary

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

Common Points: Logic: Natural underpinning for N.L. semantics

Using logic throughout implies minimal need for interfaces

Historic Overview

In parallel: Developments in linguistics and computational linguistics

Difficulties remain:

Therefore, C.L. proceeded with ad-hoc, unclear guidance from linguistics.

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.

L.P. Approaches to long-distance dependencies

Linguistically principled approaches

1. Unification-based (e.g. Lexical Functional Grammar, Generalized Phrase Structure Grammar): Unification= combination of compatible feature structures rather than of first-order terms (but it has recently been shown that feature structures may be essentially interpreted as terms allowing freedom of order and number of the arguments).

Feature structure unification as constraint enforcement

Tailorings of constraint logic programming frameworks to natural language applications (e.g. equational constraints, or constraints requiring the existence of values, set membership constraints, etc.) are also present in some form in computational linguistic formalisms (e.g. Augmented Transition Networks, Lexical Functional Grammars, Functional Unification Grammar, the Generalized Phrase-Structure Grammar framework)

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

3. Principle-and-Constraints approaches

Replacing myriads of specific rules by the deductive interaction of a small number of principles and constraints

Some hard problems in NLP- Assumption Grammars

Using assumptions for anaphora resolution:

Sample treatment of Anaphora

We exemplify the hypothesizing part through the following noun phrase rules:
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.
np(X,VP,VP):- anaphora(X), -(specifier(X)).

Timeless Assumptions

WHEN CONSUMPTION DOES NOT NECESSARILY PRECEDE ASSUMPTION:

Backwards anaphora:

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

Coordination:

Tweedledum proposed, and Tweedledee agreed to, a battle.

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

Tim built and Anne painted the cupboard.
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

Special characteristics:

Sample LogiMOO consultation in Controlled English

TEST: Go to the lobby. Look. WORDS: [go,to,the,lobby,.,look,.] SENTENCES: [go,to,the,lobby] [look]

==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

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

References

About this document ...

Natural Language and Logic Programming

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


Veronica Dahl

Sat Dec 27 18:27:30 PST 1997