Variable substitution in pattern matching?

Question

I'm developing an inference engine, this means that basically I have a certain number of "facts" which are basically the representation of the world in a certain moment. Together with the facts (that usually are only two, the starting state and the goal state) I have many rules (could literally be hundreds for certain problems). The aim of the inference engine is, given a start state and a set of rules, find the shortest path to the one of the acceptable goal states. This can be done with several algorithms like DFS, BFS or A*. The basic structure for the program is:

fact factname
  attribute1 = "value";
  attribute2 = [ 1, 2, 3];
  attribute3 = 4;
  attribute4 = 7;
  ...
endFact

rule ruleOne
  equalsto(attribute, "value") or
  greaterthan(attribute, 5)
  >
  remove(attribute);
endRule

rule ruleTwo
  isprimeinteger(attribute)
  >
  add(attribute, 1)
endRule

In the rule, the LHS (the part before the >) matches every attribute in the fact factname which is equal to "value". In this case it's only one, but there may be many. This means I have to resolve variables (often multiple times for the same fact), and the rule's LHS may have multiple conditions put in and/or with proper priority parsing.

The problem is: is there any way to resolve this kind of variables efficiently? What I'm doing now is to iterate over every attribute in the fact and basically I'm generating a quite big n-ary tree which is even unbalanced, and this is VERY slow, especially given the conditions above.

I'd love pointers to papers for this kind of pattern matching

Answer 1

No big surprise here, you're using an O(N) algorithm where a straightforward hashtable would be O(1). The hashtable would store for each attribute value the corresponding attribute.

Answer 2

I noticed you didn't use the word unification any where in your post. That's what's the algorithm you're trying to implement is generally called. Check out the Wikipedia article; there's some references at the bottom .. including one from the '70s when space and cycles mattered.

Answer 3

eduffy has it: this is called unification. Prolog is a programming language designed to do exactly what you're trying to do, in the general case, and it uses unification to do its dirty work.

However, anyone who's tried to implement arithmetic using Peano axioms in Prolog can tell you it doesn't always get there the fastest way possible. There are "constraint programming" languages that do roughly the same thing but with an emphasis on providing heuristics to help the solver find optimal solutions as quickly as possible. One of them is Comet.