Interpretation of natural language

7.3. Interpretation of natural language

Suppose we want to build a rulebase consisting of rules like ‘every human is mortal’ and ‘Socrates is a human’. A small grammar for rules of this form is given below.

sentence      --> proper_noun,verb_phrase.
sentence      --> determiner,noun,verb_phrase.
verb_phrase   --> [is],property.
property      --> [a],noun.
property      --> [mortal].
determiner    --> [every].
proper_noun   --> [socrates].
noun          --> [human].
/** <examples> ?- phrase(sentence,L). */

If the rulebase consists of Prolog clauses, then we need a way to convert natural language rules to clauses. For instance, ‘every man is human’ must be translated to the clause human(X):-man(X). The clause represents the meaning of the sentence, and assigning clauses to sentences can be seen as interpreting the sentences.

We will build such an interpreter by extending each non-terminal in the above grammar with one or more arguments, which give the meaning of that non-terminal. We start with the simplest case: the meaning of the proper noun ‘Socrates’ is the term socrates:

proper_noun(socrates) --> [socrates].

Proper nouns occur in the second rule for sentences:

sentence --> proper_noun,verb_phrase.

which can be used to construct the sentence ‘Socrates is a human’. The meaning of this sentence is the clause human(socrates):-true, which can be constructed as follows:

sentence((P(X):-true)) --> proper_noun(X),verb_phrase(P).

This rule states: P(X):-true is the meaning of a sentence if it is composed of a proper noun with meaning X followed by a verb phrase with meaning P.

Tip

Notice that the ‘token’ socrates fulfills two roles here: as a word that can be found in a sentence, and as a logical constant to be used in the clause representing the meaning of that sentence.

However, there are several problems with this grammar rule. For one thing, not every Prolog interpreter allows a variable in functor position, as in P(X). This could be solved by constructing the literal P(X) separately by means of a Prolog goal:

sentence((L:-true)) --> proper_noun(X),verb_phrase(P),
                        {L=..[P,X]}.

A more serious problem, however, is that verb phrases are not necessarily interpreted as unary predicates. For instance, transitive verbs are interpreted as binary predicates, and the meaning of the verb phrase ‘likes Achilles’ is the literal likes(X,achilles), where X is the meaning of the proper noun preceding the verb phrase.

In general, a verb phrase defines a mapping from a term X to a literal L:

sentence((L:-true)) --> proper_noun(X),verb_phrase(X=>L).

The declarative reading of this rule is: a sentence is interpreted as L:-true if it starts with a proper noun with meaning X, and it ends with a verb phrase whose meaning is applied to X to yield L. The meaning of the verb phrase is a mapping from terms to literals indicated as X=>L, where ‘=>’ is a user-defined operator. In our case, the mapping is determined by the property in the verb phrase:

verb_phrase(M)               --> [is],property(M).
property(M)                  --> [a],noun(M).
property(X=>mortal(X))       --> [mortal].
noun(X=>human(X))            --> [human].

For instance, the declarative reading of the last rule is: the meaning of the noun ‘human’ is a mapping from X to human(X).

Tip

Representing these mappings by terms X=>L is a choice made in this book, not a generally accepted notation. The key idea is to make the variable X ‘visible’ outside of the literal human(X), which could equally well be achieved by a term like m(X,human(X)) where the functor m is only used for this aim.

Exercise 7.4

Extend the following grammar rules with arguments expressing their interpretation:

verb_phrase     --> transitive_verb,proper_noun.
transitive_verb --> [likes].

It remains to consider the first rule for sentences:

sentence     --> determiner,noun,verb_phrase.

which constructs sentences like ‘every human is mortal’. As explained above, the meaning of the noun in this sentence is the mapping from X to human(X), and the meaning of the verb phrase is the mapping from X to mortal(X). These two mappings are ‘glued together’ by the non-terminal determiner:

sentence(C)   --> determiner(M1,M2,C),
                  noun(M1),verb_phrase(M2).
