[m-dev.] for review: Aditi documentation

[Simon Taylor]

> > Index: papers.html
> ...
> > +<a href = "./mu_96_45_cover.ps.gz">
> 
> Why the `./'?
> 
 
Sorry, that should be:
<a href = "http://www.cs.mu.OZ.AU/publications/tr_db/mu_96_45_cover.ps.gz">

Here's a new diff for the other parts. 

Thanks,
Simon.



Index: reference_manual.texi
===================================================================
RCS file: /home/staff/zs/imp/mercury/doc/reference_manual.texi,v
retrieving revision 1.99
diff -u -t -u -r1.99 reference_manual.texi
--- reference_manual.texi	1998/07/16 02:44:11	1.99
+++ reference_manual.texi	1998/07/21 03:01:05
@@ -12,6 +12,9 @@
 @end ifinfo
 @c @end ignore
 
+ at c Uncomment the line below to enable documentation of the Aditi interface.
+ at c @set aditi
+
 @c @smallbook
 @c @cropmarks
 @finalout
@@ -4180,6 +4183,11 @@
                                 calculated results and detecting or avoiding
                                 certain kinds of infinite loops.
 * Termination analysis::        Support for automatic proofs of termination.
+ at ifset aditi
+* Aditi deductive database interface::
+                                Support for bottom-up evaluation of Mercury
+                                predicates.
+ at end ifset
 @end menu
 
 @node Fact tables
@@ -4386,6 +4394,160 @@
 If it cannot prove the termination of the specified predicate or
 function then the compiler will quit with an error message.
 
+ at ifset aditi
+ at node Aditi deductive database interface
+ at subsection Aditi deductive database interface
+
+The University of Melbourne Mercury implementation includes support for
+compiling Mercury predicates for bottom-up evaluation using the Aditi
+deductive database system. The Aditi system is not yet publicly available,
+so this is currently not very useful to anyone other than the Mercury and
+Aditi developers.
+
+Evaluation by a deductive database system is useful for predicates which
+use large amounts of data, since the database system can use efficient join
+algorithms instead of backtracking. Also, some predicates which loop when
+executed top-down may terminate when executed bottom-up by the database (this
+effect can also be achieved using tabling (@pxref{Tabled evaluation})).
+Bottom-up evaluation computes the answers to a predicate a set at a time,
+rather than a tuple at a time as in the normal top-down execution of a
+Mercury program.
+
+There are several restrictions on predicates to be evaluated using Aditi.
+Argument types may not include polymorphic, higher-order or abstract types.
+Type classes are not supported within database predicates. The argument
+modes must not contain partially instantiated insts. Aditi predicates must
+be stratified (@pxref{Aditi glossary}) and must not be mutually recursive
+with predicates in other modules.
+
+Every predicate with a @samp{:- pragma aditi(...)} or
+ at samp{:- pragma base_relation(...)} declaration must have an input
+argument of type @samp{aditi__state}. This ensures that Aditi predicates
+are only called from within transactions and that updates and database
+calls are ordered correctly, in the same way that @samp{io__state} arguments
+are used to ensure ordering of I/O operations. Within the clauses for
+predicates with a @samp{:- pragma aditi(...)} declaration variables with
+type @samp{aditi__state} may only be passed to other database predicates --
+they may not be packaged into terms or passed to top-down Mercury predicates.
+This allows the compiler to remove all instances of @samp{aditi__state}
+variables from database predicates, and enforces the restriction that
+top-down Mercury code called from within the database cannot call bottom-up
+code, which is currently impossible for Aditi to handle.
+
+Some useful predicates are defined in @file{aditi/aditi.m} in the
+ at samp{extras} distribution.
+
+The following pragma declarations control Aditi compilation.
+
+ at example
+:- pragma aditi(@var{Name}/@var{Arity}).
+ at end example
+
+This predicate should be evaluated using the Aditi deductive database.
+
+ at example
+:- pragma base_relation(@var{Name}/@var{Arity}).
+ at end example
+
+This predicate is an Aditi base relation.
+
+ at example
+:- pragma supp_magic(@var{Name}/@var{Arity}).
+:- pragma context(@var{Name}/@var{Arity}).
+ at end example
+
+Perform either the supplementary magic sets or context transformations.
+One of these transformations must be performed on every Aditi predicate.
+ at samp{supp_magic} is the default.
+There are restrictions on predicates to which the context transformation
+can be applied; these are described in @cite{Right-, left-, and multi-linear
+rule transformations that maintain context information.} @ref{[6]}.
+
+ at example
+:- pragma naive(@var{Name}/@var{Arity}).
+:- pragma psn(@var{Name}/@var{Arity}).
+ at end example
+
+Specify naive or predicate semi-naive evaluation (@pxref{Aditi glossary})
+for the predicate.
+ at samp{psn} is the default.
+
+ at example
+:- pragma aditi_memo(@var{Name}/@var{Arity}).
+:- pragma aditi_no_memo(@var{Name}/@var{Arity}).
+ at end example
+
+The Aditi deductive database can store the results of procedures within
+a transaction to avoid unnecessary recomputations. This is unrelated to
+the type of memoing described in @ref{Tabled evaluation}.
+ at samp{no_memo} is the default.
+ at c XXX this will probably change
+
+ at example
+:- pragma owner(@var{Name}/@var{Arity}, @var{UserName}).
+ at end example
+
+The predicate is owned by the named user. A predicate in the database
+is identified by owner, module name, predicate name and arity. The owner
+field is used for security checks. If no @samp{:- pragma owner(...)}
+declaration is given, the owner is taken from the @samp{--aditi-user}
+option, which defaults to the value of the environment variable @samp{USER},
+or ``guest'' if that is not set.
+
+ at subsubsection Aditi glossary
+
+ at table @asis
+
+ at item Aditi-RL
+Aditi Relational Language is used by the Aditi system to execute queries.
+The basic instructions in Aditi-RL are relational database operations such as
+ at samp{join}, @samp{select} and @samp{project}.
+
+ at item aggregate
+Aggregates are used to compute a value such as a sum over all the solutions
+for a predicate. Aggregates can be computed over Aditi predicates using
+ at samp{aditi__aggregate_compute_initial} defined in @file{extras/aditi/aditi.m}
+in the @samp{mercury-extras} distribution.
+
+ at item base relation
+A base relation is a predicate consisting of a set of facts
+stored in a database. There must be no clauses for a base relation.
+
+ at item derived relation
+A derived relation is an Aditi predicate for which there are clauses.
+Derived relations are compiled to Aditi-RL for execution by an Aditi database.
+
+ at item predicate semi-naive evaluation
+When a recursive predicate is called, the Aditi system produces the set of all
+solutions using fixed point iteration. The set of solutions is initialised
+to those tuples which can be derived using the non-recursive rules of the
+predicate. In each iteration, new tuples are derived for the predicate using
+the recursive rules for the predicate and the tuples derived in previous
+iterations. Evaluation finishes when no new tuples are generated.
+Predicate semi-naive evaluation (@pxref{[8]}) is a method of evaluating
+recursive predicates which uses just the new tuples in each iteration
+where possible. This improves efficiency by reducing the size of joins.
+
+ at item schema
+A schema is a representation of the types of the attributes of a relation.
+
+ at item stratification
+A program is stratified if no predicate can call itself through a negation
+or an aggregate.
+
+ at item transaction
+A transaction is a database operation which is executed atomically. If
+part of a transaction fails, the database reverts to its original state
+before the transaction. For details on how transactions are implemented
+in Mercury, see @cite{Database transactions in a purely declarative logic
+programming language} @ref{[7]} and @file{extras/aditi/aditi.m} in the
+ at samp{mercury-extras} distribution.
+
+ at end table
+
+ at end ifset
+ at c aditi
+
 @node Bibliography
 @chapter Bibliography
 
@@ -4398,6 +4560,17 @@
 * [4]::         Sagonas, @cite{The SLG-WAM: A Search-Efficient Engine
                 for Well-Founded Evaluation of Normal Logic Programs}.
 * [5]::         Demoen and Sagonas, @cite{CAT: the copying approach to tabling}.
+ at ifset aditi
+* [6]::         Kemp, Ramamohanarao and Somogyi,
+                @cite{Right-, left-, and multi-linear rule transformations
+                that maintain context information}.
+* [7]::         Kemp, Conway, Harris, Henderson, Ramamohanarao and Somogyi
+                @cite{Database transactions in a purely declarative
+                logic programming language}.
+* [8]::         Ramakrishnan, Srivistava and Sudarshan,
+                @cite{Rule ordering in bottom-up fixpoint evaluation
+                of logic programs}.
+ at end ifset
 @end menu
 
 @node [1]
@@ -4435,6 +4608,38 @@
 B. Demoen and K. Sagonas, @cite{CAT: the copying approach to tabling},
 submitted for publication,
 Katholieke Universiteit Leuven, 1998.
+
+ at ifset aditi
+ at node [6]
+ at unnumberedsec [6]
+David B. Kemp and Kotagiri Ramamohanarao and Zoltan Somogyi. 
+ at cite{Right-, left-, and multi-linear rule transformations that maintain
+context information}, 
+The Proceedings of the Sixteenth Conference on Very Large Databases, pages
+380--391, August 1990.
+Available from <http://www.cs.mu.oz.au/mercury/papers/tr90-2.ps.gz>.
+
+ at node [7]
+ at unnumberedsec [7]
+
+David B. Kemp, Thomas Conway, Evan Harris, Fergus Henderson,
+Kotagiri Ramamohanarao and Zoltan Somogyi,
+ at cite{Database transactions in a purely declarative
+logic programming language},
+Technical Report 96/45, Department of Computer Science, 
+University of Melbourne, December 1996,
+Available from <http://www.cs.mu.OZ.AU/publications/tr_db/mu_96_45.ps.gz>.
+
+ at node [8]
+ at unnumberedsec [8]
+
+R. Ramakrishnan, D. Srivistava and S. Sudarshan,
+ at cite{Rule ordering in bottom-up fixpoint evaluation of logic programs}.
+In @cite{Proceedings of the Sixteenth International Conference on
+Very Large Data Bases}, page 359--371, August 1990.
+
+ at end ifset
+ at c aditi
 
 @contents
 @bye
Index: user_guide.texi
===================================================================
RCS file: /home/staff/zs/imp/mercury/doc/user_guide.texi,v
retrieving revision 1.129
diff -u -t -u -r1.129 user_guide.texi
--- user_guide.texi	1998/07/03 06:43:47	1.129
+++ user_guide.texi	1998/07/17 08:10:13
@@ -12,6 +12,9 @@
 @end ifinfo
 @end ignore
 
+ at c Uncomment the line below to enable documentation of the Aditi interface.
+ at c @set aditi
+
 @c @smallbook
 @c @cropmarks
 @finalout
@@ -85,6 +88,13 @@
 * Invocation::      List of options for the Mercury compiler
 * Environment::     Environment variables used by the compiler and utilities
 * C compilers::     How to use a C compiler other than GNU C
+ at ifset aditi 
+* Using Aditi::     Executing Mercury predicates using the Aditi
+                    deductive database
+ at end ifset 
+ at c XXX I'd like to put the Aditi section below the Using libraries section
+ at c in the menu but texinfo doesn't seem to like `@ifset's in menus.
+ at c (complains about the next entry not having an `Up' node)
 @end menu
 @end ifinfo
 
@@ -170,6 +180,9 @@
 Files ending in @file{.dep} are automatically-generated Makefile fragments
 which contain the rules for an entire program.
 
+Files ending in @file{.rlo} are Aditi-RL bytecode files, which are
+executed by the Aditi deductive database system (@pxref{Using Aditi}).
+
 As usual, @file{.c} files are C source code,
 @file{.h} files are C header files,
 @file{.o} files are object code,
@@ -841,7 +854,7 @@
 removes the @samp{.int}, @samp{.int0}, @samp{.int2},
 @samp{.int3}, @samp{.opt}, @samp{.trans_opt},
 @samp{.date}, @samp{.date0}, @samp{.date3}, @samp{.optdate},
- at samp{.trans_opt_date},
+ at samp{.trans_opt_date}, @samp{.rlo},
 @samp{.d}, and @samp{.dep} belonging to one of the modules of the program,
 and also the various possible executables for the program ---
 @samp{@var{main-module}},
@@ -1131,6 +1144,38 @@
 which is probably the simplest way of organizing things, but the
 Mercury implementation does not require that.
 
+ at ifset aditi
+ at node Using Aditi
+ at chapter Using Aditi
+
+The Mercury compiler allows compilation of predicates for execution
+using the Aditi deductive database. There are several sources of useful
+information:
+
+ at itemize @bullet
+ at item
+the ``Aditi deductive database interface'' section in 
+Mercury Language Reference Manual (listed under
+``Implementation dependent pragmas'' in the ``Pragmas'' chapter)
+ at item
+the Aditi Reference Manual (doesn't exist yet) @c XXX
+ at item
+the file @file{extras/aditi/aditi.m} in the @samp{mercury-extras} distribution
+ at end itemize
+
+As an alternative to compiling stand-alone programs, you can execute
+queries using the Aditi query shell.
+ at c XXX reference.
+
+To compile code which accesses an Aditi database, you will need to install
+the Aditi library in the @samp{extras/aditi} subdirectory of the
+ at samp{mercury-extras} distribution. Once you have done that, use the
+Mmakefile in @samp{extras/aditi/samples} as a template, changing the values
+of the variables @samp{MADITI_DIR}, @samp{ADITI_API_INCL_DIR} and
+ at samp{ADITI_API_LIB_DIR}. You should then be able to compile as
+normal using Mmake (@pxref{Using Mmake}).
+ at end ifset
+
 @node Profiling
 @chapter Profiling
 
@@ -1619,10 +1664,29 @@
 Output detailed debugging traces of the optimization process.
 
 @sp 1
- at item --debug-vn <n>
+ at item --debug-vn @var{n}
 Output detailed debugging traces of the value numbering optimization pass.
 The different bits in the number argument of this option control the
 printing of different types of tracing messages.
+
+ at sp 1
+ at item --debug-pd
+Output detailed debugging traces of the partial
+deduction and deforestation process.
+
+ at ifset aditi
+ at sp 1
+ at item --debug-rl-gen
+Output detailed debugging traces of Aditi-RL code generation
+(@pxref{Using Aditi}).
+
+ at sp 1
+ at item --debug-rl-opt
+Output detailed debugging traces of Aditi-RL optimization
+(@pxref{Using Aditi}).
+ at end ifset
+ at c aditi
+
 @end table
 
 @node Output options
@@ -1726,6 +1790,15 @@
 Generate C code in @file{@var{module}.c}
 and object code in @file{@var{module}.o}
 but do not attempt to link the named modules.
+
+ at ifset aditi
+ at sp 1
+ at item --aditi-only
+Write Aditi-RL bytecode to @file{@var{module}.rlo} and do not compile to C
+(@pxref{Using Aditi}).
+ at end ifset
+ at c aditi
+  
 @end table
 
 @node Auxiliary output options
@@ -1819,6 +1892,29 @@
 The special argument value ``all''
 will cause the printing of all these fields.
 
+ at ifset aditi
+ at sp 1
+ at item --dump-rl
+Output a human readable form of the internal compiler representation
+of the generated Aditi-RL to @file{@var{module}.rl_dump} (@pxref{Using Aditi}).
+
+ at sp 1
+ at item --dump-rl-bytecode
+Output a human readable representation of the generated Aditi-RL
+bytecodes @file{@var{module}.rla}. Aditi-RL bytecodes are directly
+executed by the Aditi system (@pxref{Using Aditi}).
+
+ at sp 1
+ at item --generate-schemas
+Output schema strings for Aditi base relations to
+ at file{@var{module}.base_schema} and for Aditi derived
+relations to @file{@var{module}.derived_schema}. A schema
+string is a representation of the types of the attributes
+of a relation (@pxref{Using Aditi}).
+
+ at end ifset
+ at c aditi
+
 @end table
 
 @node Language semantics options
@@ -2262,6 +2358,9 @@
 * Low-level (LLDS -> LLDS) optimization options::
 * Output-level (LLDS -> C) optimization options::
 * Object-level (C -> object code) optimization options::
+ at ifset aditi
+* Aditi-RL optimization options::
+ at end ifset
 @end menu
 
 @node Overall optimization options
@@ -2635,6 +2734,34 @@
 
 @end table
 
+ at ifset aditi
+ at node Aditi-RL optimization options
+ at subsection Aditi-RL optimization options
+
+These optimizations are applied to the Aditi-RL code produced
+for predicates with @samp{:- pragma aditi(...)} declarations
+(@pxref{Using Aditi}).
+
+ at table @code
+ at item --optimize-rl
+Enable the optimizations of Aditi-RL procedures described below.
+
+ at sp 1
+ at item --optimize-rl-cse
+Optimize common subexpressions in Aditi-RL procedures.
+
+ at sp 1
+ at item --optimize-rl-invariants
+Optimize loop invariants in Aditi-RL procedures.
+
+ at sp 1
+ at item --detect-rl-streams
+Detect cases where intermediate results in Aditi-RL procedures
+do not need to be materialised.
+ at end table
+ at end ifset
+ at c aditi
+
 @node Miscellaneous options
 @section Miscellaneous options
 @table @code
@@ -2667,6 +2794,32 @@
 @c This option is now obsolete.  In the past it was used to avoid
 @c NU-Prolog's "Panic: growing stacks has required shifting the heap"
 @c message.
+
+ at sp 1
+ at item --filenames-from-stdin
+Read then compile a newline terminated module name from the standard input.
+Repeat this until EOF is reached. This allows a program or user to
+interactively compile several modules without the overhead of process
+creation for each one.
+
+ at ifset aditi
+ at sp 1
+ at item --aditi
+Enable Aditi compilation.  You need to enable this option if you
+are making use of the Aditi deductive database interface (@pxref{Using Aditi}).
+
+ at sp 1
+ at item --aditi-user
+Specify the Aditi login of the owner of the predicates in any Aditi RL
+files produced if no @samp{:- pragma owner(...)} declaration is given.
+The owner field is used along with module, name and arity to identify
+predicates, and is also used for security checks. Defaults to the value
+of the @samp{USER} environment variable. If @samp{USER} is not set,
+ at samp{--aditi-user} defaults to the string ``guest''.
+
+ at end ifset
+ at c aditi
+
 @end table
 
 @node Link options