Application: A Question-Answering System

This program is an adaptation of a question-answering system developed in Pereira and Shieber (pp 149-157).  This is a simple program that demonstrates the main semantic ideas that can be represented by logical forms, quantifiers, and the lambda calculus.  The complete program is given in the attached file.

This discussion illustrates how the program is used, what it can do, and some key points about how it represents, stores, and retrieves information that it has "learned" as it interacts with the user.

Sample Dialog

Here is a dialog that occurs with the program pereiraTalk (in the directory ~allen/public_html/prolog) after typing consult(pereiraTalk). at the ?- prompt:
?- run.
>> principia is a book
Asserted "book(principia)."
>> bertrand wrote every book
Asserted "writes(bertrand, _G332):-book(_G332)."
>> what did bertrand write
>> what did allen write
>> who wrote every book
Error: "too difficult."
>> who wrote principia
>> bruce read every book that bertrand wrote
Asserted "reads(bruce, _G379):-book(_G379), writes(bertrand, _G379)."
>> shrdlu is a book
Asserted "book(shrdlu)."
>> what did bruce read
principia, shrdlu.
As is evident, the program stores information about what has been asserted and uses that information to answer questions, provided that it can parse the assertions and questions that are entered.

Successful parsing depends on syntactic correctness.  Parsable assertions result in the message "Asserted: C" where C is a Prolog rule or fact.  Not shown in this excange is the program's adding this fact to the database with which it has started (facts and rules defining the basic grammar and lexicon), and the program's translation of the original assertion into a logical form, which is its semantic representation.

Parsable questions are answered by a message "yes" (if the question is a yes/no question and the answer is true according to the facts and rules stored in the database during the processing of prior assertions), "no" (if the answer is not so justified), or a list of all values that answer the question (if the question is not a yes/no question).

The Overall Strategy

The overall strategy for the program is simple, and given by the following code:  give a prompt, read a sentence (assertion or query), parse it and discover its meaning as a logical form, convert that logical form into a Prolog clause, generate and display a reply, and then repeat these steps.  If the sentence cannot be successfully parsed (grammatical or lexicon error) or if a Prolog clause cannot be generated from the logical form, then the message Error: "too difficult" appears for that sentence.
run :- 
        write('>> '),           % prompt the user
        read_sent(Words),       % read a sentence
        talk(Words, Reply),     % process it with TALK
        print_reply(Reply),     % generate a reply
        run.                    % pocess more sentences

%%% talk(Sentence, Reply)
%%%     Sentence ==> sentence to form a reply to
%%%     Reply    <== appropriate reply to the sentence

talk(Sentence, Reply) :-                     % parse the sentence
         parse(Sentence, LF, Type),
       % convert the FOL logical form into a Horn 
       % clause, if possible
         clausify(LF, Clause, FreeVars), !,
       % concoct a reply, based on the clause and 
       % whether sentence was a query or assertion
         reply(Type, FreeVars, Clause, Reply).

talk(Sentence, error('too difficult')).

The Lexicon

Six different forms for each verb are stored in the lexicon: the nonfinite form, the third person singular form, the past tense, the past participle, the present participle, and the logical form.

The logical form for an intransitive verb is an encoding of the lambda expression \x.verb(x), where x is a placeholder for the subject.  For instance, "halts" has a logical form that encodes the expression \x.halts(x), or X^ 'halts(X).

