Position of Verbs in MRS solution trees

I am trying to figure out the right way to correctly process verbs in a logic engine. I’m trying to see if it just so happens that the way the ERG builds these trees makes things easier for me.

It will be way easier for me to process verbs if there is a way to walk a properly solved MRS scope tree, processing nodes as I go, such that, by the time I get to the verb, all of the variables it takes as arguments have been given their final values by the predicates and quantifiers I have already visited. Said another way: I’d love it if the variables a verb sees are never changed elsewhere in the tree after it is executed.

Right now I walk the tree by starting at the top predication and processing it:

  • if it is not a quantifier (like _cave_n_1) it just does “the right thing” to the set of things in the variables that are its arguments
  • If it is a quantifier, it:
    • follows the tree exhaustively through the RSTR subtree first (executing as it goes)
    • and then the body subtree
    • and then potentially does some quantification on whatever happened

So if I generate a tree for “go to a cave slowly”, I’d get a tree like this:

       │               ┌_cave_n_1:x9
                       │                  ┌pron:x3
                                          │   ┌_to_p_dir:e8,e2,x9

And I’d execute it in this order:

  1. _cave_n_1
  2. pronoun_q
  3. pron
  4. and
  5. _to_p_dir
  6. _slow_a_1
  7. _go_v_1
  8. _a_q (potential final qualification steps)

Which would work great, if I can always assume that the verb is always in a position where all its arguments have been evaluated like that example.

So, I think I’m asking if is it true that, in MRS solution trees:

  • verbs are always a “leaf” of a scope tree (i.e. they never have “scopal arguments”, aka they can’t have children)
  • verbs can never be in a subtree of a quantifier’s RSTR argument. Or, if they are, none of their variables are referenced in the BODY subtree

I hope this makes sense. I don’t understand enough yet about the grammar to know what forms I can expect where in the tree…

I think this question basically comes down to: are all instance variables bound by a quantifier? For a resolved scope tree, yes.

It’s not just verbs that behave as you’ve described, but also adjectives, prepositions, and anything with an event variable as its intrinsic variable.

However, be aware that some predicates take handles as arguments (e.g. _probable_a_1) and some take both variables and handles as arguments (e.g. _believe_v_1). (Try a sentence like “I believe it probably rained” in the ERG.)

Also, I know that you’re using terminology that reflects what you’re doing algorithmically, but this is not a normal way to talk about logical variables. A logical variable is a placeholder for an individual in a model. It cannot be “changed” because it’s just a placeholder. Mostly, you’re talking about sets of individuals, not logical variables. A logical variable is not the same as a programming variable.


As Guy said: no. There are a lot of scopal verbs (modals, verbs of communication, verbs of cognitive state like surprise or believe) and a limited number of scopal adjectives (easy) and adverbs (probably).

Again, no. Verbs will appear in the RSTR whenever a relative clause is present, and often will share arguments with content in the BODY.

For an example that demonstrates both situations, try parsing Zebras that run are trying to survive. You should get something like:

udef_q (x, RSTR: zebra_n(x) & run_v(e1,x), BODY: try_v(e2, x, survive_v(e3, x)) )


Sorry @sweaglesw, I realized I could have figured out if verbs have scopal arguments by looking in erg.smi. As you said, I found lots of examples there.

Both of your answers and examples helped me clarify what I’m really getting at. I think I have it now: I was asking the wrong questions above.

First, a couple of definitions of how I’m using terms below in response to @guyemerson:

  • “logical variables” are any of the non-scopal variables used in the ERG (e.g. x and e) and are treated like logic variables that contain a set of individuals
  • “process” means “modify the set of individuals currently in a logic variable in an appropriate way” where “appropriate way” depends on the meaning of the predicate or quantifier

I think the question I should have asked is this:

Is there a way to walk a resolved scope tree such that, by the time you reach any node, the set of individuals in its non-scopal arguments are set up correctly for that node to be able to process them to produce the meaning that was intended?

I think the answer is “Yes, in fact, that’s the whole point of scoping!”

Here’s my modified algorithm for walking the tree that I think does what I’m asking:

  • First, when I visit any node, I process that node using any non-scopal arguments (e.g. x and e) as input before following the tree down scopal arguments
    • This is because (I believe) the whole point of a predicate “outscoping” another predicate is to declare that the predicate in the higher scope needs to process the set of individuals in its logical variables before evaluating the predicate in the lower scope in order to get the logical meaning of the statement right.
  • Next, I’m also going to assume (just because it seems like the right way of doing things) that within a predicate or quantifier, scopal arguments get traversed in the order they appear as arguments. Thus, if ARG1 and ARG2 are both scopal, then the ARG1 subtree is processed before the ARG2 subtree, etc. This also implies that RSTR args are always processed before BODY arguments which seems right.
  • Finally, I think that any parts of the tree that share the same Label (i.e. predicates in conjunction) need to be evaluated such that those that have an intrinsic variable that is used elsewhere in the conjunction always come before the predicate that uses it.