determiner(X=>B,X=>H,(H:-B))  --> [every].
/** <examples> ?- phrase(sentence(C),S). ?- phrase(noun(M),N). ?- phrase(verb_phrase(M),VP). */

One could say that the meaning of the determiner ‘every’ is a second-order mapping which, given the mappings defined by the noun and verb phrase, determines a clause. Note that the noun determines the body literal, while the verb phrase determines the head; note also that the variables in the two literals are unified in the determiner rule.

With this DCG, the query ?-phrase(sentence(C),S) now produces the following answers:

C = human(socrates):-true
S = [socrates,is,a,human];
C = mortal(socrates):-true
S = [socrates,is,mortal]
C = human(X):-human(X)
S = [every,human,is,a,human];
C = mortal(X):-human(X)
S = [every,human,is,mortal];

Note that this very simple language already allows some form of reasoning: for instance, given the second and third sentence, we could conclude the fourth. We will implement a program which performs this kind of reasoning, taking sentences and questions in natural language, converting them to clausal logic, and converting the answers back to natural language. In order to make the program a bit more interesting, we will extend the grammar with existentially quantified sentences.

Consider the sentence ‘some living beings are mortal’, where ‘some’ is a determiner. The meaning of this sentence is ‘some things are living beings, and they are mortal’, which can be expressed by two clauses:

living_being(sk):-true.
mortal(sk):-true.

where sk is a Skolem constant introducing a new name for the things known to exist (see Section 2.5). The two head literals in these clauses are determined by the noun and the verb phrase, and the only thing we have to do is to substitute the Skolem constant and add the empty body:

determiner(sk=>H1,sk=>H2,[(H1:-true),(H2:-true)]) --> [some].

The complete DCG is given below. Since the determiner ‘some’ requires a plural form of noun and verb phrase, an argument for plurality (s for singular, p for plural) has been added to each non-terminal. Furthermore, since the determiner ‘some’ results in a list of clauses, the other rules for determiner and sentence have been changed accordingly.

:-op(600,xfy,'=>').
sentence(C)                      --> determiner(N,M1,M2,C),
                                     noun(N,M1),
                                     verb_phrase(N,M2).
sentence([(L:-true)])            --> proper_noun(N,X),
                                     verb_phrase(N,X=>L).
verb_phrase(s,M)                 --> [is],property(s,M).
verb_phrase(p,M)                 --> [are],property(p,M).
property(s,M)                    --> [a],noun(s,M).
property(p,M)                    --> noun(p,M).
property(_N,X=>mortal(X))        --> [mortal].
determiner(s,X=>B,X=>H,[(H:-B)]) --> [every].
determiner(p,sk=>H1,sk=>H2,[(H1:-true),(H2:-true)]) --> [some].
proper_noun(s,socrates)          --> [socrates].
noun(s,X=>human(X))              --> [human].
noun(p,X=>human(X))              --> [humans].
noun(s,X=>living_being(X))       --> [living],[being].
noun(p,X=>living_being(X))       --> [living],[beings].
/** <examples> ?- phrase(sentence(C),S). ?- phrase(sentence([(mortal(socrates):-true)]),Answer). */

In addition, we give a small grammar for allowable questions, which are of the form ‘who is mortal?’, ‘is Socrates mortal?’, and ‘are some living beings mortal?’:

question(Q)          --> [who],[is],property(s,_X=>Q).
question(Q)          --> [is],proper_noun(N,X),
                         property(N,X=>Q).
question((Q1,Q2))    --> [are],[some],noun(p,sk=>Q1),
                         property(p,sk=>Q2).
/** <examples> ?- phrase(question(mortal(L)),Question). ?- phrase(question(Query),Question). */

The program below is a shell for interactively building up and querying a small rulebase. User inputs are handled by the predicate handle_input/2; possible inputs are ‘stop’, ‘show’, a new rule, or a question. For the latter to be answered, we use a simple depth-first meta-interpreter, which possibly instantiates variables in the query. For instance, the question ‘who is mortal’ is interpreted as the goal mortal(X), which is instantiated by the meta-interpreter to mortal(socrates).

