@prefacesection(Preface)

This manual provides an introduction to AP5 to enable 
Lisp programmers to rapidly gain familiarity with AP5's programming
paradigm and to begin writing programs using AP5.  It is not intended to
serve as a reference manual.  For reference details, the reader should
consult the AP5 Manual @cite(AP5Manual).

It is assumed that the reader is familiar with the Common Lisp
programming language@cite(Steele) and understands basic
concepts of first order logic.  No familiarity with
ISI's Common Lisp Framework is assumed nor will its details
be described here. @Foot[The Common Lisp Framework @cite(CLFManual)
is a major application of AP5 that provides an object-based software
development environment.]

This document is divided into three chapters.  Chapter 1 is intended to
give an introductory overview of AP5 and to describe the
basic concepts.  After finishing this chapter, the reader should know
enough to start programming with AP5.  Chapter @Ref[using-AP5] 
provides some useful details about pragmatic aspects of using
the system.  Chapter 3 introduces selected advanced concepts.  

Readers with access to AP5 on a computer are encouraged to begin by
reading enough of Chapter @Ref[using-AP5] to be able to
execute the examples presented in the text as they read along.  All
readers are strongly encouraged to invent and experiment with their own
examples and applications.  

The typography used to denote the names of variables, relations, functions
and so forth and the notation used for descriptions of 
syntax follow the conventions of @i[Common Lisp: The Language]@cite(Steele).

@CHAPTER(An Introduction to AP5)

@SECTION(What is AP5?)

@index[AP5]AP5 is an extension to Common Lisp, as opposed to an independent
programming language.  A compiler translates the AP5 extensions into Lisp code 
sometimes relying on an extensive runtime system.  AP5 does not attempt to
duplicate the capabilities of Lisp nor does it restrict the
programmer to using a subset of the language.  AP5 is specifically
oriented toward enhancing the use of Common Lisp for
software prototyping.

AP5 enables users to write programs that incorporate higher level
@i[specifications].  It supports the notion of a @i[relation] as a
programming abstraction that can be used for data storage and retrieval
without commitment to a particular data structure or representation.
AP5 provides a notation for describing the logical organization of data
(a schema), for populating such an organization, for accessing portions
of it associatively (via queries) and for modifying the instantiated
data.  @i[This frees a programmer to initially concentrate on behavioral
functionality without concern for issues of representation and
efficiency.] @index[annotations]@i[Annotations] can be subsequently added to the
specifications which address representation and efficiency without
@Comment[in general]affecting functionality.  AP5 provides a built-in
library of annotations as well the capability to define new annotations.
These annotations are used by the AP5 compiler to optimize the database
accesses.

AP5's model of computation includes an active database.  An AP5
programmer can control the size or granularity of changes to the
database by specifying that some number of updates are to be carried out
in a single step, called an @i[atomic transition].  Using an extended
first order logic notation, a programmer can specify @i[rules] that
react to changes in the database.  

AP5 distinguishes two kinds of rules: consistency rules and automation rules.
@index[Consistency rules]@i[Consistency rules] state invariant conditions 
on data stored in the database. 
They monitor changes to the database and ensure that it obeys the desired
invariants.  They are triggered by a violation of the stated
invariants and either signal an error or attempt to carry out a repair
to restore the invariant condition.@Comment[Type checking, within user-defined
type hierarchies, utilizes this consistency rule mechanism.]
@index[automation rules]@i[Automation rules] provide for automatic invocation 
of programs.  They trigger computations in response
to logically specified transitions of the database.  Automation rules watch
for changes to the database that match user-specified criteria and then 
apply an associated response procedure to the relevant data.

@i[AP5's rules, in conjunction with the control over the granularity of
updates, simplify certain aspects of programming, @comment(beyond the
facilities provided in Common Lisp)such as the synchronization of data
updates and the detection and correction of runtime errors, and 
reduce the duplication of code.]

@Section(Understanding the basics)

@subSection(Objects, relations and facts)

AP5 provides access to an extensible global database of objects and
relations.  @index[objects]@i[Objects] are data elements like strings, integers, symbols
and so forth, or instances of user-defined types.  In fact, AP5 uses the
same notion of an object as Common Lisp -- any value that can be stored
in a variable is an object.  An @index(n-tuples)n-tuple, or simply
@index(tuples)@i[tuple], is a sequence of objects.  Tuples provide a
primitive way of representing associations among objects (e.g.,
@inlineprogramexample[<foo, "x", 123>]).

@i[Relations] serve as a convenient abstraction for organizing data.  A
@index(relation) relation contains a set of tuples all of which have the
same length, called the @index(arity)@i[arity] of the relation.
@Comment[Dennis wants a bridge here ***]

In writing programs with AP5, a programmer will often need to define new
relations.  To declare a new relation, the user must supply, at a
minimum, a name and an arity.  Relations are easily defined with the
@t(DefRelation) macro.

@index[DefRelation (macro)]
@indexsecondary[primary="DefRelation (macro)",secondary=":arity"]
@indexsecondary[primary="DefRelation (macro)",secondary=":documentation"] 
@t{DefRelation @i(name) &key :documentation :arity ... @>[@i(Macro)]}