iv(nonfinite,       LF) --> [IV], {iv(IV, _, _, _, _, LF)}.
iv(finite,          LF) --> [IV], {iv(_, IV, _, _, _, LF)}.     
iv(finite,          LF) --> [IV], {iv(_, _, IV, _, _, LF)}.     
iv(past_participle, LF) --> [IV], {iv(_, _, _, IV, _, LF)}.     
iv(pres_participle, LF) --> [IV], {iv(_, _, _, _, IV, LF)}.
iv(halt, halts, halted, halted, halting,   X^ `halts(X)).
iv(run,  runs,  ran,    run,    running,   X^ `runs(X)).
Transitive verbs have as a logical form an encoding of the lambda expression \x.\y.verb(x, y), where x is the subject of the verb and y is the object.  For instance, "speaks" is an encoding of \x.\y.speaks(x, y), or X^Y^ 'speaks(X, Y).
tv(nonfinite,   LF)         --> [TV],   {tv(TV, _, _, _, _, LF)}.
tv(finite,      LF)         --> [TV],   {tv(_, TV, _, _, _, LF)}.
tv(finite,      LF)         --> [TV],   {tv(_, _, TV, _, _, LF)}.
tv(past_participle,     LF) --> [TV],   {tv(_, _, _, TV, _, LF)}.
tv(pres_participle,     LF) --> [TV],   {tv(_, _, _, _, TV, LF)}.
tv(write,   writes,   wrote,     written,   writing,    X^Y^ `writes(X,Y)).
tv(read,    reads,    read,      read,      reading,    X^Y^ `reads(X,Y)).
tv(speak,   speaks,   spoke,     spoken,    speaking,   X^Y^ `speaks(X,Y)).
tv(meet,    meets,    met,       met,       meeting,    X^Y^ `meets(X,Y)).
tv(concern, concerns, concerned, concerned, concerning, X^Y^ `concerns(X,Y)).
tv(run,     runs,     ran,       run,       running,    X^Y^ `runs(X,Y)).
Auxiliary verbs (to, does, did, ...), relative pronouns (that, who, whom), wh-words (who, whom, what) are enoded in their usual way.

Determiners are encoded with logical forms that reflect their meaning.  For example, if we assert "Bertrand wrote every book", the system needs a logical form that will say, in effect, that "for every X , if X is a book then bertrand wrote X."  The logical form for "every" in the lexicon has that structure:

det(every,  (X^S1) ^ (X^S2) ^ all(X, S1=>S2)).

Similarly, the logical form for determiners "a" and "some" are coded as follows:

det(a,         (X^S1) ^ (X^S2) ^ exists(X, S1&S2)).
det(some,   (X^S1) ^ (X^S2) ^ exists(X, S1&S2)).

There are two different types of nouns, those which represent classifications of objects or people, and proper nouns (which represent specific objects and people themselves -- e.g., principia).  The first type of noun has a logical form which allows proper nouns to become members of that classification.  For instance, the classification "author" has the logical form \, which is encoded X^ `author(X).  The second type has itself as its logical form.

n(author,     X^ `author(X)).
pn(principia, principia).

The Grammar

The grammar for this program parses simple declarative sentences, sentences with relative clauses, inverted sentences, and various kinds of questions, using familiar strategies from our earlier studies of syntax.  What's new here is that each grammar rule generates a logical form as a byproduct (rather than a portion of a parse tree).
s(S, GapInfo)   --> np(VP^S, nogap), vp(finite, VP, GapInfo).

sinv(S, GapInfo) --> aux(finite/Form, VP1^VP2), 
                     np(VP2^S, nogap), vp(Form, VP1, GapInfo).

q(S => `answer(X))   --> whpron, vp(finite, X^S, nogap).
q(S => `answer(X))   --> whpron, sinv(S, gap(np, X)).
q(S => `answer(yes)) --> sinv(S, nogap).
q(S => `answer(yes)) --> [is],  np((X^S0)^S, nogap),
                                np((X^true)^exists(X,S0&true), nogap).

np(NP, nogap) --> det(N2^NP), n(N1), optrel(N1^N2).
np(NP, nogap) --> pn(NP).       
np((X^S)^S, gap(np, X)) --> [].

vp(Form, X^S, GapInfo)  --> tv(Form, X^VP), np(VP^S, GapInfo).
vp(Form, VP, nogap)     --> iv(Form, VP).
vp(Form1, VP2, GapInfo) --> aux(Formrlogina1/Form2, VP1^VP2),
                            vp(Form2, VP1, GapInfo).
vp(Form1, VP2, GapInfo) --> rov(Form1/Form2, NP^VP1^VP2),
                            np(NP, GapInfo), vp(Form2, VP1, nogap).
vp(Form2, VP2, GapInfo) --> rov(Form1/Form2, NP^VP1^VP2),
                            np(NP, nogap), vp(Form1, VP1, GapInfo).
vp(finite, X^S, GapInfo) --> [is], np((X^P)^exists(X,S&P), GapInfo).

optrel((X^S1)^(X^(S1&S2))) --> relpron, vp(finite, X^S2, nogap).
optrel((X^S1)^(X^(S1&S2))) --> relpron, s(S2, gap(np, X)).
optrel(N^N) --> [].

