## AP5 Reference Manualauthor: Don Cohen don@isis.cs3-inc.comThe mail will bounce but the bounce message will give you a working address. last revised: 2021/02/12 ## Contents- Introduction
- Basics
- Annotations, representations and derivations
- Rules, Constraints and Atomic Transitions
- Types
- Equivalence
- Finer Control over Implementation
- Database representation of domain model
- Miscellaneous
- Appendices
- index
## IntroductionAP5 is an extension to commonlisp which allows users to "program" at a more "specificational" level. By this we mean that it allows you to focus more on what you want the machine to do and less on the details of how. AP5 is a compromise between lisp and the gist specification language. In particular, it incorporates those parts of gist that can be reasonably compiled. Unlike gist, it allows programmers to deal with performance issues. There are two mechanisms for this. One is that the compiler can be instructed via "annotations", descibed below. The fallback mechanism is to use lisp when necessary.
AP5 represents state (that is, data) as a set of relationships among a
set of objects, as in a model of first order logic or a relational
database. The language for accessing this data includes the language of
first order logic. We will refer to it as
AP5 programs can add and remove relationships among objects. They can
also test (determine the truth value of) conditions expressed in
AP5 programs are normally built in two phases. The first is
specification, in which the programmer invents relations and rules and
uses them to write programs that "do the right thing". In the second
phase the program is optimized by adding appropriate annotations, such
as representations or sizes of relations. These annotations influence
the AP5 compiler's algorithm selection. They do AP5 differs from theorem proving systems and "logic programming" languages in that it does not allow assertion of arbitrary conditions, such as "all men are mortal". It may, however, be able to check whether all men are mortal, and if so, prevent this fact from becoming false. Another difference is that AP5 does not (normally) do unbounded searches. Queries that may cause theorem provers to start infinite computations cause AP5 to generate compile time errors.
## Organization of the manualThis manual assumes that readers are familiar with lisp. The material above is meant to provide a general idea of what AP5 is. The next chapter tells a novice what he needs to know in order to browse and start writing programs that use the database. More serious users will be interested in the middle of the manual - rules, annotations, types and equivalence. The end of the manual is meant to contain details that even serious users will rarely need.## Basics
## Wffs
At any moment only finitely many relations have been declared. These
will be referred to as "primitive relations". Well-formed formulae
( (E (x) (R 'John x (f x)))'John is a constant, x is a bound variable, and (f x) is a lisp expression. If we were to ask for the truth value of this wff, the expression (f x) would be evaluated first - note that the x refers to some lisp variable bound outside the wff. We would then find out whether the relation R contained any 3-tuple starting with the symbol John and ending with the value computed for (f x).
The set of wffs includes
TRUE,
FALSE,
Lists of the form (
Descriptions are analogous to lambda expressions in lisp. The syntax
of wffs also includes Funcall and Apply, analogous to the lisp
functions of those names. A wff whose CAR is the symbol Funcall is
interpreted by evaluating the second element and treating it as the
relation to be applied to the (values of the) other arguments. A wff
whose CAR is the symbol Apply is interpreted by evaluating the second
element and treating it as a relation to be applied to an argument
list that is constructed by evaluating all the other arguments and
appending all but the last to the last one. Thus
Relations can also be defined by computations that cannot be expressed in wffs. Descriptions, in fact, may be regarded as a special case of relation definition. Just as it is possible to replace a relation in a wff with a description, it is also possible to replace it with a more general definition. This is described in more detail in the section on anonymous relations.
## Simple Database OperationsThe simplest ways to access a database are to ask whether something is true or to add or delete facts:
Macro ( Macro ( Macro (
For example, if there were a binary relation named R, one would make it
relate the symbol George to the number 3 by doing Examples: (copy and paste from between brackets to try) [
> (in-package :ap5) #<PACKAGE AP5> > (defrelation r :arity 2) ;; define binary relation R [defrel R] #,(DBO RELATION R) > (?? r 'george 3) NIL > (?? e(x)(r 'george x)) NIL (++ r 'george 3) NIL > (?? e(x)(r 'george x)) T > (?? r 'george 3) T > (-- r 'george 3) NIL > (?? e(x)(r 'george x)) NIL Normally, non-primitive wffs can be tested but cannot be directly updated. There is also an "update" macro that combines addition and deletion: Macro ( Thus, for example, (update phone of 'George to 126)will make the phone of George be 126, and if George originally had another phone, one such phone will be removed. (update phone of 'George from 225 to 126)requires that his phone was initially 225. It removes 225 and adds 126 (although the addition may be a noop).
Examples: (copy and paste from between brackets to try) [
> (in-package :ap5) #<PACKAGE AP5> > (defrelation phone :arity 2) ;; define binary phone relation [defrel PHONE] #,(DBO RELATION PHONE) > (listof phone) ;; list all phone tuples NIL > (update phone of 'George to 126) 126 > (listof phone) ((GEORGE 126)) > (update phone of 'George to 225) 225 > (listof phone) ((GEORGE 225)) > (update phone of 'George from 225 to 126) 126 > (listof phone) ((GEORGE 126)) > (update phone of 'George from 225 to 128) *** - required precondition not true: PHONE (GEORGE 225)In addition there is a macro for creating an object and relating it to several other objects: Macro ( (create person firstname = "John" lastname = "Smith" parents = mother father)In a single atomic transition (again, see atomic), this creates a new object and adds a number of facts about it. In this case we can see its translation as follows: Examples: (copy and paste from between brackets to try) [
> (in-package :ap5) #<PACKAGE AP5> > (defrelation person :arity 1) [defrel PERSON] #,(DBO TYPE PERSON) > (defrelation firstname :arity 2) [defrel FIRSTNAME] #,(DBO RELATION FIRSTNAME) > (defrelation lastname :arity 2) [defrel LASTNAME] #,(DBO RELATION LASTNAME) > (defrelation parents :arity 3) [defrel PARENTS] #,(DBO RELATION PARENTS) > (macroexpand-1 '(create person firstname = "John" lastname = "Smith" parents = mother father)) (ATOMIC (LET ((PERSON (MAKE-DBOBJECT))) (++ PERSON PERSON) (++ FIRSTNAME PERSON "John") (++ LASTNAME PERSON "Smith") (++ PARENTS PERSON MOTHER FATHER) PERSON)) ; TIn the current version (we hope to fix this!) all create's allocate a lisp object of the same representation, called dbobject (for Data Base Object). It is still possible to do your own allocation, but the create macro does not help you. Several of the relation representations presented below require this representation. Function (
## Declaring RelationsThe generally useful form for declaring a new relation is DefRelation. We provide a brief overview here, although the details are postponed for later. For a beginner it is sufficient to know that an n-ary relation can be declared by supplying only a name and arity, e.g., Examples: (copy and paste from between brackets to try) [
> (in-package :ap5) #<PACKAGE AP5> > (DefRelation PhoneNumber :arity 2) [defrel PHONENUMBER] #,(DBO RELATION PHONENUMBER)Typically one provides documentation and declares the types (unary relations) required of objects allowed in the tuples, e.g., Examples: (copy and paste from between brackets to try) [
> (in-package :ap5) #<PACKAGE AP5> > (defrelation person :arity 1) [defrel PERSON] #,(DBO TYPE PERSON) > (DefRelation PhoneNumber :arity 2 :types (person integer) :documentation "(PhoneNumber x y) means that the integer y is the phone number of the person x") [defrel PHONENUMBER WARNING: Estimated size ... ] #,(DBO RELATION PHONENUMBER)The other common form that will be useful to a novice is defining a relation by a description, e.g., Examples: (copy and paste from between brackets to try) [
> (in-package :ap5) #<PACKAGE AP5> > (defrelation child :arity 2) [defrel CHILD] #,(DBO RELATION CHILD) > (DefRelation sibling :definition ((x y) s.t. (E (parent) (and (child parent x) (child parent y) (not (eql x y))))) :documentation "(Sibling x y) means x and y are distinct and share a parent") [defrel SIBLING]In this case the arity and types are not needed - they can be deduced from the definition. However they can be provided if you like. When a DefRelation form is evaluated for an already existing relation, the assumption is that its definition is being changed, and the result ought to conform to the new definition. As a preview and incentive to keep reading, we mention that DefRelation allows you to specify such things as - data representions of relations, e.g., hasharray, alist, etc.
- relations that are computed or derived from other relations, e.g., transitive closures
- cardinality constraints, e.g., every person has at least one office
- how many tuples you expect to populate a relation, e.g., the typical person will be the child of 2 parents and the parent of 3 children.
## Relation NamesDefRelation is analogous to Defun in lisp. It "binds" a name to a relation object, which is analogous to a lisp function object. Furthermore, it is useful not only for declaring new relations, but also for changing already existing relations. To emphasize this analogy we provide the following functions:
Function ( Function ( Function ( The functions above are trivially defined in terms of this relation: Relation (
## Generators
Typically a database is used not just to test whether a particular fact is
true, but to find out what facts are true. The general mechanism for this
is called generators. For any sequence of variables, V, (a list of distinct
symbols), and wff, W which uses (only) the variables in V freely,
there is a set of tuples that satisfy W, in the sense that substituting
the values for corresponding variables results in a wff that is true.
The usual mathematical notation for this
set is {V | W}. AP5 provides access to this set via the
We mention in passing the degenerate cases: For fans of the commonlisp DO macro and its relatives, an AP5 analog is also provided: Macro ( ## Useful generator macrosThe following common uses for generators have been encapsulated as macros:
Macro (
Macro (
Macro (
Macro (
Macro (
Macro ( Examples: (copy and paste from between brackets to try) [
> (in-package :ap5) #<PACKAGE AP5> > (defrelation phone :arity 2) [defrel PHONE] #,(DBO RELATION PHONE) > (set-listof x y s.t. (phone x y) '((george 123)(sam 456)(sam 123))) ;; provide data ;; above is equivalent to (set-listof phone '((george 123)(sam 456)(sam 123))) NIL > (listof phone) ((SAM 123) (SAM 456) (GEORGE 123)) > (loop for (x y) s.t. (phone x y) collect (list x y)) ;; similar to listof ((SAM 123) (SAM 456) (GEORGE 123)) > (loop for (y) s.t. (phone 'sam y) count t) ;; count sam's phones 2 > (loop for (y) s.t. (phone 'sam y) as i below 1 do (print y)) 123 NIL
## Getting StartedAfter having read the preceeding sections you should know almost enough to actually start using AP5. Here we try to supply what's missing.
You have to begin with a machine on which AP5 is loaded.
AP5 is defined in the AP5 package. Unless you want to do everything in
the AP5 package (as we do in most examples in this manual), it will be
convenient to use a package that Examples: > (defpackage "MY-PACKAGE" (:use "AP5" "CL")) #<PACKAGE MY-PACKAGE>It turns out that there are a few symbols in the ap5 package that conflict with symbols in the common-lisp package, and you might prefer the ap5 versions to the common-lisp versions. The symbols compile,
defmethod, defun and loop are all intended to be
upward compatible with the common-lisp versions. Loop is extended to
understand s.t. and the others are extended to include ap5 code in
code compiled to file.
Other conflicts:
**++**the ap5 operator to add to a relation, in common lisp it's the next to last form executed by the read-eval-print loop**abort**in ap5, the way to exit an atomic transaction without making any updates, a condition type in common lisp**array**a relation representation in ap5, a common lisp type**structure**a relation representation in ap5, a common lisp type**variable**a record type in ap5, a documentation type in common lisp
Examples: > (defpackage "MY-PACKAGE" (:use "AP5" "CL") (:shadowing-import-from "AP5" compile defmethod defun loop ++ abort)) In addition to this documentation you have the AP5 database to help you figure out how to do things. This is a very significant resource. Of course, its value grows as you learn more about what it contains. In order to get you started, we mention the following:
Function ( Examples: (copy and paste from between brackets to try) [
> (in-package :ap5) #<PACKAGE AP5> > (Describerel 'relation) RELATION implementation: DEFINED arity: 1 Compare Relations: (EQL) Definition: ((R) S.T. (E (X) (RELATIONARITY R X))) (Relation relation) is true of all known relations, i.e., (loop for r s.t. (Relation r) collect r) will give a list of relations. The definition of a relation is an object in the first place of a tuple of the RelationArity relation. Appears in the definition of: (#,(DBO RULE Typeconstraint-PRECEDES-IN-SEQUENCE-3) ...) Immediate superrelations: (REL-OR-IMP RULE-OR-RELATION) Immediate subrelations: (DONT-TELL-ME-ABOUT INLINEREL ...)
Function (
Function ( Relation (
If
Two particularly useful relations for browsing are: ## Annotations, representations and derivationsAt this point we have described how to declare two different kinds of relations - those that are stored explicitly in memory and those defined by wff. While this is sufficient for obtaining many interesting behaviors, AP5 offers a lot more. First, it allows you to choose a representation of data that you think will make your program more efficient. You can even create your own representations, although that is described later in the manual. Next, you can provide information to the compiler that helps it to optimize the access of compound wffs. You can also optimize your program by deciding to redundantly store a representation of a relation defined by wff. (This is advantageous if you spend a lot of time reading the relation but it's not often updated.) All of these are called "annotations" because they do not affect the meaning of the specification. They may affect whether the specification can be compiled, but if it can be compiled, it will mean the same thing regardless of the annotations. As part of the optimization process it is often useful to see what algorithms AP5 is compiling for you. The usual question is how it decides to generate a compound wff. The answer is supplied (in pseudo-code) by the following function: Function ( We divide relations into three classes: stored, derived and computed.
You tell AP5 which type of relation you are declaring by supplying
arguments to the DefRelation macro. Only one of
the keyword arguments
Relations can, in fact, be both stored and derived, i.e., a data
structure may redundantly record what could in principle be derived.
We call these relations
Another annotation is provided by the :size keyword to DefRelation. This is a list alternating between patterns and numbers. For instance, we might declare the Child relation as follows: Examples: (copy and paste from between brackets to try) [
> (in-package :ap5) #<PACKAGE AP5> > (DefRelation Child :arity 2 :documentation "(Child x y) means that y is a child of x" :size ((input output) 3 (output input) 2 (output output) 1000))This would mean that the expected values of the following programs (loop for x s.t. (child a x) count t) (loop for x s.t. (child x a) count t) (loop for (x y) s.t. (child x y) count t)would be 3, 2, and 1000 repectively, i.e., a typical person would have 3 children and 2 parents, and there would be 1000 tuples in the child relation. This information is used by the compiler to choose among algorithms. For instance, suppose you write this program: (any x s.t. (and (child p1 x) (child x p2)))Should this compile into a program that searches the children of p1 for one whose child is p2 or a program that searches the parents of p2 for one whose parent is p1? The answer depends on how expensive it is to find parents and children, but also how many there are. Normally when you find AP5 using a bad algorithm (even though you supplied what you thought were good representation choices!) the problem is that it doesn't know some critical size data. In general, patterns can contain the symbols INPUT and OUTPUT, and constants. Given arbitrary objects for the arguments labeled INPUT, the size annotation tells you how many tuples to expect from generating values of the variables labeled OUTPUT. The special size NIL means that there may be infinitely many matching tuples.
## Predefined representationsWhile it is possible to define your own representations and derivations (this is described towards the back of the manual), this is usually not necessary. The following choices are already supplied. (defrelation foo :arity 2)is equivalent to (defrelation foo :arity 2 :representation base)
(Partial-index [position]*) means that an index is maintained (implemented as a hash table) for the arguments at the specified postions, e.g., (defrelation foo :arity 3 :representation (partial-index 0 2))stores indices for the first and last arguments (positions 0 and 2). Such relations have quick access to all tuples for which a particular value occupies an indexed position. This implementation is similar to the "base" implementation in that it allows complete generation of relations of any arity. It's much faster for many types of generation but of course requires much more space. Specifying no slots, i.e., (partial-index), is functionally equivalent to base. StructProp can only be used for a binary relation that relates only DBObjects to arbitrary other objects, y. A property on the property list of the DBObject is used to store a list of objects related to that DBObject. (defrelation phone# :arity 2 :representation structprop)
Tree relations stored the tuples of the relation as a tree
with depth equal to the arity of the relation. From the root of the tree
there is one branch for each value that apppears as the first argument of
the relation, and a subtree associated with each branch similarly represents
a relation of arity one less than its parent. If the original relation was
(defrelation works-on% :arity 3 :representation tree)
TreeProp relations are a combination
of structprop and tree relations. Treeprop can only be used for binary
relations. If R is a treeprop relation and
TreeProp+ relations are a generalization of treeprop in that domain values need not be DBObjects. Range values are stored on property lists when the domain values are DBObjects and symbols, and otherwise in a hashtable. Two-Way-Structprop means that the relation is a binary relation that relates DBObjects to other DBObjects by storing each on the property list of the other. Thus for such a relation it is impossible to generate {x,y | (R x y)}. (defrelation parent :arity 2 :representation two-way-structprop) Stored-In-Place and Stored-In-Place-Single are representations which accept as a parameter a piece of code that computes a place where values are stored. This is described in the section on creating new implementations. For the purpose of declaring relations we describe the implementation translators that DefRelation accepts to create specialized relations of these two "real" implementations. GlobalVar means that the (unary) relation is stored as a list of values in the value of a global variable. This is declared in DefRelation by :representation (globalvar [variable-name])as in (defvar *booktitles* nil) (defrelation booktitles :arity 1 :representation (globalvar *booktitles*))Normally AP5 assumes that you will never set that variable other than with database update macros (,e.g., ++). This applies similarly to all of the Stored-In-Place variants. If you do intend to set it, you should see nonatomic. GlobalVar-single means that there is at most one value in the (unary) relation, and it is stored in the value of a global variable. This is declared in DefRelation by :representation (globalvar-single [variable-name])The remarks above still apply. The relation will be true of no values if the variable is unbound or a special empty marker.
The empty marker is the value of
ap5::*no-single-value-stored*.
Of course it is an error to add a
tuple containing that value - it is Declaring a -Single relation does not automatically declare a count constraint. You can, of course, include the constraint in DefRelation. :representation (structure [structure-name] [field-name])as in (defstruct ship name tons) (defrelation ship-name :representation (structure ship name)) Structure-Single is similar to defstruct except that the field contains either the single value related to the structure or an empty-marker. SymbolProp means that the (binary) relation relates symbols to the values in a list stored as a property of the symbol. Note that it is not possible to generate all the tuples of such a relation. This is declared in DefRelation by :representation (symbolprop [property-name]) SymbolProp-single is similar but only one value is stored under the property name. Alist means that the (binary) relation is stored as an association list. You have to supply a piece of code that (a) can be used with SETF and (b) finds the alist. The DefRelation parameter is :representation (alist [code to find alist])For instance, (car *data*) would be acceptable code, since (setf (car *data) [value]) can be compiled. Alist-single is similar but instead of associating a list of values with a value, only one value is stored. HashTable means that the (binary) relation is stored in a hashtable that hashes on the domain to find a list of related values. Again, you must supply a form to find the hashtable: :representation (hashtable [code to find hashtable])You (not AP5) must arrange for the hashtable to use the appropriate test for the canonicalized tuples (see Equivalence). HashTable-single is similar but only stores a single value. Array means that the relation is stored as an array. The arity of the relation must be one more than the number of dimensions of the array. Such a relation relates array indices to the elements of a list stored in the array at those indices. Again, you must supply a form to find the array, and it is your responsibility to give it the right number of dimensions: Examples: (copy and paste from between brackets to try) [
> (in-package :ap5) #<PACKAGE AP5> > (defvar myarray (make-array '(2 3 4))) MYARRAY > (defrelation arrayrel :arity 4 :representation (array myarray))In this example (++ arrayrel a b c d) would generate an error if a were not either 0 or 1 or if b were not an integer in [0,2] or c were not an integer in [0,3]. It is assumed that different array indices are not considered equivalent by the comparison relation for the relation. Array-single is similar but only stores a single value. Examples: (copy and paste from between brackets to try) [
> (in-package :ap5) #<PACKAGE AP5> > (defvar myarray1 (make-array '(2 3 4) :initial-element ap5:*no-single-value-stored*)) MYARRAY1 > (defrelation arrayrel1 :arity 4 :representation (array myarray1)) Individual and Individual-Derived are a representation and a derivation with no capabilities whatever. They are to be used for relations where all the capabilities are supplied in the DefRelation form. Some of the "representations" above and "derivations" below are actually provided via translation functions that produce Individual and Individual-Derived relations. Multiple (redundant) representations are allowed (if they are compatible) by supplying as the representation argument to defrelation a list of the form (:multiple rep1 rep2 ...), where the elements other than the first would be allowed as representation arguments.
## Predefined derivations and computationsMost of these may be used with either the:derivation or
:computation parameter of DefRelation. The only difference is
that :computation declares that the relation is static and
:derivation declares that it is not.
Defined means that the relation is defined by a description. This is what you get by supplying a :definition parameter but no implementation parameter. For example, one might define the Sibling relation from the Parent relation as ((x y) s.t. (E (z) (and (Parent x z) (Parent y z) (not (eql x y)))))In other words, two distinct objects are siblings if they share a parent. In this case it would be possible to generate the sibling relation, but not to directly update it. Recursive relations are not supported. The reason is that they typically are not really definitive, i.e., several different sets of tuples satisfy the definition. [The section on derived relations describes how you can get relations to exhibit recursive behaviors, such as transitive closures.] In fact, defined relations may not contain funcall's or apply's, and the expressions used as arguments must all be either bound variables or constants (not expressions to be evaluated at run time). [See the description of Memo if you intend to use DBObjects (,e.g., relations) or other "weird" objects as constants in wffs.]
Coded
means that a relation is computed from a lisp form. This is specified to
DefRelation by a :computation or :derivation parameter of the form
(DefRelation EQL :arity 2 :computation (coded ((x y) s.t. (eql x y))))In general, such relations are expected to be static. If this is not what you want, see the section on derived relations, in particular, the explanation of triggers. See SimpleGenerator and RelAdder for information about updating and generating. Lisp-Predicate means that the relation is computed by a lisp predicate. This is specified to DefRelation by :derivation (Lisp-Predicate [name of lisp predicate]), e.g., (DefRelation EQL :arity 2 :computation (Lisp-Predicate eql))The parameter supplied to Lisp-Predicate must be the name of a lisp predicate of arity arguments. The new relation is testable, but
not generable, assertable, or deletable. The lisp predicate serves as
the testing function. The current implementation can be used even for
predicates that cause errors, e.g., < is not defined for non-numeric
arguments. Testing code will treat any error as an indication that
the relation is false. (Be careful if you use your own predicates!)
Lisp-Function means that the relation is computed by a lisp function. This is specified to DefRelation by :derivation (Lisp-Function [fname] [input-arity] [output-arity])Fname is the name of a lisp function of input-arity arguments,
returning output-arity values. The relation is true of a tuple of
length input-arity + output-arity if the values of the
function on the first input-arity elements are the last
output-arity arguments. [In some cases it will be useful to
assign equivalence relations to the output arguments - see
Equivalence.] Such a relation is testable and can generate a
single value for its output roles given values for its input roles.
The current implementation, as above, catches errors. Any input that
causes an error in the function is assumed to participate in no tuples
of the relation.
BaseType means that the relation is an inherited type - see the description of basetypes in the section on types. Examples: (copy and paste from between brackets to try) [
> (in-package :ap5) #<PACKAGE AP5> > (DefRelation person :derivation basetype) [defrel PERSON] #,(DBO TYPE PERSON)creates a basetype named person. The :types argument can be used to supply one supertype. (If more are needed they can be added separately.) Unionclass means that the relation is a unary relation which is the union of several other unary relations. (Defrelation person :derivation (unionclass man woman child))is approximately the same as (Defrelation person :definition ((x) s.t. (or (man x) (woman x) (child x))))except that it also adds assertions that the types man, woman, and child are all subtypes of person. It is possible to include a comparison (see Equivalence) as in (Defrelation person (unionclass :equiv equal man woman child)) That turns out not to be the same as (Defrelation person :equivs (equal) (unionclass man woman child))because equivs arguments are ignored in the case of :definitions in favor of computing the equivalence from the definition. Rather, it is equivalent to (Defrelation person :definition ((x@equal) s.t. (or (man x) (woman x) (child x))))Intersectionclass means that the relation is a unary relation which is the Intersection of several other unary relations. This is completely analogous to unionclass. TClosure means that the relation is the transitive closure of another relation. The transitive closure is true of objects x and y if there is a finite sequence (with length at least two) of objects starting with x and ending with y, such that every adjacent pair of objects in the sequence is related by the other relation (called the immediate relation). This is specified to DefRelation by :derivation (tclosure [immediate-relname]) A common variant of transitive closure relates every object (of some type - usually the domain of the immediate relation) to itself. For example, the subtype relation relates every type to itself. This is equivalent to the transitive closure of a new relation defined as: ((subrel superrel) s.t. (or (isubtype subrel superrel) (and (relation subrel) (eql subrel superrel))))
Cardinality means that the relation counts the number of tuples of some other relation. For purposes of exposition, suppose we have the following relation: (Works-on% person project percent)meaning that some percentage of a person's effort is spent on a given project. Suppose further that only non-zero percentages are represented by tuples, i.e., that when a person does not work on a project at all, there is simply no tuple for that person and project. We could derive the relation (Number-of-Projects person count)which relates a person to the number of projects he works on as follows: Examples: (copy and paste from between brackets to try) [
> (in-package :ap5) #<PACKAGE AP5> > (defrelation works-on% :arity 3 :types (string string number)) [defrel WORKS-ON%] #,(DBO RELATION WORKS-ON%) > (defrelation number-of-projects :derivation (cardinality works-on% (input output output))) [defrel NUMBER-OF-PROJECTS] #,(DBO RELATION NUMBER-OF-PROJECTS) In general, every tuple of the original relation corresponds to exactly one tuple of the derived relation. That tuple is obtained by keeping only the elements of the original tuple at the "input" positions, and adding an integer to the end. The integer at the end of a derived tuple is the number of tuples of the original relation that correspond to that derived tuple. Thus, if the pattern consists entirely of output's, the derived relation will contain at most a single one-tuple: the number of tuples in the entire relation. At the other extreme, if the pattern consists entirely of input's, then the derived relation will contain exactly as many tuples as the original relation, but each tuple will have a 1 appended to the end. Sum is similar to cardinality, but instead of counting the tuples, the derived relation adds the elements of all the tuples at one particular position. Again using the works-on% relation above, we could derive the relation (Total% person total)which relates a person to the sum of his percentages on all projects as follows: Examples: (copy and paste from between brackets to try) [
> (in-package :ap5) #<PACKAGE AP5> > (defrelation works-on% :arity 3 :types (string string number)) [defrel WORKS-ON%] #,(DBO RELATION WORKS-ON%) > (defrelation total% :derivation (sum works-on% (input output sum))) [defrel TOTAL%] #,(DBO RELATION TOTAL%) Again, every original tuple corresponds to exactly one derived tuple, and that tuple is obtained by keeping only the elements of the original tuple at the "input" positions. However the number at the end of the derived tuple is the sum of numbers at the "sum" position of all corresponding tuples. The implementation ASSUMES that all tuples will contain numbers in the "sum" position. Notice that it is possible for sum relation tuples to end in zero. There will be a derived tuple if and only if there are any original corresponding tuples. Extreme is similar to cardinality and sum, but is used for finding extreme values. Again using the works-on% relation above we could derive the relation (Main-Project person project percentage)which includes a tuple of works-on% if there is no other tuple for the same person with a larger percentage as follows: Examples: (copy and paste from between brackets to try) [
> (in-package :ap5) #<PACKAGE AP5> > (defrelation works-on% :arity 3 :types (string string number)) [defrel WORKS-ON%] #,(DBO RELATION WORKS-ON%) > (DefRelation Main-Project :derivation (extreme works-on% > (input output extreme))) [defrel MAIN-PROJECT] #,(DBO RELATION MAIN-PROJECT) Notice that the tuples of an extreme relation are a subset of those of the original relation. The >= relation means that a tuple should be included if the object in its "extreme" position is greater or equal to the objects in that position of all other tuples that match in the input positions. Thus there will be at least one tuple for every person in the works-on% relation. There could also be more than one - a person might work 50% on two projects. The < relation would have meant to keep only the tuples with the smallest percentages. The relation <= does the same thing as the relation <. If we change the input to an output then all the tuples will have the same percentage - the highest percentage that anyone works on any single project. The implementation ASSUMES that the ordering relation is transitive and static. Anonymous relations: (It may be possible to define anonymous stored relations, but these are generally not as useful as derived and computed relations.) Wherever a relation is needed in a wff, it is possible to declare an "anonymous" relation. This is just like a regular relation except that it is declared without a name. EQUAL definitions will refer to the same relations, however. The form of the anonymous relation is similar to defrelation, except that the symbol DEFRELATION is replaced by ANON-REL and there is no relation name argument. Other implementations may appear in later versions of this manual.
## Partial ordersA binary relation (or description) R is a partial order if it is non-reflexive (nothing is related to itself) and transitive. The macros below provide an expression language for defining partial orders out of other partial orders.It is anticipated that these macros will be used in wffs, e.g., in the :definition argument to defrelation. Having defined a relation, R, that is a partial order, one might use it for such purposes as: (sort seq #'(lambda (x y) (?? R x y))) None of the arguments of these macros is evaluated. We use the term "ordering expression" to mean any of the following: - the NAME of a relation that is a partial order
- a description, ((v1 v2) s.t. ...), that is a partial order
- a list whose macroexpansion is an ordering expression
Macro (
Macro (
Macro (
Macro ( (E (x' y') (and (O x' y') (R x x') (R y y')))For an image order to be a partial order, it is sufficient that O be a partial order and that for any value x, all its images under R are interchangeable with respect to O. (The latter is true, in particular, if no value x has multiple images under R.) Macro ( Macro ( ## Rules, Constraints and Atomic TransitionsRules provide a way to prevent or react to certain conditions arising in the database. Not surprisingly (given what has already been described), these conditions are specified in AP5 by wffs. Before rules are described, however, we point out that the presence of rules makes it important to be able to control the size (granularity) of changes to the database. As an example, suppose we have a constraint that every person must have a unique name. If every update (++ or --) were done separately, it would be impossible to create a new person or change the name of a person, since the first step would always result in a person without a unique name. Several updates have to be made "at the same time".
The Atomic construct provides control over the size of database updates.
The lisp macro Macro ( As a first order approximation (refined below), we can view an AP5 program as doing a sequence of atomic updates: (loop while t do (atomic ...))AP5 expands each atomic update into a loop, something like: (let (automation-queue) [do atomic update] (loop while automation-queue do (funcall (pop automation-queue))))where each atomic update may add activities to the queue, and the activities themselves may do further atomic updates. The order in which these activities are performed is not specified. However, all of them will be performed before control returns to the program making the original update. The mechanism by which activities are enqueued is called automation rules, and is described below.
Furthermore, AP5 expands each (loop until [proposed atomic update consistent] do [attempt to fix atomic update]where both consistency and the mechanism for fixing atomic updates are defined by consistency rules, also described below.
At any time inside the Macro ( Variable The following macro is useful for debugging aborted updates: Macro ( There are also facilities for retrying and correcting aborted transitions. These are not detailed here because we hope they will be self explanatory.
If there is no abort, then after the database is updated,
Within an atomic,
Macro ( Macro ( Although we don't expect it to be needed very often, we mention that at the top level of an outermost atomic, the symbol REVEAL allows things that are done afterward in the atomic to "see the effects" of updates done before the reveal. The effects do not include any rules that would react to those changes. This might be useful if, for example, you want to create a rule and, in the same atomic transition, assert something about that rule. If you do (atomic (defautomation rule1 ...) (++ P (theonly r s.t. (rulename r 'rule1))))you'll get an error: the form to find the rule named rule1 is being evaluated before there is any such rule. If we do (atomic (defautomation rule1 ...) reveal (++ P (theonly r s.t. (rulename r 'rule1))))then the rule will be visible when it is needed. Of course, if the atomic aborts then this relation will not survive. For now we consider it an error for reveal to be used anywhere other than the top level of an outermost atomic. We may later define what it means in inner atomics, in consistency rule responses, etc.
## Examining and undoing historyThe ability to examine and "back up" through history, undoing database transitions makes it easier to recover from errors (and correspondingly more attractive to experiment). The database transitions are recorded in the global-history list. If all updates are reversible, events can be "undone".Function ( Note: See the note in the section about decaching. If you plan to back up to a particular point, another mechanism is more useful: Function ( Function ( This facility is used to provide a database transaction macro: Macro ( Macro ( Macro ( ## Consistency RulesConsistency rules provide a way to maintain "constraints". Constraints are conditions, expressed by wffs, that are supposed to be true in any state of the database. Each constraint is associated with a consistency rule which reacts to proposed transitions that would violate the constraint by either causing the transition to abort or proposing additonal updates for the transition. We view an atomic update as requesting the database to reach a state in which all facts added by the atomic are true and all facts deleted are false. Therefore consistency rules are not allowed to remove changes from transitions. It also follows that any attempt to add and delete the same fact in the same transition must abort.Intuitively we want atomic transitions to be augmented only with updates that are needed to satisfy the constraints. Unfortunately there may be alternative ways to satisfy this informal specification. It is also desirable for the augmentation to be easily predicted by the programmer (it helps for it to be deterministic) and relatively efficient for the machine to compute. We provide here a heuristic approximation that in practice seems to meet these requirements.
When a set of changes is proposed as an atomic transition, AP5
determines whether the state resulting from that set of changes
would be consistent (satisfy all constraints). If so, the changes are
made and the transition is complete. Otherwise, the consistency rules
associated with the threatened constraints (those that would be violated
by the proposed transition) are executed in an environment that allows
access to both the (inconsistent) proposed state and the (consistent)
current state. The rules do
This algorithm is deterministic (if the rules are deterministic) and in fact the result does not depend on the order in which the rules are considered. However infinite loops are possible, e.g., if there's a rule which reacts to the addition of R(n) for any integer n by adding R(n+1). Next, it is obvious (but important to understand) that the code in a consistency rule must be able to tolerate an inconsistent database. Also, when several cycles of consistency rules are needed, the cycle in which something happens (and thus the length of the path from one rule to another) can make a difference.
As an example, suppose we start in a situation where the (unary)
relation P is everywhere false. There are two rules, R1 and R2. R1
requires that One particularly important case is that if a rule creates some new object, and it is important that it not create two such objects, then its action should prevent it from triggering (as opposed to making an update that will cause some other rule to do something that will prevent it from triggering). Of course, if the action can be done many times without causing any trouble, such as making the same assertion, then a long path (in terms of consistency cycles) to the solution (in the sense that the rule will no longer trigger) still works.
Another point is that the inability to remove an update from a
transition sometimes necessitates the toleration of redundancy. As an
example, suppose we have a stored relation (atomic (++ R a b) (++ R b c) (++ R a c))An attempt to delete the redundant note: We are considering how to provide the ability to install such a "preprocessor" for derived relations, but this is not yet provided.
In order to decide how to react to an inconsistent set of proposed
changes, a consistency rule may want to see what has changed. For
example, one interpretation of the constraint that nobody have more
than one office is that whenever an office is given to a person, if he
already had another office then he should be required to vacate it.
In order to see what is changed, consistency rules are allowed to use a
limited form of temporal reference in the wffs that they use for
database access. In particular, the two special forms - In reactions of consistencyrules
- In triggers of consistency and automation rules (introduced below)
- In functions for generating automation invocations
- In Trigger code (introduced later)
Macro (
There are subtle differences between consistency rules that maintain
time sensitive as opposed to time insensitive conditions. For example,
if we prohibit The normal ways to declare constraints are: Macro ( Macro ( The only difference is that AlwaysRequired creates a rule that reacts when the condition is (about to be) false, while NeverPermitted reacts when it's true. Functions can create rules with computed names, triggers, etc. by calling the following versions defined as functions rather than macros: Function ( Function (
Function (
There's a constraint that only one rule have a given name. If you try to name a new rule with the same name as an old one, the old rule is deleted. Ruletriggers are like wffdefns in that they are not allowed to contain arbitrary lisp forms to be evaluated. All arguments to relations must be bound variables or constants. (However, see the description of Memo.) The RuleTrigger and Constraint-Enforcement-Level cannot be altered (other than by creating or destroying the rule). If you want to change them, you can redeclare the rule (with different values in those slots), which will have the effect of replacing the rule. Example: (neverpermit 'Two-offices-for-same-person '(E (x y person) (and (Office person x) (Office person y) (not (eql x y)))) #'(lambda (x y person) (declare (ignore x)) (when (?? Previously (Office person y)) (-- Office person y))) :incremental :reporter #'(lambda (ignore ignore2 person) (declare (ignore ignore ignore2)) (format *error-output* "~A should not have two offices" person))) Note that when a state is proposed in which p has two offices, the rule will trigger twice - each office has a turn at being both x and y. If both offices are new, there is no reaction, and the condition remains violated - which causes an abort. An alternative reaction could have been (when (?? Start (Office person x)) (-- Office person y))which would have aborted from an attempt to add two new offices for a different reason - an attempt to add and delete the same fact in the same transition. Several constraint idioms have been identified. These have been (or will be) made into relations: - subtype constraints, e.g., every integer is a number - these are discussed in the chapter on types
- type constraints on relations, e.g., the FirstName relation would only relate people to strings - these are also discussed in the chapter on types.
- disjoint types, e.g., nothing is both a symbol and a number - these will again be described in the chapter on types.
- count restrictions, e.g., no person can have more than one spouse
Notes:
## Consistency CheckersWe have generalized consistency rules to allow constraints that cannot be conveniently expressed in our relational language.Type ( Macro (
## Count Constraints
Cardinality (or "count") constraints express facts such as
"every employee has at most one office", or "every employee has at least
one office". The general form is: count-restriction m+n-tuples in the relation R,
which can be formed by inserting m arbitrary objects in specified
positions in [x_{1}, ..., x_{n}].
The types and the positions at which objects are to be inserted are
specified by "patterns" which are lists of length
The currenly supported values for **:none**There are no such tuples, e.g., while employees may in general be assigned secretaries, there should not be any secretaries who have secretaries: the constraint for the pattern (SECRETARY OUTPUT) is :none.**:multiple**The relation must contain at least one tuple, e.g., if every employee has an office, the constraint for the pattern (EMPLOYEE OUTPUT) would be :multiple.**:optional**The relation must contain at most one tuple, e.g., if no employee can have more than one office, the constraint for the pattern (EMPLOYEE OUTPUT) would be :optional.
Of course, "none" implies "optional", and "multiple" is incompatible with "none". However, "multiple" and "optional" are independent. This leads to two more possible cases: **:unique**Exactly one (both multiple and optional), e.g., every person has one office.**:any**No constraint, e.g., a person can have any number of children.
Examples: Cardinality constraints are usually declared as part of a relation declaration, with the :count argument of DefRelation. In fact, the value of this parameter is, in effect, the result of appending together a bunch of argument lists to the Restrict-Cardinality macro described below (except that the name of the relation being declared is left out). Macro (
If
Other reaction code can be supplied via the arguments
In the case of
In the case of
In order to find out what cardinality constraints apply in a given case, the following are provided: Function ( Function ( These functions amount to very limited theorem provers. They recognize that count constraints imply similar constraints for more specialized types. They currently do not try to prove subrel relationships for descriptions. The also recognize that "at most n (x,y) s.t. (R a x y)" implies "at most n (y) s.t. (R x b y)". (A similar argument for "at least" is not currently used since it requires knowing that types are non-empty.) ## Automation rulesAn automation rule reacts to a completed atomic transition. Whatever it does cannot be part of that transition. The reaction of an automation rule does not have access to two states, like that of a consistency rule, but it can be sensitive to transitions because its trigger can refer to and thereby bind variables (available to the response) from two states. In fact, automationsare required to trigger on transitions
rather than just states. They are not supposed to trigger on
transitions that have nothing to do with the trigger. Formally, a wff
is not allowed as the trigger for an automation if there is some
situation in which that wff would be true regardless of the previous
situation (or some situation that would make it true of the next
transition regardless of the next state). [I think this is the right
condition, but I haven't yet proven it.] This implies that the wff must
refer to both the current and previous state. (Actually, in the current
version, it must use Start.)
Macro (
Unlike consistency rules, the triggers for
automation rules are descriptions of the form (
## Automation GeneratorsSometimes it is inconvenient for an automation rule to have no access to the atomic transition other than the variables matched in its trigger. For example, one might want to print a warning that the following set of objects just entered the relation P, and not be satisfied with a separate warning for each. For this purpose we have generalized automation rules in a way analogous to consistency checkers.Type ( Macro (
On every state transition, every match of the description causes an
invocation of Macro ( Note: ## TypesIn AP5, the term "type" is synonymous with "unary relation". We have endeavored to provide the generally useful features normally associated with types. Of course, one typically wants to be able to test whether an object is of a particular type, or generate the objects of some type. These capabilities are provided by virtue of types being relations.
## SubtypesRelation ( Relation (
Notes:
The initial type hierarchy includes: Entity (true for any object) Number (numberp) Integer (integerp) String (Stringp) Function (Functionp) Cons (Consp) Description ((vars s.t. wff) as in defined relation) Symbol (Symbolp)
## BaseTypes (inheritance)In some applications (especially those where data tends to be called "knowledge") various forms of "inheritance" are desired. In the case of types the usual requirement is that by virtue of asserting that an object is of some type it should become an element of all supertypes. In AP5 this is accomplished by (you'd never guess!) first order logic definitions of the types involved. Types that "inherit" elements from their subtypes are called BaseTypes (which is an unfortunate name in that they have little to do with "base relations"). Basetypes are defined in terms of the SubType relation and another relation, named Classification. In particular, if some type, T1, is a basetype, it is defined as the set of objects, x, such that the Classification relation holds between x and some subtype T2 of T1 (which might be T1 itself).Typically, after declaring a baseype (with DefRelation ... :derivation basetype) one makes a number of SubType assertions.
## Type Constraints
A common use for constraints is assuring that objects in a particular slot
of a particular relation are of a particular type. For example, to be
sure that the relation
(Alwaysrequire 'Phone-Type-Restriction '(A (x y) (implies (PhoneNumber x y) (Phone y))) 'ignore :total)
This would abort something like Type constraints are normally declared along with a relation as part of the DefRelation syntax. A list of types is supplied as the :types parameter. Enforcements can also be supplied (see DefRelation for details). The default reaction code does the following: if the object in the constrained slot just ceased to be of the required type, the (now illegal) tuple is removed from the constrained relation. The intent is that when an object ceases to be of some type, any tuples involving that object, which therefore become illegal, will be removed. (AP5 does not support the notion of destroying an object.) The default reaction does nothing to react to attempts to put an object of the wrong type into a constrained relation - the attempt is allowed to abort.
## Disjointness constraintsAnother useful bit of domain model is the fact that certain types are disjoint, i.e., they have no common elements.
Macro (
## Programming constructs using typesThe following macros have been defined to facilitate the use of types in lisp code:
Macro (
Macro (
Macro ( Macro ( Macro (
Macro (
Macro (
## Type dependent I/OThe form in which DBObjects (not general lisp objects) are printed is dependent on their types.
Relation ( Macro (
For particular types of DBObjects, the syntax (DBO (DBO TYPE evaluates to the named typetypename)(DBO RULE evaluates to the named rule.
rulename)
Function ( To print a DBObject (without a proper name), AP5 looks for a type of the object which has a printer function which is willing to do the printing. This function should accept the same arguments as the common lisp :print-function option of defstruct. It should return a string to print or the value NIL. If it returns NIL the search for a printer continues. The printer function is declared by adding tuples to the relation: Relation (
The suggested convention is that printers should print
Relation ( Macro (
If there is no acceptable printing function, the printer prints The notion of "the types of an object" is really not first order, and so is not available as a relation. However, we recognize its usefulness, as in the case of printing and other "object-oriented" applications. Function ( Function (
## Examples(DefRelation person :derivation basetype) NIL (listof type) (#,(DBO TYPE PERSON) #,(DBO TYPE RULE) ...) (DefRelation employee :derivation basetype) NIL (++ Proper-Name (make-dbobject) 'Don) NIL (++ Classification (DBO Don) (DBO Type Employee)) NIL (loop for p s.t. (person p) collect p) NIL (++ Subtype (DBO Type Employee) (DBO Type Person)) NIL (listof person) (DON)
## EquivalenceIn describing the semantics of AP5's virtual database, we have had to appeal to the concept of two references to values being references to "the same value". Unlike logicians, lisp programmers regularly deal with several theories of equality. For example they sometimes compare objects with EQ (in common-lisp, more often EQL), and sometimes with EQUAL. If we do
We will only refer to the equivalence of two values
## Non-uniform Equivalence
Up to now we have spoken of a relation in the database as arbitrarily
partitioning tuples of lisp values into TRUE tuples and FALSE tuples.
We now refine this concept. For each relation R, there is a fixed (not
varying over time) n-tuple of equivalence relations E(R), where n is the
arity of R. We will call this the Adding or deleting tuples must make all equivalent tuples true or false. It is not possible to add and delete equivalent tuples in an atomic transition (any attempt to do so will abort). We can now explain why equivalence relations are not to be updated. Suppose the relation R uses equivalence relation E and that R holds for object o1 but not for object o2. If E starts to hold between o1 and o2 then clearly R has to change, but there seems to be no basis for deciding whether R should start to hold of o2 or cease to hold of o1.
The concept of equivalence also has semantic import for generating.
When we generate (x
Relation ( This solves the problem of equivalence for primitive stored relations. The remaining problem is what to do about wffs (including defined relations, which are defined by wffs). As an extreme example of the problem, suppose we have a relation R with the equivalence signature [Same-Color, Same-Size]. What should be the result of generating x s.t. (R x x)? If we regard R as relating equivalence classes, we're looking for things that are both Same-Color and Same-Size equivalence classes. It seems unlikely that there are any, even if you think the concept is sensible. AP5 in general disallows wffs in which one variable appears in positions that are compared by different equivalence relations. The example above would generate a compile-time error. If all the positions in which a variable appears are compared by the same equivalence relation, that equivalence is used for the variable. For instance if you do (listof x s.t. (and (P x) (Q x)))where P and Q use the same equivalence relation, the result will be one representative of each equivalence class of that same equivalence relation which satisfies both P and Q. A degenerate case is that (listof x y s.t. (R x y))will produce the tuples of R with respect to the equivalence signature of R. This takes care of almost but not quite all cases of interest. We now turn to the exceptions. One case is that one actually wants to ask the question at the beginning of the section: does the set R contain an element that is Equal to '(1 2 3). Suppose the comparison for R is actually Eql. The rule just stated indicates that (?? E (x) (and (R x) (Equal x '(1 2 3))))is ill-formed unless the Equal relation compares its arguments by Eql. (Even if it did, we wouldn't be able to ask similar questions for sets that used other comparisons.) Equivalence relations could reasonably be assigned any signature composed of finer equivalence relations (subrelations), e.g., it would make sense to consider the signature of Equal to be [Eql, Eql] or [Eq, Eq]. (This intuition is justified by a more formal argument below.) By convention, equivalence relations are considered to use themselves to compare their arguments, e.g., the equivalence signature for Equal is [Equal, Equal]. However, equivalence relations are exceptions to the rule above: variables may appear as arguments to equivalence relations if they are compared by finer equivalence relations (subrelations of the equivalence in question). Equivalence relations are thus used to translate between equivalence classes of different equivalence relations. In the example above we can think of Equal as being applied to two Eql equivalence classes: they are considered Equal if they are both subsets of the same Equal equivalence class. However this raises the question of how to interpret a request to generate x s.t. (E (y) (and (R y) (Equal x y)))In particular, by what equivalence should x be compared? The answer is provided by the following rule: if a variable appears only in equivalence relations, it is compared by the equivalence relation that relates two objects only if they are related by all
of the equivalence relations in which the variable appears. (Usually
one is finer than all the others, and that one is used. However, if
there is no finest, e.g., x appears only as arguments to same-color
and same-size, then objects are considered equivalent if they have
both the same color and same size.) Therefore in this example, x is
compared by Equal, and this query "summarizes" R, identifying elements
that are Equal. In general AP5 can generate coarser equivalence
classes from finer ones but not the other way around. For example,
while it can generate the query above, it cannot generate
x s.t. (E (y) (and (R y) (Eq x y)))which would be a set of larger (or equal) cardinality than R. As another example where "translation" between equivalence classes is useful, consider how one might want to combine relations with different signatures. Suppose R1 is a set compared by Eql and R2 is a set compared by Equal. We might want to describe the "union" of these sets as compared by Eql: x s.t. (or (R1 x) (E (y) (and (R2 y) (Equal x y))))This set could not be generated since it might contain infinitely many objects for every element of R2. On the other hand the "union" as compared by Equal would be described as: x s.t. (or (R2 x) (E (y) (and (R1 y) (Equal x y))))This set could be generated (if both R1 and R2 could be generated). Of course, the "union" as compared by other equivalences can also be described by introducing two existential quantifiers. In the same way that variables can be introduced with types, there is a syntax that allows introduction of variables with equivalence relations. If the name contains the character "@", the part after the @ is expected to be the name of an equivalence relation (see esoteric syntax). Thus person#x@equal, person#@equal and x@equal are all possible ways to introduce a variable with an equivalence. ((x@equal) s.t. (R a x))means the same thing as ((x) s.t. (E (x') (and (R a x') (equal x x'))))ExpandDescription (described later) can be used to see what other uses of @ mean.
In the same sense that it's "reasonable" to assign different signatures to equivalence relations, it's also "reasonable" to assign different signatures to static relations that cannot be generated at all. Recall that the signature really only affects the meanings of updates (how large an equivalence class is being updated) and generation (how large an equivalence class is represented by a generated tuple). For a relation like Integer, there is one coarsest possible comparison, which divides all objects into only two equivalence classes: integers and non-integers. However, any finer equivalence relation would be just as reasonable. In particular, it's convenient to be able to ask whether an object is an Integer in the set R, no matter what equivalence relation is used to compare elements of R, as long as that equivalence relation is finer than "both-integers-or-both-not". Notice that if R is a set of numbers compared by = (which relates the integer 1 to the non-integer 1.0), then this does not make sense. In order to allow this sort of overloading, we mark slots of such relations with the following relation: Relation (
## Support for Multiple Equivalences
The burden of maintaining and generating tuples for individual relations
so as to account for the equivalence signatures of those relations is
passed along by AP5 to the individual implementations in the library.
For example, BASE relations store a single representative tuple of any
equivalance class of tuples, and search for tuples with the MEMBER
function, using a suitable :TEST parameter to
account for the relation's equivalence signature. The implementation
may compile in the signature (preferably), or defer looking it up until
run-time. Each implementation must either be so general as to handle
any equivalence relation, whether pre- or user-defined, or must produce
a
Although we have provided, we believe, meaningful semantics and useful support for multiple theories of equality, this support ends at the outer boundary of a wff. Once values obtained from a generator are passed out into the lisp world there is no "memory" of what equivalence class was used to generate them. Certain transformations you might expect to affect only efficiency actually affect semantics. For example, the program (loop for x s.t. (and (P x) (Q x)) collect x)might denote a list that is a superset of that denoted by (loop for x s.t. (P x) when (?? Q x) collect x)if Q's signature has a finer equivalence relation than is P's.
## Equivalence RelationsAP5 considers an equivalence relation to be a binary relation which has been declared as an equivalence relation by asserting into the relation Relation (
Relation ( Function
(
AP5 currently needs some help with new equivalence relations. For reasons of efficiency it sometimes enters objects into hashtables. In order to use hashtables supported by common lisp (EQ, EQL, EQUAL, EQUALP), AP5 needs a fact of the following form: for all x,y, (EQUIV x y) iff (EQ/EQL/EQUAL (f x) (f y)) and (EQUIV x (f x))where EQUIV is the new equivalence relation, EQ/EQL/EQUAL is one of the relations EQ, EQL, or EQUAL, and f is a function. These facts are represented by the relation Relation ( (It would of course be possible to not require canonicalization functions and use less efficient algorithms. AP5 does not do this. We hope the problem will be solved by future extensions to common lisp hashing.) A convenient way to declare (most) new equivalence relations is: Macro ( (Lisp-Predicate-Equivalence-Relation string= equal equal canonical-cl-string=)where canonical-cl-string= simply maps symbols to their names. This actually defines the String= relation by the following code: (lambda (x y) (or (equal x y) (ignore-errors (string= x y)))) ## Finer Control over ImplementationIt is not expected that users will forever be content with the implementations described in this manual. An implementation is really nothing more than a symbol with which to associate capabilities that are shared by a set of relations (those of that implementation). This section tells you how to extend the capabilities of implementations, how to define new implementations and how to tune the systems you build. Each of these is done by telling AP5 more about the relations (or implementations) so that it can better decide how to use them (in the case of tuning), or so that it can interpret requests that previously had no meaning or implement requests that could not otherwise be implemented (in the case of extending relations or defining new implementations).
## TuningIn order to choose among several possible algorithms, AP5 estimates the cost of doing things one way or another. In the process, it uses various data that can be specified to defrelation. Most of this same information can be declared for whole classes of "implementations" (representations, derivations or computations) via the same arguments to defrepresentation, defderivation and defcomputation.
Testeffort provides an estimate of the effort to test a relation. It can be specified as a numerical argument to DefRelation, or more generally as a functional argument for either a relation or an implementation. When provided for an implementation it is taken to apply to all relations of that implementation (except those relations with their own testeffort entries). The function should take as arguments the wff to be tested, i.e., for a n-place relation it will be passed n+1 arguments, the first of which is the relation. The result should be either NIL (meaning that the relation cannot be tested), or a number proportional to the effort for doing the test. There has been little effort so far to calibrate the constant of proportionality, but the intent is that the result be the number of primitive machine instructions (assumed to be constant time) required for the test. To see AP5's estimate of the effort of testing a wff, try the function Function ( Function ( Variable
## Examples
Relation ( :size ((INPUT OUTPUT) 1 (OUTPUT INPUT) 1 (OUTPUT OUTPUT) NIL) :testeffort (LAMBDA (&REST X) 1)In other words, the expected size of The effort to test a base relation is proportional to both the number of tuples in the relation and the size of the tuples: (DefRepresentation base ... :testeffort (lambda (&rest pat) (* (relationsize (cdr pat) pat) 3 (length pat))) ...)
## Extending the Capabilities of a RelationRelations are expected to present the following interfaces to the world (none is required, but relations that provide them are correspondingly more useful):
- Add - a way to add a tuple to the relation
- Delete - a way to delete a tuple from the relation
- Test - a way to test a tuple for inclusion in the relation
- Generate - a way to find (some of) the tuples in the relation
- Trigger - in rare cases (described below) AP5 needs help to recognize that a tuple has been added or deleted from a relation
Triggers may only be associated with an individual relation, while the others may also be associated with an implementation (meaning that they are common to all relations of that implementation). If a relation and its implementation both have generators, all these generators are presumed to work for the relation. On the other hand, providing adders, deleters or testers for a relation will cause the corresponding interfaces for the implementation not to be used for that relation. Only if the relation itself has no associated data is the data associated with its implementation used. If neither exists, the relation is incapable of the corresponding action. The user is expected to keep the interfaces to a given relation consistent, e.g., guarantee that after a --, a ?? will return NIL. There are currently two protocols for adding and deleting tuples. All relations (other than computed relations) may be given adders and deleters, which provide a way to add or delete a single tuple. Stored relations may be given updaters, which provide a way to make a whole set of updates together. If both are provided, AP5 is free to use either. In the case of derived relations (see the section on derived relations) which includes defined relations, the adder and deleter actually perform other database updates. For stored relations the adders, deleters and updaters alter lisp data structures.
In the cases of adding, deleting, and testing,
the value is a functional object which must accept as arguments the
relation and elements of the tuple to be added, deleted or tested,
i.e., As a simple example, here's a declaration of a stored relation in which an adder, deleter and tester are provided:
(defrelation R1 :representation individual :arity 1 :tester (lambda (&rest ignore) (declare (ignore ignore)) `(lambda (rel x)(declare (ignore rel)) (member x *R1DATA*))) :adder (lambda (&rest ignore) (declare (ignore ignore)) `(lambda (rel x) (declare (ignore rel)) (pushnew x *R1DATA*))) :deleter (lambda (&rest ignore) (declare (ignore ignore)) `(lambda (rel x) (declare (ignore rel)) (setf *R1DATA* (delete x *R1DATA* :count 1))))) The Updater for a stored relation is a function of three arguments: the relation to be updated, a list of tuples to be added and a list of tuples to be deleted. Each tuple is represented as a list of objects. The function should make no other assumptions about the add and delete lists and their elements (representing the tuples). In particular, it is an error to smash them or to save pointers to them. It is sometimes desirable for applications to provide relations to users on a read-only basis. This is done by declaring that the relation is not allowed to be explicitly updated: Relation (
## GeneratorsBefore describing the general case, we mention a simple mechanism for the usual case where you're willing to supply a function that computes a list of all the tuples to be generated. Of course this may be inefficient if there are many such tuples, since the cost of computing and storing them will be mostly wasted if only a few are used.
These forms may be supplied as generators to defrelation: (SimpleMultipleGenerator pattern form {cost})Pattern looks like arguments to a primitive wff, but the arguments are
all either (distinct) symbols, standing for the inputs, or the symbol
OUTPUT, standing for something to be generated.
Form is a lisp expression that uses the symbols standing for
inputs, and computes the tuples to be generated. The difference
between SimpleGenerator and SimpleMultipleGenerator is that
SimpleGenerator can only describe a generator for a single output
position: form should return a list of such outputs.
SimpleMultipleGenerator can describe generators for multiple output
positions: form must return a list of tuples of objects, where the
tuple corresponds to the OUTPUT's of the pattern in the same order.
As a special case, a SimpleGenerator form is allowed to return a
single non-listp value which is interpreted as the only value to be
generated.
(DefRelation + :computation (lisp-function + 2 1) :generator ((simplegenerator (a output c) (and (numberp a) (numberp c) (- c a))) (simplegenerator (output a c) (and (numberp a) (numberp c) (- c a)))))declares a three place relation - the lisp-function computation supplies one generator: (listof x s.t. (+ 3 4 x))returns (7). The other generator arguments allow other kinds of generation, e.g., (listof x s.t. (+ 3 x 7))returns (4). The optional cost argument is a form that estimates the cost of the generator (roughly the cost of evaluating the second argument). If not supplied, SimpleGenerator assumes that it's cheap.
Generators are somewhat more complex than adders, deleters and testers
because one typically wants to generate different
subsets of a relation in different ways. AP5 accepts algorithms
for a limited class of such subsets, namely those in which certain positions
of the tuples are fixed. For instance you can supply an algorithm for
generating
The value of a generator argument is a "generator macro", which is a
function to be applied to a list of arguments of the form
The attributes of a generator are Template, Effort and InitialState.
Template is a list of items that indicate which positions of
the relation must be supplied as input and which can be generated as
output. The convention is that the symbols Input and Output indicate the
type of each argument. For example, a generator for a StructProp
relation ## ExamplesThere is only one generator for the Base implementation, which could have been defined as follows:
(DefRepresentation Base ... :generator ((lambda (subsetflg vars rel &rest args) `((template ,(loop for arg in args collect 'output)) (effort ,(* (relationsize args (cons rel args)) 3 (length args))) (initialstate (lambda (rel &rest args) (let ((state
This generator will be specialized by AP5 for the cases where some of
the positions are bound at input, or where the same variable appears
more than once, e.g.,
## Derived RelationsDerived relations are computed from other relations and therefore will, in general, change when those other relations change. AP5 requires the code that implements such relations to follow a few conventions: -
*It must access the database only via AP5 access mechanisms.*That is, it should not duplicate the lisp code used to implement the stored relations on which the derived relation depends. This is important because AP5 does something special to handle temporal reference for stored relations, but it assumes this is not necessary for derived relations since the code for those derived relations will access the adjusted versions of stored relations. (AP5 treats relations that cannot be updated in the same way - see PossibleToAdd.) -
*Update code (in reladders and reldeleters) must use ++ and -- to do updates of stored relations, and not directly alter lisp data.*In other words, the update code for a derived relation translates updates of that relation into updates of the stored relations on which the derived relation depends. AP5 handles these updates during the phase of an atomic update where the atomic transition is being computed (like consistency rules), rather than afterwards when the changes are considered satisfactory and are to actually be made. Conversely, an update macro for a stored relation is expected to change the underlying lisp data and not do database updates. The update macro for a derived relation may access the database (in order to decide what changes to make). The database it sees is the (possibly inconsistent) one that resulted from the previous consistency cycle, i.e., if the update was done by a consistency rule, the macro can see the state that triggered that rule. -
*If the relation can change, AP5 must be made aware of when tuples are added or deleted, in order to trigger rules and compute starts.*The mechanism for doing this is described below. It is also possible to explicitly admit that a relation can change but we are not telling AP5 how to detect such changes. In this case AP5 will not allow rules that must trigger on such changes. See NonTriggerable.
Triggers are declared in DefRelation via the :trigger argument. They specify that the relation being declared is derived from another relation, which kinds of changes to that relation can cause which kinds of changes to this one, and how those changes are computed. For instance, when R1 becomes true we can use F to compute the tuples of R2 (the relation being declared) which thereby become false. AP5 assumes that the set of such supporting relations declared in this way is complete - if none of them change then R2 is presumed not to change either. After AP5 computes all the updates to all relations on which R2 depends, it finds the set of functions that translate those into updates of R2, and calls each such function once to compute updates to R2. The function takes three arguments: the relation for which it is to compute the updates, whether additions to that relation are of interest and whether deletions are of interest. Most functions will compute only additions or only deletions and can thus ignore the last two arguments, but a function that computes both may be able to avoid work if only one is of interest. The function is free to report updates that are not of interest, but AP5 will ignore them. However, it is an error for a function to report updates other than those for which it was declared. The function can access the updates to R2's supporting relations, e.g., R1, or other relations on which they depend, by generating wffs containing Start. It is an error to read other relations. The function should "report updates" by using ++ and -- syntax, as if it were actually updating the derived relation. It is all right for a trigger function to report the same update more than once, but it must not report a fact that was already true as an addition or a fact that was already false as a deletion. Trigger functions may also be used to generate tuples of the derived relation that "start" to be true or false. It is possible that the function may be called for this purpose even when none of the relations it depends on have changed. (We mention this so that you can write the function to avoid large amounts of unnecessary work.) A possible future extension is to allow one function to compute updates to several derived relations at once.
In order to trigger rules AP5 must assume (require) that relations not
change "behind its back" - all changes to derived relations must be
described by trigger. All changes to stored relations must be done
with ++ and --. (But see nontriggerable.) An important case to
recognize, is that some implementations of lisp actually smash code,
for example in macro expansions. Thus you might do (++ R (setq a '(lambda (x) (push x foo)))) (funcall a 1) (?? R (setq a '(lambda (x) (push x foo))))and get the result NIL, even though R compared its arguments with EQUAL. Even worse, there might be a rule prohibiting the macroexpanded version of the lambda expression from being in R, in which case the inconsistency has gone undetected. If such smashing cannot be prevented, another possible solution is to compare the slot with an equivalence that considers the smashed object to be equivalent to the original. (The relation Symbol-Functional-Equivalentp is meant to help solve this problem.) In addition, the rule compiler needs to know what can possibly change. This is partly a matter of optimization: there's no need to compile code to react to events that can never happen. However there are times when it's more than just optimization. A rule cannot be compiled (and the transition that defines it will abort) if it requires generating a set that cannot be generated. If this is needed only in response to an event that cannot occur, then the rule actually could be compiled if AP5 only knew that the event could not occur. Normally AP5 knows what relations can be updated by the use of :representation or :derivation as opposed to :computation. Finer detail can be provided by the arguments PossibleToAdd and PossibleToDelete. Relation ( Relation (
Finally, it is sometimes convenient to think of lisp functions as
relations even if you don't want to specify exactly what they depend on
or how. Of course, these "relations" cannot be
used to trigger rules. This is declared by inserting into the relation Relation ( See also the discussion of the No-Trigger relation in the section on rule triggering.
## Expanding defined relations "in line"
Defined relations may be thought of as either analogous to functions or
macros in lisp. There's no semantic difference between the two.
However, implementation considerations may favor one over the other.
Just as lisp provides both options, AP5 allows a defined relation to be
treated either way. Treating a definition as a macro means that one
ends up processing larger wffs (which means more compilation time). On
the other hand, this makes certain optimizations possible. For
instance, if P were defined as (and Q R), then (and P (not Q)) would
simplify to False if P were treated like a macro. Indeed there are
cases where a query can only be compiled if a definition is treated as a
macro. On the other hand, functions have the advantage of allowing
sharing of code, e.g., there would be more code shared between
For purposes of ++ (--), AP5 does not distinguish between function-like relations and macro-like relations. If the relation has an updater (adder, deleter), it is used. Similarly, if the relation has been declared impossible to directly add (delete), a compile time error results. Otherwise the definition is used. This may work if the definition is not a compound wff. (Actually, updates of negations and descriptions are translated in a reasonable way.) For purposes of testing, generating and rule triggering, AP5 normally treats defined relations as functions. One exception is that a relation which is defined by a non-compound wff is normally treated as a macro. Another exception is definitions such as ((x) s.t. (or (eql x 'a) (eql x 'b)))where the variable could be compared by several equivalence relations. These must be treated as macros since the equivalence will be determined by other uses of the variable in a larger context. If, on the other hand, the definition had been ((x@eql) s.t. (or (eql x 'a) (eql x 'b)))then the equivalence for x would be fixed and the relation could be treated as a function. There are two ways of overriding the defaults. One is to declare a relation "inline" with DefRelation, which means that the relation should be treated as a macro. If a relation is not in this set (and equivalence considerations do not force it to be treated as a macro) it is treated as a function. You can add or remove elements of this set.
A finer control is at the level of a given wff. The syntax for wffs
allows two special cases: ## Nonatomic relationsAll of the relations described so far have been assumed to change only as a result of ++ and --. However, this is not always desirable. First, there is data, such at the current time, which changes without any explicit updates. Second, the updates may be done in some program that was not originally written with AP5, but is simply being interfaced to an AP5 program. Finally, there are times when one is willing to give up such amenities as rule triggering and history recording in order to gain performance. AP5 allows such relations to be declared as "nonatomic". This means that they do not follow the normal atomic semantics of changing only as part of an atomic transition. In fact, they may change during an atomic transition, and remain changed even though the atomic aborts! Declaring a relation as nonatomic means that - you cannot trigger any rules on updates to the relation
- you will be warned if the relation appears in a rule trigger at all
(for instance, it seems strange to impose the constraint that
can only be true before 2:30 PM, since the constraint will be checked only at one time during the atomic. If that's 2:29:59 then the atomic might finish successfully after 2:30!)(Start (P x)) - updates to the relation take immediate effect (unlike atomic relations)
- updates to the relation are not stored in the history
Any derived relation which is derived from a nonatomic relation is also nonatomic. If you provide an adder or deleter to such a relation it may only update other nonatomic relations. (Otherwise the update could not take immediate effect.)
## DefRelation - putting it all togetherNow that we've discussed most of the data that goes into defining a relation we supply the total documentation for DefRelation:
Macro (
Name is the name of the relation to be declared.
The rest are keyword arguments (in this case there are so many that
I prefer the normal lisp notation to the bnf shorthand for optional
syntax, e.g., {:tester Exactly one of representation, derivation, computation, definition or implementation should be supplied. Implementation is treated as a synonym for representation and is allowed for backward compatibility. Representation indicates that the relation is stored, derivation that it is derived and computation that it is computed. Definition indicates that it is defined by a description, and is either derived or computed, but this can be determined by analyzing the description. We refer to these parameters collectively as the "implementation". This is used to determine the relationimplementation of the relation. In the case of definition, if the value is a list of length three with s.t. as the second element, that value is the description that defines the relation. Otherwise, the value is treated as a macro form to be expanded to produce the description. In these cases the iplementation of the relation is the symbol defined. Otherwise (not definition), if the implementation parameter is the name of an implementation, that will be the implementation of the relation. If the representation is a list starting with :multiple (currently this is supported only for representation), then each remaining member of the list is a representation of the relation in the same form as described here. This is a way to get multiple redundant representations in order to have a larger choice of generators.
Otherwise the value is used like a macro to compute a new defrelation form.
This value is either a list, (F . arguments) or a symbol, F, which is treated
just like (F). The arguments convey more information about the relation to
be declared. We call a function F used in this context an
(Defun F (relname keywords &rest arguments) ...)Relname and keywords are the first argument and the rest of the argument list passed to DefRelation. Arguments is the rest of the implementation parameter (which of course is also contained in the keywords list). All arguments to defrelation other than the implementation are used only by F. It should generate warnings if it decides to ignore them. Normally it will include them in its result. As an example, (DefRelation R2 :representation (D2 1 4) :adder add-R2)would be expanded by doing (funcall 'D2 'R2 '(:representation (D2 1 4) :adder add-R2) 1 4)The result might be something like (:arity 2 :representation MyRep :adder add-R2 :tester test-R2)in which case the original defrelation would be roughly equivalent to (DefRelation R2 :arity 2 :representation MyRep :adder add-R2 :tester test-R2)The only difference is that the original implementation, in this case the list (D2 1 4) would be related to the relation R2 by the following relation: Relation ( It is conventional to use the same name for parameterized implementations and the functions that translate them, i.e., the SUM derivation is translated by the Sum function, so that a derivation of the form (SUM ...) translates into a derivation of SUM. If none of implementataion parameters is supplied, the default is representation base. Documentation is a documentation string. Arity is the arity of the relation. If a definition is supplied the length of its argument list will be used as the arity. An error will be signalled if this disagrees with a supplied arity. Some implementation translators supply an arity. Otherwise, if equivs or types are specified, arity defaults to the maximum of their lengths. Otherwise the arity must be specified. Equivs is a list of comparisons for the slots. (See the section on equivalence.) Each element is either the name of an equivalence relation, :any for an anycomparison slot, or :default. If the list is shorter than the arity, any missing slots will be treated like :default. If a definition is supplied, the comparisons will be computed from it, and any non-defaulted comparison that disagrees will cause an error. Otherwise, defaults are derived from the type constraint of the slots, as specified by the Types parameter. Comparisons are derived from type constraints as follows: If the type constraint is a description, it is analyzed to find the comparison of its argument. (This could be :any.) Otherwise, if the type is NOT in the AnyComparison relation, then its comparison is used (as it must be for the typeconstraint to be well formed). Otherwise the defaults are examined. Relation ( Definition is a description of which tuples are in the relation. Types is a list of type constraints, either type names or unary descriptions. If its length is less than arity, any remaining slots will be unconstrained (type entity). Argnames allows you to specify a list of names (symbols) for the arguments of the relation. If this argument is not supplied, the argument names can also be supplied using the syntax described in esoteric syntax as part of the definition if there is one, or otherwise as part of the the types argument. For instance, instead of (Defrelation supervisor :types (person person) :argnames (underling boss))one might write (Defrelation supervisor :types (person#underling person#boss) ...)to indicate which argument was which. For cases where the type argument contains a description, an argument name can be specified as in (Defrelation supervisor :types (((person#underling) s.t. ...) ...) ...) The argument names for a relation are stored in the relationargnames relation.
Type-enforcements is a corresponding list of enforcements for the
type constraints. If its length is less than the length of Types,
any remaining enforcements will be defaulted. The default, which
may also be specified by the symbol :default, is :none for derived
relations and relations with definitions, and :incremental for others.
In addition to an enforcement, this argument may supply a reaction in
the same way as reactions are supplied to DefTypeConstraints.
A given enforcement may be either an enforcement name, e.g., :none,
a reaction, i.e., :remove, :norepair or (:repair Size is a list alternating between input/output patterns and numbers, where each pair is a tuple to be added to the relsize relation with the new relation cons'd onto the front, e.g., :size ((input input output) 10 (output output output) 100) Count is interpreted as a set of argument lists for restrict-cardinality: If you take a list of restrict-cardinality forms, remove the first two elements of each ('restrict-cardinality and the relation name), and then append all the lists together, you'll have an acceptable :count argument. None of these should use the :delete-any-other-countspecs argument. Instead :keep-other-countspecs can be specified in DefRelation. If it is T then all count constraints will be retained. Otherwise it should be a list of patterns of count constraints to keep. The default is NIL. Any count constraints other than these and the ones specified by the :count argument will be deleted. Updater, Tester and Testeffort are the relupdater, reltester and testeffort of the relation. Generator specifies a set of generators. It may be either a single generator or a list of generators. A single generator is either a symbol, which is assumed to name a function, a list starting with Lambda, which is assumed to be a function, or a list starting with SimpleGenerator or SimpleMultipleGenerator, which is just like the corresponding form that could be evaluated except that the arguments need not be quoted and the relation name is omitted from the pattern, e.g., (simplegenerator (x output y) (ignore-errors (- y x))). Trigger, if specified, should be a list of trigger specifications, as in (defrelation derived-rel ... :trigger ((r1 + f1 +) (r1 - f2 -)) ...)which means that f1 computes additions to derived-rel (that's the second +) from additions of r1 (the first +) and f2 computes deletions from derived-rel from deletions of r1. Notice in this syntax, + and - are used to represent new truth values of true and false. The symbol +- may be used to mean both. This is equivalent to two trigger specifications, one containing + and the other -. (You can use two +-'s in the same specification, in which case it's equivalent to four specifications.) Similarly, the relation may be a list of relation names, in which case it stands for one copy of the specification for each name. If the functions are specified by symbols (function names), the definitions will have to come after the DefRelation since they will do adds and deletes of this relation. Finally, if any of the "function" specifications is NIL, this is taken to mean that there is a dependency that is not specified. This currently has the effect of declaring the relation nontriggerable. Inline means to declare the relation to be inline. It defaults to T iff no representation is provided, a definition is provided and the definition "expands to" a non-compound wff. Nonatomic means that the relation is nonatomic as described above. In this case it becomes relevant that additions and deletions to the relation may be idempotent, i.e., the code works whether the fact was already true or not. This can be specified by the idempotent argument, which may be NIL (the default), (:add), (:delete), or (:add :delete). If :add is in the list then it is assumed safe to call the adder or updater to add a tuple without first checking that the tuple to be added is false. Similarly, if :delete is in the list it is assumed safe to call the deleter or updater to delete a tuple without first checking that it was true. For fanatical optimizers, the allow-interrupts argument specifies that updates may be done without the protection of a critical section. Cache-Generators means to compute a set of generators for the relation. This is likely to save time later when the relation is used. If the value is T then all possible generators will be precomputed. NIL means to compute none. Otherwise the value should be a list of patterns for which generators should be cached. Each pattern is a list whose length is the arity of the relation being declared and whose elements are symbols named INPUT or OUTPUT. The pattern means to cache a generator which accepts bindings for the INPUT positions and generates bindings for the OUTPUT positions. The default value is T for relations of arity 3 or less and NIL for others.
Alsofns is a list of functions to be called in the same transition where
the implementation is stored. This is typically used for storing other
related attributes of the relation.
These functions are passed the relation (not its name) as their only argument.
I now think that this should be replaced by a declarative description of what data is to be added by the current defrelation. This should be stored with the relation, and then defrelation, if the relation already existed, should arrange to compare the new additional data to the old version, and make appropriate changes atomically. For instance, the replacement for alsofns might report that we are to add the relationship (tclosure R1 R2) as the result of this definition of R2 (meaning that R2 is the transitive closure of R1). In that case, if the relation R2 already existed, we should find the added data for the old definition and compare it to the data to be added for the new definition in order to compute a set of changes to make, e.g., if R2 was not previously a transitive closure at all, we would remove its old data and add the tclosure tuple. Current uses of alsofns: - unionclass and intersectionclass add subtype relationships (which are not undone on redefinition)
- basetype adds subtype relationships (and matchnode?)
- lisp-predicate-equivalence-relation (adds canonicalizer,equivalence-relation)
- tclosure (asserts tclosure)
- partial-index (can remove old index data)
- slot(-single), stored-in-place(-single) and all variants (asserts stored-where)
When a DefRelation form is evaluated for an already existing relation, the assumption is that its definition is being changed, and the result ought to be something like the result of deleting the relation and then redefining it. However deleting the relation would remove certain data that might have been added after the previous definition, and it's not clear that this is the intent. Our current solution works as follows: If the representation, derivation, or arity of the relation changes, all adder, deleter, tester, generator, trigger, size, and count data is removed from the old relation. These are presumed to be justified by the arity and representation or derivation of the relation. Regardless of whether the representation, derivation or arity changes, all values provided in these parameters are then added, and any values provided in the previous definition (using DefRelation) but not provided in this definition are removed.
## Defattribute - the common special caseMost relations turn out to be binary. For this common case, the following macro offers more succinct syntax than defrelation: Macro ( Relname is the relation name - the first argument of defrelation, Domain-name is the first element of defrelation's :types. Range-name is the second element of defrelation's :types. The rest are keyword arguments: :Domain-equivalence and range-equivalence are the first and second elements of defrelation's :equivs. :Domain-type-enforcement and :range-type-enforcement are the corresponding elements of defrelation's :type-enforcements. :Countspec is the count keyword (such as :any) for the pattern (domain-name output). :Inverse-countspec is the one for (output range-name). :Replacing and :inverse-replacing specify that the too-many repairs for these should replace old values. :Default and :inverse-default are the corresponding default value functions for too-few repairs. :Count-enforcement and inverse-count-enforcement are the corresponding enforcements. :Size is the number of tuples for the pattern (domain-name output), :inverse-size is the number for the pattern (output range-name), and :total-size is the number for the pattern (output output). :Inverse-name is the name for another relation to be declared as the inverse of this one, i.e., if this relation relates x to y then the inverse relates y to x. (This does not correspond to any argument of defrelation.) :Definition, :derivation, and :computation are as in defrelation.
## Creating new representations, derivations, computationsNew representations and derivations can be declared via these two macros: Macro ( Macro ( Macro (
## Database representation of domain modelWhile we have provided a lot of convenient macros for declaring relations and rules, these are also objects in the database. Specifically, all rules and relations are DBObjects with various attributes. For relations some of these have been mentioned before. Many others are described later (under "Finer Control over Implementation").
Formally, we do ## RelationsRelation ( Relation ( Relation ( Type ( Relation (
Relation ( (Defrelation supervisor :arity 2)or a list of nil's, in a case like (Defrelation supervisor :types (person person))or a list of more useful symbols, e.g., (underling boss), in a case like (Defrelation supervisor :types (person#underling person#boss))or in a case like (Defrelation supervisor :definition ((person#underling person#boss) s.t. ...))or in a case like (Defrelation supervisor :arity 2 :argnames (underling boss))
Relation (
Relation (
Relation (
changes arbitrarily As an example, suppose you were given the functions HardCopy-Device-P(string) ; is string the name of a printer Add-HardCopy-Device(string) ; make string the name of a printerYou might declare a HardCopy-Device relation as follows: (DefRelation HardCopy-Device :arity 1 :representation individual :tester (lambda (&rest ignore) (declare (ignore ignore)) '(lambda (rel x) (declare (ignore rel)) (HardCopy-Device-P x))) :adder (lambda (&rest ignore) (declare (ignore ignore)) '(lambda (rel x) (declare (ignore rel)) (Add-HardCopy-Device x))) :nontriggerable t)The nontriggerable means that Add-HardCopy-Device might be called directly, as opposed to being done as a result of (++ HardCopy-Device ...). If you
wish to use HardCopy-Device in rules you must "promise" that this will not
happen, i.e., remove the :nontriggerable t. In this example, there is no way
to remove a HardCopy-Device or to generate all HardCopy-Devices. If these
capabilities existed they could be included in the DefRelation form.
}
Representations, derivations and computations are all represented by the single relation: Relation ( Relation ( Many attributes are shared among these implementation objects and relations. In general, a relation "inherits" these attributes from its implementation. The following are all parameters of defrelation: Relation ( Triggers are not inherited from implementations. They are represented as follows: Relation ( Similarly the following are only defined for relations. Relation (
## RulesType ( Type ( The components of consistency rules are accessible via: Relation ( Other rules also have names, triggers and code. Particular types of consistency rules are also accessible from the database: The following relations provide access to count constraints: Relation ( Relation ( Relation ( Relation (
Relation ( SubRel is actually defined as the transitive closure of: Relation ( Relation (
Relation ( It turns out that the form of a type constraint for a unary relation is identical to the form of a subtype constraint. In fact, the rule that is created either way will be recognized as an instance of both. The only difference is in the default enforcement and the action to be taken in order to maintain consistency. The relevant relation for disjointness constraints is: Relation ( Relation (
## Rules that Maintain RelationsEfficiency considerations sometimes dictate that a relation that could be defined ought to be cached. For example, the definition is expensive to access, and the relation is accessed much more often than it is updated. In AP5, the way to get the right thing to happen is to create a rule that causes the (stored) relation to track the definition. This could be (and in fact used to be) done by consistency rules. Unfortunately, such an implementation does not quite achieve the same effect as a defined relation. For example, an update that appears to cause a change in a defined relation might trigger a consistency rule which "undoes" that change. If the defined relation were replaced by a stored relation that was maintained by another consistency rule, the attempt to "undo" the change would cause an abort (whereas the defined relation is free to change back). Instead of using consistency rules, AP5 has another type of rule, called a MaintainRule, which attempts to make a maintained relation behave just like a defined relation. This will enable users to start out by defining relations and later optimize their programs by changing them to maintained relations.
The only difference between defined and maintained relations (other than
performance) is that
defined relations can have update macros that say how the relations in
their definitions should be altered to change the truth value of the
definition. Of course a maintained relation has to be stored, so its
update macros have to describe how its stored value is changed. If you
want to maintain a defined relation with update macros, you'll have to
divide it into two relations:
Note: AP5 has a consistency rule that causes relations to be maintained whenever they have an implementation other than DEFINED and a definition. ("Defined" relations, i.e., those that are always derived from definitions, also have definitions, but their implementation is DEFINED.) The relation
Relation ( Relation (
Note: Maintained relations are stored in the manner specified by their implementations. For example, if you do (DefRelation PersonPhone :implementation structprop :definition ((x y) s.t. (E (office) (and (PersonOffice x office) (OfficePhone office y)))))you will get a structprop relation which tracks the definition. The relation Relation (
These rules always assume that, at the time of rule declaration, the
relation matches the definition, i.e., that the relation need only be
maintained incrementally. Usually this requires only that the
definition be declared before any updates that make it true, e.g., in
the PersonPhone example, before any PersonOffice or OfficePhone tuples
are added. By default, AP5 will generate an error if you try to
directly update a maintained relation, since this is supposed to be
done only be the maintaining rule. However, if you discover that the
maintained relation is wrong (for example if you failed to insert a
tuple before asking that the relation be maintained), you can update
it with
Variable ## MiscellaneousFirst come those things that are so miscellaneous that they don't even belong in one of the following sections:
The object of a high level compiler like AP5 is that you shouldn't have
to think about the algorithms it chooses. In general, this is all right
if the computations will be cheap. AP5 tries to warn you when this is
not the case. In particular:
## More esoteric wff syntaxBy default DefRelation declares a macro for the name of the relation being declared (unless it already has a function or macro definition). We will refer to this as a relation macro. If we define a binary relation R, then we get the following macro expansions: (R x y) => (?? R x y) (R x) => (any y s.t. (R x y)) (R) => (any x y s.t. (R x y))This macro also treats any symbol that looks like a variable named "$" as a new existential variable. Multiple uses of $ need not refer to the same object. Similarly, any symbol that looks like a variable named "?" (for compatibility with earlier versions of AP5, "~" is treated exactly the same as "?") is treated as a place holder for outputs to be generated. Any missing arguments are filled in by ?. Thus: (R ? y) => (any x s.t. (R x y)) (R ? $) => (any x s.t. (E (y) (R x y))) (R $ $) => (?? E (x y) (R x y)) (R $) => (any y s.t. (E (x) (R x y)))
In any syntactic context where a wff is expected, certain abbreviations are permitted. These are expressed by special syntax for arguments of primitive relations and are allowed regardless of whether the named relation has a relation macro. Arguments of primitive relations are interpreted as follows: - Names of bound variables refer to those variables.
- $ introduces a new existential variable as in the case of relation macros.
- Any list starting with a relation (name) followed by the right number of arguments or fewer, exactly one of which named "=" refers to any object which satisfies the relation when substituted for the =. Missing arguments are filled in with $'s.
- Any other list starting with a wff macro (see below) is macroexpand-1'd and the result is interpreted as the argument - note this list may contain = and may also macroexpand into things containing =.
- Anything else is treated as a lisp expression (or constant) to be evaluated in the context of bindings outside the wff. This case, of course, includes uses of relation macros as described above.
Note that ?, =, and $ are notational shorthands. Anything that can be expressed with them can also be expressed without them. They allow more concise (one might also say "cryptic") expression of certain things, by giving up control of where the new quantifiers are to be placed. The answer, in the case of $ and = is that the scope of the quantifier is just the primitive wff containing the $ or =. Thus (?? not (P x (Q x =))) => (?? not (E (y) (and (P x y) (Q x y))))as opposed to, say (?? E (y) (and (not (P x y)) (Q x y))) (?? A (x) (implies (P x) (Q x (R = $))))] => (?? A (x) (implies (P x) (E (y z) (and (R y z) (Q x y)))))as opposed to (?? E (y z) (A (x) (implies (P x) (and (R y z) (Q x y)))))] Although the rules above look complicated, the syntax is not really difficult to use. You can use expanddescription to find out for sure what an expression means. We present some examples for motivation: ((x) s.t. (and (spouse x $) (not (child x $)))) ; married people without children ((x) s.t. (office x (office p =))) ; people who have an office in common with p ((x) s.t. (office x (office p ?))) ; people in an arbitrarily chosen office of p ; note the difference (unless p necessarily has a unique office) ((x) s.t. (phone (office x =) 226)) ; people with an office that has 226 as a phoneNote that ((x) s.t. (office x)) is an error - the trailing $'s are
supplied only for lists that appear as arguments and not for top level wffs.
Wff syntax allows variables to be introduced (either by quantifiers
or descriptions) with types and equivalence relations
by using a symbol containing the characters "#" and "@".
In the most general form
a variable is introduced as
Currently defined macros include:
Special symbols are also supported on Also see the section on partial orders, which are implemented as macros.
When you create such macros for use in wffs you must inform AP5 of that fact
by adding them to the relation:
## Functions useful for extending the environmentThis section lists a number of internal functions that have been useful in previous attemots to extend the programming environment. We make no claims for completeness.
Function (
Function ( (any x s.t. (compare-relation relation position x) ifnone (dbo relation eql))except for a few special cases, which generate errors if error is non-NIL:
- If (anycomparison
*relation**position*) the value is T - If
*relation*is an equivalence relation the value is (list*relation*) - If
*relation*is defined in such a way that the specified argument is used only in equivalence relations, the value is a list of those equivalence relations.
Function (
Function (
Variable
## Advising, debugging, optimizing Rules
Rule triggering is performed by a match network conceptually similar to that
used by the OPS family of production systems interpreters.
The match network consists of objects called MatchNode's, identified
by the type
Every matchnode is responsible for detecting tuples matching a description
corresponding to the relations:
There are two ways in which the list (
Matchnodes are also related to each other via the relation:
The relations
## Advice for every transitionAs a convenience for causing something to happen after every database transition, we advertiseVariable ap5::*advice-for-every-transition*This is a list of functions of no arguments to which users may add their own entries. On every transition every such function will be called. The only real difference between such advice and an Automation Generator with the trigger (nil s.t. true) is that the advice will never be turned off by with-dormant-rules. (The uses we have seen for such advice are things like updating the display to reflect changes in the database.)
As a convenience to those who wish to write such code, the following
function is provided:
It is recommended that after using this function to identify interesting updates, further processing be done via normal AP5 mechanisms, so as to avoid having to worry about such things as equivalence relations.
## Debugging Rules
We advertise for purposes of debugging the fact that all rules
are invoked by
Also, at the start of every consistency cycle,
For purposes of performance monitoring, we advertise two internal
functions used for matching rule triggers:
## Optimizing RulesIt is not difficult to create special purpose matchnodes that interface to the match network even though they work very differently from matchnodes built by the rule compiler. However this degree of optimization seems not to be normally needed and so (until demand is demonstrated) we do not describe here how to do this. Rather we concentrate on mechanisms for giving the rule compiler advice that it can use to produce more efficient match networks.
For non primitive wffs, the relation
In the interest of efficiency, you may want to take a look at the triggers of the matchnodes that were built in order to enforce a rule, so you can declare some as No-Trigger's and deactivate them. Similarly, if you notice that certain updates take a long time, you might be interested in looking for costly and unnecessary matchnodes that are activated by the update.
Function (
Function (
In order to look at the triggers of matchnodes, it will be convenient to use
Function ( The following functions may be useful for debugging or for efficiency hacks, but of course, they might endanger the integrity of the database:
Function ( For example, one might do (++ No-Trigger '((x y) s.t. (and (Start (P x)) (Previously (Q y)))))if you knew (but AP5 didn't) that this was impossible. Similarly, you might do (++ No-Trigger '((x y) s.t. (and (Start (P x)) (Q y))))if you knew that this condition was not of any interest by itself but was only being used to trigger Of course, this declaration can also be used to tell the system not to worry about a condition that could in fact arise, if you're willing to take responsibility for either seeing that it doesn't or noticing and taking appropriate action when it does.
## Transition History
An additional piece of data that may turn out to be useful (more generally
than for debugging rules) is that AP5 records all the transitions.
[We reserve the right to change the representation] but as of this writing:
For each transition:
Direct records non-noop updates to stored relations (which may include inherits [This derives from a context mechanism that is no longer supported.]). DirectDelta is a version of Direct in which inherits that change the truth value of a tuple have been replaced by updates that explicitly describe the effect of the inherit (by pretending to be additions or deletions) and inherits that do not affect the truth value have been deleted. Indirect records "virtual updates" computed by triggers (described later). Maintain records updates to maintained relations. Again records updates that were noops or repetitions. Delta is the union of DirectDelta, Indirect and Maintain.
Function (
Function (
Variable
## Checkers
This section does not really describe any rules, but rather a hook that is
occasionally useful.
## Multiple Processes
Since multiple processes are not part of commonlisp, they have
received no attention in this manual. However, for machines that do
support processes there are some difficult database issues. In
particular, how can you write programs to run (and behave properly!)
while the database is changing in unpredictable ways? Even what
appears as a simple database query may return odd results. For
example, suppose you do (listof x s.t. (P x)). It is conceivable that
your query starts in a state where the answer ought to be NIL, that in
the course of evaluating the query an atomic update occurs which
yields a state in which the answer ought to be (1 2), and that the
query actually returns (2)! The point is that queries take time to
evaluate, and, even if they don't run while the database is being
updated, they can run partly in one state and partly in another. The
result might not actually be the "right" answer for any time during
which the query was being evaluated! Often this is not important.
However, if it is, you can use:
## Large WffsWffmacros and (inline) defined relations are a significant source of power for the user of AP5. Unfortunately, they cannot in general help AP5 to compile the code the user writes with them. (See the next section if you need convincing.) Thus one will occasionally see a concise looking piece of specification that takes a long time to compile, or cannot be compiled. One reason that it can take a long time to compile is that the short wff actually expands into a very long wff. In order to see the expanded form of a wff, you can use:Function ( expanddescription description
{:allowevalargs allowevalargs}
{:keepstarts keepstarts} ...)For example: (expanddescription '((x) s.t. (xor (relation x)(type x)))) ((Var-X) S.T. (OR (AND (A (Var-F76109) (NOT (RELATIONARITY Var-X Var-F76109))) (RELATIONARITY Var-X 1)) (AND (E (Var-F76108) (RELATIONARITY Var-X Var-F76108)) (NOT (RELATIONARITY Var-X 1))))) NIL NILThe value of allowevalargs should be T if you intend to use lisp
expressions as arguments. The additional values record the uses of
such lisp expressions and the uses of expressions to be used as
relations (in funcall and apply wffs). The value of keepstarts
should be T if you do not want START's translated into PREVIOUSLY's.
On occasion, you will notice that the resulting wff could be simplified. Alas, the simplifier used by AP5 is imperfect, and this can force the compiler to do extra work, or occasionally even fail where you might be able to succeed. Although we can imagine ways of improving the simplifier, it will probably always miss some simplifications that you can see. In the example above, the first disjunct is actually impossible - if something has an arity of one, then it must have an arity! In such a case, you can always lend a helping hand and provide the simplified version of the wff to AP5.
## Decaching Compiled Code (and other data)
AP5 does a lot of compilation in addition to the functions that you
explicitly ask to be compiled. It internally caches most of this
compiled code. Unfortunately, when you change some data that AP5 uses
in order to compile this code, the cached data becomes obsolete. This
section describes some of these caches and tells you how to decache it
should that become necessary.
## Relation testing, adding, deleting code
The macros ??, ++ and -- each store code in the
property lists of relations. If the tester, adder or deleter
change, this code should be decached (there's an
automation rule to do this). Similarly, if you change one of these
operations without updating the database (by redefining a function that
is used to macroexpand a database operation), you'll have to decache
this code in order to have the correct code installed (the next time you
attempt the operation). The value of the properties
## Code for Generating RelationsWhen code for generating a description (in this case the term "description" is used to include things with lisp expressions to be evaluated) is produced, a compiled version is cached. This code is associated with a canonical form of the description and used whenever matching descriptions are to be generated. This has two important consequences. First, subsequent generation of similar descriptions will be faster (, i.e., the first one is slower). Second, whenever the method for generating changes, the cache must be updated. There are rules to decache entries that may be affected by database activity, but if you redefine a function that is used in generating, you should decache whatever uses the old version.
The relation
Macro (
It is not necessary to explicitly cache generators for compound wffs that
are used by functions defined by defun if you use:
Since the first use of a generator is slower, some applications might want to preload the generator cache.
When you decache generators the default is not to recompile any
of them until they are needed. Sometimes this is a bad tradeoff.
If, for instance, you're about to save a world it would be better to
recompile all the decached generatores first.
Another use of this macro is that when you make a patch that decaches generators you can recompile them as part of the patch (so those who load the patch won't have to recompile them). This can be done by first recompiling the decached generators in your environment, then doing the decache that will be part of the patch, and finally putting (ap5::Recompile-Decached-Generators) in the patch file. Thus you evaluate something like this: (ap5::Recompile-Decached-Generators) ; this recompiles everything in the environment so only the things ; decached below will be included in the patch file (Decache-Rel ...) ; typically changes to DefRelation cause decaching tooand then compile a patch file that looks like this: (Decache-Rel ...) ; same as above (ap5::Recompile-Decached-Generators) ; compiling this causes the generators you just decached ; to be recompiled and recached in your environment, and ; also causes them to be saved on the patch file)Of course, you should make sure that the generators you save on the patch file only refer to relations that will be in the environments where the patch will be loaded.
It may also be useful to be able to change the data in the generator cache.
The most likely thing is to want to change the function that
actually does the generating. For a canonical pattern to be generated
(slot 1 of a generator-cache tuple), the function
## Code in the Match NetworkThe compilation of rules involves building "matchnodes", which contain compiled code of two kinds. One is code that generates objects that match some pattern. This code can stop working if the generators or testers become less capable. The other kind is code that recognizes whether tuples are the same. This can become obsolete if the equivalence relations used to compare the objects of the relations involved are changed (in which case other things may need to be fixed).
## Code for comparing tuples of RelationsThe comparison relations for a given relation are compiled into a piece of code that compares tuples for that relation. If you decide to change the comparisons for a relation after using that relation, you should decache that function. Note however, that this will not change the data stored for the relation, which might also be necessary if the comparison changes.
## Expansions of DefinitionsIn an effort to optimize the processing of definitions for defined relations, AP5 caches an expanded version of the definition of a relation in the ap5::EXPANDED-DEFN property of the relation. Should this definition change, the value should be decached. (An automation rule does this.) (I don't know what ought to happen to other things that were computed from the old definition. Are they still what you intended?)
## Decaching
Function (
Decache-rel is driven by the relation
## Dumping strange objects to compiled filesCompilation of some AP5 programs to files may apparently require that some nonstandard lisp object be dumped to the compiled file, e.g., a relation. For instance suppose the file contains the following:(defun subtype-of-person (type) (?? subtype type #,(dbo type person)))or (defrelation subtype-of-person :definition ((x) s.t. (subtype x #,(dbo type person))))The problem is that there is no commonlisp standard way to save the object #,(dbo type person) to a compiled file. In the first case we could get around this problem by changing the definition slightly: (defun subtype-of-person (type) (?? subtype type (dbo type person)))which incurs a runtime cost of computing (dbo type person) on every execution. However, this is not a solution to the second example, since defining wffs are not allowed to contain lisp expressions that have to be evaluated. They may only contain constants. Therefore a better solution would be something like: (defconstant *type-person* (dbo type person)) (defrelation subtype-of-person :defintion ((x) s.t. (subtype x *type-person*)))However, even this is not quite good enough, since macros may expand into forms that find they need to make up constants (and it may not be possible to stick defconstant forms inside the macro expansion). Our solution to this problem is Macro ( memo form)The first time this is evaluated, the form is evaluated and its result is stored. The form is not executed on later evaluations. The stored result is always returned as the value. This form therefore satisfies the usual definition of a constant since the values on all executions are EQ. Note, however, that this may not be "constant enough" - if the value is smashed, programs that access its fields can get different results. Also remember that other forms that are EQUAL may evaluate to different things. In any case, wff syntax considers lists starting with Memo to be constants. Thus we can write: (defrelation subtype-of-person :defintion ((x) s.t. (subtype x (memo (dbo type person))))) Macro ( constant form)This is similar to memo, but it does not save the value of the first execution. Rather the form is executed every time, and AP5 trusts that the values are "constant enough".
## Appendices## Additional declarations for relations and implementationsMost of what you need to do in declaring a relation is done by the DefRelation macro. Additional information less commonly needed includes:(++ subtype rel rel) ; for its sub/super types ## An example of an AP5 ProgramWe present a development of a "topological sort", as described in CACM of June 1985 in the "programming pearls" column, p. 573. The problem is to find a linear ordering for a finite set of nodes, which conforms to a provided partial ordering. The algorithm is to repeatedly find a node which has no predecessor, put it in the list, and remove it from the graph. If this can be done until the graph is empty (has no more nodes) then the order of elements in the list is an answer. Otherwise there is no answer (the graph has cycles). In AP5, I choose to represent the graph (which is, after all, a set of nodes and edges) by two relations, which in the prototype version will be declared as base relations:
(defrelation node :arity 1 :documentation "the set (type) of nodes") (defrelation edge :types (node node) :documentation "the set of edges") I will actually use the type constraint to remove the edges connecting nodes which are deleted. Nodes will be deleted merely by making them cease to be nodes. Now for some data:
(set-listof n s.t. (node n) '(a b c d e f g h i)) (set-listof n1 n2 s.t. (edge n1 n2) '((a b)(a f)(b f)(d c)(d h)(e b) (e d)(f h)(g e)(g c)(i e)(i c))) And now for the program:
(loop while (?? E (n) (node n)) collect ; while there are nodes (forany node#n s.t. ; find one with (not (E (x) (edge x n))) ; no predecessor (-- node n) ; remove it from the graph n ; and use it as next node ifnone (error "cycles in graph"))) (I G E D C A B F H) ; this was the result This program is, of course, not particularly efficient. If efficiency is a concern (the program is to be run often or on large problems) it can now be optimized. The most obvious problem is that the entire set of edges must be searched in order to find that a given node has no predecessors. This could be fixed by changing the implementation of the edge relation, e.g., making it a Two-Way-Structprop relation. This reduces the cost of determining whether a node has any predecessors to a constant.
Another problem is that the program may have to search the entire set of
nodes on each iteration to find one without a predecessor. This could
be fixed by maintaining the (unary) relation Node-With-No-Predecessor,
defined as At this point, we have reduced the cost of the program to near the lower bound. The cost of the I/O is proportional to the number of nodes plus the number of edges. The only remaining costs over and above this lower bound (as far as I can see) come from searching for a particular edge in the set of edges from or to a given node (to delete it), and similarly searching the set of nodes without predecessors. If these sets are expected to be large, the implementations can be further optimized, e.g., to use hashtables. ## index[sorted with all non-alphabetic characters were removed]++ -- ?? # (wff syntax) @ (wff syntax) $ (wff syntax) ~ (wff syntax) ~ ? (wff syntax) = (wff syntax) A (wff syntax) abort abortdata abort-transaction *advice-for-every-transition* again alist (representation) alist-single (representation) all (wff syntax) all-types-of alwaysrequire alwaysrequired and (wff syntax) anonymous relation (wff syntax) any anycomparison any-for aptypecase arity (concept) array (representation) array-single (representation) atomic atomic transition (concept) automation rule automationgenerator automationgenerator automationrule base (representation) basetype (derivation) basetype cache-generators canonicalize-trigger canonicalizer cardinality (derivation) cardinality-for-tuple cardinality-of-pattern change checker classification coded (derivation) compare-relation compound wff (concept) computed relation (concept) consistency rule consistencychecker consistencychecker consistency-cycles consistencyrule constant constraint (concept) constraint-enforcement-level create *current-rule* dbo dbobject (type) deactivate-matchnode deactivate-rule decache-rel-keyword-fn declare-type defattribute default-equivalence defaultrelsize defautomation defautomationgenerator defcomputation defconsistencychecker defderivation defdisjoint defined (derivation) defrelation (simple) defrelation (general) defrepresentation defun defun-typed delta derived relation (concept) derived-from derived-from* derived describe-algorithm describerel describerule description (concept) descriptionp direct disjointtypes doautomationrule doc doconsistencyrule domaintainrule do-matchcode do-matchcompare dont-tell-me-about do-s.t. E (wff syntax) effort enqueue-automation eql eql equiv (wff syntax) equiv (wff syntax) equivalence (concept) equivalence-relation exists (wff syntax) expanddescription extreme (derivation) false (wff syntax) fix-maintained-relation forany fortheonly from-abort functional-equivalence-testable gendeleter geneffortwarning generator-cache generators gensizewarning get-comparison global-history globalvar (representation) globalvar-single (representation) hashtable (representation) hashtable-single (representation) history history-label idisjointtypes if-then-else ignore-vars image-order implementation translator (concept) implementation implies (wff syntax) implies (wff syntax) inatomic inconsistency-reporter indirect individual (representation) individual-derived (derivation) initialstate inline (wff syntax) inlinerel insist intersectionclass (derivation) intransaction inverse-order isubrel let-typed lexicographic-order lisp-function (derivation) lisp-predicate (derivation) lisp-predicate-equivalence-relation listof literal-order lookup-gen loop maintain maintained relation (concept) maintainedrel maintainrule maintainrule make-dbobject map-updates matchautomation matchconsistency matchmaintain matchnode matchnodes-< matchnodes-> matchsuccessor matchvars matchwff *max-history-length* memo mnodetriggers most-specific-types-of multiple-for names-not-allowed-for-relations neverpermit neverpermitted none-for nontriggerable not (wff syntax) not-allowed-to-update notinline (wff syntax) no-trigger *no-single-value-stored* object (concept) optional-for or (wff syntax) order-by-class originalupdates parameter-list parse-var partial-index (representation) possibletoadd possibletoadd possibletodelete possibletodelete possibletoupdate *potential-wff-macro-form* previously (wff syntax) previously (macro) printdbo printer priority-order prog-typed proper-name prototype-mode rboundp reactivate-rule reader reladder relation) relation (concept) relationargnames relationarity relationimplementation relation-in-defn relation-in-defn* relationname relationname relationp relationsize reldeleter relgenerator relsize reltester relupdater restrict-cardinality returning reveal rmakunbound rule (concept) rule rulecode rulename rules-sensitive-to ruletrigger set-listof showdelta show-history SimpleGenerator SimpleMultipleGenerator s.t. start (wff syntax) start-ccycle stored relation (concept) structprop (representation) structure (representation) structure-single (representation) subrel subreltrigger subtype sum (derivation) symbol-functional-equivalentp symbolprop (representation) symbolprop-single (representation) symbol-relation tclosure (derivation) tell-me-about template testeffort testeffort theonly transaction tree (representation) treeprop (representation) treeprop+ (representation) trigger triggereffortwarning triggersizewarning true (wff syntax) tuple (concept) two-way-structprop (representation) typeconstraint type (concept) undo-to unionclass (derivation) unique-for update wff (concept) wffdefn wff-if wffmacro with-dormant-rules withwriteaccess |