Fibonacci? On Lazy Evaluation and Generative Arithmetics in Xcerpt
Xcerpt's computational power is rather obviously turing-complete. So let's solve some problems that are unusual for a query language, but standard tasks for general programming languages. The first problem discussed in this series are a rule-set for computing the Fibonacci numbers. Such a rule-set might actually be useful in a query language, e.g., to test whether a set of queried data values corresponds to a Fibonacci distribution. However, there are a number of problems with a program for generating Fibonacci numbers in Xcerpt. These problems are discussed in the following.
Generative Arithmetics (and Functions in General)
For each variable in an Xcerpt rule at least one occurrence of that variable in the rule must be generative or defining, i.e., it must during evaluation "generate" bindings for that variable. Unfortunately, there is currently no built-in means to enumerate infinite sets such as integers which are needed as input domain for Fibonacci numbers. Current Xcerpt specifications and the 2004 prototype do not provide for generative built-in functions. Rather functions may in query terms only occur in condition boxes, i.e., to restrict previously established binding candidate sets. During our recent exploration of Web services a similar issue has arisen. Our current thinking is that an appropriate solution is the redefinition of conjuncts in query terms to include also built-ins. However, in that case a means must be provided to differentiate between "input" and "output" parameters or, speaking in functional terms, between parameters and result. Both syntactical and semantical consequences of such a solution are currently under investigation, for preliminary results see Clemens Scheffel's master thesis.
At the time being, no generative arithmetics are
provided, thus another way of grounding the input for a
function such as the Fibonacci function must be found.
Therefore, the solution at
http://svn.amachos.com/xcerpt/applications/2006/fibonacci/
chooses to ground the input for the Fibonacci function
using a Peano-style successor function on "integers":
Starting with zero we can enumerate all
integers by successively adding succ() functor
to the integer. Such a solution, unfortunately, poses
another problem:
Lazy vs. Set-based Evaluation
We claim sometimes that the 2004 Xcerpt prototype uses backward-chaining. But, as also stated in other places, it actually uses a set-based backward-chaining where all solutions for a rule that is "called" from another rule are computed before they are combined with solutions for other conjunctions in the calling rule (if there are any). Though this behavior is conceptually needed, the 2004 implementation probably takes the semantics too literally at this point. For the upcoming AMachoS implementation we are working on a lazy- or cursor-based evaluation where only as much of the solutions of a called rule are generated as needed for further processing.
As the current prototype, however, still uses plain
set-based evaluation a proper Peano-style successor
function can not be implemented as it generates infinitely
many answers, thus leading to non-termination even if the
Fibonacci function is called with properly bound input
variables. Hence, the solution at
http://svn.amachos.com/xcerpt/applications/2006/fibonacci/
uses a fixed interval of integers to ground the Fibonacci
function: Instead of a proper, recursive
succ() function just some base cases for the
interval 1-5 are provided.
If you have comments or questions on this application, please post them here or at the xcerpt-devel mailing list.