If the system can express “every man is a person”, then it becomes more specific.
It’s a special case. You might want to change a rule while keeping the same condition, or change both the rule and the condition. What’s the general operation?
I highly recommend this paper: Predicate dispatching: A unified theory of dispatch. It defines a rule-based language that orders rules by logical implication, and outlines an algorithm for determining precedence statically. There’s also a link to a sample implementation (in Java).
Also, this paper discusses approaches for optimizing predicate dispatching: Efficient Multiple and Predicate Dispatching
Finally, you might also like to check out the language I implemented for my PhD thesis: Socrates. It extends predicate dispatching to handle aspect-oriented programming, and uses partial evaluation techniques to determine rule precedence. The dissertation is here and the implementation (embedded in PLT Scheme, the predecessor to Racket) is here.
TL;DR:
- In lieu of a full OO system with an inheritance hierarchy, you can just have some base type implication assertions, e.g. “IsGem(X) -> IsTreasure(X)” and “IsTreasure(X) -> IsObject(X)”
- In order to determine if a predicate P implies predicate Q, you can test whether “!P || Q” can be reduced to true.
- The real question is how to design a language for specifying exceptions to using implication for precedence. In Socrates, there are two kinds of rules, “plain” and “around”, and “around” rules always precede “plain” rules; otherwise, precedence is determined by lexical ordering when it’s otherwise ambiguous. This is basically the simplest possible thing that made my case studies work, but in practice you probably want something more sophisticated. I haven’t read this thread in detail yet, but it sounds like you’re declaring precedence between rulebooks, which is similar to the “dominates” keyword in AspectJ; my hunch is that this will be good enough to get you most of what you’d want. As usual, a good corpus of test cases would help clarify this…
It sounds like the “Efficient Multiple and Predicate Dispatching” is what I want to read. (I have not yet started reading…) I am particularly interested in the idea of turning a bunch of mutually exclusive rules into a table lookup or switch/case statement.
That is, if I have rules for “smelling ginger”, “smelling mint”, “smelling rosemary”, etc, I want to compile them into a constant-time lookup. Inform 6 let you do this kind of optimization moderately well; the “dispatch mechanism” was to look up a before property from an object and then do a verb-switch inside that property. (Neither operation is actually constant-time in I6, but for fairly simple games it was good enough.)
I’m hardly the most informed person to weigh in on this discussion, but doesn’t it make sense to first figure out precisely what the semantics ought to be and then find out how to make them run fast?
It seems to me that if you analyze the rule conditions right, you’ll wind up knowing both which ones are more specific than others and which ones form a mutually-exclusive set on a single variable. I am happy to see a paper which supports this theory.
Another way of looking at it is that if you can’t implement the non-overlapping case efficiently, then it may not be worth pursuing this approach at all, since that is going to cover 90%+ of the cases in practice. For my thesis work, I was pretty sure that it could be handled efficiently, because of that paper and my intuition, so I didn’t bother implementing the optimizations (it simply does a linear search through all rules for the given verb, plus all rules that aren’t tied to a single verb) and instead focused on expressibility (which for my purposes only meant handling common AOP scenarios).
Now I have read some of the papers. (Although it confirms that I was never cut out for academia. I can absorb so many pages of this stuff before my brain glazes over.)
Current thoughts: the whole business of turning rule precedence into an ordering of rules, seductive though it seems, may have been a will-o-wisp. These papers are concerned with a tree of conditions, each of which splits the notional space into smaller chunks. A rule is more specific than another when it selects out a subset of that chunk.
They really, really want rule conditions to never overlap. But IF rules overlap all the time. ("…when pushing something", “…when the noun is a cloud”, “…when it’s night-time”.)
(There’s a clever dodge with “classifiers” in the Kaplan+Chambers paper, where you call out a bunch of conditions in a particular order and say “That’s the order, dammit; make the overlaps disappear so that it works out.” I think that’s cheating. Which is to say, it doesn’t scale any better than any other explicit-ordering mechanism.)
What if… this is off the cuff, apologies if it makes no sense… what if we resolve an overlap by pointing at one rule and saying “You can be split with respect to that condition.” So:
R1: when action=pushing, …
R2: when noun=cloud, … (can split with respect to action=pushing)
The system then knows it can rewrite R2 to make a clear specificity ordering:
R2a: when noun=cloud and action=pushing, …
R2b: when noun=cloud and action!=pushing, …
Roughly the split declaration means “R2 takes precedence over R1”, but it does it in terms of this existing model which is supposed to work nicely.
Not sure how the game author would describe this. One way would be to just point at R1 and say “that condition”. But we could also name other conditions. It might be useful to say:
R2: when noun=cloud, … (can split with respect to action)
…that is, split finely into every action value. So R2 would be treated as an exception to every “when action” rule.
This system fails if you split R1 with respect to R2 and also R2 with respect to R1. Then the system would split everything down to individual cases with identical conditions, and they’d still conflict. But I guess that’s exactly the same as simply writing two different rules with identical conditions. “Don’t do that.”
Mind you, there are plenty of cases when we do that… say the Standard Rules define a default rule
Rd: always print “Nothing happens.”
In your game you want to change this unconditionally, so you write
Rg: always print “Something happens!”
Obviously these rules have identical conditions (“always”). This is where I’ve always invoked a lexicographic model, like saying “Game rules always take precedence over Extension rules, which take precedence over Standard rules.” But I’m not sure how to fit that into the split-tree model I described above.
(But maybe it doesn’t have to.)
Could do it by invoking any split condition:
Rg: always print “Something happens!” (can split with respect to the phase of the moon)
Now Rga and Rgb are both strict exceptions to Rd. Woot! Presumably we’d want a way to invent ad-hoc arbitrary conditions for this purpose.
Stole my idea. 
While I appreciate the O(1) lookups you (zarf) are going for, an else-if chain isn’t what I’d call a performance killer.
It can, but the current craptastic “expression-specificness measurer” doesn’t look to see how complicated IsMan(x) is. It just counts terms between ANDs.
Which, on the subject: thank you Doug for the links on predicate dispatching. As soon as I can translate it from academia-ese to plain software engineering, it will be very useful.
I don’t see that as a conflict either. Appending to the body and appending to the condition are orthogonal to each other. Maybe I’m missing something?
That sounds like a laborious and non-obvious way of simply saying R2 precedes R1. And it still just solves precedence for a single pair of rules. A work of IF will have at least hundreds of rules, possibly thousands, which means there’s a million pairings. No one will write a million R2 precedes R1 sentences, especially if they have to hunt down the condition on the other, conflicting rule and copy-paste that into the first rule’s declaration.
As for the master ordering algorithm, well, let me digest Doug’s excellent resources.
It’s not that I’m trying to optimize performance here. I’m trying to construct a model which has enough smarts that it can optimize performance.
No, it solves precedence for one rule versus a category of rules – those that have similar conditions. I have a feeling this is the leverage I’ve been hunting for.
The majority of those pairings are don’t-cares. (Any pair of rules that has mutually exclusive conditions.) Since I’m not trying to put all those rules into a (total) precedence ordering, those cases can be completely ignored.
Aha, that sounds more general.
Is the idea that you can pick a rule (by name) and alter either the body or the condition? Just appending, or is prepending/replacing also possible? Is this the same mechanism as adding/replacing rules in a rulebook? (I7 formally declares a rulebook to be a special case of rule, although we don’t usually think of it that way.)
Yes. Though I’ll admit that altering the body isn’t really high on my list of priorities, since appending statement S to the end of rule R’s body is the same thing as sticking S into a new rule T and then stating “R [immediately?] precedes T”.
Also, the description-of-rules mechanic can pick rules by more than just by name. And it seems useful to be able to pick out rules by a subexpression in the condition as well. The prototype can already pick by a variable in the condition, so expanding that to a subexpression is straightforward, at least conceptually.
With conditions, appending and prepending are the same thing, since AND is commutative.
With bodies, well, again, either prepending or appending still looks identical to “R precedes T”… or “T precedes R”, as appropriate. Maybe call it “immediately precedes”?
For totally replacing either of them, I currently ain’t got nothing for ya.
Neither I nor that prototype really have a definition of what constitutes a rulebook to begin with. Saying ‘rules mentioning darkness precede rules mentioning touching’ will group said rules together, sort both sets by specificity of condition, then execute the darkness set before the touching set… but there’s no mention or implication that there exists a Darkness Rulebook. As I said far upthread, I prefer the description-of-rules mechanic because its way of selection will “go get” appropriate rules, rather than waiting passively for something else to “send” a new rule to it. No “add a rule to a book” mechanic needed.
For replacing a rule with another rule, well, the declarative statement “ replace ” can exist beside “ precede ”. Similar for replacing conditions totally: add a declarative to the language specifying the new condition, and the description-of-rules which shall be modified such. The description mechanic just selects; the declarative statement says what to do with them.