Adventure in Prolog

Contents

Preface

Prolog Tools

1- Getting Started

2- Facts

3- Simple Queries

4- Compound Queries

5- Rules

6- Arithmetic

7- Managing Data

8- Recursion

9- Data Structures

10- Unification

11- Lists

12- Operators

13- Cut

14- Control Structures

15- Natural Language

Appendix

Index

Natural Language

Prolog is especially well-suited for developing natural language systems. In this chapter we will create an English front end for Nani Search.

But before moving to Nani Search, we will develop a natural language parser for a simple subset of English. Once that is understood, we will use the same technology for Nani Search.

The simple subset of English will include sentences such as

• The dog ate the bone.
• The big brown mouse chases a lazy cat.

This grammar can be described with the following grammar rules. (The first rule says a sentence is made up of a noun phrase followed by a verb phrase. The last rule says an adjective is either 'big', or 'brown', or 'lazy.' The '|' means 'or.')

sentence :

nounphrase, verbphrase.

nounphrase :

determiner, nounexpression.

nounphrase :

nounexpression.

nounexpression :

noun.

nounexpression :

adjective, nounexpression.

verbphrase :

verb, nounphrase.

determiner :

the | a.

noun :

dog | bone | mouse | cat.

verb :

ate | chases.

adjective :

big | brown | lazy.

To begin with, we will simply determine if a sentence is a legal sentence. In other words, we will write a predicate sentence/1, which will determine if its argument is a sentence.

The sentence will be represented as a list of words. Our two examples are

[the,dog,ate,the,bone]
[the,big,brown,mouse,chases,a,lazy,cat]

There are two basic strategies for solving a parsing problem like this. The first is a generate-and-test strategy, where the list to be parsed is split in different ways, with the splittings tested to see if they are components of a legal sentence. We have already seen that we can use append/3 to generate the splittings of a list. With this approach, the top-level rule would be

sentence(L) :-
  append(NP, VP, L),
  nounphrase(NP),
  verbphrase(VP).

The append/3 predicate will generate possible values for the variables NP and VP, by splitting the original list L. The next two goals test each of the portions of the list to see if they are grammatically correct. If not, backtracking into append/3 causes another possible splitting to be generated.

The clauses for nounphrase/1 and verbphrase/1 are similar to sentence/1, and call further predicates that deal with smaller units of a sentence, until the word definitions are met, such as

verb([ate]).
verb([chases]).

noun([mouse]).
noun([dog]).

Difference Lists

The above strategy, however, is extremely slow because of the constant generation and testing of trial solutions that do not work. Furthermore, the generating and testing is happening at multiple levels.

The more efficient strategy is to skip the generation step and pass the entire list to the lower level predicates, which in turn will take the grammatical portion of the sentence they are looking for from the front of the list and return the remainder of the list.

To do this, we use a structure called a difference list. It is two related lists, in which the first list is the full list and the second list is the remainder. The two lists can be two arguments in a predicate, but they are more readable if represented as a single argument with the minus sign (-) operator, like X-Y.

Here then is the first grammar rule using difference lists. A list S is a sentence if we can extract a nounphrase from the beginning of it, with a remainder list of S1, and if we can extract a verb phrase from S1 with the empty list as the remainder.

sentence(S) :-
  nounphrase(S-S1),
  verbphrase(S1-[]).

Before filling in nounphrase/1 and verbphrase/1, we will jump to the lowest level predicates that define the actual words. They too must be difference lists. They are simple. If the head of the first list is the word, the remainder list is simply the tail.

noun([dog|X]-X).
noun([cat|X]-X).
noun([mouse|X]-X).

verb([ate|X]-X).
verb([chases|X]-X).

adjective([big|X]-X).
adjective([brown|X]-X).
adjective([lazy|X]-X).

determiner([the|X]-X).
determiner([a|X]-X).

Testing shows how the difference lists work.

?- noun([dog,ate,the,bone]-X).
X = [ate,the,bone] 

?- verb([dog,ate,the,bone]-X).
no

Continuing with the new grammar rules we have

nounphrase(NP-X):-
  determiner(NP-S1),
  nounexpression(S1-X).
nounphrase(NP-X):-
  nounexpression(NP-X).

nounexpression(NE-X):-
  noun(NE-X).
