Implementing ERG Verb Predicates in Prolog

Next:

Previous:

Sometimes verbs are queries about the state of the world and sometimes they are commands to change it. Let’s take the verb “shine”:

  1. Command: “Shine the light” means the engine should actually put the output of the light somewhere, potentially changing the state of the world to be lit. State has to change.
  2. Query: “Is the light shining?” or proposition (which is just a query too): “the light is shining” both which mean query the state of the world to see if this is true.

You could try to write a Prolog predicate that does both but the code to query and assert facts in Prolog is very different. Most likely you’d pass a flag which controls a big if statement, effectively switching between two predicates. Not to mention the fact that doing something in the real world involves a plan and is not always straightforward. “get the book” can involve many implied stages that need to be worked out. For all of these reasons, in Perplexity, I decided to write different predicates for the verb: a “query predicate” and a “task predicate”.

To do its job, a query predicate may have to try various interpretations of a verb. For example “is” could mean up to 4 different queries in the current Perplexity. Each of these meanings is a different query that queries state in the “real world”, the world that exists now, which I call the “default world”. Thus, there will be one or more “default world predicates” for a verb that runs as a query like “is the light shining?”.

Similarly, to do its job, a task predicate may need to try several different “methods” (or “approaches”) to changing state. It needs a planner and I used a “Hierarchical Task Network” planner in Perplexity. Moving a book may involve moving something from on top of it first, for example. Thus, there will be one or more “HTN Methods” for a verb that runs as a command like “shine the light”.

Finally, it turns that sometimes other predicates add or modify existing verb data to get the verb “Event” to work right. Prepositions provide data about relationships, some predicates provide an Actor, etc. All of this event data needs to be collected together along with the data that is passed directly to the verb as arguments and put into a unified form on the event. And: all of this works exactly the same for both query predicates and task predicates. So it made sense to break out this logic into yet another predicate that can be used by both: the “event predicate”.

So, it turned out that handing verbs is complex (who knew?) and implementing a verb in Prolog has these parts (depending on the verb):

The ACE Parser provides information about whether a phrase is a command, a proposition, or a query to make detecting the query vs. command cases easy. So, the first step in executing a phrase in the engine is to add the correct form (query or command) of the Prolog verb predicate to the Prolog, then it can be executed.

…but before it can be executed, it needs to be implemented. How this is done is the purpose of this section.

Let’s go through “there is a rock” as an example:

Type: proposition
[ TOP: h0
INDEX: e2
RELS: < 
[ _a_q__xhh LBL: h5 ARG0: x4 [ x PERS: 3 NUM: sg IND: + ] RSTR: h6 BODY: h7 ]
[ _rock_n_1__x LBL: h8 ARG0: x4 [ x PERS: 3 NUM: sg IND: + ] ]
[ _be_v_there__ex LBL: h1 ARG0: e2 [ e SF: prop TENSE: pres MOOD: indicative PROG: - PERF: - ] ARG1: x4 ]
>
HCONS: < h0 qeq h1 h6 qeq h8 > ]

                   ┌_rock_n_1__x:x4
 _a_q__xhh:x4,h6,h7┤
                   └_be_v_there__ex:e2,x4

Logic: _a_q__xhh(x4, _rock_n_1__x(x4), _be_v_there__ex(e2, x4))

Prolog: 
d_a_q__xhh(
    arg(X56728, var([name(x4), type(reg), pers(3), num(sg)])), 
    arg(d_noun__x(arg('rock', word('rock')), arg(X56728, var([name(x4), type(reg), pers(3), num(sg)]))), term), 
    arg(conj(d_be_v_there__ex(arg(E56729, var([name(e2), index(yes), tense(pres)])), arg(X56728, var([name(x4), type(reg), pers(3), num(sg)])), arg(create, var([type(quote)]))), 
        conj(query_be_v_there__ex(arg(E56729, var([name(e2), index(yes), tense(pres)]))))), term), 
    arg(Quote56730, var([type(quote)]))).

