The PROPS Language

Syntax and Operation of the PROPS Language

PROPS is a production system language that is implemented in Prolog. The high-level syntax and interpreter incorporate the assumptions of production system architectures, but the low-level syntax utilizes Prolog notation, and the interpreter has limited access to Prolog capabilities.

Working Memory

As in other production system frameworks, a PROPS program stores content in a working memory and a production memory. The working memory contains a set of elements stated as Prolog "facts", each of which has a predicate and zero or more arguments. For example,

    on(a, b), 
    blue(object1), 
    single_list([1,2,3]), 
    two_lists([a1,b2], [e5,d4,c3]), and
    stack([s,[np,[noun,john]],[vp,[aux,can],[verb,dance]]])

would all be legitimate working memory elements. Unlike Prolog, only constant symbols can appear as arguments to predicates in working memory, with variables being disallowed.

You can add new elements to working memory using the add command, which takes a single argument that should satisfy the syntax of a working memory element. You can invoke this command at the top level of the interpreter, use it in a file that you load into the interpreter, or include it in the right-hand side of a production rule. If you use the add command in a file, you should preceed each instance with ":-" to ensure Prolog handles it correctly.

You can remove elements from working memory using the remove command, which takes one argument that should satisfy the syntax of a working memory element. This may contain the variable "_" for one or more of the predicate's arguments. In this case, the command will remove all elements from working memory that match the pattern. An important special case is remove(_), which will clear the contents of working memory. You can use this command at the top level of the interpreter, invoke it in a file that you load into the interpreter, or include it in the right-hand side of a rule.

Production Memory

Production memory contains a list of production rules. Each rule must begin with a name, which is a string of letters without blank spaces. Next comes the word "if" followed by one or more conditions that are separated by the word "and". The conditions are followed by the word "then", after which come one or more actions. Following the Prolog convention, each rule ends with a period. Conditions and actions may contain pattern-match variables, each of which begins with a capital letter, as in Prolog.

Consider a simple example for transitive reasoning about the relation taller_than, which has two conditions and one action that adds a new element to working memory. As in other production system formalisms, the variables mentioned in the left-hand side carry over to the right-hand side.

  infer_taller
    if
       taller_than(X, Y) and
       taller_than(Y, Z) 
    then
       add(taller_than(X, Z)).

Now consider a more complex rule that we might use in transforming a list in working memory into a reversed version. This rule demonstrates the use of lists in conditions and actions. If working memory contains the element original_list([b,c,d]) and reversed_list([a]), then the left-hand side would match with X binding to b, Rest binding to [c,d], and Y binding to [a]. If selected for application, this rule instantiation would remove these two elements from working memory and add the elements original_list([c,d]) and reversed_list([b,a]).

  reverse_list
    if 
       original_list([X|Rest]) and
       reversed_list(Y)
    then
       remove(original_list(_)) and
       remove(reversed_list(Y)) and
       add(original_list(Rest)) and
       add(reversed_list([X|Y])).

By default, conditions in the left-hand side must match against working memory elements, but rules can also include Boolean tests that are embedded in the check predicate. This can take as its single argument a Prolog expression that begins with any of the predicates equal, not_equal, is_in, is_not_in, member, and not_member. These return true or false and assume that their arguments are bound elsewhere in the rule's left-hand side. These simple predicates are efficient to execute, so it is safe to include them as conditions. For instance, the rule

  contains
    if
       list_of_interest([X|Y]) and 
       some_list_structure(Z) and
       check(is_in(X, Z)) and 
       contained(W)
    then
       remove(list_of_interest([X|Y])) and 
       remove(contained(W)) and
       add(list_of_interest(Y)) and
       add(contained([X|W])).

would match against the working memory elements list_of_interest([c,d,e]), some_list_structure([h,[f,c],[a,b],g]), and contained([b,a]) because, once it binds X to c and Z to [h,[f,c],[a,b],g], the instantiated expression check(is_in(c, [h,[f,c],[a,b],g])) returns true. You can use the Prolog predicate member in a similar way, but is_in checks for the presence of a symbol at any level of embedding.

