home / intro / faq / tutorial / manual / models / download / people / about

pattern matching

So far, we've seen how classes, properties and methods are defined, and how objects are created. The language keeps a record of concepts in a global database. The pattern matcher (PM), which we'll turn to now, provides a means of retrieving instances, and detecting relationships between them. It is based on an implementation of the RETE algorithm, which is an efficient solution to the many object/many pattern problem encountered early in AI research¹. Little b incorporates a widely used open source implementation: LISA (Lisp Intelligent Software Agents).

queries

The simplest way to interact with the pattern matching system is the QUERY macro. It is intended to be used at the command-line, as a way of interogating the database. It takes a pattern and pattern variables as arguments, and returns lists of objects satisfying the pattern.

long form Query has a short and a long form: (QUERY pattern) or (QUERY pattern-vars pattern). Patterns describe objects; when a matching pattern is found, pattern variables capture the values of fields of those objects, or the objects themselves.

We'll look at the long-hand form of query first. Pattern variables are symbols which begin with a question mark. The first argument to the query may be a single pattern matching variable or a list of them. The first case, causes query to return a list of objects which are matched by that variable in the pattern provided as the second argument.

In the adjacent example, at the first command prompt, (query ?o (?o [x ?])), ?O matches all objects of class X. The pattern (?o [x ?]) is a var-binding pattern; ?O is bound during the matching process instances which match [x ?]. The ? symbol, indicates that the A field of X may take be value. This expression effectively says, "return all ?O where ?O is the object which matches [x ?]". When the pattern var in the first argument does not appear in the pattern, it is assumed to refer to the entire pattern. That is - as a shortcut, you could write (query ?o [x ?]) instead.

The second command prompt shows an example of matching multiple variables. The returned value in this case is more complicated; it is a list of binding sets. Conceptually, a binding set indicates an association between variables and objects which satisfies the pattern. Each binding set is a list of cons pairs, written (?VAR. VALUE). This is why b prints so many parenthesis when multiple variables are matched.

The third command prompt shows how property values can be captured. Notice that [x "no property"] is not returned in the resulting list. An important feature of properties is that if they are not bound, they are not detected by the pattern matching system.

On the fourth line, a constraint is implied. By reusing the ?F variable, in the position of the identity field of both X and Y objects, we return only those X objects which have the same value for the A field as Y objects do for their B field. Constraining fields to hold the same value (tested using EQUALP), is a powerful capability which enables relationships to be detected.

The fourth and fifth lines show examples of compound patterns, patterns which take other patterns as arguments. :AND requires that every sub-pattern match in order for the pattern to succeed. :OR will succeed when any of its sub-patterns match. :AND and :OR may be nested within each other, but may not appear inside other pattern matching blocks.

The sixth line shows how to perform arbitrary tests, based on Lisp functions. The form (numberp ?f) is evaluated during the pattern matching process. If it returns NIL, the pattern will not match. Tests are only run once all the patterns before them are satisfied. A pattern may not consist only of a test; neither may a test begin a compound pattern.

short form The short form of query,

is provided as a convenience. Under the hood, it expands into the long form. When the pattern contains one or more pattern variables, these are collected into a list and used as the first argument to the long form of query. When the pattern contains no pattern variables, the pattern is treated as a varbind pattern with an implicit pattern variable which is the sole first argument to the long form.

We can rewrite on lines 1-3 above as:

Notice that it is not necessary to write ? (second line above) for identity fields. The remaining queries (lines 4-6) are not possible to write using the shorthand form.

rules

Rules provide a means for running code whenever a pattern is matched. They are defined using the DEFRULE macro, which takes a pattern, the symbol =>, and one or more forms which will be executed when the pattern is matched:

The pattern, and code body are sometimes referred to as the LHS and RHS (left hand and right hand sides) of the rule. Each possible match of the LHS results in the RHS being executed. During the pattern matching process, the pattern variables become bound. When the RHS is run, these bindings are available.

A rule may be thought of as a function that runs non-deterministically. Whereas a function definition has variables bound when the function is explicitly called, a rule's variables are bound whenever a match is detected. This happens when new objects are added to the database, and when a rule is first created.

pattern summary

The following table is a rough guide which summarizes the patterns that may be provided to QUERY and DEFRULE. It makes reference to id-pattern-args and property-pattern-args. Id pattern args have a structure identical to an object constructor

the defcon macro