2004–2008
2004–2008
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 AMaχoS 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.
Fibonacci? Generative Arithmetics in Xcerpt
Tuesday, April 17, 2007
… arithmetics and value invention in Xcerpt.
Publication:
—
Poster:
—
Sources:
… arithmetics and value invention in Xcerpt.
Publication:
—
Poster:
—
Sources:
Imprint Privacy Disclaimer |