The rest of these sections will walk through how the verb parts of the Prolog code at the bottom are implemented and what purpose they serve.

The d_be_v_there__ex(Event, What, Quote) Event Predicate

This is the form of predicate you’ve seen so far when converting MRS to Prolog. It has to pay attention to quoting since it has an event. Because verbs have other predicates that do the real work of querying or changing state, the d_verb event predicate only packs the verb information onto the event or unpacks all the verb data from the Event. Because that’s all it does, I’ve called this form the “event predicate”.

Here’s the implementation of the event predicate for d_be_v_there__ex as in “there is a rock”. The funny arg(_,_) terms are described in the section on writing MRS predicates:

% d_ "event predicate"
% Responsible for quoting/unquoting arguments and attaching/retrieving them from the EventID
% - When Quote == create, it packs all arguments up and attaches them as data to the EventID
% - When Quote == eval, it unpacks the data from the event and puts it back into the arguments
d_be_v_there__ex(EventIDArg, WhatIDArg, QuoteArg) :- 
    arg(_, _) = EventIDArg, 
    arg(_, _) = WhatIDArg, 
    arg(_, _) = QuoteArg,  
  % eventPredicateArg() is true if we are not being asked to run in the "default" world
  % that's the definition of an "event predicate"
  eventPredicateArg(EventIDArg, QuoteArg),
  
  % The following three predicates are helpers which take the QuoteArg as their last argument
  % They are designed to make building event predicates easy and do the packing and unpacking
  
  % First (create) create the actual event id or (eval) do nothing  
  relArgCreate(EventIDArg, EventIDArg, instanceOf, arg(idEvent, term), QuoteArg),  
  % Then (create) attach the verb to the event or (eval) check to make sure it matches 
  actionForEvent(EventIDArg, arg(task_be_v_there__ex, term), QuoteArg),  
  % Then (create) attach the target of the verb to the event or (eval) retrieve it
  targetForEvent(EventIDArg, WhatIDArg, QuoteArg).

Again, this predicate just attaches/retrieves all the data about the verb from the Event, the query_ or task_ predicates actually do the event, those are described below.

The query_be_v_there__ex(Event) Query Predicate

OK, so we have a predicate that quotes and unquotes the verb information (the “event predicate”). If the verb is used in a way that is querying the world, it also needs a “query predicate” of the form query_verb(Event).

It is added during the final stage before execution right after the event predicate using the conj() predicate. conj just means “conjunction” and does an “and” operation, which just means it executes it the way Prolog normally would:

"there is a rock."

Prolog:
d_a_q__xhh(
    arg(X56728, var([name(x4), type(reg), pers(3), num(sg)])), 
    arg(d_noun__x(arg('rock', word('rock')), arg(X56728, var([name(x4), type(reg), pers(3), num(sg)]))), term), 
    arg(conj(d_be_v_there__ex(
                arg(E56729, var([name(e2), index(yes), tense(pres)])), 
                arg(X56728, var([name(x4), type(reg), pers(3), num(sg)])), 
                arg(create, var([type(quote)]))), 
        
        % <---- This line was added --->        
        conj(query_be_v_there__ex(arg(E56729, var([name(e2), index(yes), tense(pres)]))))), term), 
        % ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^        
    
    arg(Quote56730, var([type(quote)]))).

The query predicate always begins with query_ and takes a single argument that is the Event variable introduced by the verb. This works because the event predicate form (d_be_v_there__ex) quotes all the data about the verb and attaches it to the event. The query_ predicate just has to retrieve the information that the verb (and any other predicates) added to the event and…do whatever it does.

Here’s the implementation of the query_be_v_there__ex query predicate. It starts by checking the verb structure to make sure everything is OK and then unquotes the data from the event using the event predicate (described above). It “does whatever it does” by using yet another predicate: the “default world predicate” which has the same signature as the event predicate above: d_be_v_there__ex. However, it is called using the event default and using quote == eval. The default world predicate is described next.