Parsing Example: Assertions

Parsing an assertion proceeds in two steps: developing a logical form for the meaning of the assertion and then adding that logical form (converted to Prolog) to the database of facts and rules.  The first step is initiated by:

parse(Sentence, LF, assertion) :- s(LF, nogap, Sentence, []).

The reply to an assertion is made simply be reporting to the user the Prolog fact or rule that was generated from the logical form after the paring of the sentence.  The reply function also adds this fact or rule to the Prolog program, so that it can participate in answering future queries.  This is accomplished by the Prolog function "assert", which takes any Prolog fact or rule and adds it dynamically to the database.

reply(assertion, _FreeVars, Assertion, asserted(Assertion)) :- assert(Assertion), !.

Parsing Example: Queries

Parsing a query requires that an answer be developed alongside the logical form.  If the sentence is a query, then the productions for function q all return a logical form LF =  "Q => answer(A)".  This logical form is then used to develop an answer, which will be true exactly when the database of facts and rules can justify the truth of A.  The first call in this process is:

parse(Sentence, LF, query) :- q(LF, Sentence, []).

For example, the parse for the sentence "who wrote principia" wlll return the logical form

LF = `writes(X, principia)=> `answer(X)

The reply to a query is made by first finding a set of all the answers that satisfy the query, replying with that set (if it exists), or "no" if it doesn't.

reply(query, FreeVars, (answer(Answer):-Condition), Reply) :-
                   (setof(Answer, FreeVars^Condition, Answers) -> Reply = answer(Answers) ;
                                                                  (Answer = yes -> Reply = answer([no]) ;
                                                                                             Reply = answer([none]))), !.

This can be read as an ordinary "if-then-else" statement, where the arrows -> denote "then" and the semicolons (;) denote "or else".  So the first line generates the Reply if such a set is found, and the second generates the Reply if the answer is "yes," and otherwise the third line generates the Reply.

The setof function builds an ordered set of instances of Answer, called Answers (in the form of a list without duplicates) that satisfies the goal FreeVars^Condition.  For instance, if the goal is answer(X) := writes(X, principia), then the call is setof(X, FreeVars^writes(X, principia), Answers).  If the fact writes(bertrand, principia) is in the database at the time, then setof will return Answers = [bertrand].  Otherwise, setof will fail.

Clausify: Converting Logical Forms to Prolog Clauses

The function clausify converts a logical form to an equivalent Prolog fact or rule, whenever it can.  That is, given a logical form FOL, clausify generates a Clause which is the equivalent Prolog fact or rule.  A third argument to the function, FreeVars, is a list of the variables that are free in the antecedent of the clause.
clausify(FOL, Clause, FreeVars)
Universally quantified logical forms are clausified by stripping the quantifier from the clausified version of the logical form.  For instance, clausify(all(B, book(B) & wrote(bertrand, B)), Clause, FreeVars) leaves Clause = book(B), wrote(bertrand, B) and FreeVars = [B].  This makes sense, since both forms are logically equivalent to "B is a book if and only if bertrand wrote B."
clausify(all(X,F0),F,[X|V]) :- clausify(F0,F,V).
For implications, the consequent C0 is clausifed as the literal C and the antecedent A0 is clausified as A.  Then the Prolog clause C :- A, itself an implication, is formed out of these results.  The list V of free variables is passed along in this process.
clausify(A0=>C0,(C:-A),V) :- clausify_literal(C0,C), clausify_antecedent(A0,A,V).
Literals are left unchanged by clausify, though an empty free variable list is generated.

clausify(C0,C,[]) :- clausify_literal(C0,C).

The function clausify_antecedent(FOL, Clause, FreeVars) leaves literals unchanged (except the literal marker is removed).  For conjunctions, clausify-antecedent clausifies each conjunct separately and then combines them with a comma to form the right-hand side of a Prolog rule.  For existentials, the quantifier is stripped and the free variable is added to the free variable list.

clausify_antecedent(L0,L,[]) :- clausify_literal(L0,L).

clausify_antecedent(E0&F0, (E,F), V) :- clausify_antecedent(E0,E,V0),
clausify_antecedent(exists(X,F0), F, [X|V]) :- clausify_antecedent(F0,F,V).

clausify_literal(`L, L).