nounexpression(NE-X):-
  adjective(NE-S1),
  nounexpression(S1-X).

verbphrase(VP-X):-
  verb(VP-S1),
  nounphrase(S1-X).

NOTE: The recursive call in the definition of nounexpression/1. It allows sentences to have any number of adjectives before a noun.

These rules can now be used to test sentences.

?- sentence([the,lazy,mouse,ate,a,dog]).
yes

?- sentence([the,dog,ate]).
no

?- sentence([a,big,brown,cat,chases,a,lazy,brown,dog]).
yes

?- sentence([the,cat,jumps,the,mouse]).
no

Figure 15.1 contains a trace of the sentence/1 predicate for a simple sentence.

?- sentence([dog,chases,cat]).

1-1 CALL sentence([dog,chases,cat])
    2-1 CALL nounphrase([dog,chases,cat]-_0)
        3-1 CALL determiner([dog,chases,cat]-_0)
        3-1 FAIL determiner([dog,chases,cat]-_0)
    2-1 REDO nounphrase([dog,chases,cat]-_0)
        3-1 CALL nounexpression([dog,chases,cat]- _0)
            4-1 CALL noun([dog,chases,cat]-_0)
            4-1 EXIT noun([dog,chases,cat]-  
            [chases,cat])

        3-1 EXIT nounexpression([dog,chases,cat]-
                        [chases,cat])
    2-1 EXIT nounphrase([dog,chases,cat]-
                    [chases,cat])

    2-2 CALL verbphrase([chases,cat]-[])
        3-1 CALL verb([chases,cat]-_4)
        3-1 EXIT verb([chases,cat]-[cat])

        3-2 CALL nounphrase([cat]-[])
            4-1 CALL determiner([cat]-[])
            4-1 FAIL determiner([cat]-[])
        3-2 REDO nounphrase([cat]-[])
            4-1 CALL nounexpression([cat]-[])
                5-1 CALL noun([cat]-[])
                5-1 EXIT noun([cat]-[])
            4-1 EXIT nounexpression([cat]-[])
        3-2 EXIT nounphrase([cat]-[])
    2-2 EXIT verbphrase([chases,cat]-[])
1-1 EXIT sentence([dog,chases,cat])
      yes

Figure 15.1. Trace of sentence/1

Natural Language Front End

We will now use this sentence-parsing technique to build a simple English language front end for Nani Search.

For the time being we will make two assumptions. The first is that we can get the user's input sentence in list form. The second is that we can represent our commands in list form. For example, we can express goto(office) as [goto, office], and look as [look].

With these assumptions, the task of our natural language front end is to translate a user's natural sentence list into an acceptable command list. For example, we would want to translate [go,to,the,office] into [goto, office].

We will write a high-level predicate, called command/2, that performs this translation. Its format will be

command(OutputList, InputList).

The simplest commands are the ones that are made up of a verb with no object, such as look, list_possessions, and end. We can define this situation as follows.

command([V], InList):- verb(V, InList-[]).

We will define verbs as in the earlier example, only this time we will include an extra argument, which identifies the command for use in building the output list. We can also allow as many different ways of expressing a command as we feel like as in the two ways to say 'look' and the three ways to say 'end.'

verb(look, [look|X]-X).
verb(look, [look,around|X]-X).
verb(list_possessions, [inventory|X]-X).
verb(end, [end|X]-X).
verb(end, [quit|X]-X).
verb(end, [good,bye|X]-X).

We can now test what we've got.

?- command(X,[look]).
X = [look]

?- command(X,[look,around]).
X = [look]

?- command(X,[inventory]).
X = [list_possessions]

?- command(X,[good,bye]).
X = [end]

We now move to the more complicated case of a command composed of a verb and an object. Using the grammatical constructs we saw in the beginning of this chapter, we could easily construct this grammar. However, we would like to have our interface recognize the semantics of the sentence as well as the formal grammar.

For example, we would like to make sure that 'goto' verbs have a place as an object, and that the other verbs have a thing as an object. We can include this knowledge in our natural language routine with another argument.

Here is how the extra argument is used to ensure the object type required by the verb matches the object type of the noun.

command([V,O], InList) :-
  verb(Object_Type, V, InList-S1),
  object(Object_Type, O, S1-[]).

Here is how we specify the new verbs.