% query_ "query predicate"
% Responsible for unpacking the Event using the event predicate and running the semantics using the 
% default world predicate
query_be_v_there__ex(EventIDArg) :- 
    arg(_, _) = EventIDArg,  
  % make sure the Event has a target and check the optional stative preposition if it exists
  verbStructure(EventIDArg, [tree(req, idTarget, []), tree(opt, idStativeEvent, [])]),  
  % if everything checks out, unpack the arguments using the event predicate
  d_be_v_there__ex(EventIDArg, WhatIDArg, arg(eval, term)), arg(WhatID, _) = WhatIDArg,  
  % and run the semantics of the event using the default world predicate(s) - described next
  d_be_v_there__ex(arg(default, term), WhatIDArg, arg(eval, term)).

The d_be_v_there__ex(Event, What, Quote) Default World Predicate(s)

The default world predicates are called by the query predicate and are responsible for actually doing the query for the verb. They have the same name and signature as the event predicate above.

There are often several default world predicates for a verb since a verb can have multiple semantic interpretations. For example, d_be_v_id__exx has 4 alternative interpretations in Perplexity:

Each is a different implementation of the default world predicate for d_be_v_id__exx that Prolog will try. The event and query predicates always look the same, however, so there is just one of each of them.

Because it executes the verb in the “default” (i.e. normal) world, it only executes if EventID the term default (or a variable) and Quote == eval. d_be_v_there__ex only has one interpretation so it only has one default world predicate. To see if something is “there” (as in “There is a rock”) it just checks if What exists at all using isInstance:

% d_ "default world predicate"
% Responsible for implementing the actual semantics of the verb when run in the "default world"
d_be_v_there__ex(EventIDArg, WhatIDArg, QuoteArg) :- 
    % Note that the eventID is "default" for the default world and quote is "eval"
    arg(default, _) = EventIDArg, 
    arg(WhatID, _) = WhatIDArg, 
    arg(eval, _) = QuoteArg,  
  % This checks to see if WhatID is "there" meaning "exists in the world"
  isInstance(WhatID).

The task_be_v_there__ex(Event) Task Predicate

If the verb is used in a way that needs to modify the world (e.g. “shine the light”) it needs a predicate that does work which is very different from a query. This is done by the “task predicate”. Task and query predicates have the same signature: just a single Event argument, but they do very different things. This predicate is added during the final stage before execution right after the event predicate, just like the query predicate.

The job of the task predicate is to take the same Event information that the query predicate used but, instead of seeing if it is true in the world, it has to make the world be that way. So the Event information will be a description of how the world should end up when done, or what the speaker wants to get done. Coming up with a plan to solve a problem is the job of a “planner” algorithm, and Perplexity uses the well researched “Hierarchical Task Network” (HTN) planning approach to do its work.

HTNs mesh well with the way Prolog works and so the approach was easy to implement in Prolog. It is also a very efficient approach to planning that avoids many problems of other planning approaches. There are lots of research papers on the approach, but less on how to implement it in practice. So, I wrote a series of blog posts that describe how it works and how I used it in a production game called Exospecies. I won’t go into the theory here because it is covered in those posts.

To build the task predicate, you need to build an HTN Method (described in the links above) which is just a predicate that checks some conditions in the if part, and, if true, runs the methods in the do part. Even though our example verb doesn’t run as a command, I’ve written what it might look like if it did:

