Symmetric Relations Best Practice

Authoring Dialog
1

Quick sanity check:

#alice
#bob

(#alice has met #bob)
(#bob has met #alice)

It works, but is it the most idiomatic way to do a symmetric relation? ($ has met $) is just an example. I ask because I’m still getting my head around the following, and am not sure if I can leverage it here:

Remember that when a predicate is queried, the query is compared to each of the rule heads, in program order, until a match is found. That comparison is in fact carried out by attempting to unify each parameter of the query with the corresponding parameter of the rule head.
This has a very interesting and useful consequence, which is that parameters can be used interchangeably as inputs or outputs

– From the Dialog language manual - Chapter 2.

1 Like
2

One of Dialog’s greatest strengths is that it’s very easy to build relations out of other relations. So:

($X knows $Y)
    ($X has met $Y) (or) ($Y has met $X)
3 Likes
3

Thank you, that makes sense and is very cool. :smiley:

4 
($X knows $Y)
	*($X has met $Y) (or) *($Y has met $X)

Is it safe to multiquery in a disjunction like this, when you want to find every possible match for the first branch of the (or) before going on to the next?
Sorry for the clunky wording, I’m still talking about symmetry really.

Case

Alice has met Bob, Bob has met Charlie and Delta.
Without those multiqueries in ($X knows $Y), a query to *(#bob knows $) only gets me #charlie and #alice.
If I’m following the manual and the trace properly, this happens because the success of (#bob has met #charlie) causes the first branch of the (or) to succeed. Delta misses out, even if (#bob has met #delta) is declared.

The solution with the two multiqueries does seem to do what I want, but I don’t grasp this well enough yet to know if it’ll screw things up in a program more complex than checking who knows whom.

5

I believe this is correct. Wrapping the multiquery in (exhaust) will make it backtrack over all choice points, even after one of the inner queries fully succeeds.

2 Likes
6

It is indeed!

The key to both multiqueries and (or) is choice points: forks in the path of execution, where Dialog will try one option after another. Whenever a query fails, it backs up to the last choice point and tries again.

Multiqueries and (or) both create choice points. So the result here is that it’ll first explore all options for ($X has met $Y) and see if any of them makes the outer query succeed. If none of them does, it’ll back up to the (or) choice point and take the other branch, then explore all options for ($Y has met $X) and see if any of them makes the outer query succeed. If not, it fails.

And if the outer query is a multiquery, it’ll keep trying all of these until it’s satisfied.

3 Likes
7

Got it! Thanks for the confirmation and the explanation. Thanks also to Linus Åkesson and anyone else involved in giving Dialog such good debugging tools. They’re simple but powerful just like the language, and (trace on) is hugely helpful for visualizing what’s going on, even when you’re just starting out.

1 Like
8

The manual covers this already, but I would like to emphasize it here because it is crucial to understand multiqueries and choice points.

All queries create choice points, simple and multi both. The only difference is that the choice points created by simple ones get destroyed(popped off the stack) when they return success and the ones associated to multi queries survive on the CP stack even when they return success. That is what allows the ability to backtrack (in cases with success) with multiqueries and prevents it with simple queries. Both kinds of queries keep their CP on the stack on fail, except the last fail.

2 Likes