Interestingly, for transforming this answer back to natural language we do not need a separate grammar for answers: we can use the existing grammar for sentences! For instance, we can generate the answer ‘Socrates is mortal’ by means of the query

?-phrase(sentence([(mortal(socrates):-true)]),Answer).
Answer = [socrates,is,mortal]

Therefore, the only thing we have to do after the meta-interpreter has found an answer is to transform the instantiated query (a conjunction of literals) to a list of clauses with empty body (see predicate transform/2). Again, we encounter the declarative power of DCG’s, which can at the same time be used for interpreting natural language sentences, and for constructing sentences that express a certain logical meaning.

% natural language shell
nl_shell(Rulebase):-
    get_input(Input),
    handle_input(Input,Rulebase).

% handle input from user
handle_input(stop,_Rulebase):-!.
handle_input(show,Rulebase):-!,
    show_rules(Rulebase),
    nl_shell(Rulebase).
handle_input(Sentence,Rulebase):-
    phrase(sentence(Rule),Sentence),!,  % new rule
    nl_shell([Rule|Rulebase]).
handle_input(Question,Rulebase):-
    phrase(question(Query),Question),  % question
    prove_rb(Query,Rulebase),!,        % it can be solved
    transform(Query,Clauses),          % transform to
    phrase(sentence(Clauses),Answer),  % answer
    show_answer(Answer),
    nl_shell(Rulebase).
handle_input(_Question,Rulebase):-  % illegal sentence or
    show_answer('No'),              % no answer found
    nl_shell(Rulebase).

% show current rulebase
show_rules([]).
show_rules([Rule|Rules]):-
    phrase(sentence(Rule),Sentence),
    show_answer(Sentence),
    show_rules(Rules).

% meta-interpreter
prove_rb(true,_Rulebase):-!.
prove_rb((A,B),Rulebase):-!,
    prove_rb(A,Rulebase),
    prove_rb(B,Rulebase).
prove_rb(A,Rulebase):-
    find_clause((A:-B),Rulebase),
    prove_rb(B,Rulebase).

% find applicable clause in rulebase
find_clause(Clause,[Rule|_Rules]):-
    copy_element(Clause,Rule).  % don't instantiate Rule
find_clause(Clause,[_Rule|Rules]):-
    find_clause(Clause,Rules).

%%% copy_element/2: see Section 10.2 (appendix) 

% transform query to answer
transform((A,B),[(A:-true)|Rest]):-!,
    transform(B,Rest).
transform(A,[(A:-true)]).

% get input from user
get_input(Input):-
    write('? '),read(Input).

% show answer to user
show_answer(Answer):-
    write('! '),write(Answer),nl.
/** <examples> ?- nl_shell([]). */

A conversation with this program might proceed as follows (following ? is user input, following ! is program output):

? [every,human,is,mortal].
? [socrates,is,a,human].
? [who,is,mortal].
! [socrates,is,mortal]
? [some,living,beings,are,humans].
? show.
! [some,living,beings,are,humans]
! [socrates,is,a,human]
! [every,human,is,mortal]
? [are,some,living,beings,mortal].
! [some,living,beings,are,mortal]
? stop.

Exercise 7.5

The predicates for user-interaction nl_shell/1 and handle_input/2 are mutually recursive. This might cause memory problems in longer sessions. Rewrite the interactive loop into a so-called failure-driven loop:

shell:-repeat,get_input(X),handle_input(X).
handle_input(stop):-!.
handle_input(X):- /* do something */,fail.

handle_input/1 is now a predicate which always fails, unless the loop should be terminated. Upon its failure, the first clause will backtrack to repeat, which is a built-in predicate which succeeds an indefinite number of times. Thus, get_input/1 will again be called.
(NB. Since it is impossible to pass arguments on to the next iteration, the changes to the rulebase have to be made through side-effects, i.e. by means of assert/1 and retract/1.)