Using this approach I can correct my previous questions:

  • I don’t actually care if a verb is a “leaf” node, I just care if, by the time I want to evaluate the verb node, its non-scopal arguments contain the correct set of individuals to reflect the meaning of the utterance
  • The same is true for verbs in a subtree of a RSTR argument

Looking at the two trees you guys provided as examples, “Zebras that run are trying to survive” works using that approach:

       │               ┌_try_v_1:e2,x3,h9┐
       │               │                 └_survive_v_1:e11,x3,i12
                       │   ┌_zebra_n_1:x3

Logic: udef_q(x3, and(_zebra_n_1(x3), _run_v_1(e8, x3)), _try_v_1(e2, x3, _survive_v_1(e11, x3, i12)))

But "I believe it probably rained" still confuses me since, even though "_probable_a_1(i10, _rain_v_1(e13))" is a scopal argument of "_believe_v_1", it shares no variables with it or any of the rest of the tree.

Shouldn’t it have some reference to the characteristic variable (e2) of "_believe_v_1"? or have its own characteristic variable that "_believe_v_1" references?

       │                  ┌pron:x3
Logic: pronoun_q(x3, pron(x3), _believe_v_1(e2, x3, _probable_a_1(i10, _rain_v_1(e13))))

Any pointers on how to think about “I believe it probably rained”?

And: Does this algorithm for processing the tree make sense?

Do not try to re-invent the wheel, particularly when it comes to overloading terminology. A variable is not a set. To refer to the set of individuals for which a predicate is true, that is the “extension” of the predicate.

This is not how predicate logic is defined, and I think this is the source of the following confusion:

If you have a scope tree, each node has a certain number of free variables (those appearing somewhere lower in the tree, but quantified higher in the tree). A quantifier also has a bound variable. Each node has a truth value (true or false), given a value for each free variable. The root of the tree has no free variables, and so it has a truth value without specifying anything. For a little more detail, there is a one-and-a-half page summary on pages 119-120 of my PhD thesis: https://www.cl.cam.ac.uk/~gete2/thesis.pdf

For a logical operator, the truth value of the node is defined in terms of the truth value of the child(ren). For example, negation flips the truth value. For “probably”, you have to move to a probability logic, where each node has a probability of truth rather than binary truth/falsehood. Then, “probably” gives a new probability as a function of the child’s probability.

(The above is just for declaratives, and has to be adapted slightly for interrogatives and imperatives.)

1 Like

Wow, very helpful! The sections on Model-Theoretic Semantics (1.3), Modelling meaning (2), Classical Model Theory (3.1), and Quantifiers and First-Order Logic (7) are great summaries of areas I’ve had to research elsewhere and try to understand the hard way.

Anyway, to your point: I didn’t mean to redefine the terms, I was just trying to explain how I was using them in my writeup since I don’t yet know the right terms to use (or the right way to use them). Thanks for helping me on that front.

After reading through your thesis many times, I’m still struggling to understand how to interpret a scopal argument that is not the RSTR or BODY of a quantifier. Let’s switch to “I believe it is raining” to get rid of pesky probabilities for the moment:

Logic: pronoun_q(x3, pron(x3), _believe_v_1(e2, x3, _rain_v_1(e10)))

If I wanted to find a set of assignments to variables for which the statement is true, then I think I’d need to do this (starting at the leaves):

  • _rain_v_1: put an event individual in e10 such that rain(e10) is true
    • There is an implicit existential quantifier on e10 between believe and rain that has an empty RSTR and the node as the BODY
  • _believe_v_1: converts to a conjunction of:
    • believe(e2): put an event individual in e2 for which believe(e2) is true
    • ARG1(e2, x3): put an individual in x3 for which ARG1(e2, x3) is true (using the same individual in e2 as above)
    • ARG2(e2, ?h8?): use the same individual in e2 as above… but I don’t know how to think about what is in the second position of ARG2 since it is scopal

Can you describe how to evaluate the truth value of ARG2? Or how to think about it?

To the extent that you can treat logic as a computer program for your system to evaluate, logic is declarative rather than procedural. Evaluating the truth value of a predicate is not quite the same thing as making an assignment of the free variables to objects in the model. Given an expression of first order predicate calculus, a model, and an assignment of any free variables, you can compute a truth value. You ask the model whether each predicate is true of the objects in question and combine those truth values using the logical connectives that make up the formula, and you’re done.

It turns out natural language does not fit neatly into first order predicate calculus, and as such the ERG does not restrict itself to first order predicate calculus. The interpretation of predicates such as _believe_v_1 is not specified by the grammar, and unfortunately, there is not canonical resource that you can turn to for a definitive answer. Even worse, the answer is different for each scopal operator.

