[m-dev.] for review: Aditi documentation
Simon Taylor
stayl at cs.mu.OZ.AU
Thu Jul 16 15:26:42 AEST 1998
Hi Fergus,
This is round two of the Aditi documentation.
Thanks,
Simon.
Estimated hours taken: 3
Aditi documentation.
doc/reference_manual.texi
doc/user_guide.texi
Documentation of Aditi options and pragmas (commented out).
www/papers.html
Added the transactions paper and the context transformation paper
(commented out).
www/papers/tr90-2.ps.gz
The context transformmation paper, added here because David Kemp
is longer in the department.
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/16 05:12:20
@@ -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,130 @@
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 compiler 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.
+
+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. Every Aditi predicate
+must have one input argument of type @samp{aditi:state} - this ensures
+that database predicates cannot be called outside a transaction. Aditi
+predicates must be stratified and must not be mutually recursive with
+predicates in other modules.
+
+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 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 for the predicate.
+ at samp{psn} is the default.
+
+ at example
+:- pragma memo(@var{Name}/@var{Arity}).
+:- pragma 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.
+ 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. If no
+ at samp{:- pragma owner(...)} declaration is given, the owner is taken from
+the @samp{--aditi-user} option.
+
+ 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 @samp{aditi:state}
+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.
+
+ 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 schema
+A schema is a representation of the types of the attributes a relation.
+
+ at item stratification
+A program is stratified if there are no recursive arcs in the call graph
+which pass 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{aditi/aditi.m} in the
+ at samp{extras} distribution.
+
+ at end table
+
+ at end ifset
+ at c aditi
+
@node Bibliography
@chapter Bibliography
@@ -4398,6 +4530,14 @@
* [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},
+ at end ifset
@end menu
@node [1]
@@ -4435,6 +4575,30 @@
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 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/16 05:16:51
@@ -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
@@ -1131,6 +1141,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{aditi/aditi.m} in the @samp{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{aditi} subdirectory of the @samp{extras}
+distribution. Once you have done that, use the Mmakefile in
+ at 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 +1661,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 +1787,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 +1889,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 +2355,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 +2731,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 +2791,27 @@
@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 a newline separated list of module names to compile
+from the standard input rather than the command line.
+
+ 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 any Aditi RL files produced.
+Defaults to the value of the USER environment variable. If USER is
+not set, @samp{--aditi-user} defaults to the string ``guest''.
+
+ at end ifset
+ at c aditi
+
@end table
@node Link options
Index: papers.html
===================================================================
RCS file: /home/staff/zs/imp/www/papers.html,v
retrieving revision 1.11
diff -u -t -u -r1.11 papers.html
--- papers.html 1998/04/21 04:53:49 1.11
+++ papers.html 1998/07/16 04:52:31
@@ -330,6 +330,69 @@
</ul>
+<!---------- The Aditi interface is not useful yet
+--------------------------------------------------
+
+The following papers are relevant to the interface to the Aditi deductive
+database system (see the "Aditi deductive database interface"
+section in Mercury Language Reference Manual listed under
+"Implementation dependent pragmas" in the "Pragmas" chapter).
+The first describes the method used to express transactions and
+updates in Mercury. The second describes a source-to-source transformation
+implemented in the Mercury compiler.
+
+<p>
+<ul>
+
+
+<li>
+<strong>
+Database transactions in a purely declarative logic programming language.
+</strong>
+<br>
+David B. Kemp, Thomas Conway, Evan Harris, Fergus Henderson,
+Kotagiri Ramamohanarao and Zoltan Somogyi.
+<br>
+<em>
+Technical Report 96/45
+</em>
+Department of Computer Science, University of Melbourne, December 1996.
+<a href = "http://www.cs.mu.OZ.AU/publications/tr_db/mu_96_45.ps.gz">
+Available here (58K)
+</a>
+<a href = "./mu_96_45_cover.ps.gz">
+with cover page.
+</a>
+
+<li>
+<strong>
+Right-, left-, and multi-linear rule transformations that maintain
+context information.
+</strong>
+<br>
+David B. Kemp and Kotagiri Ramamohanarao and Zoltan Somogyi.
+<br>
+<em>
+Technical Report 90/2
+</em>
+Department of Computer Science, University of Melbourne, October 1997.
+<a href = "papers/tr90-2.ps.gz">
+Available here (48K).
+</a>
+Note that this paper incorrectly claims that
+the context transformation can be applied to
+mixed-linear predicates containing pseudo-left-linear rules
+as well as other linear rules.
+It is corrected in David Kemp's thesis,
+<a href = "http://www.cs.mu.oz.au/~kemp/papers/thesis.ps.gz">
+available here (560K).
+</a>
+
+</ul>
+
+--------------------------------------------------
+-------------------------------------------------->
+
<hr>
<h2><a name="presentations">Presentations on Mercury<a></h2>
More information about the developers
mailing list