Subset-equational programming in intelligent decision systems

Subset-equational programming is a paradigm of programming with subset and equality assertions. The underlying computational model is based on innermost reduction of expressions and restricted associative-commutative (a-c) matching for iteration over set-valued terms, where ∪ is the a-c constructor. Subset assertions incorporate a "collect-all" capability, so that the different subset assertions matching a goal expression and the different a-c matches with each subset assertion are all considered in defining the resulting set of the goal expression. We provide several examples to illustrate the paradigm, and also describe extensions to improve programming convenience: negation by failure, relative sets and quantities. We also discuss the use of subset-equational programming for intelligent decision systems: the rule-based notation is well-suited for expressing domain knowledge and rules; subset assertions are especially appropriate in backchaining systems like MYCIN, which performs an exhaustive depth-first consideration of subproblems before arriving at some decision; and restricted a-c matching is very convenient for querying attributes of objects in such systems, by relieving the concern for the next ordering of attributes.