Menu
▾
▴
[Xsb-commits] CVS: XSB/docs/userman builtin.tex, 1.68, 1.69 rbltin.tex, 1.54, 1.55 state.tex, 1.41, 1.42
|
From: Terrance S. <ts...@us...> - 2008-03-27 19:47:09
|
Update of /cvsroot/xsb/XSB/docs/userman In directory sc8-pr-cvs10.sourceforge.net:/tmp/cvs-serv28719 Modified Files: builtin.tex rbltin.tex state.tex Log Message: Rewrote doc for index/[2,3] and fiddled with dynamic/1. Index: builtin.tex =================================================================== RCS file: /cvsroot/xsb/XSB/docs/userman/builtin.tex,v retrieving revision 1.68 retrieving revision 1.69 diff -u -r1.68 -r1.69 --- builtin.tex 22 Mar 2008 18:09:30 -0000 1.68 +++ builtin.tex 27 Mar 2008 19:47:12 -0000 1.69 @@ -353,8 +353,8 @@ \bi \item {\tt instantiation\_error} \ei -\item {\tt Stream\_or\_alias} is neither a variable, nor a a stream - term nor an alias. +\item {\tt Stream\_or\_alias} is neither a variable, nor a stream term + nor an alias. \bi \item {\tt domain\_error(stream\_or\_alias,Stream\_or\_alias)} \ei Index: rbltin.tex =================================================================== RCS file: /cvsroot/xsb/XSB/docs/userman/rbltin.tex,v retrieving revision 1.54 retrieving revision 1.55 diff -u -r1.54 -r1.55 --- rbltin.tex 21 Feb 2008 19:45:53 -0000 1.54 +++ rbltin.tex 27 Mar 2008 19:47:12 -0000 1.55 @@ -395,45 +395,51 @@ \vspace{-.35in} \standarditem{index(+PredSpec, +IndexSpec, +HashTableSize)}{index/3} -If {\tt index/3} is used, then the predicate indicated by {\tt -PredSpec} is declared to be indexed according to {\tt IndexSpec} using -initial hash table of sizes of {\tt HashTableSize}. After this -directive is given, all clauses asserted to {\tt PredSpec} will be so -indexed. - -For dynamic predicates, -{\tt index/2} is an executable directive that can be used to specify -the indexing of a predicate before clauses to that predicate have been -asserted. - - -As an example, one could specify: {\tt index(p/5,[1+2,1,4],300)}. -After clauses are asserted to it, a call to {\tt p/5} would first -check to see if both the first and second arguments are non-variable -and if so, use an index based on both those values. Otherwise, it -would see if the second argument is non-variable and if so, use an -index based on it. Otherwise, it would see if the fourth argument is -non-variable and if so use an index based on it. As a last resort, it would -use no index but backtrack through all the clauses in the predicate. -(Notice that it may well make sense to include an argument that -appears in a joint specification later alone, as 1 in this example, -but it never makes sense foring the single argument to appear earlier. In -that case the joint index would never be used.) +| If {\tt index/3} is used, then the predicate indicated by {\tt +| PredSpec} is declared to be indexed according to {\tt IndexSpec} using +| initial hash table of sizes of {\tt HashTableSize}. After this +| directive is given, all clauses asserted to {\tt PredSpec} will be so +| indexed. + +| For dynamic predicates, +| {\tt index/2} is an executable directive that can be used to specify +| the indexing of a predicate before clauses to that predicate have been +| asserted. + + +| As an example, one could specify: {\tt index(p/5,[1+2,1,4],300)}. +| After clauses are asserted to it, a call to {\tt p/5} would first +| check to see if both the first and second arguments are non-variable +| and if so, use an index based on both those values. Otherwise, it +| would see if the second argument is non-variable and if so, use an +| index based on it. Otherwise, it would see if the fourth argument is +| non-variable and if so use an index based on it. As a last resort, it would +| use no index but a list containing an element that is a variablebacktrack through all the clauses in the predicate. +| (Notice that it may well make sense to include an argument that +| appears in a joint specification later alone, as 1 in this example, +| but it never makes sense foring the single argument to appear earlier. In +| that case the joint index would never be used.) } \standarditem{index(+PredSpec, +IndexSpec)}{index/2} \label{index_dynamic} \index{indexing!dynamic predicates} - -In general, XSB supports hash-based indexing on various arguments or -combinations of arguments, along with trie-based indexing. The -availability of various kinds of indexing depends on whether code is -static (e.g. compiled) or dynamic (e.g. asserted or loaded with {\tt -load\_dyn/1}). The executable directive {\tt index/2} does {\em -not\/} re-index an already existing predicate but takes effect only -for clauses asserted after the directive has been given. Index -directives can be given to the compiler as part of source code or -executed during program execution (analogously to {\tt op/3}). +% +In {\tt index(PredSpec, IndexSpec)}, {\tt PredSpec} is a predicate +indicator or term indicator, and {\tt IndexSpec} is a form of index +specification as described below. + +In general, XSB supports hash-based indexing on various arguments of +clauses, on combinations of arguments, as well as within the arguments +of a clause. The availability of various kinds of indexing depends on +whether code is static (e.g. compiled) or dynamic (e.g. asserted, +loaded with {\tt load\_dyn/1} and so on). Index directives can be +given to the compiler as part of source code or executed during +program execution (analogously to {\tt op/3}). When executed during +program execution, {\tt index/2} does {\em not\/} re-index an already +existing predicate; however for dynamic predicates {\tt index/2} does +affect the index for clauses asserted after the directive has been +given. \begin{itemize} \item {\em Hash-based Indexing} @@ -443,36 +449,43 @@ indicates the argument on which an index is to be constructed. If {\tt IndexSpec} is~0, then no index is kept (possibly an efficient strategy for predicates with only one or two clauses.) -\item {\em Dynamic Predicates} -For a dynamic predicate, (to which no clauses have yet been asserted), -{\tt IndexSpec} is either an {\tt IndexElt} or a list of {\tt -IndexElt}s. Each {\tt IndexElt} defines an index and specifies an argument or group of -arguments that make up the search key of the index. An argument is -indicated by a small integer ({\tt ArgNo}) indicating the argument number (starting -from 1) to use in the index. An argument indicator may optionally be annotated -as {\tt *(ArgNo)}. The argument number alone indicates that only the -main functor symbol of the indicated argument will participate in the -index. When annotated with the asterisk, the first 5 fields in the -corresponding term (in a depth-first traversal of the term) will be -used in the index. If there are fewer than 5, they all will be used. -If any of the first 5 is a variable, then the index cannot be used. - -An index is usually on a single argument, in which case the {\tt -IndexElt} consists of a single argument indicator. However, sometimes -one wants an index on multiple arguments, meaning that the values of -several arguments are to be concatenated to create the search key of -the index. Such a multi-argument (or joint) index is indicated by -using an {\tt IndexElt} that has up to 3 argument indicators separated -by the {\tt +} (plus) operator, e.g., {\tt 1+2+3}. - -For example, {\tt index(p/3,[2,1])} indicates that clauses asserted to -the predicate {\tt p/3} should be indexed on both the second and the -first argument. Subsequent calls to {\tt p/3} will first check to see -if the second argument is non-variable, and if so use that index, using -the main functor symbol of that argument. If the second argument is -variable, it will next check to see if the first argument is -non-variable and if so, use that index, built on the main functor -symbol of the first argument. +% +\item {\em Dynamic Predicates} For a dynamic predicate, (to which no + clauses have yet been asserted), a wide variety of indexing + techniques are possible. We discuss their syntax first, and then + their semantics. For dynamic predicates then, {\tt IndexSpec} can + be either an {\em indexing element} or a list of indexing elements. + Each indexing element defines a separate index and specifies an + argument or group of arguments that make up the search key of that + index. Thus an indexing element consists of one or more {\em + argument indicators} joined together by {\tt +/2}. An argument + indicator is may be an integer ({\tt ArgNo}) indicating an argument + number (starting from 1) to use in the index, or it may have the + form {\tt *(ArgNo)}. + + If {\tt ArgNo} is an integer, only the main functor symbol of + argument {\tt ArgNo} will participate in the index. When annotated + with the asterisk, the first 5 fields of argument {\tt ArgNo} (in a + depth-first traversal of the term) will be used in the index. If + there are fewer than 5, they all will be used. If any of the first + 5 is a variable, then the index cannot be used. + + An index is usually on a single argument, in which case the indexing + element consists of a single argument indicator. If an indexing + element contains more than one argument specifier, then a joint + index is specified i.e. an index will be constructed so that the + values of each argument indicator are to be concatenated to create the + search key of the index. + +Examples help clarify this. {\tt index(p/3,[2,1])} indicates that +clauses asserted for the predicate {\tt p/3} should be indexed on both +the second and the first argument. A query $Q$ to {\tt p/3} will +first use the second argument index to {\tt p/3} if the second +argument of $Q$ is non-variable, and will use the main functor of the +second argument. Otherwise, if the second argument of $Q$ is a +variable, but not the first argument, the first argument index of {\tt + p/3} will be used. If both arguments in $Q$ are variables, no index +will be used and $Q$ will backtrack through all clauses for {\tt p/3}. {\tt index(p/3,[*(2),1])} would result in similar behavior as the previous example, but the first index to be tried (on the second @@ -483,16 +496,16 @@ After clauses are asserted to it, a call to {\tt p/5} would first check to see if both the first and second arguments are non-variable and if so, use an index based on both those values. Otherwise, it -would see if the first argument is non-variable and if so, use an index -based on it. Otherwise, it would see if the fourth argument is +would see if the first argument is non-variable and if so, use an +index based on it. Otherwise, it would see if the fourth argument is non-variable and if so use an index based on it. As a last resort, it would use no index but backtrack through all the clauses in the -predicate. In all these cases, the indexes are built using only the -main functor symbol in the indicated argument position. (Notice that -it may well make sense to include an argument that appears in a joint -specification later alone, as 1 in this example, but it never makes -sense forcing the single argument to appear earlier. In that case the -joint index would never be used.) +predicate. In each of these cases, the indexes are built using only +the main functor symbol in the indicated argument position. (Notice +that it may well make sense to include an argument that appears in a +joint specification later alone, as 1 in this example, but it never +makes sense forcing the single argument to appear earlier. In that +case the joint index would never be used.) If we want to use similar indexing on {\tt p/5} of the previous example, except say argument 1 takes on complex term values and we @@ -501,66 +514,114 @@ \end{itemize} -\item {\em Trie-based Indexing} -The executable declaration {\tt index(Predspec,trie)} causes clauses -for {\tt Predspec} to be asserted using tries (see \cite{RRSSW98}, -which is available through the XSB web page). The name trie indexing -is something of a misnomer since the trie itself both indexes the term -and represents it. In XSB, the above trie index is formed using a -left-to-right traversal of the unit clauses. These indexes can be -very effective if discriminating information lies deep within a term, -and if there is sharing of left-prefixes of a term, can reduce the -space needed to represent terms. Furthermore, asserting a unit clause -as a trie is much faster than asserting it using default WAM code. -\comment{ -Trie indexing can be used with alternative or joint indexes. For the -directive {\tt index(p/3,[2,1],trie)}, two trie indices would be -formed for {\tt p/3}: one that traversed arguments in order {\em -2,1,3} and another that traversed arguments in order {\em 1,2,3}. The -actual implementation seeks to reduce redundant storage of code for -alternative indices. -} - +\item {\em Trie-based Indexing} +% +If {\tt Predspec} is dynamic, the executable directive {\tt + index(Predspec,trie)} causes clauses for {\tt Predspec} to be +asserted using tries (see \cite{RRSSW98}, which is available through +the XSB web page). The name trie indexing is something of a misnomer +since the trie itself both indexes the term and represents it. In +XSB, a trie index is formed using a left-to-right traversal of the +unit clauses. These indexes can be very effective if discriminating +information lies deep within a term, and if there is sharing of +left-prefixes of a term, trie indexing can reduce the space needed to +represent terms. Furthermore, asserting a unit clause as a trie is +much faster than asserting it using default WAM code. +%%%%%%%%%%%% +\comment{ Trie + indexing can be used with alternative or joint indexes. For the + directive {\tt index(p/3,[2,1],trie)}, two trie indices would be + formed for {\tt p/3}: one that traversed arguments in order {\em + 2,1,3} and another that traversed arguments in order {\em 1,2,3}. + The actual implementation seeks to reduce redundant storage of code + for alternative indices. } +%%%%%%%%%%%% Despite these advantages, representing terms as tries leads to semantic differences from asserted code, of which the user should be aware. First, the order of clauses within a trie is arbitrary: using {\tt asserta/1} or {\tt assertz} for a predicate currently using trie indexing will give the same behavior as using {\tt assert}. Also, the current version of XSB only allows trie indexing for unit clauses. - -Trie-based indexing is available only for dynamic predicates. \end{itemize} +{\bf Error Cases} +\bi +\item {\tt PredSpec} or {\tt IndexSpec} is a variable +\bi +\item {\tt instantiation\_error} +\ei +\item {\tt PredSpec} is neither a variable, a predicate indicator, nor a + callable term. +\bi +\item {\tt type\_error(predicate\_indicator\_or\_callable,PredSpec)} +\ei +\item {\tt IndexSpec} is not ground +\bi +\item {\tt instantiation\_error} +\ei +\item {\tt IndexSpec} is neither a properly formed indexing element + nor a list of indexing elements +\bi +\item {\tt domain\_error(indexing\_element,IndexSpec)} +\ei +\item {\tt IndexSpec} is a list containing an element {\tt IndexElt} + that not a properly formed indexing element +\bi +\item {\tt domain\_error(indexing\_element,IndexElt)} +\ei +\item {\tt PredSpec} represents a predicate that has been previously + defined to be static +\bi +\item {\tt permission\_error(modify,static\_predicate)} +\ei +\ei + \standarditem{dynamic(+PredSpec)}{dynamic/1}\label{dynamic/1} % +In XSB, {\tt PredSpec} may be a predicate indicator, a callable term, +or a comma-list or list of predicate indicators or callable terms. + As a compiler directive, {\tt dynamic/1} is necessary to specify that code in a compiled file is to be treated as dynamic: without this declaration compiled clauses will be treated as static. As an -executable directive, if {\tt Predicate} is not previously defined, it +executable directive, if {\tt PredSpec} is not previously defined, it will be initialized to a dynamic predicate without any clauses. If -{\tt Predicate} is previously defined and dynamic, {\tt dynamic/1} has -no effect. If {\tt Predicate} is previously defined as static, a -permission error will be thrown. If {\tt Predicate} is previously -defined as static, a permission error will be thrown. +{\tt PredSpec} is previously defined and dynamic, {\tt dynamic/1} has +no effect. If {\tt PredSpec} was previously defined as static, a +permission error will be thrown. {\bf Error Cases} \bi -\item {\tt Predicate} has been previously defined to be static +\item {\tt PredSpec} is a variable +\bi +\item {\tt instantiation\_error} +\ei +\item {\tt PredSpec} is neither a variable, a predicate indicator, a + callable term, or a comma-list or list of predicate indicators or + callable terms. +\bi +\item {\tt type\_error(callable,PredSpec)} +\ei +\item A predicate in {\tt PredSpec} has been previously defined to be static \bi \item {\tt permission\_error(modify,static\_predicate)} \ei \ei +In addition, if a predicate {\tt p/n} was declared to be dynamic and a +file containing clauses for {\tt p/n} is later consulted, a permission +error will be thrown. + \comment{ % 07/11 changed this behavior -If previously defined as compiled, {\tt Predicate} will be converted -to dynamic, which means that clauses can be added, although the -compiled portion cannot be manipulated. Note that {\tt dynamic/1} can -be used like a compiler directive, since it will be passed through to -be executed when the module is loaded. Note, however, that the -semantics is different from that of the standard \cite{ISO-Prolog} -when the file contains clauses defining the so-specified predicate. +| If previously defined as compiled, {\tt Predicate} will be converted +| to dynamic, which means that clauses can be added, although the +| compiled portion cannot be manipulated. Note that {\tt dynamic/1} can +| be used like a compiler directive, since it will be passed through to +| be executed when the module is loaded. Note, however, that the +| semantics is different from that of the standard \cite{ISO-Prolog} +| when the file contains clauses defining the so-specified predicate. } \standarditem{table(+PredSpec)}{table/1} Index: state.tex =================================================================== RCS file: /cvsroot/xsb/XSB/docs/userman/state.tex,v retrieving revision 1.41 retrieving revision 1.42 diff -u -r1.41 -r1.42 --- state.tex 16 Mar 2008 19:06:24 -0000 1.41 +++ state.tex 27 Mar 2008 19:47:12 -0000 1.42 @@ -33,12 +33,13 @@ soon as it is loaded in the system or when another module that is loaded in the system imports some predicates from module {\tt M}. - Note that due to the dynamic loading of \ourprolog, a module can be - current even if it has not been loaded, and that some predicates of - that module may not be defined. In fact, a module can be current even - if it does not exist. This situation occurs when a predicate is - improperly imported from a non-existent module. Despite this, - a module can never lose the property of being {\em current}. + Note that due to the dynamic loading of XSB, a module can be + current even if it has not been loaded, and that some predicates + of that module may not be defined. In fact, a module can be + current even if it does not exist. This situation occurs when a + predicate is improperly imported from a non-existent module. + Despite this, a module can never lose the property of being {\em + current}. \end{itemize} \begin{description} |