verb(place, goto, [go,to|X]-X).
verb(place, goto, [go|X]-X).
verb(place, goto, [move,to|X]-X).

We can even recognize the case where the 'goto' verb was implied, that is if the user just typed in a room name without a preceding verb. In this case the list and its remainder are the same. The existing room/1 predicate is used to check if the list element is a room except when the room name is made up of two words.

The rule states "If we are looking for a verb at the beginning of a list, and the list begins with a room, then assume a 'goto' verb was found and return the full list for processing as the object of the 'goto' verb."

verb(place, goto, [X|Y]-[X|Y]):- room(X).
verb(place, goto, [dining,room|Y]-[dining,room|Y]).

Some of the verbs for things are

verb(thing, take, [take|X]-X).
verb(thing, drop, [drop|X]-X).
verb(thing, drop, [put|X]-X).
verb(thing, turn_on, [turn,on|X]-X).

Optionally, an 'object' may be preceded by a determiner. Here are the two rules for 'object,' which cover both cases.

object(Type, N, S1-S3) :-
  det(S1-S2),
  noun(Type, N, S2-S3).
object(Type, N, S1-S2) :-
  noun(Type, N, S1-S2).

Since we are just going to throw the determiner away, we don't need to carry extra arguments.

det([the|X]- X).
det([a|X]-X).
det([an|X]-X).

We define nouns like verbs, but use their occurrence in the game to define most of them. Only those names that are made up of two or more words require special treatment. Nouns of place are defined in the game as rooms.

noun(place, R, [R|X]-X):- room(R).
noun(place, 'dining room', [dining,room|X]-X).

Things are distinguished by appearing in a 'location' or 'have' predicate. Again, we make exceptions for cases where the thing name has two words.

noun(thing, T, [T|X]-X):- location(T,_).
noun(thing, T, [T|X]-X):- have(T).
noun(thing, 'washing machine', [washing,machine|X]-X).

We can build into the grammar an awareness of the current game situation, and have the parser respond accordingly. For example, we might provide a command that allows the player to turn the room lights on or off. This command might be turn_on(light) as opposed to turn_on(flashlight). If the user types in 'turn on the light' we would like to determine which light was meant.

We can assume the room light was always meant, unless the player has the flashlight. In that case we will assume the flashlight was meant.

noun(thing, flashlight, [light|X], X):- have(flashlight).
noun(thing, light, [light|X], X).

We can now try it out.

?- command(X,[go,to,the,office]).
X = [goto, office]

?- command(X,[go,dining,room]).
X = [goto, 'dining room']

?- command(X,[kitchen]).
X = [goto, kitchen]

?- command(X,[take,the,apple]).
X = [take, apple]

?- command(X,[turn,on,the,light]).
X = [turn_on, light]

?- asserta(have(flashlight)), command(X,[turn,on,the,light]).
X = [turn_on, flashlight]

It should fail in the following situations that don't conform to our grammar or semantics.

?- command(X,[go,to,the,desk]).
no

?- command(X,[go,attic]).
no

?- command(X,[drop,an,office]).
no

Definite Clause Grammar

The use of difference lists for parsing is so common in Prolog, that most Prologs contain additional syntactic sugaring that simplifies the syntax by hiding the difference lists from view. This syntax is called Definite Clause Grammar (DCG), and looks like normal Prolog, only the neck symbol (:-) is replaced with an arrow (-->). The DCG representation is parsed and translated to normal Prolog with difference lists.

Using DCG, the 'sentence' predicate developed earlier would be phrased

sentence --> nounphrase, verbphrase.

This would be translated into normal Prolog, with difference lists, but represented as separate arguments rather than as single arguments separated by a minus (-) as we implemented them. The above example would be translated into the following equivalent Prolog.

sentence(S1, S2):-
  nounphrase(S1, S3),
  verbphrase(S3, S2).

Thus, if we define 'sentence' using DCG we still must call it with two arguments, even though the arguments were not explicitly stated in the DCG representation.

?- sentence([dog,chases,cat], []).

The DCG vocabulary is represented by simple lists.

noun --> [dog].
verb --> [chases].

These are translated into Prolog as difference lists.

noun([dog|X], X).
verb([chases|X], X).