% task_ "task predicate"
% For completeness I show here what a task predicate *might* look like if
% "there is a rock" was used as a command (which it isn't) to create a thing in the world
% This predicate is responsible for changing the state of the world to be whatever the event describes
task_be_v_there__ex(EventIDArg) :- arg(_, _) = EventIDArg,  htnMethod([], Context,  
  % If all this is true...
  if([
      % make sure the Event has a target and check the optional stative preposition if it exists
      verbStructure(EventIDArg, [tree(req, idTarget, []), tree(opt, idStativeEvent, [])]),  
      % if everything checks out, unquote the arguments
      d_be_v_there__ex(EventIDArg, WhatIDArg, arg(eval, term)), arg(WhatID, _) = WhatIDArg
  ]),  
  % Do the work of changing the state by calling another task
  do([createThing(WhatID), storeArgMethod(EventIDArg, WhatIDArg)]) ).

The if part looks a lot like the query predicate, except that instead of querying the state of the world using the default world predicate, it uses the HTN planning infrastructure to come up with a plan to change the world using one or more HTN Methods. Those are described next.

And, just like the query predicate, the last thing it does is run the storeArgMethod HTN method which is a detail described at the very end and not important for overall understanding.

The task_be_v_there__ex HTN Methods

Just like the query predicate might have multiple default world predicates representing different interpretations, the task predicate might have different HTN Methods to change the world depending on the current state of the world.

If a user asks to “put the book on the floor” the task predicate for put may be able to just get the book and use an HTN method to move it to the floor. If there is something on top of it, there may be a different HTN Method that knows how to move things around first and then use that method to finally move the book. Doing that planning work is what the HTN Planner system does well and the detail is described in a separate series of blog posts here.

Since the point of the Perplexity prototype was to investigate natural language and not planning, not a lot of work has been done building interesting HTN Methods so far. But here are three methods that illustrate how the read verb does the work of reading an “Object” to give a sense of how it works. The tryError predicate used in the implementation is described in detail elsewhere:

% if Object is a book that contains pages, read each of them in order  
readObject(Actor, Object, Context) :- htnMethod([allOf], Context,  
  if([  
      tryError(inReach(Object), location(readObject, notWithinReach, Object)),  
      tryError(instanceOf(Object, idBook), location(read, noText, Object)),  
      containedIn(Page, Object, 1),  
      instanceOf(Page, idPage)  
  ]),  
  do([readObject(Actor, Page)]) ).  
  
% if Object *is* text, just read it  
readObject(_, Object, Context) :- htnMethod([], Context,  
  if([  
      tryError(inReach(Object), location(readObject, notWithinReach, Object)),  
      instanceOf(Object, idText),  
      tryError(getText(Object, _, Text), location(read, noText, Object))  
  ]),  
  do([opMessage(readTextOnly, Text)]) ).  
  
% if Object is or has text that is a part of it, just read it  
readObject(_, Object, Context) :- htnMethod([], Context,  
  if([  
      tryError(inReach(Object), location(readObject, notWithinReach, Object)),  
      tryError(getText(Object, _, Text), location(read, noText, Object))  
  ]),  
  do([opMessage(read, Object, Text)]) ).

It looks a lot like the way you would write Prolog predicates that are variations of each other. The HTN methods get more interesting with more interesting problems like moving a book out from under something, which I haven’t really tackled yet in the prototype.

Free Variables

For performance reasons, sometimes free variables are passed as arguments to predicates (the reason for this is described in a separate post). But, there is a subtlety when dealing with free variables in task_ predicates. Look at the (incorrect) implementation of drop below:

task_drop_v_cause__exx(EventIDArg, Context) :- arg(_, _) = EventIDArg, htnMethod([], Context,  
  if([  
      % Make sure we have a preposition  
	  verbStructure(EventIDArg, [tree(req, idActor, []), tree(req, idTarget, []), 
		  tree(req, idDirectionalEvent, []), tree(opt, idStativeEvent, [])]),  
	  d_drop_v_cause__exx(EventIDArg, _, WhatIDArg, arg(eval, term)), arg(WhatID, _) = WhatIDArg,  
	  directionalPrepositionFace(EventIDArg, arg(Object2Face, term)),  
  ]),  
  do([move(WhatID, Object2Face)]) ).

WhatID will be passed as a free variable if the user says to “drop everything” and the move method that gets called will properly try to bind that free variable to every thing in the world. This would be a fine behavior except that we ask the HTN engine only to return the first (best) plan when it executes so it actually will only drop the first thing it can drop. Not what the user wanted.

The fix is to make sure the top level predicate is an allOf predicate (meaning, include all bindings of free variables in a single solution) and to do the bindings of the free variable in the top level drop predicate:

% Note the addition of "allOf" in the definition of the htnMethod
task_drop_v_cause__exx(EventIDArg, Context) :- arg(_, _) = EventIDArg, htnMethod([allOf], Context,  
  if([  
      % Make sure we have a preposition  
      verbStructure(EventIDArg, [tree(req, idActor, []), tree(req, idTarget, []), 
	      tree(req, idDirectionalEvent, []), tree(opt, idStativeEvent, [])]),  
	  d_drop_v_cause__exx(EventIDArg, _, WhatIDArg, arg(eval, term)), arg(WhatID, _) = WhatIDArg,  
	  directionalPrepositionFace(EventIDArg, arg(Object2Face, term)),  

	  % now bind the (potentially) free variable to anything it can be
	  defaultActor(ActorID),  
	  tryError(holding(ActorID, _, WhatID), location(d_drop_v_cause__exx, notHolding, WhatID)),  
	  % Ignore things that are part of a whole  
	  wholeFromPart(WhatID, WholeID)  
  ]),  
  do([move(WholeID, Object2Face)]) ).

There is another fix which I’ve used in verbs where “everything” doesn’t make much sense, as in ‘yell everything’ (meaning to yell every possible thing): just fail if a variable is free. Here’s an alternate version of drop that requires the user to say what to drop by failing with a beMoreSpecific error if a free variable gets through:

% No "allOf" in this definition of the htnMethod
task_drop_v_cause__exx(EventIDArg, Context) :- arg(_, _) = EventIDArg, htnMethod([], Context,  
  if([  
      % Make sure we have a preposition  
      verbStructure(EventIDArg, [tree(req, idActor, []), tree(req, idTarget, []), 
	      tree(req, idDirectionalEvent, []), tree(opt, idStativeEvent, [])]),  
	  d_drop_v_cause__exx(EventIDArg, _, WhatIDArg, arg(eval, term)), arg(WhatID, _) = WhatIDArg,  
	  directionalPrepositionFace(EventIDArg, arg(Object2Face, term)),  

    % Handle free variables by failing if you get one
    tryError(not(var(WhatID)),
        context(task_drop_v_cause__exx, beMoreSpecific)),

	  defaultActor(ActorID),  
	  tryError(holding(ActorID, _, WhatID), location(d_drop_v_cause__exx, notHolding, WhatID)),  
	  % Ignore things that are part of a whole  
	  wholeFromPart(WhatID, WholeID)  
  ]),  
  do([move(WholeID, Object2Face)]) ).

Putting it all together: the event, default world, query, task and HTN Method predicates

There’s a lot to implementing a verb, so I thought I’d bring it all together in one place. Here is the MRS, solved tree and Prolog for “there is a rock”:

Type: proposition
[ TOP: h0
INDEX: e2
RELS: < 
[ _a_q__xhh LBL: h5 ARG0: x4 [ x PERS: 3 NUM: sg IND: + ] RSTR: h6 BODY: h7 ]
[ _rock_n_1__x LBL: h8 ARG0: x4 [ x PERS: 3 NUM: sg IND: + ] ]
[ _be_v_there__ex LBL: h1 ARG0: e2 [ e SF: prop TENSE: pres MOOD: indicative PROG: - PERF: - ] ARG1: x4 ]
>
HCONS: < h0 qeq h1 h6 qeq h8 > ]

                   ┌_rock_n_1__x:x4
 _a_q__xhh:x4,h6,h7┤
                   └_be_v_there__ex:e2,x4

Logic: _a_q__xhh(x4, _rock_n_1__x(x4), _be_v_there__ex(e2, x4))

Prolog: 
d_a_q__xhh(
    arg(X56728, var([name(x4), type(reg), pers(3), num(sg)])), 
    arg(d_noun__x(arg('rock', word('rock')), arg(X56728, var([name(x4), type(reg), pers(3), num(sg)]))), term), 
    arg(conj(d_be_v_there__ex(arg(E56729, var([name(e2), index(yes), tense(pres)])), arg(X56728, var([name(x4), type(reg), pers(3), num(sg)])), arg(create, var([type(quote)]))), 
        conj(query_be_v_there__ex(arg(E56729, var([name(e2), index(yes), tense(pres)]))))), term), 
    arg(Quote56730, var([type(quote)]))).

and here is the implementation:

% d_ "event predicate"
% Responsible for quoting/unquoting arguments and attaching/retrieving them from the EventID
% - When Quote == create, it packs all arguments up and attaches them as data to the EventID
% - When Quote == eval, it unpacks the data from the event and puts it back into the arguments
d_be_v_there__ex(EventIDArg, WhatIDArg, QuoteArg) :- 
    arg(_, _) = EventIDArg, arg(_, _) = WhatIDArg, arg(_, _) = QuoteArg,  
  % eventPredicateArg() is true if we are not being asked to run in the "default" world
  % that's the definition of an "event predicate"
  eventPredicateArg(EventIDArg, QuoteArg),
  
  % The following three predicates are helpers which take the QuoteArg as their last argument
  % They are designed to make building event predicates easy and do the packing and unpacking
  
  % First (create) create the actual event id or (eval) do nothing  
  relArgCreate(EventIDArg, EventIDArg, instanceOf, arg(idEvent, term), QuoteArg),  
  % Then (create) attach the verb to the event or (eval) check to make sure it matches 
  actionForEvent(EventIDArg, arg(task_be_v_there__ex, term), QuoteArg),  
  % Then (create) attach the target of the verb to the event or (eval) retrieve it
  targetForEvent(EventIDArg, WhatIDArg, QuoteArg).  


% query_ "query predicate"
% Responsible for unpacking the Event using the event predicate and running the semantics using the 
% default world predicate
query_be_v_there__ex(EventIDArg) :- 
  arg(_, _) = EventIDArg,  
  % make sure the Event has a target and check the optional stative preposition if it exists
  verbStructure(EventIDArg, [tree(req, idTarget, []), tree(opt, idStativeEvent, [])]),  
  % if everything checks out, unpack the arguments using the event predicate
  d_be_v_there__ex(EventIDArg, WhatIDArg, arg(eval, term)), arg(WhatID, _) = WhatIDArg,  
  % and run the semantics of the event using the default world predicate(s) - described next
  d_be_v_there__ex(arg(default, term), WhatIDArg, arg(eval, term)).


% d_ "default world predicate"
% Responsible for implementing the actual semantics of the verb when run in the "default world"
d_be_v_there__ex(EventIDArg, WhatIDArg, QuoteArg) :- 
  % Note that the eventID is "default" for the default world and quote is "eval"
  arg(default, _) = EventIDArg, arg(WhatID, _) = WhatIDArg, arg(eval, _) = QuoteArg,  
  % This checks to see if WhatID is "there" meaning "exists in the world"
  isInstance(WhatID).


% task_ "task predicate"
% For completeness I show here what a task predicate *might* look like if
% "there is a rock" was used as a command (which it isn't) to create a thing in the world
% Responsible for changing the state of the world to be whatever the event describes
task_be_v_there__ex(EventIDArg) :- arg(_, _) = EventIDArg,  htnMethod([], Context,  
  % If all this is true...
  if([
    % make sure the Event has a target and check the optional stative preposition if it exists
    verbStructure(EventIDArg, [tree(req, idTarget, []), tree(opt, idStativeEvent, [])]),  
    % if everything checks out, unpack the arguments
    d_be_v_there__ex(EventIDArg, WhatIDArg, arg(eval, term)), arg(WhatID, _) = WhatIDArg
  ]),  
  % Do the work of changing the state by calling another task
  do([createThing(WhatID)]) ).

Next:

Previous:

Leave a comment or question