In some cases, you will also need to use Prolog predicates in the right-hand side to bind variables for use in later actions. For instance, the previous rule adds the contained symbol to the beginning of the list that is the argument of contains. If you wanted instead to add it to the end of that list, then you could achieve this with the rule

  contains2
    if
       list_of_interest([X|Y]) and 
       some_list_structure(Z) and
       check(is_in(X, Z)) and 
       contained(W)
    then
       remove(list_of_interest([X|Y])) and 
       remove(contained(W)) and
       add(list_of_interest(Y)) and
       append(W, X, Appended) and
       add(contained(Appended)).

Upon matching the above structures, the previous contains rule would add the element contained([c,b,a]) to working memory, whereas the new contains2 rule would instead add contained([b,a,c]). This is because, once X is bound to c and W is bound to [b,a], the definition of append will cause Prolog to bind Appended to [b,a,c]. As before, we recommend restricting this coding style to simple predicates that are efficient to execute, as the purpose is bind variables, not to rely on Prolog instead of the PROPS interpreter.

You may also find useful two other commands that are available for calling in the right-hand side of production rules:

print, which takes a single argument that may be either a string or a bound variable and prints it; and
read, which takes a single unbound variable as an argument and binds it to what the user types.

To use PROPS, you should launch Prolog and then load any files you have prepared using the consult command. Typically, you will load a single file that contains both your production rules and your initial working memory, although you can also store content in separate files and load all of them.

You can add new rules to production memory using the add_rule command, which takes a single argument that should satisfy the syntax of a production rule. Although you can invoke this command at the top level of the interpreter, you will typically use it in a file that you load into the interpreter, in which case you should preceed it with ":-" to ensure Prolog handles it correctly. You can also invoke remove_rule, which takes one argument and removes from production memory any rule with that name. The special case remove_rule(_) clears the contents of production memory.

Running a PROPS Program

Once you have populated production memory and working memory, you can use the run command to execute the program. If you provide this with zero arguments, as in run, it causes the program to run until either no rules match or one fires that executes the end command. If you provide it with a numeric argument, as in run(5), it will run for that many cycles before halting. This second mode is useful for debugging, since you can use the show_wm command to inspect the contents of working memory after the run ends. You can also use the show_pm command to show the contents of production memory. In between runs of your production system program, you will have full access to Prolog's commands.

Like other production system languages, PROPS operates in recognize-act cycles. On each cycle, it finds all instantiations of rules that match against the current contents of working memory, except for those that have fired on earlier cycles. The interpreter selects one of these for application, preferring rules that were added to production memory earlier. If more than one instantiation of the same rule matches with different bindings, then it selects one of them at random. Once PROPS has selected a rule instantiation, it carries the bindings over to the right-hand side and executes the instantiated actions. Typically, these alter the contents of working memory, letting different rule instantiations match on the next cycle. This process continues until no rules match, a rule executes the end command, or the system exceeds the number of cycles specified in the call to run. When a rule with end fires, or if the user calls the reset command at the top level, the interpreter removes information about previous rule firings, so that instantiations selected earlier become available for consideration.

By default, the PROPS interpreter will print, on each cycle during a run, the cycle number and the rule that fired on that cycle. However, you can also use the command trace_wm to display the contents of working memory after each cycle. Calling trace_wm(all) at the top level will lead PROPS to show the entire contents of working memory on each cycle, but this can be overwhelming. You can tell the system to show elements that match a given pattern P with trace_wm(P). For instance, the successive commands trace_wm(on(_, a)) and trace_wm(in(_, _)) would cause PROPS to display all elements that match these to patterns on each cycle. Using the command trace_wm with no arguments turns off this trace facility.

Sample Programs and Traces

You may find it useful to inspect two sample PROPS programs. The first makes inferences about kinship relations, whereas the second reverses a given list. These files should clarify the syntax for both production rules and the contents of working memory. You may also want to examine two additional files, available here and here, that contain traces of PROPS runs with these programs. These demonstrate use of the run, show_wm, and wm_trace commands, the last two of which should prove useful for debugging purposes.