For example, we can declare a new binary relation called @t[office] as follows:
@Begin(ProgramExample)
(DefRelation office@indexexample[office] 
  :arity 2 
  :documentation "(Office person number) associates a person with  
                  that person's office number.")
@End(ProgramExample)

The newly created
@t[office] relation will contain a time-varying set of 2-tuples in which the first
element is to represent a person and the second element is to represent the person's office number.

A @index(facts)@i[fact] corresponds to a combination of a relation and a tuple of the
appropriate arity.  A fact can be represented as a list whose car is the name of a 
relation and whose cdr is an appropriate tuple of objects.  
For example, @inlineprogramexample[(office Jim 22)] and 
@inlineprogramexample[(office Mary 12)] are facts. 
The first fact can be read as: @i[The tuple] @inlineprogramexample(<Jim 22>) 
@i[in the @t(office) relation], or less formally as: @i[Jim's office is number 22].

Facts in AP5 are either true or false.  No other truth values are
possible.  Truth in this case is relative to the database.  A given
state of the database divides the set of facts into two subsets - those
that are true and those that are false.  
@Comment[As we will see, facts that
are not directly decidable in terms of the state of the database but
that can be derived from true facts are also true.]
Thus, depending upon the state of the associated database, each of
the above facts may be true or false.  @Comment[This characteristic of databases
is sometimes called the "closed-world assumption."]

@subSection(@index[Database operations]Testing, asserting and retracting facts)

AP5 allows simple facts to be asserted or retracted from the
database and provides a way to query the database to determine
whether a given fact or logical composition of facts is true
or false.  The argument to each of the following macros is a spliced-in fact: 

@Begin(Description)
@indexentry[Key="??",Entry="@t<??> (macro)",Number]
@t<?? ,@@@i[fact]>@\Return @t[T] if @i[fact] is true and @t[NIL] otherwise (@index[queries]query).@>[@i(Macro)]

@indexentry[Key="++",Entry="@t<++> (macro)",Number]
@t<++ ,@@@i[fact]>@\Make @i[fact] true (@index[assertions]assertion).@>[@i(Macro)]

@indexentry[Key="--",Entry="@t<--> (macro)",Number]
@t<-- ,@@@i[fact]>@\Make @i[fact] false (@index[retractions]retraction).@>[@i(Macro)]
@End(Description) 

Asserting a true fact or retracting a false fact is a no-op.  Each of
these macros @i[quote] the supplied relation-name but @i[evaluate] the elements
of the tuple.  The macros @t[++] and @t[--] return no meaningful value.

Assuming that the office relation is initially false
for all tuples, here are some examples:

@Begin(ProgramExample)
(++ office 'Jim 12)
(?? office 'Jim 12) => T 
(++ office 'Mary 24)
(?? office 'Mary 12) => NIL
(?? office 'Jim 'Mary) => NIL
(?? office 'Mary 24) => T
(-- office 'Jim 12)
(?? office 'Jim 12) => NIL
@End(ProgramExample)

@subSection(Predefined relations)

A number of relations are predefined in AP5.  Many of these
are relational analogs of Lisp functions for object comparison (including equality) 
such as @t[eq], @t[eql], @t[equal], @t[string-equal], @t[=], @t[>], @t[<], @t[>=], @t[<=],
and mathematical operations such as @t[+], @t[-], @t[*], and @t[/].

@Begin(ProgramExample)
(?? eql "Mary" "Mary") => NIL
(?? equal "Mary" "Mary") => T
(?? = 3 3) => T
(?? < 5 3) => NIL
(?? + 2 2 4) => T
(?? > (length '(a b c d)) 3) => T
@End(ProgramExample) 
 
@index(types)@i[Types] in AP5 are unary relations (relations whose arity is 1).  
As in Common Lisp, AP5 types denote (possibly infinite) sets of objects.
All atomic Common Lisp type specifiers are recognized as types in AP5.  
These include @t[character], @t[integer], @t[list], @t[number], @t[string] and @t[symbol] 
as well as types introduced with @t[deftype], @t[defstruct] or @t[defclass].

@begin(programexample)
(?? symbol 'Jim) => T
(?? string 'Mary) => NIL
(?? integer 22) => T
(?? integer 3.91) => NIL
(?? integer (+ 2 3)) => T
(?? list (+ 2 3)) => NIL
@end(programexample)

A programmer can easily declare new types:

@Begin(ProgramExample)
(DefRelation person@indexexample[person]
  :arity 1	
  :documentation "(Person x) an object representing a person.")

(++ person 'Jim)
(++ person 'Mary)
(?? person 'Jim) => T
@End(ProgramExample)

@Comment[Using strings and other structures may require knowledge of equivalence]

@subSection(@index(Well-formed formulas)Well-formed formulas)

@index(Wffs)@i[Wffs], or @i[well-formed formulas], are
expressions in first-order logic.  @Comment[AP5 uses the language of first-order logic
to specify queries and ... ***]
The simplest wffs are the wff
constants, @t[TRUE] and @t[FALSE].  A @indexsecondary[primary="wffs",secondary="primitive wffs"]
@index[primitive wffs]@i[primitive wff] is a list whose
car is the name of a relation and whose cdr (the operands) is a list of
length equal to the arity of the relation.  
@Comment{When each operand of a primitive wff is an object, Lisp bound variable or Lisp expression, it comprises a fact.
We can test whether the fact is true by evaluating the Lisp form @t<(?? ,@@@i[wff])>.
All of the earlier query examples were of this form.}

Here are some examples of primitive wffs:
@Begin(ProgramExample)
(office 'Jim 22)
(office 'Jim 'Mary)
(string (concatenate "Mary" "and" "Jim"))
(= 2 (- 23 21))
(eql *package* (find-package "AP5-USER")) 
@End(ProgramExample)

@Comment[In addition to Lisp expressions, the operands of a primitive
wff may also be quantified variables (see below).]

@indexsecondary[primary="wffs",secondary="compound wffs"]
@index[compound wffs]@i[Compound wffs], can be constructed from
primitive wffs by the addition of logical connectives and/or logical quantifiers.
The following @index(logical connectives)logical connectives are 
recognized@Foot[Others are described in Section @Ref(shortcuts).]:

@begin(description, leftmargin 24, indent -24)
@index[NOT (logical connective)]@indexsecondary[primary="wff syntax",secondary="NOT"]
@t<(NOT @i(wff))>@\Negation of @i(wff)

@index[OR (logical connective)]@indexsecondary[primary="wff syntax",secondary="OR"]
@t<(OR @i(wff1 wff2 ...))>@\Disjunction of @i(wff1), @i(wff2) ...
 
@index[AND (logical connective)]@indexsecondary[primary="wff syntax",secondary="AND"]
@t<(AND @i(wff1 wff2 ...))>@\Conjunction of @i(wff1), @i(wff2) ...

@index[IMPLIES (logical connective)]
@t<(IMPLIES @i(wff1 wff2))>@\Implication between @i(wff1) and @i(wff2)
@end(description)

The meaning of a query for a wff whose car is a logical connective 
is determined by applying the standard rules of propositional logic:

@t<(?? NOT @i(wff1))> @math[@eqv] @t<(not (?? ,@@@i(wff1)))>

@t<(?? OR @i(wff1 wff2 ...))> @math[@eqv] @t<(or (?? ,@@@i(wff1))(?? ,@@@i(wff2)) ...)>

@t<(?? AND @i(wff1 wff2 ...))> @math[@eqv] @t<(and (?? ,@@@i(wff1))(?? ,@@@i(wff2)) ...)>

@t<(?? IMPLIES @i(wff1 wff2))> @math[@eqv] @t<(or (not (?? ,@@@i(wff1))) (?? ,@@@i[wff2]))>

@begin(programexample, above 2)
(++ office 'Jim 12)
(++ office 'Mary 24)
(?? not (office 'Jim 20)) => T
(?? or (office 'Jim 20)(office 'Jim 12)) => T
(?? and (office 'Mary 24)(office 'Jim 20)) => NIL
(?? implies (office 'Jim 12)(office 'Mary 24)) => T
@end(programexample)

The syntax for compound wffs also includes @index(logical quantifiers)
universally and existentially quantified variables:

@begin(description)
@indexentry[Key="A",Entry="@t<A> (universal quantifier)",Number]@indexsecondary[primary="wff syntax",secondary="A"]
@t<(A @i(vars wff))>@\universal quantification where @i(vars)
is a list of symbols used as operands of primitive wffs within @i(wff) 

@indexentry[Key="E",Entry="@t<E> (existential quantifier)",Number]@indexsecondary[primary="wff syntax",secondary="E"] 
@t<(E @i(vars wff))>@\existential quantification where @i(vars) 
is a list of symbols used as operands of primitive wffs within @i(wff)
@end(description)

Although all queries with quantified variables are meaningful as part of an AP5 specification,
not all such queries can be converted to operational programs. 

@begin[programexample]
(?? E (i) (< 3 i)) => TRANSLATION ERROR 
(?? A (x) (implies (= x 5) (< x 6))) => T 
@end[programexample]

In general, only primitive wffs can be asserted or retracted. 

@begin[programexample]
(++ or (office 'Fred 18)(office 'Fred 20)) => TRANSLATION ERROR
(?? A (x y) (implies (office x y) (integer y))) => T
(++ A (x y) (implies (office x y) (integer y))) => TRANSLATION ERROR
@end[programexample]
@COMMENT[(++ A (x) (implies (> x 1) (> x 0)))]

@SubSECTION[@index(Descriptions)Descriptions]

A @i[description] is a list of the form @t[(@i(vars) s.t. @i(wff))]
where @i(vars) is a list of variables used freely in @i(wff).  A
description denotes the set of all tuples of values that, when substituted for
@i[vars], satisfy @i[wff].@comment[Like a relation, a description can be
used to distinguish those objects for which wff is true.]  As we will
see, descriptions are very useful in describing generators for relations,
triggers for rules and in defining new relations.

@indexsecondary[primary="descriptions",secondary="ground descriptions"]
A @index[ground descriptions]@i[ground description] is a
description having the property that all of the
operands of its constituent primitive wffs are constants, quantified
variables, or variables from the variable list of the description
(i.e. no operand is a non-constant Lisp expression).
Ground descriptions can serve as unnamed relations (analogous to the use
of lambda expressions as functions in Lisp) and can in general be
substituted wherever relation names may appear.  

Here are some example ground descriptions:
@Begin(ProgramExample)
((x y) s.t. (office x y))
((p i) s.t. (and (office p i)(> i 15)))
((n) s.t. (E (person) (office person n)))
@End(ProgramExample)

The following examples illustrate the substitution of a ground description 
for the name of a relation in a query:
@Begin(ProgramExample)
(++ office 'Jim 12) 
(++ office 'Mary 24)

(?? ((p i) s.t. (and (office p i)(integer i))) 'Mary 24) => T
(?? ((p i) s.t. (and (office p i)(integer i))) 'Jim 13) => NIL
(?? ((p i) s.t. (and (noffice p i)(> i 15))) 'Mary 24) 
    => TRANSLATION ERROR

@End(ProgramExample)

@subSECTION[Generating the tuples of a relation]

AP5 provides @index[generators]generators for certain relations, so that programs can
iterate through the tuples of these relations.  However, not all relations can be
generated (e.g., @inlineprogramexample[((x) s.t. (and (integer x)(> 0 x)))]).
Remember that ground descriptions are implicit definitions of relations.

AP5 has extended the Common Lisp @t(loop) macro to provide access to this capability.  
A @t[do-s.t.] macro is also defined for
programmers who prefer the syntax of the Common Lisp @t[dolist] macro.  

@indexsecondary[primary="generators",secondary="Loop"]  
@index[loop (macro)]
@t<loop for ,@@@i[description] @i(iteration-body)>@>[@i(Macro)]
@linkedtext{Iterate over the set of tuples that satisfy @i(description).
For each iteration the variables from the @i[vars] list of the @i(description)
are bound to the elements of some satisfying tuple.  These variables can be
accessed lexically within @i(iteration-body).}

@indexsecondary[primary="generators",secondary="Do-s.t."]
@index[do-s.t. (macro)]
@t<do-s.t. (@i[vars wff] [@i(resultform)]) {@i[declaration]}@+(*) {@i[tag] || @i[statement]}@+(*)>@>[@i(Macro)] 
@linkedtext{@t<Do-s.t.> provides a way of iterating over the description @t<(@i(vars) s.t. @i(wff))> with a syntax analogous to the 
Common Lisp @t[dolist] macro.}

@Begin(Group)

Here are some example generators:

@Begin(ProgramExample)
(loop for x in '(John Jim Mary Fred Dave Jane)
      as y in '(18 12 24 18 10 16)
      do (++ office x y))

@hinge
(loop for (x) s.t. (E (y) (and (office x y) (= y 18))) collect x)
      => (FRED JOHN)

(let (output)
  (do-s.t. (x (E (y) (and (office x y) (= y 18))) output)
    (push x output))) 
      => (JOHN FRED)

(loop for (i) s.t. (and (integer i)(< 3 i)) collect i)
      => TRANSLATION ERROR

(loop for (number) s.t. (office x 18) count t) => 2 

@End(ProgramExample)
@End(Group)
 
@COMMENT (base,  full-index,  treeprop relations can be generated)
AP5 provides a number of macros for common generator idioms that could
also be written with the @t(do-s.t.) or @t(loop) macros.  The @t<any>
and @t<theonly> macros are used to retrieve a single tuple of values that
match a description:

@indexsecondary[primary="generators",secondary="Any"]
@index[any (macro)]@t<any ,@@@i[description] [ifnone {@i(form)}@+(+)]>@>[@i(Macro)]
@linkedtext{If the description is satisfied, one set of values for the variables in 
@i[vars] is returned as multiple values.  If the description is not satisfied, the
sequence of 
@t[ifnone] @i[forms] (an implicit @t[progn]) will be evaluated (the default is to generate an error)
and the last value(s) returned.  @t<Any> effectively makes an
arbitrary selection from the set of satisfying tuples.}

@indexsecondary[primary="generators",secondary="TheOnly"]
@index[TheOnly (macro)]@t<theonly ,@@@i[description] [ifnone {@i(form)}@+(+)] [ifmany {@i(form)}@+(+)]>@>[@i(Macro)]
@linkedtext{This is like @t[any] except that if multiple tuples satisfy the
description, the sequence of @t[ifmany] @i[forms] (an implicit @t[progn]) will be evaluated (the default is to
generate an error) and the last value(s) returned.  @t<Theonly> is
typically used to guarantee that exactly one tuple matches
the description.}

@Begin(ProgramExample)
(any (x y) s.t. (office x y)) => MARY, 24 [arbitrary selection]
(theonly (x) s.t. (office x 24)) => MARY
(theonly (y) s.t. (office 'Jim y)) => 12
(any (x) s.t. (office x 20) ifnone nil) => NIL
@End(ProgramExample)

The @t<forany> and @t<fortheonly> macros are used to perform some operation on 
a single set of values that match a description:

@indexsecondary[primary="generators",secondary="ForAny"]
@index[ForAny (macro)]@t<forany ,@@@i[description] {@i(do-form)}@+(*) [ifnone {@i(form)}@+(+)]>@>[@i(Macro)]
@linkedtext{Analogous to @t[any] but if the description is satisfied, the sequence of 
@i(do-forms) is evaluated (an implicit @t[progn]) with variables in  
@i[vars] bound to the elements of some satisfying tuple.  The value(s) of the last @i[do-form] are returned.}

@indexsecondary[primary="generators",secondary="ForTheOnly"]
@multi<name=fortheonly, syntax=",@@@i[description] {@i(do-form)}@+(*) 
[ifnone {@i(form)}@+(+)] [ifmany {@i(form)}@+(+)]", type=Macro>
@index[ForTheOnly (macro)]
@linkedtext{Analogous to @t[theonly] but if the description is satisfied, 
the sequence of @i(do-forms) is evaluated with the variables in @i[vars] 
bound to the set of satisfying values.}

@Begin(ProgramExample)
(forany (person) s.t. (E (n)(office person n)) (string-capitalize person))
	=> "Mary" [arbitrary selection]
(fortheonly (x) s.t. (office x 99) (-- office x 99) ifnone 'none)
        => NONE
@End(ProgramExample)

The @t<listof> and @t<set-listof> macros are used to retrieve or to store
the set of tuples that match a description:

@indexsecondary[primary="generators",secondary="Listof"] 
@index[listof (macro)]@t<listof ,@@@i[description]>@>[@i(Macro)] 
@linkedtext{If @i[description] contains contains only one variable in its @i(vars) list, this is
equivalent to @t[(loop for ,@@@i[description] collect (car @i(vars)))] otherwise it is equivalent to 
@t[(loop for ,@@@i[description] collect (list ,@@@i(vars)))].}

@index[Set-Listof (macro)]@t<set-listof ,@@@i[description] @i(tuple-list)>@>[@i(Macro)] 
@linkedtext{@t[Set-listof] provides a way to set or initialize the tuples that match a description.
Note that the wff in @i(description) must be a primitive wff.}

@begin(programexample)
(set-listof (p n) s.t. (office p n)
	'((JOHN 18) (JIM 12) (MARY 24) 
	  (FRED 18) (DAVE 10) (JANE 16)))
(listof (p n) s.t. (office p n)) =>
     ((JANE 16) (DAVE 10) (FRED 18) (MARY 24) (JIM 12) (JOHN 18))
(set-listof (x) s.t. (office x 18) '(FRANK)) 
(listof (p n) s.t. (office p n)) =>
     ((FRANK 18) (JANE 16) (DAVE 10) (MARY 24) (JIM 12))
(set-listof (p n) s.t. (office p n)
	'((JOHN 18) (JIM 12) (MARY 24) 
	  (FRED 18) (DAVE 10) (JANE 16))) 
(listof (p n) s.t. (office p n)) =>
     ((FRED 18) (JOHN 18) (JANE 16) (DAVE 10) (MARY 24) (JIM 12))
@end(programexample)

To obtain a list of the people who share an office
we might evaluate the following:

@begin(programexample)
(listof (x) s.t. (E (o y) (and (office x o)(office y o))))
    => (MARY FRED JOHN JANE DAVE JIM)
@end(programexample)

This result was probably @i[not] what we expected since it includes all people with offices.
To find out what is going wrong, we can query AP5 to find out who shares an office with Mary.

@Begin(ProgramExample)
(listof (x) s.t. (E (o) (and (office x o)(office 'Mary o))))
    => (MARY)
@End(ProgramExample)

We failed to specify 
in the description that @t[x] and @t[y]
must be distinct (i.e., not equivalent@Foot[Section @Ref(equiv) of this
manual discusses equivalence in AP5 in more detail.]).
The corrected generator and result are:

@Begin(ProgramExample)
(listof (x) s.t. (E (o y) (and (office x o)
	                       (office y o)
	                       (not (eql x y)))))
    => (JOHN FRED) 
@End(ProgramExample)

@SUBSECTION[@index[Atomic transitions]Atomic database transitions]

@label(atomic)
The AP5 database changes state with every assertion or retraction of a fact
(unless the asserted fact is already true or the retracted fact is already false). 
@Comment{The concept of an @i[atomic transition] gives a programmer greater control
over the granularity of these changes.  The @t[Atomic] macro requires all 
changes to the database within its dynamic scope to be performed at the same time.  
Thus, there is no state in
which some of these changes have been carried out while others are
pending.  Furthermore, if there are contradictory updates, e.g., the same 
fact is asserted and retracted within a single atomic transition,
the transaction will abort.}
@i[Atomic transitions] allow a programmer to group database updates so that the
database moves directly from one meaningful state to the next.  The
importance of this is three-fold.  First, asynchronous processes are
prevented from accessing the database in an inconsistent state.  This is
a simple form of resource locking.  Second, certain rules can alter the
updates within a transition to maintain the consistency of the database
and rules can be specified that trigger upon complex transitions.  
Third, atomic transitions allow the programmer to control the state 
of the database seen by the application program.  Any
database retrievals performed to compute the updates for an atomic transition will access
the database as it exists in the state prior to the transition.
This eliminates the need to have programs temporarily store the old state
of the database while computing the new state.

The @t[Atomic] macro requires all changes to the database within its
dynamic scope to be combined within a single transition, i.e., there is
no visible state in which some of the changes have been carried out while 
others are pending.  The transaction will be aborted
if @Comment{an @t[Abort] macro is executed or} 
contradictory updates are encountered,
e.g., the same fact is asserted and retracted,
within the @t[Atomic].

@index[Atomic (macro)]@t<Atomic {@i(form)}@+(*) [ifabort {@i(abortform)}@+(*)] 
[ifnormal {@i(normalform)}@+(*)]>@>[@i(Macro)]
@linkedtext{The sequence of @i[forms] is evaluated (an implicit
@t[progn]) but no updates take effect until all have been successfully
evaluated.  If any of these @i[forms] cause an abort, the database is
@i[not] changed and the sequence of @i[abortforms] is evaluated.  If the
@i[forms] are successfully evaluated, the database is updated (subject
to consistency rule validation) and the sequence of @i[normalforms] is
evaluated.}

Suppose that there were a rule that would become violated whenever a person had either more
or less than one office.  To update an
office without violating this rule, an 
@t[Atomic] would have to be used:

@begin[programexample]
(atomic (++ person 'Kelly)
	(++ office 'Kelly 18))

(theonly (n) s.t. (office 'Kelly n)) => 18

(atomic (-- office 'Kelly 18)
	(++ office 'Kelly 22))
@end[programexample]

@SECTION(Declaring @index(relation)relations)

AP5 distinguished three kinds of relations: transition relations,
derived relations and computed relations.  The contents of a @i[transition relation]
are determined by database transitions (explicit assertions and retractions of tuples),
i.e., a transition relation contains only
those tuples that have explicitly been asserted into the relation more
recently than they have been retracted.  A @i[derived relation]
is defined by a computation that depends upon the contents of other (less
derived) relations.  A @i[computed relation] contains an
@i[invariant] set of tuples that is determined by a computation that
is @i[not] dependent on the contents of the database.

@subsection(@index[Transition relations]Transition relations)

@indexsecondary[primary="relations",secondary="transition relations"]
Transition relations are the most basic relations in AP5.  The name refers to the fact that
transitions between states of the database define the contents of these
relations.  The @t[office] relation we have been using in the examples
so far is a transition relation.

At a minimum, to define a transition relation a user must supply a name
and arity to @t[DefRelation].  

Let's define another transition relation and try some generators:

@begin[Group]
@begin(programexample)
(DefRelation office-phone@indexexample[office-phone]
  :arity 2 
  :documentation "(Office-phone office-number phone-extension) associates an 
                  office with its phone extension.")
 
@hinge
(set-listof (x y) s.t. (office-phone x y)
	'((10 123) (12 333) (14 542) (16 234)
	  (18 562) (20 405) (22 239) (24 342)))

@hinge
(set-listof (o n) s.t. (office o n)
	'((JOHN 18) (AMY 24) (JANE 16) (DAVE 10) 
          (FRED 18) (MARY 24) (JIM 12) (MARK 14)))

@hinge
(?? office 'John 18) => T
(theonly (x) s.t. (office 'John x)) => 18
(theonly (x) s.t. (office x 23)) => UNSATISFIED ERROR

@hinge
(any (x) s.t. (office x 16)) => JANE 

@hinge
(listof (p n) s.t. (E (o) (and (office p o)(office-phone o n)))) 
    => ((MARK 542)
	(JIM 333)
	(MARY 342)
	(FRED 562)
	(DAVE 123)
	(JANE 234)
	(AMY 342)
	(JOHN 562))

@hinge
(any (x n) s.t. (E (y) (and (office x y)(office-phone y n))))
    => MARK, 542 [arbitrary selection]

@End(ProgramExample)
@end[Group]

@SUBSECTION[@index[Defined relations]Defined relations]

@indexsecondary[primary="relations",secondary="defined relations"]
Not every relation needs to be explicitly populated with data.  Much of the power of AP5 
comes from its ability to support relations derived from 
other existing relations and Lisp computations.
Defined relations are one kind of derived relation.
A @i[defined relation] is a relation defined strictly in terms of a ground description.
Any relations referenced in the description must already have been declared, thus
recursive definitions are not allowed@Foot[As we will see in Section @Ref[derived], 
the transitive closure of a relation can be defined.]. 
To declare a defined relation, the user supplies the defining description
as the @t[:definition] argument to @t[DefRelation].

@indexsecondary[primary="DefRelation (macro)",secondary=":definition"]
@t[DefRelation @i(name) &key :documentation :arity :definition ...]@>[@i(Macro)] 

For example, we could define a new relation @t[extension] from a description we generated earlier: 
@inlineprogramexample[((x y) s.t. (E (office-number) (and (office x office-number) (office-phone office-number y))))].

@begin(programexample)
@indexexample[extension]
(DefRelation extension
  :definition ((x y) s.t. (E (office-number)
	                       (and (office x office-number)
	                            (office-phone office-number y))))
  :documentation "(Extension person phone-extension) associates a person 
                  with the phone-extension of his or her office.") 
@end(programexample)

Notice that it wasn't necessary to explicitly supply an arity in this declaration
since the arity was implicit in the definition, i.e., there are two variables in 
the variable list of the description.

@begin(programexample)
(loop for (x y) s.t. (extension x y)
	        do (format T "@f0[]%Name: @f0[]A@f0[]12TExtension: @f0[]D" x y))
    =>  Name: MARK  Extension: 542
        Name: JOHN  Extension: 562	 
        Name: AMY   Extension: 342
	Name: JANE  Extension: 234
	Name: DAVE  Extension: 123
	Name: FRED  Extension: 562
	Name: MARY  Extension: 342
	Name: JIM   Extension: 333
	NIL 
@end(programexample) 

A defined relation can be treated just like a transition relation with the exception
of updating.  Unlike transition relations, tuples of defined and other derived relations 
cannot be updated unless updating procedures have been
provided (see Section @Ref[capabilities]).

We can demonstrate this with our newly defined relation:
@begin(programexample)
(?? E (x) (extension 'Jim x)) => T
(theonly (x) s.t. (extension 'Jim x)) => 333
(?? extension 'Mark 14) => NIL
(?? E (x) (extension x 777)) => NIL
(++ extension 'Mark 123) => UPDATE VIOLATION
@end(programexample)

A programmer can also use descriptions to define new
types@Foot{@t[Integer-in-range]@index[integer-in-range (relation)] is
a predefined relation in AP5 whose three operands are integers and
whose first operand is @t[>=] the second operand but @t[<=] the third operand.}:

@Begin(ProgramExample)
@indexexample[office-number]
(DefRelation office-number 
  :definition ((x) s.t. (integer-in-range x 1 99))
  :documentation "(Office-number i) an integer from 1 to 99 inclusive")

(?? office-number 845) => NIL
(?? office-number 84) => T
@End(ProgramExample) 

We can define an @t[office-mate] relation using a slight modification of
a description introduced earlier:

@begin(programexample)
@indexexample[office-mate]
(DefRelation office-mate
  :definition ((p1 p2) s.t. (E (o) (and (office p1 o)
                                        (office p2 o)
                                        (not (eql p1 p2))))))
@end(programexample)

A query to find all pairs of people who share an office
would then be simply: 

@begin(programexample)
(listof (x y) s.t. (office-mate x y))
    => ((AMY MARY) (JOHN FRED) (MARY AMY) (FRED JOHN))
@end(programexample)  

@subSECTION(Derived relations)
@Label[Derived]

Defined relations are one particularly useful kind of
relation that is derived from existing relations and Lisp computations.

@indexsecondary[primary="relations",secondary="derived relations"]
In general, a @index[derived relations]derived relation is a relation
defined in terms of transition relations and/or other (less) derived
relations.  To determine whether a given tuple is true for a derived
relation it is necessary to perform a computation that examines the
tuples of the relations from which it is derived.  Derived relations are
specified by the @t[:derivation] keyword of @t(DefRelation).

@indexsecondary[primary="DefRelation (macro)",secondary=":derivation"]
@multi{name=DefRelation, args=name, keys=" :documentation :arity :definition
:derivation ...", type=Macro}

AP5 recognizes several predefined @index[derivation idioms]derivation idioms for relations.  In addition,
a programmer is free to add new derivation idioms.  The @t[tclosure], @t[cardinality], @t[sum] and @t[extreme] derivation
idioms are described in this section.

@begin(description)
@indexsecondary[primary="derivation idioms",secondary="tclosure"]    
@index[tclosure (derivation idiom)]@t[tclosure]@\@Multiple[A binary relation that 
is defined as the transitive closure of some other relation.  A transitive 
closure@index[transitive closure] is effectively the result of iterating a relation 
any finite, non-zero, number of times and so approximates a recursive definition.

@t{(tclosure @i(relation-name))}]
@end(description)

@begin[programexample]
(DefRelation forward-phone@indexexample[forward-phone] 
  :arity 2
  :documentation "(Forward-phone x y) associates extension x 
                  and extension y when x is forwarded to y.")

(++ forward-phone 333 123)
(++ forward-phone 123 542)
(++ forward-phone 405 239)
(?? forward-phone 333 123) => T

(DefRelation forwarding-path@indexexample[forwarding-path]  
  :derivation (tclosure forward-phone))

(listof (n) s.t. (forwarding-path 333 n)) => (123 542)
@end[programexample]

We can write a program that will find the office
number of the phone that will ring if anyone tries to call Jim's
extension as follows:

@begin[programexample]
(any (x) s.t. (E (a b) (and (extension 'Jim a) 
	                    (or (forwarding-path a b)
			        (= a b)) 
	                    (not (E (y) (forward-phone b y)))
	                    (office-phone x b)))) => 14 
@end[programexample]

The @t[cardinality], @t[sum] and @t[extreme] derivations are calculated
in terms of certain projections of the tuples of some target relation.
These projections are specified by a pattern@indexsecondary[primary="patterns",secondary="in derivation idioms"] that is a list,
corresponding to the operands in the target relation, whose elements are the
symbols @t[input] or @t[output] (this list also contains, for the @t[sum] and @t[extreme]
derivations, respectively, one instance of the
symbol @t[sum] or @t[extreme]).  Each unique set of values for the
@t[input] positions of a pattern defines a projection of matching
tuples in the relation.  There will be one tuple in the derived relation
for each projection of the target relation.

@begin(description)
@indexsecondary[primary="derivation idioms",secondary="cardinality"]
@index[cardinality (derivation idiom)]@t[cardinality]@\@Multiple[A relation that 
counts the number of tuples in projections of some other relation. 
Each derived tuple is a concatenation of
a unique set of values in the target relation
corresponding to the @t[input] positions of the pattern (a projection) 
and a number representing
the number of tuples in the target relation that match that projection.

@t{(cardinality @i(relation-name) @i(pattern))}]
@end(description)

@Begin(ProgramExample)
@indexexample[people-per-office]
(DefRelation people-per-office
  :derivation (cardinality office (output input))
  :documentation "(People-per-office office-number n) associates 
                  an office number with the number of occupants.")

(listof (office n) s.t. (people-per-office office n))
    => ((16 1) (10 1) (18 2) (24 2) (12 1) (14 1))
@End(ProgramExample) 

@begin(description)
@indexsecondary[primary="derivation idioms",secondary="sum"] 
@index[sum (derivation idiom)]@t[sum]@\@Multiple[A relation that 
calculates the sum of the values of tuples in projections of some other relation.  
Each derived tuple is a concatenation of
a unique set of values in the target relation
corresponding to the @t[input] positions of the pattern (a projection) 
and a number representing the sum of the elements corresponding to the @t[sum] position 
of tuples in the target relation that match that projection.  
The @t[sum] position is assumed to contain only numbers.

@t{(sum @i(relation-name) @i(pattern))}]
@end(description)

@Begin(ProgramExample)
@indexexample[overtime]
(DefRelation overtime
  :arity 3
  :documentation "(Overtime person month hours) associates a person
                  with a number representing a month of the year  
                  and a number that is the amount of overtime in 
                  hours the person worked that month.")

@indexexample[total-overtime-per-month]
(DefRelation total-overtime-per-month
  :derivation (sum overtime (output input sum))
  :documentation "(Total-overtime-per-month month #hours) associates
	          a month with a number representing the total number 
                  of overtime hours worked that month.")

@indexexample[total-overtime-per-person]
(DefRelation total-overtime-per-person
  :derivation (sum overtime (input output sum))
  :documentation "(Total-overtime-per-person person #hours) associates 
                  a person with a number representing the total number 
                  of overtime hours (across all months) worked by that 
                  person.")
@End(ProgramExample)

@begin(description)
@indexsecondary[primary="derivation idioms",secondary="extreme"] 
@index[extreme (derivation idiom)]@t[extreme]@\@Multiple[A relation that 
finds the extreme values of tuples in projections of some other relation.
The derived tuples are
a subset of the tuples in the target relation
that have an extreme value (according to the specified ordering function)
in the @t[extreme] position of the pattern.

@t{(extreme @i(relation-name) @i(ordering-relation) @i(pattern))}]
@end(description)

@Begin(ProgramExample)
@indexexample[maximum-monthly-overtime]
(DefRelation maximum-monthly-overtime
  :derivation (extreme overtime >= (output input extreme))
  :documentation "(Maximum-monthly-overtime month #hours) associates 
                  a month with a number representing the maximum number 
                  of overtime hours worked by any person that month.")
@End(ProgramExample)

@subSECTION(Computed relations)

@indexsecondary[primary="relations",secondary="computed relations"]
A @index[computed relations]computed relation is a relation defined by a
Lisp computation that does @i[not] depend on the contents of the AP5
database.  The contents of a computed relations are invariant.  Derivation
idioms are equally suitable for specifying derived or computed
relations; the key distinction is whether or not the tuples of the
relation ever change.
Computed relations are
specified by the @t[:computation] keyword of @t(DefRelation).

@indexsecondary[primary="DefRelation (macro)",secondary=":computation"]
@multi{name=DefRelation, args=name, keys=" :documentation :arity :definition
:derivation :computation ...", type=Macro}

The following predefined derivation idioms are frequently used to 
specify computed relations:

@begin(description, leftmargin 18, indent -18)
@indexsecondary[primary="derivation idioms",secondary="coded"] 
@index[coded (derivation idiom)]@t[coded]@\@Multiple[A relation computed by a Lisp form.

@t{(coded (@i(vars) s.t. @i(lispform)))}
@\@i(Vars) is a list of variables used freely in @i(lispform) and @i(lispform)
should return a non-NIL value if the relation is true for some set of values
for @i(vars).] 

@indexsecondary[primary="derivation idioms",secondary="lisp-predicate"]  
@index[lisp-predicate (derivation idiom)]@t[lisp-predicate]@Multiple[@\A relation 
computed by a Lisp predicate.

@t{(lisp-predicate @i(predicate-name))}]

@indexsecondary[primary="derivation idioms",secondary="lisp-function"]    
@index[lisp-function (derivation idiom)]@t[lisp-function]@\@Multiple[A relation 
computed by a Lisp function.  The arity of the relation is equal to the sum 
of the number of inputs and outputs of the function.  

@t{(lisp-function @i(function-name input-arity output-arity))}

For relations defined with this idiom, it is possible both to test
for tuple membership and to generate any subset of the @i(output-arity) elements of tuples given
the remaining elements as inputs.]
@end(description)

@Begin(ProgramExample)
(DefRelation list-of-integers@indexexample[list-of-integers]  
   :arity 1
   :computation (coded ((x) s.t. (and (listp x)
				      (every #'integerp x)))))

(?? list-of-integers '(12 a 18)) => NIL
(?? list-of-integers '(235 74 46 3 1)) => T

(DefRelation evenp@indexexample[evenp] 
  :arity 1 
  :computation (lisp-predicate evenp))

(?? evenp 23) => NIL
(?? A (x y) (implies (office x y)(evenp y))) => T

(defun factorial (i)
  (when (and (integerp i)(> i 0)) 
    (if (= i 1) i (* i (factorial (- i 1))))))

(DefRelation factorial@indexexample[factorial]   
  :computation (lisp-function factorial 1 1)) 

(?? factorial 6 720) => T
(theonly (x) s.t. (factorial 7 x)) => 5040
@End(ProgramExample)  

@SECTION(Using @index[rules]rules)

Rules serve as a mechanism for maintaining conditions and 
reacting to changes or proposed changes to the database.
The two kinds of rules in AP5 are consistency rules and automation rules.

@SUBSECTION(@index(consistency rules)Consistency rules)
@Label[cons-rules]

@indexsecondary[primary="rules",secondary="consistency rules"]
@i[Consistency rules] maintain invariants stated as wffs.  A consistency
rule intercepts a proposed transition to the database that would
violate its associated invariant.  In addition to detecting
violations, a consistency rule allows the AP5 programmer to specify how
to react to the situation, i.e., how to
attempt to restore (repair) the invariant.  The repair procedure can augment the transition by adding or
retracting tuples from the database but it currently cannot reverse updates already included
in the transition.  Any and all consistency rules whose invariants are
violated by a given atomic transition will be triggered and their invariants must be 
restored for the transition to occur.  Repairs that
restore an invariant but that are incompatible with other repairs to the
transition will cause an abort.

A consistency rule has a name, a trigger and optionally, a repair procedure.
The name is a unique symbol used for identifying the
rule.  Declaring a rule with the same name as an existing rule is
treated as a redefinition.  The trigger is a wff specifying some invariant
condition of the database.  Like the wff of a ground description, all
operands of its constituent primitive wffs must be constants or
quantified variables.  The repair is a Lisp function that is
intended to restore the invariant.  The arguments to this function
are the values of any outermost quantified variables bound in the trigger of the rule.

Two macros are provided for declaring consistency rules:

@index[AlwaysRequired (Macro)]
@t[AlwaysRequired @i(name trigger) &key :repair :documentation]@>[@i(Macro)] 
@linkedtext{@t[AlwaysRequired] creates a rule that reacts when the condition in the trigger would become false.}

@index[NeverPermitted (Macro)]
@t[NeverPermitted @i(name trigger) &key :repair :documentation]@>[@i(Macro)] 
@linkedtext{@t[NeverPermitted] creates a rule that reacts when the condition in the trigger would become true.}

It is often useful for a rule's trigger and/or repair to be able to refer to either the (consistent)
database state prior to the atomic transition or to the proposed
(inconsistent) state.  Wffs within the trigger or repair of a
consistency rule normally refer to the state proposed after the
transition.  AP5 provides some additional wff syntax for 
@indexsecondary[primary="wffs",secondary="temporal wffs"]@index[temporal wffs]temporal reference.
@indexsecondary[primary="wff syntax",secondary="Previously"]
@index[Previously (wff macro)]@t[Previously] means evaluate the wff
relative to the state prior to the transition.  @indexsecondary[primary="wff syntax",secondary="Start"]
@index[Start (wff macro)]@inlineprogramexample[Start @i(wff)] means 
@inlineprogramexample[(AND @i[wff] (NOT (Previously @i[wff])))]
where the wff outside of the scope of @t[Previously] is evaluated in
the proposed state.

@Begin(Group)

We can now declare some invariants involving relations we defined earlier:

@Begin(ProgramExample)
@indexexample[office-domain-is-person (rule)]
(AlwaysRequired office-domain-is-person
                (A (x y) (implies (office x y) (person x)))
                :documentation "The domain of the office must be a
	                        person.")

@hinge                                
@indexexample[office-domain-is-person (rule)]
(AlwaysRequired office-range-is-office-number
                (A (x y) (implies (office x y) (office-number y)))
                :documentation "The range of the office relation 
                                must be an office-number.") @Foot{This
rule is actually invalid and cannot be installed because of an equivalence mismatch between 
the relations @t[office] and @t[office-number].  }

@hinge
@indexexample[multiple-forward-targets (rule)]
(NeverPermitted multiple-forward-targets
                (E (phone target1)
	           (E (target2) (and (forward-phone phone target1)
				     (forward-phone phone target2)
			             (not (= target1 target2)))))
                :documentation "At most one phone can be the target 
                                when a phone is forwarded."
                :repair
		(lambda (phone target) 
			(when (?? Previously (forward-phone phone target))
			  (-- forward-phone phone target))))

@hinge
@indexexample[multiple-forward-targets (rule)]
(NeverPermitted forwarding-cycles
                (E (x) (forwarding-path x x)) 
		:documentation "Never allow a phone to be directly or
                                indirectly forwarded to itself.")

@End(ProgramExample)
@End(Group)

Certain idiomatic consistency rules can be specified as part of the @t(DefRelation) macro
using the @t[:types] or @t[:count] keywords.
These rules embody invariants
pertaining to the types of objects permissible in tuples of a relation or to the
number of tuples allowed in certain "projections" of a relation.

@indexsecondary[primary="DefRelation (macro)",secondary=":count"]
@indexsecondary[primary="DefRelation (macro)",secondary=":types"]
@multi{name=DefRelation, args=name, keys=" :documentation :arity :definition
:derivation :computation :types :count 
...", type=Macro}

@Paragraph[@index(type constraints)Type constraints]
@indexsecondary[primary="Consistency rules", secondary="type constraints"]
A @i[type constraint] ensures that the object in
a particular slot of any tuple of a relation is of a particular type.
Type constraints enable the user to rule out the assertion of arbitrary
values for the operands of a relation.  For example, the assertion
@inlineprogramexample[(++ office 'IBM '(3 3 4 A Z))] would not be
allowed if type constraints specify that the operands must be a string
and an integer.  Type constraints can be declared by supplying a list of
typenames (or unary descriptions) corresponding to the operands of the relation as the
@t[:types] argument of @t(DefRelation).  The set of all AP5 objects is
denoted by a special type called @index[Entity (type)]@t[Entity].  Thus, to
leave a slot unconstrained or to remove an existing type constraint, the type
@t(Entity) should be specified.

Here is an augmented definition for the @t(office) relation that 
will install consistency rules similar to the @t[office-domain-is-person] 
and @t[office-range-is-office-number] rules introduced earlier:

@begin[programexample]
(DefRelation office@indexexample[office] 
  :arity 2 
  :types (person office-number)
  :documentation "(Office person number) associates a person with  
                  that person's office number.")

(?? office 'Bob "20") => NIL
(++ office 'Bob "20") => TYPE CONSTRAINT VIOLATIONS
(-- office 'Bob "abc")  [no-op]

(++ person 'Bob)
(++ office 'Bob 20)
(++ office 'Bob 14)
(listof (n) s.t. (office 'Bob n)) => (20 14)
@end[programexample]

We can constrain the @t[office-phone] relation using a unary description: 

@Begin(ProgramExample)
(DefRelation office-phone@indexexample[office-phone]  
  :arity 2 
  :types (office-number ((i) s.t. (integer-in-range i 100 999)))
  :documentation "(Office-phone office-number phone-extension) associates  
                  an office with a three digit integer that is the 
                  office's phone-extension.")

(++ office-phone 21 23) => TYPE CONSTRAINT VIOLATION
(++ office-phone 21 1001) => TYPE CONSTRAINT VIOLATION
(++ office-phone 21 493)
(listof (i) s.t. (office-phone 21 i)) => (493)
@End(ProgramExample)

@Paragraph[@index(count constraints)Count constraints]
@indexsecondary[primary="Consistency rules", secondary="count or cardinality constraints"]
@index(cardinality constraints)Cardinality (or count) constraints 
express conditions such as 
"every person has at most one office" (i.e., there is at most one tuple
in the @t[office] relation for each person in the database).  While these conditions can be
expressed in first order logic, e.g., @inlineprogramexample[(A (person x y)
(implies (and (office person x)(office person y)) (= x y)))],
count constraints express them more concisely as the combination of
a pattern@indexsecondary[primary="patterns",secondary="in count constraints"] and a count restriction,
e.g., for the @t[office] relation @inlineprogramexample[((person output) :countspec :optional)].

The pattern is a list corresponding to the
operands of the relation, whose elements are either
typenames or unary descriptions, or the symbol @t[output].
A count constraint specifies that for each tuple of 
values of the corresponding types (or descriptions) in the pattern,
the number of matching tuples in the relation 
should satisfy the associated count restriction.

@Begin(Group)

A @index[countspecs]count restriction is one of the following values:

@begin(format)
     @t[:none] - exactly zero
     @t[:multiple] - at least one
     @t[:optional] - at most one
     @t[:unique] - exactly one
     @t[:any] - unrestricted
@end(format)
@End(Group)

Count constraints are declared by supplying, as the @t[:count] argument to
@t(DefRelation), a list containing patterns each of which is
followed by the keyword 
@t[:countspec] and a count restriction.  
Several constraints can be declared on the same relation.

The following declaration restricts the @t(forward-phone) relation to integers 
and permits at most one target for each phone 
(like the earlier @t[multiple-forward-targets] rule but no repair is supplied)  
@Foot{Note that if the @t[multiple-forward-targets] rule is present in the runtime
environment of the example, the example updates should not abort, 
rather the count constraint violation should be repaired by @t[multiple-forward-targets].}:

@begin[programexample]
(DefRelation forward-phone@indexexample[forward-phone] 
  :types (integer integer)  
  :count ((integer output) :countspec :optional)
  :documentation "(Forward-phone x y) associates extension x and 
                  extension y when x is forwarded to y.  At most 
                  one target extension is allowed per phone.")

(progn
  (++ forward-phone 333 123)
  (++ forward-phone 333 405)) => COUNT CONSTRAINT VIOLATION

(theonly (i) s.t. (forward-phone 333 i)) => 123
@end[programexample]

Rather than aborting, we could repair violations of the above count constraint
that limits a phone to at most one forwarding target by simply 
replacing the existing tuple with the one asserted in the transition
(like the earlier @t[multiple-forward-targets] rule).  
A @index[repair idiom]repair idiom 
has been conveniently provided for just this case.  It is
applicable when the count specifier is @t[:optional] or @t[:unique] and
is specified by adding the keyword @t[:replacing] followed by T when
specifying the count constraint.  

@begin[programexample]
(DefRelation forward-phone@indexexample[forward-phone]  
  :types (integer integer)  
  :count ((integer output) :countspec :optional :replacing T)
  :documentation "(Forward-phone x y) associates extension x and 
                  extension y when x is forwarded to y.  At most 
                  one target extension is allowed per phone.")

(progn
  (++ forward-phone 333 123)
  (++ forward-phone 333 405)) 

(theonly (i) s.t. (forward-phone 333 i)) => 405
@end[programexample]

Another repair idiom is useful in cases where the count specifier is
@t[:unique] or @t[:multiple] and the desired repair is to assert one or
more default tuples when the constraint is violated.  The repair is 
a Lisp function that will be applied to
elements of the violating tuple that correspond to non-@t[output] elements
in the pattern of the count constraint.  This function should
return as multiple values one or more lists of default elements for the
@t[output] elements in the pattern.  These returned elements are
merged with the tuple elements passed as arguments to the repair
function to create the default tuples to be asserted.

@Begin(ProgramExample)
(DefRelation project@indexexample[project]
  :types (symbol)
  :documentation "(Project symbol) a name representing a project")

(DefRelation works-on@indexexample[works-on] 
  :types (person project)
  :count ((person output) :countspec :multiple
	  :default (lambda (person) (declare (ignore person))
			   (values (list 'overhead) (list 'IR&D))))
  :documentation "(Works-on person project) associates a person  
                  with the name of a project on which he or she
                  is working.")

@hinge
(set-listof (x) s.t. (project x) '(CLF FSD IR&D OVERHEAD))

(atomic 
  (set-listof (x) s.t. (person x) '(Carla Zack))
  (++ works-on 'Carla 'CLF)
  (++ works-on 'Zack 'CLF)
  (++ works-on 'Zack 'FSD))

@hinge
(listof (x) s.t. (works-on 'Zack x))
  => (FSD CLF)

(-- works-on 'Carla 'CLF)  [Violates the count constraint for @t(works-on) 
                            so defaults are supplied.] 

(listof (x) s.t. (works-on 'Carla x))
  => (IR&D OVERHEAD)
@End(ProgramExample)
			  
@SUBSECTION(@index(automation rules)Automation rules)

@indexsecondary[primary="rules",secondary="automation rules"]
@i[Automation rules] provide a method for automatically invoking programs 
whenever a specified condition arises in the database.  
The condition is specified as a description that, 
when satisfied, will trigger a program described in the automation rule.  
The program is specified as a Lisp function that is applied
to the tuples of values that satisfied the trigger.  
Unlike consistency rules, the response of an automation rule is not
incorporated into the triggering transition but is enqueued for subsequent
execution.  In contrast to consistency rules, which express an invariant 
that must always be true (or false),
an automation rule reacts to a condition @i(becoming) true (or false).   

An automation rule has a name, a trigger, and a response.  
The name is a unique symbol used for identifying the rule.  Declaring a 
rule with the same name as an existing rule is treated as a redefinition.  
The trigger of an automation rule is a ground description that refers to a
specific database transition.  The triggering description currently must contain @t[Start].
(Moreover, descriptions that can be true for some state of the database
regardless of the previous state, such as @inlineprogramexample[(NOT (Start @i(wff1)))] or 
@inlineprogramexample[(OR @i(wff1) (Start @i(wff2)))], cannot be used as triggers.)  
The response of an automation rule is a 
Lisp function that is applied to the tuples of values that satisfied the 
trigger.  Because the response will not necessarily be executed in the  
state immediately following the triggering database transition, it
cannot reliably access the database states immediately before or after the 
transition (unlike the repair of a consistency rule).

The @t[DefAutomation] macro is used to declare automation rules:

@index[DefAutomation (macro)]
@t[DefAutomation @i(name trigger response) &key :documentation]@>[@i(Macro)] 
@linkedtext{@t[DefAutomation] creates a rule that executes @i(response) 
when the transition specified in @i[trigger] occurs.}

@Begin[Group]

Here is an example that sends a notification over a computer network (the 
@t[extension] relation which was previously discarded must first be reinstalled):  

@Begin(ProgramExample)
@indexexample[extension]
(DefRelation extension
  :definition ((x y) s.t. (E (office-number)
	                       (and (office x office-number)
	                            (office-phone office-number y))))
  :documentation "(Extension person phone-extension) associates a person 
                  with the phone-extension of his or her office.") 

@hinge
(defun notify-receptionist (person phone-extension added-or-deleted)
  "This function notifies the receptionist that the relationship 
   between a specified person and phone-extension has changed."
  ...)

@hinge
@indexexample[notify-added (rule)]
(DefAutomation notify-added 
               ((x y) s.t. (Start (extension x y)))
               (lambda (x y) (notify-receptionist x y 'added)) 
               :documentation "Whenever a tuple is added to the 
                               extension relation, send a notice to 
                               the receptionist announcing the new 
                               person and extension number.")

@indexexample[notify-deleted (rule)]
(DefAutomation notify-deleted
               ((x y) s.t. (Start (not (extension x y))))
               (lambda (x y) (notify-receptionist x y 'deleted)) 
               :documentation "Whenever a tuple is deleted from the
	                       extension relation, send a notice to
	                       the receptionist announcing the old 
                               person and extension number.")

@End(ProgramExample)
@End[Group]

@SECTION(Annotating relations)

Once the desired functionality of an application has been obtained, a programmer
will often want to improve the performance.
In AP5, this can be accomplished through annotations recognized by  
the @t[DefRelation] macro.  These annotations can be used to  
choose representations for transition relations, to cache derived
relations and to provide estimates of the size of a relation so that
descriptions involving the relation can be efficiently compiled.

@subSECTION(@index[representations]Representations)

An AP5 programmer can provide an annotation for a transition relation 
to specify a representation (data structure) for that relation.
Representations normally affect only the efficiency of an AP5 program.  
They do so by determining which data structures and indices will be 
maintained to facilitate queries and generators.  Some 
representations do not permit all queries to be compiled. 
@Comment{However, because some
representations are not generable for all combinations of bound and unbound
variables some choices of representation or combination of choices for several
relations may not be consistent with an AP5 specification (if it requires
them to be generated). @COMMENT[***something missing/ only for transition relations?] 
In such situations, the AP5 compiler will signal an error.}

All transition relations have a representation.  
A representation is specified by supplying the name of a representation as the @t[:representation]
argument to @t[DefRelation].  If no representation
is specified in the @t[DefRelation] declaration, the default @t[base] representation is used.

@indexsecondary[primary="DefRelation (macro)",secondary=":representation"]
@multi{name=DefRelation, args=name, keys=" :documentation :arity :definition
:derivation :computation :types :count :representation ...", type=Macro}

AP5 supplies over twenty predefined representations.
Some common representations are (see Section @Ref[other-reps] for others):
@begin(description)
@indexsecondary[primary="representations",secondary="base"]
@index[base (representation)]@t[base]@\The default representation in which a list of tuples in the relation is stored.

@indexsecondary[primary="representations",secondary="full-index"]
@index[full-index (representation)]@t[full-index]@\An index is 
maintained for each operand. 
This provides hashed access in return for the storage overhead.  This
representation is typically used when it is important to have efficient
retrieval of tuples given a value for any of the operands.

@Comment{@indexsecondary[primary="representations",secondary="partial-index"]
@index[partial-index (representation)]@t[partial-index]@\An index is 
maintained only for the specified operands.  The specification is a list consisting of 
the symbol @t[partial-index] followed by one or more integers corresponding to operands for which
an index is to be maintained (e.g., for a relation whose arity is 5, 
@inlineprogramexample[(partial-index 0 3)] specifies an index for the first and fourth operand).  
This representation provides hashed access in return for the storage overhead.  
}
@indexsecondary[primary="representations",secondary="tree"]
@index[tree (representation)]@t[tree]@\In this representation, values of the initial operands are used as discriminators
for subtrees of the remaining operands.  This is
implemented with association lists or hashtables depending on the number of branches.
@end(description)

If we expect a large number of tuples in the @t[office] relation 
and it is important to have efficient access to the office number(s)
corresponding a person and vice versa, we might use a full-index representation: 

@Begin(ProgramExample)
(DefRelation office@indexexample[office]
  :arity 2
  :types (person office-number)
  :representation full-index
  :documentation "(Office person number) associates a person with  
                  that person's office number.")
@End(ProgramExample)

A tree representation would be appropriate for a relation that 
associates students with their courses and course grades when it is important 
to have efficient access to a grade when given a student and a course and/or
efficient access to a given student's courses and grades:

@Begin(ProgramExample)
(DefRelation student-grade@indexexample[student-grade]
  :arity 3 
  :representation tree
  :documentation "(Student-grade student course grade) associates a student 
                  and course with the student's grade in that course.")
@End(ProgramExample)

@subSECTION(@index[Size annotations]Size annotations)

@i[Size annotations] also can be supplied by an AP5 programmer when declaring
relations.  These annotations are used by AP5 to estimate costs when
evaluating different algorithms for generating descriptions involving
the relation.  A size annotation is intended to provide an estimate of the
expected number of tuples in a given projection of a relation.    
Each size annotation consists of a list @indexsecondary[primary="patterns",secondary="in size annotations"] corresponding to
the operands in the relation, whose elements are one of the
symbols @t[input] (for "given" values) or @t[output] (for values to be
generated) and an integer (or @t[NIL] to indicate infinitely
many) that is the expected number of tuples of that projection of the
relation.  The total number of tuples in the relation is specified by a
list consisting of the symbol @t[output] for each operand of the
relation.  Note that size annotations do not @i[limit] the number of tuples in a relation;
they are only @i[estimates] of the size of specified projections of the relation.      

Size annotations are specified with the @t[:size] keyword in a
@t[DefRelation] declaration.

@indexsecondary[primary="DefRelation (macro)",secondary=":size"]
@multi{name=DefRelation, args=name, keys=" :documentation :arity :definition
:derivation :computation :types :count :representation :size ...", type=Macro}

@Begin(ProgramExample)
(DefRelation research-staff@indexexample[research-staff] 
  :arity 2
  :documentation "(Research-staff organization person) associates an
                  organization with a person who is employed by the 
                  organization as a researcher."
  :size ((output output) 100 (input output) 25 (output input) 1))
@End(ProgramExample)

The above size annotations estimate that the @t[research-staff] relation
will contain a total of 100 tuples, that 25 tuples will match the
description @Inlineprogramexample[((x) s.t. (research-staff company
x))] for a given company and that only one tuple will match the
description @Inlineprogramexample[((x) s.t. (research-staff x person))]
for a given person.

@SUBSECTION(@index[Caching relations]Caching derived relations)

Through annotations, an AP5 programmer can also request maintenance of a 
cached representation of a relation that
is derived from a definition.  (Currently, only defined relations  
may be maintained, but any derived relation should be cacheable.) 
@comment(This may be inconvenient, but it
does not actually limit the expressive power since you can always define
a new relation to be equivalent to the one you wanted maintained, and
then maintain the defined relation instead.) 

The annotation is made by supplying both a definition or derivation
@i[and] a representation in a single @t[DefRelation] declaration.
Typically, an AP5 programmer starts out using a derived relation and
later adds a representation annotation to improve efficiency.  This annotion is appropriate
when the increased access speed of the cache is considered to
outweigh the cost, in space, of holding the cache and the cost, in time, of
maintaining it.

Once the annotation has been supplied,
whenever transition relations change in a way that makes a tuple of 
the maintained (derived and cached) relation become true the derived tuple
will be added to the cache.  Similarly, when changes to transition relations 
cause a tuple of the derived relation to become false, that tuple will be
removed.

We can cause a cache to be maintained for the @t[extension] 
relation as follows:   

@Begin(ProgramExample)
(DefRelation extension@indexexample[extension]
  :definition ((x y) s.t. (E (office-number)
	                        (and (office x office-number)
	                             (office-phone office-number y))))
  :representation tree
  :documentation "(Extension person phone-extension) associates a person 
                  with the phone-extension of his or her office.") 
@End(ProgramExample)

@CHAPTER(Using AP5)
@label(using-AP5)

To use AP5 it is customary to start up a Lisp image already including 
the AP5 system since adding AP5 to a standard Lisp image is time consuming.

@SECTION(@index[packages]Packages)

The @index[AP5 (package)]AP5 package is reserved for the symbols of the
AP5 system itself.  All necessary symbols are exported from this
package.  User applications should reside in a package that uses the
AP5 package and the Lisp package.  
Such an application package can be defined in Common Lisp as follows:

@index[AP5-USER (package)] 
@begin(programexample)
(in-package 'AP5-USER :use (list (find-package "LISP")
				 (find-package "AP5")))
@end(programexample)

This application package is appropriate for executing examples in a Lisp
interactor and for writing application source files.

@SECTION(Relation names and redeclarations)

Relations are named by supplying a symbol as the first argument to @t[DefRelation].
The following functions are defined in AP5 to provide a way to test,
access and remove this association between a name (symbol) and a relation.
They are analogous to the corresponding Common Lisp functions
for symbols and function definitions.

@index[Rboundp (function)]@t[Rboundp @i(symbol)]@>[@i(Function)]
@linkedtext{Returns @t[T] if @i[symbol] is the name of a relation and @t[NIL] otherwise.}

@index[Rmakunbound (function)]@t[Rmakunbound @i(symbol)]@>[@i(Function)]
@linkedtext{Removes the association between @i[symbol] and any relation object.}

Whenever a @t[DefRelation] declaration is evaluated for an existing relation
(the supplied name is the name of an existing relation),
the existing relation will be changed to comply with the new
specification.  The tuples of the relation are @i[not] re-represented; a warning may
be issued if this is likely to cause problems (e.g., a new 
type constraint has been added and existing tuples may violate that constraint).  
AP5 attempts to retain properties of the existing relation which
are not in conflict with the new specification.
However, if a different arity, representation or derivation is specified,
existing capabilities
(see Section @Ref[capabilities]) of the relation will @i[not] be retained.
Furthermore, the new specification may cause incompatible 
rules and relations defined in terms of the 
existing relation to be discarded.  A warning is issued when this occurs.  

@SECTION(Documentation utilities)

AP5 includes some simple utilities to provide documentation for relations, rules and other objects:

@index[Doc (relation)]@t[Doc] @i(symbol type string)@>[@i(Relation)]
@Begin(LinkedText)
@t[Doc] associates AP5 relations and rules with documentation strings. 
This relation will contain documentation provided with the :documentation keyword
in relation and rule declarations as well as any other documentation accessible with
the Common Lisp @t[documentation] function.
By convention, the names of the operands of the relation may be taken from the first line of
the documentation for the relation or from the typeconstraints on the
relation.
@End(LinkedText)

@index[DescribeRel (function)]@t[DescribeRel @i(relation-name) &optional (@i(stream *standard-output*))]@>[@i(Function)]
@Begin(LinkedText)
@t[DescribeRel] prints useful information about a relation including the arity, type constraints, equivalence signature,
annotations and so forth.
@End(LinkedText)

@index[DescribeRule (function)]@t[DescribeRule @i(rule-name) &optional (@i(stream *standard-output*))]@>[@i(Function)]
@Begin(LinkedText)
@t[DescribeRule] prints useful information about a rule including the type of rule, trigger, repair or response, 
and enforcement level.
@End(LinkedText)

@index[Describe-Algorithm (function)]@t[Describe-Algorithm @i(description)]@>[@i(Function)]
@Begin(LinkedText)
@t[Describe-Algorithm] shows the translation of a description into a generator 
for that description along with cost and size estimates.
@End(LinkedText)

@index[Tell-Me-About (function)]@t[Tell-Me-About @i(object) &key :stream]@>[@i(Function)]
@Begin(LinkedText)
@t[Tell-Me-About] searches the database for true facts involving @i(object) and prints them to
@t[:stream] (which defaults to *standard-output*).  Due to the non-uniform nature of relation 
representations, this function cannot generally find all facts involving @i(object). 
@End(LinkedText)

@Begin(ProgramExample)
(DescribeRel 'extension) =>
    EXTENSION  implementation: TREE
    arity: 2
    Compare Relations: (EQL =)
    arguments: (PERSON ENTITY)
    Definition:
    ((X Y) S.T. (E (OFFICE-NUMBER) (AND (OFFICE X OFFICE-NUMBER)
	                                (OFFICE-PHONE OFFICE-NUMBER Y))))
    (Extension person phone-extension) associates a person 
    with the phone-extension of his or her office.
    Appears in the definition of: 
    (Typeconstraint-EXTENSION-0 Maintain-EXTENSION)

@hinge
(DescribeRule 'forwarding-cycles) =>
    FORWARDING-CYCLES  (CONSISTENCY)
    Never allow a phone to be directly or
    indirectly forwarded to itself.
    Trigger: (E (X) (FORWARDING-PATH X X))
    Code: IGNORE
    Enforcement: INCREMENTAL
    NIL

@hinge
(Describe-Algorithm 
    '((x y) s.t. (E (office-number)
	            (and (office x office-number)
	                 (office-phone office-number y))))) =>
    (((X0 X1)
      S.T.
      (E (X2) (AND (OFFICE-PHONE X2 X1) (OFFICE X0 X2))))
     =
     (REMOVE-DUPLICATES
	(LOOP FOR
	      (X0 X1 X2)
	      S.T.
	      (AND (OFFICE-PHONE X2 X1) (OFFICE X0 X2))
	      (COMMENT ((X0 X1 X2) S.T. (AND (OFFICE-PHONE X2 X1)
	                                     (OFFICE X0 X2)))
		       =
		       (LOOP FOR
			     (X2 X1)
			     S.T.
			     (OFFICE-PHONE X2 X1)
			     NCONC
			     (LOOP FOR
				   (X0)
				   S.T.
				   (OFFICE X0 X2)
				   COLLECT
				   (LIST X0 X1 X2))))
	      COLLECT
	      (LIST X0 X1)))
     :COST 5600 :SIZE 100.0)

@hinge
(Tell-Me-About 13) =>
    13 is a INTEGER
    13 is a OFFICE-NUMBER
    13 : ISQRT = 3
    13 : ABS = 13
    ...

@End(ProgramExample)

@SECTION(Load and compile dependencies)

All AP5 relations must be declared prior to being used.  This is
analogous to the treatment of macros in Common Lisp.  Thus types must be
declared prior to relations or generators that refer to them,
relations must be declared prior to other relations, procedures or rules
that use them, and so forth.  This means that AP5 declarations must be
ordered appropriately within a file for purposes of compiling and
loading.  However, unlike Lisp macros, redefinition of an AP5 relation
will update any code that uses that definition rather than requiring
the user to recompile that code.  Note also that compiling a @t[DefRelation]
declaration will cause the relation to be installed in
the compiling environment; it is not necessary to load source
versions prior to compiling.

@SECTION(@index[Transition history]Transition history)

AP5 records all database transitions in a global
history list and allows a user to examine the history of events and to
undo events.  The @t[History] function provides
an interface to this transition history.  Events may be undone either in a
backward or forward sense.  Backward undoing means the most recent
event is undone and forgotten so that the state of the database is as
it was prior to that event.  Forward undoing means to apply a new
atomic update to the database that has the opposite effect of the
event being undone.  Rules are disabled for backward undoing 
but are in force for forward undoing (thus forward undoing may
cause an abort or trigger automations).

@index[History (function)]@t[History &key :print-length :print-level :search-key ...]@>[@i(Function)]  

@Begin(Group)

The command options for the history browser are:

@begin(description, leftmargin 16, indent -10, font smallbodyfont, spread .5)
?@\print a help message

<space>@\show the previous event

p@\change printing parameters

j@\jump to an arbitrary event

b@\undo backward (only allowed from the end) then show previous event

f@\undo the current event forward then show previous event

s@\search for an event

x@\exit with the current event as the value of HISTORY (for further processing)

q@\quit
@end(description)

@End(Group)

@SECTION(The @indexentry[Key="Coroner",Entry="The Coroner",Number]Coroner)

The Coroner is a debugging facility 
for failed AP5 atomic updates.  In
most cases when an atomic update fails, a proceedable error will be
generated that presents the option of invoking the Coroner.  When invoked, the
Coroner prints a report about the failed update into an edit buffer.  In
particular, the atomic update is presented in a textual form that can be
edited by the user.  While editing the update, the user is free
to modify the database (or the rules).  When the editing is finished, the Coroner
will ask whether the possibly modified update should be retried.
If approved, the edited update will be executed in place of the
original atomic update.

@comment[ An example: (atomic (++ office "Brad" 876)(-- office "Brad" 876))] 

@CHAPTER(Advanced Concepts)

@SECTION(Type hierarchies and @index[basetype (derivation idiom)]basetypes)
@indexsecondary[primary="derivation idioms",secondary="basetype"]
@indexsecondary[primary="types",secondary="basetype"] 

A programmer can easily define (or extend) type hierarchies in AP5.
AP5 provides a derivation idiom, called a @i[basetype], for defining 
types that are intended to participate in such a hierarchy.
When one basetype is declared to be a subtype of another,
instances of the subtype will automatically be  
recognized as instances of the supertype.  
As a consequence, consistency rules that apply
to a supertype apply also to any subtypes.
 
A basetype is declared by specifying @t[basetype] as the @t[:derivation]
argument to @t[DefRelation].  Within the declaration of a basetype,
its supertype can be declared by supplying  
another existing basetype as the @t[:types] argument. 

@Begin(ProgramExample)
@indexexample[person](DefRelation person :derivation basetype)
@indexexample[employee](DefRelation employee :derivation basetype :types (person))
@indexexample[salaried-employee](DefRelation salaried-employee :derivation basetype :types (employee))
@indexexample[hourly-employee](DefRelation hourly-employee :derivation basetype :types (employee))

(++ hourly-employee 'Susan)
(?? salaried-employee 'Susan) => NIL 
(?? employee 'Susan) => T
(?? person 'Susan) => T

(DefRelation ss#@indexexample[ss#]
  :types (person integer)
  :count ((person output) :countspec :optional
	  (employee output) :countspec :unique))

(++ hourly-employee 'Bart) => COUNT CONSTRAINT VIOLATION
(atomic (++ hourly-employee 'Bart)
	(++ ss# 'Bart 123456789))
@End(ProgramExample) 

@Comment{Since both of the count constraints pertaining
to person and employee would apply to an employee
and any subtypes of employee,
we could have declared the @t[:countspec] on 
(employee output) to be @t[:multiple].}

@SECTION(@index(equivalence)Equivalence)
@label(equiv)

Lisp programmers are familiar with different notions of object
equivalence.  For example, two strings that are not @t[eql] may still
be @t[equal].  In AP5, the notion of object equivalence is similarly relative
to an @i[equivalence relation].  A number of equivalence relations are
predefined in AP5 including analogs to the Common Lisp predicates
@t[eq], @t[eql], @t[=], @t[equal], @t[equalp], @t[string-equal],
@t[string=], @t[char-equal], and @t[char=].  AP5 programmers may also
define new equivalence relations.

When declaring new relations, it is important to be able to specify
which equivalence relations will be used to compare the objects of the
tuples of the relation, i.e., which representations for objects of the
tuples will be treated as the same and which representations will be
treated as different.  Consider the following relation used to represent
the index entries for a book:

@Begin(ProgramExample)
(Defrelation index@indexexample[index]
  :arity 2 
  :documentation "(Index word n) associates a word with a number 
                  representing the page number of an important
	          usage of that word.")

(++ index "black" 12)
(?? index "black" 12) => NIL
@End(ProgramExample)

The above query returns @t[NIL] because the equivalence relation used to
determine whether the objects in the query match the objects in the earlier
assertion is the default, @t[eql].  Using other equivalence relations,
such as @t[string=], to compare the strings representing words would have 
caused the query to return @t[T].
This can be seen in the following query:

@Begin(ProgramExample)
(?? e (word) (and (index word 12)
	          (string-equal word "black"))) => T
@End(ProgramExample)

Each relation in AP5 has an associated equivalence signature that is an
n-tuple of equivalence relations.  The arity of the
equivalence signature must correspond to the arity of the relation.
The default equivalence signature for AP5 relations is derived from the type
constraints on the relation (@t[eql] is the default comparison for
@t[Entity]).

Specifying @t[string] and @t[integer] as type constraints on the
@t[index] relation would give it an equivalence signature of @t[(string-equal
=)].

@Begin(ProgramExample)
(DefRelation index@indexexample[index]
  :arity 2
  :types (string integer)
  :documentation "(Index word n) associates a word with a number 
                  representing the page number of an important
	          usage of that word.")

(++ index "white" 21)
(?? index "white" 21) => T
(?? index "White" 21) => T
@End(ProgramExample)
  
A programmer can also explicitly specify an equivalence signature when
declaring a new relation, by supplying a list of equivalence relations
corresponding to the operands of the relation as the @t[:equivs] keyword
argument of @t[DefRelation].

@indexsecondary[primary="DefRelation (macro)",secondary=":equivs"]
@multi{name=DefRelation, args=name, keys=" :documentation :arity :definition
:derivation :computation :types :count :representation :size :equivs ...", type=Macro}

Using @t[:equivs] we can redefine the @t[index] relation to continue to 
represent words as strings but to distinguish case differences:

@Begin(ProgramExample)
(DefRelation index@indexexample[index]
  :arity 2
  :types (string integer)
  :equivs (string= =)
  :documentation "(Index word n) associates a word with a number 
                  representing the page number of an important
	          usage of that word.")

(++ index "gray" 99)
(?? index "gray" 99) => T
(?? index "Gray" 99) => NIL
@End(ProgramExample)

@Comment[There is no notion of automatic coercion of equivalence in AP5.
Every variable in a wff must consistently use the same equivalence.  ]

@SECTION(Extending the capabilities of a relation)
@label[capabilities]

AP5 relations may have a number of @index[capabilities]capabilities.  These capabilities
include testing of tuples in the relation, asserting new tuples into the
relation, retracting existing tuples from the relation, generating the
tuples for certain projections of the relation,
triggering, i.e., recognizing the updates to a relation, and estimating the effort to test a relation.  
Many of these capabilities are supplied by the choice of a particular representation,
derivation or computation.  An AP5 programmer can supply others.
If a programmer wishes to supply all of the capabilities for a relation,
a dummy representation (called @index[individual (representation)]@t[individual]) 
and a dummy derivation 
(called @index[individual-derived (derivation idiom)]@t[individual-derived]) are recognized by AP5. 
The @t[DefRelation] macro supplies keywords for specifying code to provide
each of these capabilities for a relation.

@index[DefRelation (macro)]
@indexsecondary[primary="DefRelation (macro)",secondary=":adder"] 
@indexsecondary[primary="DefRelation (macro)",secondary=":deleter"] 
@indexsecondary[primary="DefRelation (macro)",secondary=":generator"] 
@indexsecondary[primary="DefRelation (macro)",secondary=":tester"] 
@indexsecondary[primary="DefRelation (macro)",secondary=":trigger"] 
@indexsecondary[primary="DefRelation (macro)",secondary=":updater"]
@indexsecondary[primary="DefRelation (macro)",secondary=":testeffort"]
@multi{name=DefRelation, args=name, keys=" :documentation :arity :definition
:derivation :computation :types :count :representation :size :equivs 
:tester :updater :adder :deleter :generator :trigger :testeffort ...", type=Macro}

A @indexsecondary[primary="capabilities",secondary="tester"]@index[tester (capability)]@i[tester] 
is a function that will be
applied to a list of arguments consisting of a primitive-wff (a relation
and the elements of a candidate tuple of the corresponding arity).  It
should return a function that will accept the
runtime values of these arguments.  The tester code should return NIL if
the tuple is not in the relation and a non-NIL value otherwise.

@Begin(ProgramExample)
(defun integer-pair-tester (relation arg1 arg2)
  (declare (ignore relation))
  (and (integerp arg1)(integerp arg2)))

(DefRelation integer-pair@indexexample[integer-pair] 
  :arity 2
  :derivation individual-derived
  :tester (lambda (&rest args)
	    (declare (ignore args))
	    'integer-pair-tester)) 

(?? integer-pair 2 1) => T
(?? integer-pair 2 'test) => NIL

@End(ProgramExample)

An @indexsecondary[primary="capabilities",secondary="updater"]@index[updater (capability)]@i[updater] 
is a function that
will be applied to three arguments: a transition relation to be updated, a list
of the tuples to be added and a list of the tuples to be retracted.  The function
should update the underlying data structures in order to carry out the updates so specified. 
The update code for a transition relation should not access the database.

Derived relations are currently updated by adders and deleters.
@indexsecondary[primary="capabilities",secondary="adder"]@index[adder (capability)]@i[Adders] and 
@indexsecondary[primary="capabilities",secondary="deleter"]@index[deleter (capability)]@i[deleters] 
are functions 
that will be applied to a list of arguments corresponding to a
primitive-wff, i.e., to a relation and the elements of a candidate
tuple.  They should return a function that will
accept the runtime values of these arguments. 
@Comment[By supplying adders and deleters, it is possible to define
assertions and retractions of tuples for derived relations.]
The adder and deleter code for a derived relation should translate 
into updates of the
relations from which the relation is derived.

@begin(programexample)
(theonly (o) s.t. (office 'Mark o)) => 14
(listof (n) s.t. (office-phone 14 n)) => (542) 
(++ extension 'Mark 982) => UPDATE VIOLATION

@hinge
@indexexample[extension]
(DefRelation extension
  :definition ((p e) s.t. (E (n) (and (office p n) (office-phone n e))))
  :documentation "(Extension person phone-extension) associates a person 
                  with the phone-extension of his or her office.  When 
                  asserting an extension, if the person has an office
                  install the phone-extension in that office.  When 
                  retracting an extension, if is indeed the extension of 
                  the person, remove the phone-extension from the office." 
  :adder (lambda (&rest args)
	   '(lambda (ignore p e)
	      (let ((office (theonly (o) s.t. (office p o) :ifnone nil))
		    (phone-location (theonly (o) s.t. (office-phone o e)
					     :ifnone nil)))
	        (if office
		    (if (and phone-location (not (= office phone-location)))
			(error "Extension ~A is already assigned to
	                       office ~A." e phone-location)
			(++ office-phone office e))
	            (error "Can't assert an extension until
                            ~A is assigned to an office." p)))))
  :deleter (lambda (&rest args)
	     '(lambda (ignore p e)
		(let ((office (theonly (o) s.t. (and (office p o)
						     (office-phone o e))
				       :ifnone nil)))
		  (when office (-- office-phone office e))))))

@hinge
(++ extension 'Mark 982)
(listof (n) s.t. (office-phone 14 n))) => (542 982) 
@end(programexample)

@comment(function that is a generator?)  
A @indexsecondary[primary="capabilities",secondary="generator"]@index[generator (capability)]@i[generator]
is specified with a list starting with
@t[SimpleGenerator]@index[SimpleGenerator] or @t[SimpleMultipleGenerator]@index[SimpleMultipleGenerator] followed by a 
pattern@indexsecondary[primary="patterns",secondary="in generator specifications"] and
a form that defines the generator for the pattern 
(A generator can also be specified with a function; 
see the reference manual). 
The pattern is a list of symbols with the symbol @t[output] standing
for the elements to be generated.  A SimpleGenerator can only describe a generator
for a single output position (the defining form should return a list of these
values) whereas a SimpleMultipleGenerator can describe a generator for multiple
output positions (the defining form should return of list of tuples of these 
positions in the order in which they appear in the pattern).
AP5 supplies generators for defined relations automatically.

@Begin(ProgramExample)
(theonly x s.t. (sqrt x 5.3)) => TRANSLATION ERROR

(DefRelation sqrt@indexexample[sqrt] 
  :arity 2
  :derivation individual-derived
  :tester (lambda (&rest args) 
	    '(lambda (rel arg1 arg2)
	       (declare (ignore rel))
	       (= arg1 (* arg2 arg2))))
  :generator ((simplegenerator (output y)
			       (and (numberp y)
				    (list (* y y)))) 
              (simplegenerator (x output)
			       (and (numberp x)
				    (list (sqrt x)
					  (- (sqrt x)))))))

(?? sqrt 9.0 3) => T
(theonly x s.t. (sqrt x 5)) => 25
(listof (n) s.t. (sqrt 2 n)) => (1.4142135 -1.4142135)
@End(ProgramExample)

In order to trigger rules that depend on changes to derived relations,
AP5 must be notified of such changes.  The mechanism for this is called a
@index[trigger (capability)]@i[trigger].
A trigger is a list of specifications of the form 
@i[(relation truth-value-1 trigger-function truth-value-2)]
where the truth-values are "@t[+]" or "@t[-]" representing TRUE and FALSE.
Whenever a tuple of the @i[relation] acquires  @i[truth-value-1], 
the @i[trigger-function] will compute
tuples for the derived relation, which acquire @i[truth-value-2].
The @i[trigger-function] is a function that takes three arguments:
the derived relation for which it is to compute updates and booleans indicating 
whether additions are of interest
and whether deletions are of interest.  These latter two arguments can be  
ignored when the function computes only assertions or only deletions.
The trigger function is responsible for reporting changes to a derived relation
based on changes to the relation in the trigger specification.  These changes
are reported as assertions or deletions of the the derived relation.
AP5 supplies triggers for defined relations automatically.

[Example to be provided.]

@indexsecondary[primary="capabilities",secondary="testeffort"]@index[TestEffort (capability)]The @i[testeffort] is a
function that provides an numerical estimate of the time it takes to test a relation.
Like the size annotation, the @i[testeffort] estimate is used by AP5 to estimate costs when
evaluating different algorithms for generating descriptions involving the relation. 
The @i[test-effort-function] is intended to be applied to a primitive wff (i.e., its arguments are 
the name of the relation to be tested and a number of
objects corresponding to the arity of that relation) and should return a number 
corresponding to the estimated time in microseconds required to test the wff (or @t[NIL] to indicate 
that the relation cannot be tested).

AP5 provides a function to access the test effort estimate for a primitive wff:

@index[TestEffort (function)]@t[TestEffort @i(wff)]@>[@i(Function)]
@Begin(LinkedText)
@t[TestEffort] returns the current estimate of the effort to test a wff.
This estimate is intended to be the number of microseconds required for the test. 
@End(LinkedText)


@Comment{

(DefRelation people-per-office 
  :derivation (cardinality office (output input))
  :trigger ((office + foo +)(office - foo -))
  :documentation "(People-per-office office-number n) associates 
                  an office number with the number of occupants.")

(defun foo (relation addp delp)
  (declare (ignore relation))
  (loop for o s.t. (change (p) (office p o))
	(let ((new (theonly p s.t. (office p o))) 
	      (old (previously (theonly p s.t. (office p o)))))
	  (when delp (-- people-per-office o old))
	  (when addp (++ people-per-office o new)))) }

@SECTION(Additional @index[representations]representations)
@label[other-reps]
The following four representations apply to binary relations that involve dbobjects.
A @index[DBObject (type)]@i[dbobject] is a predefined type whose instances have a property list 
and are thus useful in conjunction with certain representations
that depend on property lists. @comment[create macro]

@begin(description)
@indexsecondary[primary="representations",secondary="structprop"]
@index[structprop (representation)]@t[structprop]@\This representaion associates dbobjects with other objects
by putting the other objects on the property list of the dbobjects. 

@indexsecondary[primary="representations",secondary="treeprop"]  
@index[treeprop (representation)]@t[treeprop]@\A combination of structprop and tree representations.

@indexsecondary[primary="representations",secondary="treeprop+"]  
@index[treeprop+ (representation)]@t[treeprop+]@\The structprop representation is used
when the first operand is a dbobject, otherwise a hashed representation is used. 

@indexsecondary[primary="representations",secondary="two-way-structprop"]
@index[two-way-structprop (representation)]@t[two-way-structprop]@\This representation is like structprop but
both operands must be dbobjects and each is stored on the property list of the other.
@end(description)

Specialized representations are also provided for storing the tuples of a relation in Lisp data structures.
These include: @t[globalvar], @t[defstruct], @t[symbolprop], @t[alist], @t[hashtable], and @t[array].  
These representations require a specification that identifies the place where the values are stored.

@begin(description)   
@index[globalvar (representation)]@t[globalvar]@\A unary relation stored as a list of values bound to a Lisp global variable.
@*In @t[DefRelation], this is specified by @t{:representation (globalvar @i<variable>)}.

@index[defstruct (representation)]@t[defstruct]@\A binary relation that relates objects 
represented as a Lisp structure to lists of values stored in some field of the structure.
@*@t{:representation (defstruct @i<structure-name field-name>)}

@index[symbolprop (representation)]@t[symbolprop]@\A binary relation that relates a symbol in the domain 
to a list of values stored as a property of the symbol.
@*@t{:representation (symbolprop @i<property-name>)}

@index[alist (representation)]@t[alist]@\A binary relation stored as an association list of keys and lists of values.
@*@t{:representation (alist @i(<code to find alist>))}

@index[hashtable (representation)]@t[hashtable]@\A binary relation stored in a hashtable 
in which the domain of the relation serves as the index for accessing a list of values.
@*@t{:representation (hashtable @i(<code to find hashtable>))}

@index[array (representation)]@t[array]@\A relation stored as
an array whose dimensions are one less than the arity of the relation. 
Such a relation relates array indices to a list 
of values stored in the array at those indices. 
@*@inlineprogramexample{:representation (array @i(<code to find array>))}
@end(description)

Analogous representations (called @t[globalvar-single], @t[defstruct-single] and so forth) 
are supplied for cases where at most one value is to be stored.  

@Begin(ProgramExample)
(defvar *dictionary* (make-hash-table))

(DefRelation dictionary-entry
  :types (symbol string)
  :representation (hashtable-single *dictionary*))

(++ dictionary-entry
    'arity "the number of objects in each tuple of a relation")
@End(ProgramExample)

@comment[Examples***]

@SECTION(Notational shortcuts)
@label(shortcuts)

AP5 provides a syntax in which variables (introduced by quantifiers or
descriptions) can be restricted to values of a particular type.  The
character @index[# (within a variable name)]@indexsecondary[primary="wff syntax",secondary="#"]"#" is reserved to express this
restriction.  Variables of the form @i[type#name] translate as a
variable named @i[name] restricted to values of type @i[type].  The name
may also be omitted in which case @i[type] will also be
used as the variable name, thus @i[type#] translates as a variable named
@i[type] of type @i[type].  This way of introducing a type restriction is equivalent to supplying
the type restriction explicitly.

@begin(programexample)
((x) s.t. (person x)) @math[@eqv] ((person#x) s.t. TRUE)
((x y) s.t. (and (hourly-employee x)(office x y)))
	@math[@eqv] ((hourly-employee#x y) s.t. (office x y)) 
(?? E (x) (and (hourly-employee x)(office-mate 'Jim x)))
	@math[@eqv] (?? E (hourly-employee#x)(office-mate 'Jim x)) 
@end(programexample)

For certain generator macros, @t[any], @t[theonly] and @t[listof], and the @t[set-listof] macro,
a relation name can be substituted as a shorthand for the corresponding spliced-in description.

@Begin(ProgramExample)
(any (p) s.t. (person p)) @math[@eqv] (any person) 
(listof (p n) s.t. (office p n)) @math[@eqv] (listof office)
(set-listof (x y) s.t. (forward-phone x y) '((333 123)(123 542)(405 239))) 
        @math[@eqv] (set-listof forward-phone '((333 123)(123 542)(405 239))) 
        
@End(ProgramExample)

Within a wff, the symbol @index[$ (within a wff)]@indexsecondary[primary="wff syntax",secondary="$"]"$" can be used as a shorthand to introduce additional
existentially quantified variables.  Multiple usages of "$" need not
refer to the same value.

@Begin(ProgramExample)
((x) s.t. (E (y) (extension x y))) @math[@eqv] ((x) s.t. (extension x $))
@End(ProgramExample)

@SubHeading(Wff macros)

The syntax of wffs can be extended by macros.  In contexts where a wff is
expected, a list whose initial symbol is not a known relation name or 
piece of wff syntax will be macroexpanded and the result treated as a wff.
Predefined wff macros include:  

@Begin(Description, leftmargin 20, indent -20)
@indexsecondary[primary="wff syntax",secondary="Implies"]@index[implies (wff macro)]
(@t[Implies] @i(wff1 wff2))@\@math[@eqv] (OR (NOT @i(wff1)) @i(wff2))

@indexsecondary[primary="wff syntax",secondary="Equiv"]@index[equiv (wff macro)]
(@t[Equiv] @i(wff1 wff2))@\@math[@eqv] (AND (implies @i(wff1) @i(wff2))
                       (implies @i(wff2) @i(wff1)))

@indexsecondary[primary="wff syntax",secondary="Xor"]@index[xor (wff macro)]
(@t[Xor] @i(wff1 wff2))@\@math[@eqv] (NOT (equiv @i(wff1) @i(wff2)))

@indexsecondary[primary="wff syntax",secondary="If-Then-Else"]@index[If-Then-Else (wff macro)]
(@t[If-Then-Else] @i(wff1 wff2 wff3))@\@math[@eqv] (OR (AND @i(wff1) @i(wff2))
                                  (AND (NOT @i(wff1))(@i(wff3))))
   
@indexsecondary[primary="wff syntax",secondary="Exists"]@index[exists (wff macro)]
(Exists @i(vars wff))@\@math[@eqv] (E @i(vars wff))
 
@indexsecondary[primary="wff syntax",secondary="All"]@index[all (wff macro)]
(All @i(vars wff))@\@math[@eqv] (A @i(vars wff))

@End(Description)

@indexsecondary[primary="wff syntax",secondary="Funcall"]@index[funcall (wff macro)]
@indexsecondary[primary="wff syntax",secondary="Apply"]@index[apply (wff macro)]
In addition, the wff macros @t[funcall] and @t[apply] are defined in a manner analogous to 
their Lisp counterparts.  In contexts where a wff is
expected, a list whose car is the symbol @t[funcall] is translated by
evaluating the second element and treating the result as a relation to be applied to
the values of the remaining arguments comprising the list.  Similarly, a list whose car is the symbol 
@t[apply] is translated by evaluating the second element and treating the result as a 
relation to be applied to the argument list that results when a list of the values of all 
but the last of the remaining arguments is appended to the value
of the last remaining argument.

@SECTION(The AP5 Computation Model)

The following brief description of the @index[AP5 computation model]AP5
computation model is intended to supplement the earlier discussion of
database updates, atomic transitions, and rules.  The computation model
used by AP5 layers a coarse-grained cycle over the fine-grained cycle of
computations defined by Common Lisp.  This cycle, shown in Figure
@ref(Computation-Model-Figure), begins when an application proposes one
or more updates to the database (an atomic transition) and ends
when either the transition is aborted or the updates are transacted,
resulting in the next consistent state of the database and the execution
of any computations specified by automation rules that have been
triggered.

@begin(figure)
@blankspace(5 inches)
@caption(The AP5 Computation Model)
@tag(Computation-Model-Figure)
@end(figure)

The initial set of proposed changes to the database consists of
assertions or deletions of facts, i.e., primitive wffs involving transition
relations, where updates of derived relations have been translated into updates
of transition relations. 

A @i[consistency manager] examines the proposed changes, aborts if there
are contradictory updates (assertion and deletion of the same fact) and
otherwise executes one or more consistency cycles.  Within a consistency
cycle, the changes to the database are simulated resulting in a
potential state of the database, which is accessible only to the
consistency manager.  The consistency manager then determines if any
constraints would be violated by this potential state transition.
If not, the consistency cycle is finished, the database is updated 
(but not yet made accessible to other processes) and
control is passed to the automation manager.

If there are consistency violations, any associated repair procedures
are collected and executed in the context of the potential state
transition.  These repair procedures cannot alter the proposed set of updates 
except by supplying additional proposed updates (or aborting) and may 
access the current or proposed database states.  Unless contradictory updates
have been introduced, the consistency manager then executes another
consistency cycle with the modified set of proposed changes.  This cycling
will continue until the transition succeeds (there are no more
violations of consistency rules) or aborts (a rule explicitly aborts or there are contradictory
updates or there are consistency violations but the set of proposed changes
is unchanged from the previous cycle) or some set limit
of cycles is exceeded.

An @i[automation manager] carries out the final steps of the computation
cycle.  It examines the successful state transition, finds any
automation rules triggered by the transition and gathers a set of
pending automation procedures.  Automation rules specify procedures to
be enqueued.  The new database state is now made
accessible to all processes and the enqueued automation procedures are
executed.  When the queue is empty, the application that initiated the
transition is allowed to resume.

@appendix(Defining, saving and restoring @index(worlds)Worlds)

@label(worldssection)
@comment[see pet-food:>Worlds>documentation>version5.mss]
Worlds is an augmentation
of AP5 that provides for the persistance and sharing of subsets of
a database.  Briefly, Worlds allows a user to specify
the subset of interest (called a worldspec).  This worldspec is then
instantiated as a structure, called a world, that can be populated with facts comprising
the specified subset.  A world can be named and associated with a creator.  
A particular state of a world 
can be saved to disk or restored.  More details are
available in the Worlds Manual @cite(Worldsmanual).

Some relevant functions are:

@multi{name=createworldspec, args="name comment exporttypes importtypes spec", 
keys=" :creator", type=Function}
@linkedtext{@t[Createworldspec] defines and saves a specification for a world.}

@multi{name=createworld, args="name comment worldspec", keys=" :creator :seedset :savepath",
type=Function}
@linkedtext{@t[Createworld] actually creates and saves a world according to a worldspec.
When specified, the @t[:seedset] is a unary description which identifies objects that
serve to seed the world in that their associated relations with other objects constitute the
world.}

@t[populate @i[world] &key :in :out]@>[@i(Function)]
@linkedtext{@t[Populate] puts objects into an existing world.}

@t[save @i[world] &key :batch :comment]@>[@i(Function)]
@linkedtext{@t[Save] saves the current state of a world.}

@t[commit @i[world] &key :batch :comment]@>[@i(Function)]
@linkedtext{@t[Commit] puts objects into an existing seeded world and saves that world.}

@t[restore] @i[world] &key :targetstate :frombatch]@>[@i(Function)]
@linkedtext{@t[Restore] restores the state of a world previously saved.}

@t[loadworld @i[name] &key :creator]@>[@i(Function)]
@linkedtext{@t[Loadworld] loads a previously created world (but unlike @t[restore] the world is unpopulated).}

@t[loadworldspec @i[name] &key :creator]@>[@i(Function)]
@linkedtext{@t[Loadworldspec] loads previously defined worldspecs.}


@comment[ In(world entity)  internal or exported
Relations and basetypes 
name (dbobject string-or-symbol)
creator (world-or-worldspec string)  

name and creator are strings that are used as identifiers]

@Begin(Group)

Here are some of the transition relations we have defined in the examples:

@begin(programexample)

(DefRelation person
  :types (symbol)	
  :documentation "(Person x) an object representing a person.")

(DefRelation office-number
  :types (integer)
  :definition ((x) s.t. (integer-in-range x 1 99))
  :documentation "(Office-number i) an integer from 1 to 99 inclusive")

(DefRelation office 
  :types (person office-number)
  :count ((person output) :countspec :optional)) 
  :documentation "(Office person number) associates a person with  
                  that person's office number.")

(DefRelation office-phone 
  :types (office-number ((i) s.t. (integer-in-range i 100 999)))
  :count ((output integer) :countspec :optional))
  :documentation "The office-phone relation associates an office (actually
                  an office number) with a number that is the 
                  office's phone number.")

(DefRelation forward-phone 
  :arity 2
  :documentation "Forward-phone models the association between phone 
                  numbers when a phone is forwarded.")

(set-listof (p) s.t. (person p)
	'(John Amy Jane Dave Fred Mary Jim Mark))

(set-listof (o n) s.t. (office o n)
	'((John 18) (Amy 24) (Jane 16) (Dave 10) 
          (Fred 18) (Mary 24) (Jim 12) (Mark 14)))

(set-listof (x y) s.t. (office-phone x y)
	'((10 123) (12 333) (14 542) (16 234)
	  (18 562) (20 405) (22 239) (24 342)))

(set-listof (x y) s.t. (forward-phone x y)
	'((333 123) (123 542) (405 239)))
@End(ProgramExample)
@End(Group)

@Begin(Group)

The following is an example of the use of WORLDS to save and restore the
data in the above relations.  First we define a specification for the world:

@Begin(ProgramExample) 
(setq testworldspec
      (createworldspec
	"test"
	"Worldspec used as a example in the training manual"
	nil
	nil
	'((:internal
	    (person
	      (office @@ $))
	    (phone-number 
	      (office-phone @@ $)
	      (forward-phone @@ $))))
	:creator "user")) 
@End(ProgramExample)
@End(Group)

Then we create an instance of the world and populate it:
@Begin(ProgramExample)
(setq testworld
	(createworld
	  "testworld"
	  "World used as an example in the training manual"
	  testworldspec
	  :creator "user"))

(populate testworld :in (listof (o) s.t. (E (n) (office o n))))
@End(ProgramExample)

We can now save this state of the world:
@Begin(ProgramExample)
(save testworld :batch t :comment "Initial testworld")
@end(programexample)

Change the data of these relations:
@Begin(ProgramExample)
(set-listof (p) s.t. (person p)
	'(John Amy Fred Mary Wanda Bill))

(set-listof (o n) s.t. (office o n)
	'((John 10) (Amy 12) (Fred 12)
	  (Mary 16) (Wanda 20) (Bill 24)))

(listof (p) s.t. (office p '12)) => (Fred Amy)
@End(ProgramExample)

Save the new state of the world:
@Begin(ProgramExample)
(save testworld :batch t :comment "Second testworld") 
@end(programexample)

And now restore the former state of the world:
@Begin(ProgramExample)
(setq target (any (s) s.t. (and (state testworld s)
	                        (comment s "Initial testworld"))))

(wor::restore (loadworld "testworld" :creator "user" :targetstate target)) 

(listof (p) s.t. (office p '12))
      => '(MARK)
@end(programexample)

@Appendix(Glossary)

@begin(description, font smallbodyfont, leftmargin +20, indent -20, spread .5)
@i(annotation)@\optional declarations in a specification that address representation 
and efficiency concerns rather than functionality

@i(arity)@\the number of objects in each tuple of a relation

@i(atomic transition)@\change to a database in which one or more data updates are treated as a single step

@i(automation rule)@\rule that invokes some computation in response to a database transition that matches a
specified pattern 

@i(compound-wff)@\wff containing a quantifier, connective or temporal operator

@i(computed relation)@\unchanging relation defined in terms of arbitrary Lisp computations

@i(consistency rule)@\rule that enforces conditions on the database by
signaling an error or attempting to carry out a repair procedure

@i[count constraint]@\idiomatic consistency rule that restricts the cardinality of certain projections of 
the tuples of a relation

@i(defined relation)@\derived relation specified by a ground description

@i(derivation idiom)@\predefined syntax for methods which derive or compute relations
from other relations and Lisp computations 

@i(derived relation)@\potentially changing relation defined in terms of other relations that are 
either transition relations or less derived relations

@i(description)@\list of the form @t[(@i(vars) s.t. @i(wff))] that can serve as a relation

@i(generator)@\procedure that iterates through the tuples of a relation or description

@i(ground description)@\description having the property that all of the
operands of its constituent primitive wffs are constants, quantified
variables, or variables from from the variable list of the description

@i(n-tuple)@\sequence of n objects

@i(object)@\any value that can be stored in a variable 

@i(primitive-wff)@\wff whose car is a relation name and whose cdr is list whose length is equal to the arity of the relation

@i(relation)@\(possibly infinite) set of tuples that are all the same length

@i(representation)@\data structure for a transition relation

@i(rule)@\mechanism that reacts to changes or proposed changes to the database

@i(specification)@\detailed functional description of a system 

@i(transition relation)@\relation whose contents are defined by database updates
 
@i(tuple)@\sequence of objects 

@i(type)@\relation whose arity is 1

@i[type constraint]@\idiomatic consistency rule that restricts the types of the operands of a relation

@i(well-formed formula)@\expression in first order logic

@Comment<@i(wff)@\well-formed formula>
@end(description)



@COMMENT[Queries that contain vars translate into generators
(?? e (x) (= x 5)) translates to (forany (x) s.t. (= x 5) T ifnone NIL)
]