There are areas of logical theory that accommodate some of the most common such scopal operators. For instance, modal logic explores the interpretation of the operators “must” and “might.” Epistemic logic allows for operators of the form “A knows that B.” But a grand unified theory of logic, in which arbitrary formulae from the ERG can be evaluated to a truth value given some appropriately defined model, does not (yet) exist.

You might reasonably ask, then, what is the ERG doing producing these uninterpretable logical formulae? The answer is twofold.

  • The formulae the ERG produces are interpretable for the simpler cases, as you have already seen for yourself.
  • It maps the form of English sentences onto a logical form that is comparable to the shape assumed by theories of logic that “push the envelope” past the simple sentences towards the harder ones (modal logic, epistemic logic, others), and it makes the larger body of scopal operators that don’t map perfectly onto well-studied ones look as similar as possible.

The good news is that you may not need to give an exhaustive interpretation of all possible scopal operators to make a fun game. If the user gives you something that’s hard to interpret, you could just tell them they’re being too vague :-). What’s an example of an input you want your system to be able to interpret that has a difficult scopal operator in it, and what do you want the system to do in that situation?


OK, that helps @sweaglesw. It is kind of the approach I’ve been taking anyway, which is to encounter a new term, figure out what I think it means, and get the system to do that. Didn’t feel very principled but…

This thread was created because I am trying to get more verbs implemented in the system (hence the title). Here’s the case that sent me down this rabbit hole:

If you are in a cave system and someone tells you “Go to a cave”, you have a few options:

  1. be a wise guy and say “I’m already in one”
  2. do what a human would probably do and try to go to a different cave. If there aren’t any, say something reasonable.
  3. do what a computer would probably do and list all possible caves, pick whatever one is first, and go there. If it is the cave you are in, you are in case 1, otherwise you are in case 2

My prototype currently does #3 and I want it to do #2. My current system uses Prolog to evaluate the logic’ish output of the ERG. Here’s this case:

                │                  ┌pron:x3
                                   │   ┌_to_p_dir:e8,e2,x9
Logic: _a_q(x9, _cave_n_1(x9), pronoun_q(x3, pron(x3), and(_to_p_dir(e8, e2, x9), _go_v_1(e2, x3))))
Prolog: =(CreateOrEval, create), d_pronoun(you, X9125), d_a_q(d_noun(cave, X9126)), d_to_p_dir(E9122, E9124, X9126, CreateOrEval), d_go_v_1(E9124, X9125, CreateOrEval), !().

I execute that Prolog expression and get back a handle to the event instance that gets created by _go_v_1. I then go run separate code to go to whichever cave the Prolog code chose. If the code chose my current cave I get #1 above, otherwise I get #2.

What I want to do is actually put the “go” code into the Prolog engine so that, when it evaluates the verb _go_v_1, it actually tries going to that cave - in the Prolog solver - and, if it fails, it backtracks and tries other caves. That consistently gives me #2 and a good model for implementing other verbs.

The problem is: in order to do that, when the Prolog solver gets to _go_v_1, I need all of _go_v_1’s variables to be set correctly based on the semantics of the sentence so I can actually execute the code properly. This might not be the case if a verb has scopal arguments and they, for example, are resolved by the solver after the verb. Which is why I’ve been trying to get my head around scopal arguments to see what options I have.

At this point I see these options:

  1. Go with the “clean” approach I outlined above and (as you suggested) punt the verbs with scopal arguments back to the user
  2. Go with the “clean” approach but allow the code for the verb to resolve scopal arguments during its processing. Kind of like a “look ahead”. I have to think about this more.
  3. Do some multi-pass approach for cases that have alternatives like “Go to a cave” where I somehow get all the alternatives and try each of them after resolving the statement (kind of like doing backtracking after the fact). I have to think about this more as well.

Of course it bugs me to cut out a huge class of verbs, so I’ll probably drill into #2 or #3 for a while to see if anything pans out…

Don’t let it bug you too much! There are plenty of cases where the reasonable thing is probably to reject the input. For example, what if the user says, “Imagine that you’re in a cave”?

In making your game, remember the best is the enemy of the good.

For the sake of future generations, here’s how I ended up handling verbs when converting to Prolog:

  1. First, the “canonical” Prolog is created using this algorithm
  2. The actual Prolog predicates that implement the verbs were more complicated than I expected
  3. And because of that, a final “extra” verb term was required before execution as described here.

The way I solved the problem of verbs having scopal arguments was pretty simple: the verb (or whatever term with a scopal argument) gets the branch of the tree represented by the scopal argument passed to it, and then what to do with it is its problem as described here. Mostly, it will end up evaluating the argument first, and then doing its own logic. Seems to work well.