As with the natural language front end for Nani Search, we often want to mix pure Prolog with the grammar and include extra arguments to carry semantic information. The arguments are simply added as normal arguments and the pure Prolog is enclosed in curly brackets ({}) to prevent the DCG parser from translating it. Some of the complex rules in our game grammar would then be

command([V,O]) --> 
  verb(Object_Type, V), 
  object(Object_Type, O).

verb(place, goto) --> [go, to].
verb(thing, take) --> [take].

object(Type, N) --> det, noun(Type, N).
object(Type, N) --> noun(Type, N).

det --> [the].
det --> [a].

noun(place,X) --> [X], {room(X)}.
noun(place,'dining room') --> [dining, room].
noun(thing,X) --> [X], {location(X,_)}.

Because the DCG automatically takes off the first argument, we cannot examine it and send it along as we did in testing for a 'goto' verb when only the room name was given in the command. We can recognize this case with an additional 'command' clause.

command([goto, Place]) --> noun(place, Place).

Reading Sentences

Now for the missing pieces. We must include a predicate that reads a normal sentence from the user and puts it into a list. Figure 15.2 contains a program to perform the task. It is composed of two parts. The first part reads a line of ASCII characters from the user, using the built-in predicate get0/1, which reads a single ASCII character. The line is assumed terminated by an ASCII 13, which is a carriage return. The second part uses DCG to parse the list of characters into a list of words, using another built-in predicate name/2, which converts a list of ASCII characters into an atom.

% read a line of words from the user

read_list(L) :-
  write('> '),
  read_line(CL),
  wordlist(L,CL,[]), !.

read_line(L) :-
  get0(C),
  buildlist(C,L).

buildlist(13,[]) :- !.
buildlist(C,[C|X]) :-
  get0(C2),
  buildlist(C2,X).
 
wordlist([X|Y]) --> word(X), whitespace, wordlist(Y).
wordlist([X]) --> whitespace, wordlist(X).
wordlist([X]) --> word(X).
wordlist([X]) --> word(X), whitespace.

word(W) --> charlist(X), {name(W,X)}.

charlist([X|Y]) --> chr(X), charlist(Y).
charlist([X]) --> chr(X).

chr(X) --> [X],{X>=48}.

whitespace --> whsp, whitespace.
whitespace --> whsp.

whsp --> [X], {X<48}.

Figure 15.2. Program to read input sentences

The other missing piece converts a command in the format [goto,office] to a normal-looking command goto(office). This is done with a standard built-in predicate called 'univ', which is represented by an equal sign and two periods (=..). It translates a predicate and its arguments into a list whose first element is the predicate name and whose remaining elements are the arguments. It works in reverse as well, which is how we will want to use it. For example

?- pred(arg1,arg2) =..  X.
X = [pred, arg1, arg2] 

?- pred =..  X.
X = [pred] 

?- X =..  [pred,arg1,arg1].
X = pred(arg1, arg2) 

?- X =..  [pred].
X = pred 

We can now use these two predicates, along with command/2 to write get_command/1, which reads a sentence from the user and returns a command to command_loop/0.

get_command(C) :-
  read_list(L),
  command(CL,L),
  C =..  CL, !.
get_command(_) :-
  write('I don''t understand'), nl, fail.

We have now gone from writing the simple facts in the early chapters to a full adventure game with a natural language front end. You have also written an expert system, an intelligent genealogical logicbase and a standard business application. Use these as a basis for continued learning by experimentation.

Exercises

Adventure Game

1- Expand the natural language capabilities to handle all of the commands of Nani Search.

2- Expand the natural language front end to allow for compound sentences, such as "go to the kitchen and take the apple," or "take the apple and the broccoli."

3- Expand the natural language to allow for pronouns. To do this the 'noun' predicate must save the last noun and its type. When the word 'it' is encountered pick up that last noun. Then 'take the apple' followed by 'eat it' will work. (You will probably have to go directly to the difference list notation to make sentences such as "turn it on" work.)

Genealogical Logicbase

4- Build a natural language query system that responds to queries such as "Who are dennis' children?" and "How many nephews does jay have?" Assuming you write a predicate get_query/1 that returns a Prolog query, you can call the Prolog query with the call/1 built-in predicate. For example,

main_loop :-
  repeat,
  get_query(X),
  call(X),
  X = end.