Conversion From Scope-Resolved Tree to Prolog
Once we have scope-resolved the MRS into a tree, we have all the information necessary to execute it in some engine. I’ve chosen to use the SWI-Prolog engine for execution since it is well-suited for logic problems and I have some familiarity with it. You could probably do something similiar with any number of different logic engines but I haven’t tried.
The “idealized” process for converting the tree into Prolog is simple. Prolog (in very simplified terms) expects a set of predicate logic-type predicates, separated by commas, and executes them in order from left to right. So, I walk the tree recursively and flatten it. This model can build Prolog that could be executed out of any MRS that comes out of the ERG. However, implementing the Prolog predicates to make it actually run is really the hard work. How I did that is described in a different post.
Here’s an example of the “idealized” process for converting a scope-resolved MRS tree to Prolog:
"Put the diamond on the table"
MRS:
[ TOP: h0
INDEX: e2
RELS: < [ _the_q LBL: h10 ARG0: x8 [ x PERS: 3 NUM: sg IND: + ] RSTR: h11 BODY: h12 ]
[ _diamond_n_1 LBL: h13 ARG0: x8 [ x PERS: 3 NUM: sg IND: + ] ]
[ _the_q LBL: h17 ARG0: x16 [ x PERS: 3 NUM: sg IND: + ] RSTR: h18 BODY: h19 ]
[ _table_n_1 LBL: h20 ARG0: x16 [ x PERS: 3 NUM: sg IND: + ] ]
[ pronoun_q LBL: h4 ARG0: x3 [ x PERS: 2 PT: zero ] RSTR: h5 BODY: h6 ]
[ pron LBL: h7 ARG0: x3 [ x PERS: 2 PT: zero ] ]
[ _put_v_1 LBL: h1 ARG0: e2 [ e SF: comm TENSE: pres MOOD: indicative PROG: - PERF: - ] ARG1: x3 ARG2: x8 ARG3: h9 ]
[ _on_p_loc LBL: h14 ARG0: e15 [ e SF: prop TENSE: untensed MOOD: indicative PROG: - PERF: - ] ARG1: x8 ARG2: x16 ]
>
HCONS: < h0 qeq h1 h5 qeq h7 h9 qeq h14 h11 qeq h13 h18 qeq h20 > ]
Scope-resolved tree:
┌_diamond_n_1__x:x8
_the_q:x8,h11,h12┤
│ ┌_table_n_1:x16
└_the_q:x16,h18,h19┤
│ ┌pron:x3
└pronoun_q:x3,h5,h6┤
└_put_v_1:e2,x3,x8,h9┐
└_on_p_loc:e15,x8,x16
Idealized Conversion: _the_q(x8, _diamond_n_1(x8), _the_q(x16, _table_n_1(x16),
pronoun_q(x3, pron__x(x3), _put_v_1(e2, x3, x8, _on_p_loc(e15, x8, x16)))))
The “idealized” conversion won’t actually run in Prolog but it is surprisingly close. There are some simple issues like the fact that Prolog names can’t start with _ and some more structural problems that need to be addressed based on my experience trying to build the predicates. To make it actually execute I had to :
- Make predicate names be valid Prolog
- Make variable names be valid Prolog
- Pass ERG variable metadata along with variables
- [optional] Pass metadata to indicate which variables were free variables
- Mark each predicate with an index that indicates how deep in the tree it is for good error reporting
- Find a way to allow the same predicate to evaluate the current world (“Is the book on the table?”) or create a future world (“Put the book on the table”)
- [optional] Convert noun and adjective predicates to a uniform form (i.e.
noun(Word, X)oradjective(Word, X) - Figure out how to handle dropped or used
i,u,parguments - Handle a couple of predicates (
FWSeqandOrd) that were just tricky
The rest of this post outlines how I accomplished each of those to get from the “idealized” form to a form that will truly execute (and is lots harder to read…sorry!).
Note that, with the exception of the final bullet, this can all be done mechanically with no special knowledge of what any of the predicates actually do. Thus, it should work for any MRS.
Make Predicate Names Valid Prolog
Prolog doesn’t like names that start with “_” so I just added “d” (for “Delph-in”) on the front. I did this for predicates that didn’t start with underscore too just to keep things consistent:
Old: _the_q(x8, _diamond_n_1(x8), _the_q(x16, _table_n_1(x16), pronoun_q(x3, pron__x(x3),
_put_v_1(e2, x3, x8, _on_p_loc(e15, x8, x16)))))
New: d_the_q(x8, d_diamond_n_1(x8), d_the_q(x16, d_table_n_1(x16), d_pronoun_q(x3, d_pron__x(x3),
d_put_v_1(e2, x3, x8, d_on_p_loc(e15, x8, x16)))))
In addition, the ERG often has predicates that use the same predicate name and argument count but the arguments have different types (i.e. h, e, x, etc). Prolog terms don’t have a notion of “type” so I needed a way to distinguish the predicates. I simply added the ERG argument types onto the end of the predicate after __ like this:
Old: d_the_q(x8, d_diamond_n_1(x8), d_the_q(x16, d_table_n_1(x16),
d_pronoun_q(x3, d_pron__x(x3), d_put_v_1(e2, x3, x8, d_on_p_loc(e15, x8, x16)))))
New: d_the_q__xhh(x8, d_diamond_n_1__x(x8), d_the_q__xhh(x16, d_table_n_1__x(x16),
d_pronoun_q__xhh(x3, d_pron__x(x3), d_put_v_1__exxh(e2, x3, x8, d_on_p_loc__exx(e15, x8, x16)))))
Make Variable Names Valid Prolog
Prolog needs variables to start with a capital letter and I found I needed to sometimes add new arguments to the predicates as well (more on that later). To make sure variables are unique, the conversion process maps them to uppercase with a monotonically increasing number after them:
Old: d_the_q__xhh(x8, d_diamond_n_1__x(x8), d_the_q__xhh(x16, d_table_n_1__x(x16),
d_pronoun_q__xhh(x3, d_pron__x(x3), d_put_v_1__exxh(e2, x3, x8, d_on_p_loc__exx(e15, x8, x16)))))
New: d_the_q__xhh(X9124, d_diamond_n_1__x(X9124), d_the_q__xhh(X9126, d_table_n_1__x(X9126),
d_pronoun_q__xhh(X9128, d_pron__x(X9128), d_put_v_1__exxh(E9129, X9128, X9124,
d_on_p_loc__exx(E9130, X9124, X9126)))))
Add All ERG Metadata to Variables
Prolog replaces variables with their value at runtime and it is not possible to know what the original variable was:
% This will always write the value of X and there
% is no way to know, from inside of writeln,
% that the value came from a variable called "X"
foo(X) :- writeln(X).
This makes reporting decent errors very hard. In addition, some predicates need to do things differently depending on the metadata such as returning different results depending on plurality. So, arguments are passed in the prototype using a special Prolog predicate called arg/2. It holds the variable or value in the first position and metadata such as the original variable name, tense, and plurality in the second position.
Thus the Prolog representation of x8 in _the_q (from the above MRS):
[ _the_q LBL: h10 ARG0: x8 [ x PERS: 3 NUM: sg IND: + ] RSTR: h11 BODY: h12 ]
looks like this:
arg(X9124, var([name(x8), pers(3), num(sg)]))
If the argument is not a variable but is instead a predicate (i.e. a scopal argument), it gets the metadata term indicating as much:
arg(exampleTerm(foo), term)
Unfortunately, this really makes it hard to read but I wasn’t able to find a better solution. So here’s the example Prolog with this pattern added and indentation to make it a little easier to follow:
Old: d_the_q__xhh(
X9124,
d_diamond_n_1__x(X9124),
d_the_q__xhh(
X9126,
d_table_n_1__x(X9126),
d_pronoun_q__xhh(
X9128,
d_pron__x(X9128),
d_put_v_1__exxh(
E9129,
X9128,
X9124,
d_on_p_loc__exx(
E9130,
X9124,
X9126)))))
New: d_the_q__xhh(
arg(X9124, var([name(x8), pers(3), num(sg)])),
arg(d_diamond_n_1__x(arg(X9124, var([name(x8), pers(3), num(sg)]))), term),
arg(d_the_q__xhh(
arg(X9126, var([name(x16), pers(3), num(sg)])),
arg(d_table_n_1__x(arg(X9126, var([name(x16), pers(3), num(sg)]))), term),
arg(d_pronoun_q__xhh(
arg(X9128, var([name(x3), pers(2)])),
arg(d_pron__x(arg(X9128, var([name(x3), pers(2)]))), term),
arg(d_put_v_1__exxh(
arg(E9129, var([name(e2), index(yes), tense(pres)])),
arg(X9128, var([name(x3), pers(2)])),
arg(X9124, var([name(x8), pers(3), num(sg)])),
arg(d_on_p_loc__exx(
arg(E9130, var([name(e15), tense(untensed)])),
arg(X9124, var([name(x8), pers(3), num(sg)])),
arg(X9126, var([name(x16), pers(3), num(sg)]))), term))), term))))).
[optional] Add Extra Metadata to Free Variables
The ERG predicate thing(x) can be much more efficiently encoded if it is implemented as a free variable in Prolog. However, this requires free variables to be marked with extra metadata so they can be stored properly.
To do this I’ve used the metadata type/1 which takes a single argument of value raw (for a a free variable) or reg (for a regular variable):
old: d_thing__x(arg(X9004, var([name(x5)])))
new: d_thing__x(arg(X9004, var([name(x5), type(raw)])))
This wasn’t necessary in theory, but the performance was so bad it really was necessary in practice.
Add Extra Metadata to the Index Variable
The INDEX" variable in MRS is the variable introduced by the predicate acting as the “main point of the phrase”, i.e. the thing being done, which is usually the main verb.
Because predicates that take scopal arguments are responsible for executing them, I’ve found it necessary (e.g. in the implementation of subord__ehh) to be able to find out what verb is the INDEX of the phrase at runtime. To do this, another piece of metadata index(yes) is added to the variable that is introduced by the index of the phrase.
Record the Depth of Each Predicate
I’ve found that the best way to report errors to the user is to report the error from the deepest execution point. I.e. the farthest we got in solving the logic. Since there is no built-in way to do this in Prolog, I had to build the infrastructure myself. That link describes why, but here’s we’ll just do it.
As we walk the tree and build the Prolog, we wrap each one with a helper predicate called erg/2 which records how deep into the predicates we are. At runtime, this is used to report back better errors.
old: d_the_q__xhh(
arg(X9124, var([name(x8), pers(3), num(sg)])),
arg(d_diamond_n_1__x(arg(X9124, var([name(x8), pers(3), num(sg)]))), term),
arg(d_the_q__xhh(
arg(X9126, var([name(x16), pers(3), num(sg)])),
arg(d_table_n_1__x(arg(X9126, var([name(x16), pers(3), num(sg)]))), term),
arg(d_pronoun_q__xhh(
arg(X9128, var([name(x3), pers(2)])),
arg(d_pron__x(arg(X9128, var([name(x3), pers(2)]))), term),
arg(d_put_v_1__exxh(
arg(E9129, var([name(e2), index(yes), tense(pres)])),
arg(X9128, var([name(x3), pers(2)])),
arg(X9124, var([name(x8), pers(3), num(sg)])),
arg(d_on_p_loc__exx(
arg(E9130, var([name(e15), tense(untensed)])),
arg(X9124, var([name(x8), pers(3), num(sg)])),
arg(X9126, var([name(x16), pers(3), num(sg)]))), term))), term))))).
new: erg(1, d_the_q__xhh(
arg(X9124, var([name(x8), pers(3), num(sg)])),
arg(erg(2, d_diamond_n_1__x(arg(X9124, var([name(x8), pers(3), num(sg)])))), term),
arg(erg(3, d_the_q__xhh(
arg(X9126, var([name(x16), pers(3), num(sg)])),
arg(erg(4, d_table_n_1__x(arg(X9126, var([name(x16), pers(3), num(sg)])))), term),
arg(erg(5, d_pronoun_q__xhh(
arg(X9128, var([name(x3), pers(2)])),
arg(erg(6, d_pron__x(arg(X9128, var([name(x3), pers(2)])))), term),
arg(erg(7, d_put_v_1__exxh(
arg(E9129, var([name(e2), index(yes), tense(pres)])),
arg(X9128, var([name(x3), pers(2)])),
arg(X9124, var([name(x8), pers(3), num(sg)])),
arg(erg(8, d_on_p_loc__exx(
arg(E9130, var([name(e15), tense(untensed)])),
arg(X9124, var([name(x8), pers(3), num(sg)])),
arg(X9126, var([name(x16), pers(3), num(sg)])))))), term)))), term)))))).
Add A “Quoting” Argument To Predicates That Introduce An Event Or Have Scopal Arguments
Predicates that introduce an Event and those with scopal arguments need an additional “quoting” argument added to the end that I’ve called QuoteOrEval or sometimes just Quote. Conceptually, this is like the LISP concept of quoting, meaning: don’t evaluate, just represent yourself as data. The reasons for this are complicated and described in a separate post.
[optional] Convert Nouns and Adjectives To Noun(Word, X) or Adjective(Word, X)
Because of the way I’ve encoded the state of the world, I’ve found that converting nouns and adjectives from their original form where every noun or adjective has a different predicate to a a single noun or adjective predicate just made things easier to implement since they are all treated the same:
_diamond_n_1(x8) -> noun('diamond', x8)
_blue_a(e13, x30) -> adjective(e13, x30, 'blue')
This can be done mechanically just be looking at the part of speech part of the name: the _n_ in _diamond_n_1 and _a in _blue_a.
Convert Unused i, u, p Arguments to Atoms Instead of Variables
While most arguments are of type e (event) or x (instance) or h (scopal), sometimes predicates get argument types that are “underspecified” or “halfway in-between” these (as described here) and in a separate post here:
i(for individual) is a generalization over eventualities and instances;p(the half-way mark in the alphabet between h and x) is a generalization over labels and instances;u(for unspecific or maybe unbound) generalizes over all of the above.
Moreover, sometimes these variables are actually used as variables in the predicate (i.e. assigned values) and sometimes they are used as placeholders meaning “this variable is not used” (called a “dropped argument”). If the same predicate can be used in both ways, it needs to be able to tell the difference somehow.
My solution here is to detect if the variable is used elsewhere in the MRS. If it is, it should be a variable, if not, it is treated like a dropped argument. For example:
"what is the book called?"
Logic: which_q__xhh(x5, thing__x(x5), _the_q__xhh(x3, _book_n_of__xi(x3, i13),
_call_v_name__eixx(e2, i14, x5, x3)))
In this example, neither of the second arguments to _call_v_name__eixx and _book_n_of__xi are used anywhere else in the MRS. These are examples of “dropped arguments” or arguments which should be ignored by the predicate implementation. When a i, p or u argument is in a predicate but not used anywhere else like this, the Prolog conversion passes an atom that is the i, p or u like arg(i, term) instead of a variable like arg(I4095, var([name(i14)]):
d_call_v_name__eixx(
arg(E9016, var([name(e2), index(yes), tense(pres)])),
arg(i, term), arg(X9013, var([name(x5), type(raw)])),
arg(X9015, var([name(x3), type(reg), pers(3), num(sg)])),
arg(create, var([type(quote)])))
This allows the predicate to detect the two different cases and behave appropriately. It could have alternatively been handled as additional metadata but, because it was really important to the semantics, I wanted it to be more obvious.
Other Predicate Transformations: FWSeq and Ord
There are cases where the predicates generated by the ERG were in a form that was just not natural for Prolog (at least the way I have structured it) and had to be transformed into something else or added onto. This was surprisingly infrequent, though. In my experiments I only found two examples: FWSeq and Ordinal.
FWSeq
The ERG (mostly) converts phrases in quotes to be a stylized sequence of quoted and fwseq predicates like this:
"yell 'I am free!'"
┌pron__x:x3
pronoun_q__xhh:x3,h5,h6┤
│ ┌_yell_v_1__exx:e2,x3,x8
└proper_q__xhh:x8,h10,h11┤
│ ┌fw_seq__xxi:x9052,x13,i14
│ ├fw_seq__xii:x13,i15,i16
│ ├quoted__ci:I,i15
└and┤
├fw_seq_end_z__xx:x8,x9052
├quoted__ci:free,i14
└quoted__ci:am,i16
I found it necessary to add one more predicate onto the end (the fw_seq_end_z__xx predicate above) in order to do a reversal of the phrase that gets built up simply due to the execution model of Prolog.
Ord
When an ordinal phrase is given like:
"read the first page"
┌pron__x:x3
pronoun_q__xhh:x3,h5,h6┤
│ ┌_read_v_1__exx:e2,x3,x8
└_the_q__xhh:x8,h10,h11┤
├ord__cex:1,e14,x8
└_page_n_1__x:x8
I found it much easier to deal with by transforming the ord__cex predicate into having a scopal argument that described what we are “ordinaling” so it could do a count of it like this:
┌pron__x:x3
pronoun_q__xhh:x3,h5,h6┤
│ ┌_read_v_1__exx:e2,x3,x8
└_the_q__xhh:x8,h10,h11┤
└ord__cexh:1,e14,x8,h9090┐
└_page_n_1__x:x8
Summary
This section outlined the conversion of a scope-resolved MRS tree into a form that could be executed by Prolog. With the exception of the last FWSeq and Ord translation, it can all be done with no knowledge of the semantics of the predicates at all and thus should work with any MRS.