Mutual Recursion with Anonymous (Inline) Functions in XPath 3
Do you remember the time when some people thought it was impossible to implement recursion using XPath anonymous (inline) functions? Fortunately for everyone, this turned out to be ultimately not true. 11 years ago, in a post in this blog, I demonstrated a technique to implement anonymous function recursion.
There are many proverbs about the fact that history seems to repeat itself:
If history repeats itself, and the unexpected always happens, how incapable must Man be of learning from experience.
As it turns out, a person who I deeply respect has been stating that: “At present this can be achieved by declaring a local variable bound to an anonymous function, but it’s clumsy to have to use completely different syntax for local and global functions, and functions defined in this way cannot be mutually recursive.”
The purpose of this article is to show clearly and without any doubt that the statement: “(XPath inline (anonymous)) functions defined in this way cannot be mutually recursive” is false.
To start with, here is the Wikipedia definition for “Mutual recursion”:
“In mathematics and computer science, mutual recursion is a form of recursion where two mathematical or computational objects, such as functions or datatypes, are defined in terms of each other”.[1]
Again there is one of the simplest and shortest examples of mutual recursion:
A standard example of mutual recursion, which is admittedly artificial, determines whether a non-negative number is even or odd by defining two separate functions that call each other, decrementing by 1 each time.[3] In C:
bool is_even(unsigned int n) {
if (n == 0)
return true;
else
return is_odd(n - 1);
}
bool is_odd(unsigned int n) {
if (n == 0)
return false;
else
return is_even(n - 1);
}
These functions are based on the observation that the question is 4 even? is equivalent to is 3 odd?, which is in turn equivalent to is 2 even?, and so on down to 0
Here is an implementation of a mutual-recursive solution to this problem in pure XPath 3:
Generators are well known and provided out of the box in many programming languages. Per Wikipedia:
“In computer science, a generator is a routine that can be used to control the iteration behaviour of a loop. All generators are also iterators.[1] A generator is very similar to a function that returns an array, in that a generator has parameters, can be called, and generates a sequence of values.
However, instead of building an array containing all the values and returning them all at once, a generator yields the values one at a time, which requires less memory and allows the caller to get started processing the first few values immediately. In short, a generator looks like a function but behaves like an iterator.”
The goal of this proposal (major use-cases)
A generator in XPath should be a tool to easily implement the solutions to the following use-cases:
Processing a huge collection whose members may not all be needed.
A generator will produce only the next member of the collection and only on demand basis.
Handling a collection containing unknown or infinite number of members.
When requested the next member of the collection the generator will always produce it, if the collection still contains any members. It is the responsibility of the caller to issue only the necessary number of requests for the really needed next members.
What is achieved in both cases:
A (next) member is produced only on request. No time is spent on producing all members of the collection.
A (next) member is produced only on request. No memory is consumed to store all members of the collection.
A good problem that is based on these use-cases is to generate a collection of the first N members that have some wanted properties, and are generated from other collection(s), when it is not known what the size of the original input collections would be in order for the desired number of N members to be discovered.
For example: Produce the first 1 000 000 (1M) prime numbers.
let $generator as record
(initialized as xs:boolean,
endReached as xs:boolean,
getCurrent as function(..) as item()*,
moveNext as function(..) as .. ,
* )
It has four fixed-named keys, and any other map-keys, as required to hold the internal state of that specific generator.
Here is the meaning of the four fixed/named keys:
initialized is a boolean. When a generator $gen is initially instantiated, $gen?initialized is false(). Any call to $gen?getCurrent() raises an error. In order to get the first value of the represented collection, the caller must call $gen?moveNext()
endReached is a boolean. If after a call to moveNext() the value of the returned generator’s endReached key is true() then calling moveNext() and/or getCurrent() on this generator raises an error.
getCurrent is a function of zero arguments. It must only be called if the values of initialized is true() and the value of endReached is false(), otherwise an error must be raised. This function produces the current member of the collection after the last call to moveNext, if this call didn’t return a generator whose endReached value was true()
moveNext is a function of zero arguments. When called on a generator whose endReached value is false() then it produces the next (state of the) generator. including a possibly true() value of endReached and if this value is still false(), then calling getCurrent() produces the value of the next member of the collection.
Examples of operations on generators
The following examples are written in pseudo-code as at the time of writing there was no available implementation of records. And also, the code for recursion in pure XPath makes any such example longer than necessary for grasping its meaning.
Take the first N members of the collection
take($gen as generator, $n as xs:integer, $result as array(*) = []) as array(*)
{
let $gen := if(not($gen?initialized)) then $gen?moveNext()
else $gen
$result := if(not($gen?endReached) and $n gt 0)
then array:append($result, $gen?getCurrent())
return
if(not($gen?endReached) and $n gt 0)
then take($gen?moveNext(), $n -1, $result)
else $result
}
Skip the first N members from the collection
skip($gen as generator, $n as xs:integer) as generator
{
if($n eq 0) then $gen
else
{
let $gen := if(not($gen?initialized)) then $gen?moveNext()
else $gen
return
if(not($gen?endReached) then skip($gen?moveNext(), $n -1)
else $gen
}
}
Subrange of size N starting at the M-th member
subrange($gen as generator, $m as xs:integer, $n as xs:integer)
{
take(skip($gen, $m -1), $n)
}
Head of a generator
head($gen as generator)
{
take($gen, 1)
}
Tail of a generator
tail($gen as generator)
{
skip($gen, 1)
}
At index N
at($ind as xs:integer)
{
subrange($ind, 1)
}
For Each
for-each($gen as generator, $fun as function(*))
{
map:put($gen, "getCurrent", function() { $fun($gen?getCurrent()) } )
}
For Each Pair
for-each-pair($gen1 as generator, $gen2 as generator, $fun as function(*))
{
let $gen1 := if(not($gen1?initialized)) then $gen1?moveNext()
else $gen1,
$gen2 := if(not($gen2?initialized)) then $gen2?moveNext()
else $gen2,
return
if($gen1?endReached or $gen2?endReached)
then map:put($gen1, "endReached", true())
else map:put(map:put($gen1, "getCurrent",
function()
{ $fun($gen1?getCurrent(), $gen2?getCurrent()) }),
"moveNext",
function()
{ for-each-pair(skip($gen1, 1), skip($gen2, 1), $fun)}
)
}
Filter
filter($gen as generator, $pred as function(item()*) as xs:boolean)
{
let $gen := if(not($gen?initialized)) then $gen?moveNext()
else $gen,
$moveNext := function() { filter($gen?moveNext(), $pred) }
return if($gen?endReached or $pred($gen?getCurrent()))
then map:put($gen, "moveNext", $moveNext)
else filter($gen?moveNext(), $pred)
}
The trouble with XPath‘s fn:fold-right. Laziness in XPath.
This article discusses the standard XPath 3.1 function fn:fold-right, its definition in the official Spec, its lack of apparent use-cases and its utter failure to reproduce the (lazy) behavior of Haskell’s foldr , which is presumed to be the motivation behind fn:fold-right. The 2nd part of the article introduces the implementation of short-circuiting and generators, which together unprecedentedly provide laziness in XPath. Based on these, a new XPath function: fn:fold-right-lazy is implemented, that utilizes laziness, similar to Haskell’s foldr. This behavior is demonstrated in specific examples
Introduction
Higher order functions were introduced into XPath starting with version 3.0 in 2014 and later in version 3.1 in 2017. The definition of the standard function fn:fold-right closely mimics that of Haskell’s foldr, and anyone acquainted with foldr can be left with the impression that fn:fold-right would have identical behavior (and hence use-cases) as Haskell’s foldr.
Unfortunately, there is a critical difference between the definitions of these two functions. Whereas the definition of foldr explicitly defines its behavior when provided with a function, lazy in its 1st argument – from Haskell’s definition of foldr:
“… Note that since the head of the resulting expression is produced by an application of the operator to the first element of the list, given an operator lazy in its right argument, foldr can produce a terminating expression from an unbounded list.”
The XPath definition of fn:fold-right does not mention any laziness.
There is no official concept of “laziness” in XPath, thus fn:fold-right doesn’t cover some of the most important use-cases of Haskell’s foldr , which can successfully produce a result when passed an infinite (or having unlimited length) list.
This in fact makes fn:fold-right almost useless, and explains why even some of the members of the XPath 3.1 WG have stated on occasions that they do not see why the function was introduced.
1. fn:fold-right gone wrong – example
This Haskell code:
foldr (\x y -> (if x == 0 then 0 else x*y)) 1 (map (\x -> x - 15) [1 ..1000000])
foldr (\x y -> (if x == 0 then 0 else x*y)) 1 (map (\x -> x - 15) [1 ..10000000])
foldr (\x y -> (if x == 0 then 0 else x*y)) 1 (map (\x -> x - 15) [1 ..])
produces the product of all numbers in the following list, respectively:
Because all these 3 lists contain a zero as their 15th item, the expected result is 0 when evaluating any of these 3 expressions – even in the last case where the provided as argument list is infinite. And this is indeed what happens:
Not only Haskell produces the correct result in all cases, but regardless of the list’s length, the result is produced instantaneously!
Now, let us evaluate this equivalent XPath expression with BaseX:
let $product := function($input as array(xs:integer)) as xs:integer
{ array:fold-right($input,
1,
function($x as xs:integer, $y as xs:integer) as xs:integer
{if($x eq 0) then 0 else $x * $y})
},
$ar := array { (1 to 36) ! function($x as xs:integer) as xs:integer {$x -15}(.)}
return
$product($ar)
Here we are passing a list containing just 36 integers. The result is quite unexpected and spectacular:
Here is what happens:
Even though when processing the 15th integer in the array the result is 0, the XPath processor continues to evaluate the RHS (right-hand side) until the last member of the array (36).
On “its way back” the XPath processor multiplies: (36*35*34*33*32* …*6*5*4)*3, and the result of the right-most multiplication is bigger than the maximum integer (or decimal) that this XPath processor supports.
C r r r a s s h … As seen in the screenshot above.
The root cause for this unfortunate behavior is that the XPath processor doesn’t support short-circuiting and laziness. And thus, fn:fold-right is useless even in the normal/trivial case of a collection (array) with only 36 members. Not to speak of collections containing millions of members, or even infinite ones…
Let us see what happens when evaluating similar expressions with another XPath processor: Saxon.
Saxon seems to produce the correct result, however it takes exponentially longer times when the length of the passed array is increased, leading to this one:
It took 261 seconds for the evaluation to be done, but accessing the 15th member of the array and short-circuiting to 0 should be almost instantaneous… So what happens in this case? The difference between BaseX and Saxon is that Saxon implements a “Big Integer” and thus can multiply almost 1 000 000 integers without getting a value that cannot be handled… But doing almost 1M multiplications of big integers obviously takes time …
What is common in these two examples? Obviously, neither BaseX nor Saxon detects and performs short-circuiting. Why is this? What is the reason for this?
I asked a developer of BaseX if I could submit a bug about this behavior. His answer was shockingly unexpected: “This is not a bug, because no requirement in the Specification has been violated”.
Thus, the main cause of the common behavior of both XPath processors to handle the evaluation of these examples, is the specification of the function, which blatantly allows such crap to happen.
Now that we see this, let us try to provide the wanted, useful behavior writing our own function.
2. The fix: Step 1 – fn:fold-right in pure XPath
Before going in depth with our pure XPath solution, we need as a base a pure-XPath implementation of fn:fold-right .
let $fold-right-inner := function ($seq as item()*,
$zero as item()*,
$f as function(item(), item()*) as item()* ,
$self as function(*)
) as item()*
{
if(empty($seq)) then $zero
else
$f(head($seq), $self(tail($seq), $zero, $f, $self))
},
$fold-right := function ($seq as item()*,
$zero as item()*,
$f as function(item(), item()*) as item()*
) as item()*
{
$fold-right-inner($seq, $zero, $f, $fold-right-inner)
},
$fAdd := function($x, $y) {$x + $y},
$fMult := function($x, $y) {$x * $y}
return
$fold-right((1 to 6) ! function($x){$x - 3}(.), 1, $fMult)
When we evaluate the above with any of the two XPath processors, the correct result is produced:
720
And we certainly do have exactly the same problems as the provided built-in fn:fold-right with a similar example:
3. The fix: Step 2 – $fold-right-sc detecting and performing short-circuiting
Now that we have $fold-right as a base, let us add code to it so that it will detect and perform short-circuiting. We will implement a function similar to $fold-right but having this signature:
$fold-right-sc := function ($seq as item()*,
$zero as item()*,
$f as function(item(), item()*) as item()*,
$fGetPartial as function(*)
) as item()*
The last of the function’s parameters $fGetPartial returns a new function that is the partial application of $f, when its 1st argument is set to the current member of the input sequence $seq. The idea is that whenever short-circuiting is possible, $fGetPartial returns not a function having one argument (arity 1), but a constant – a function with 0 arguments (arity 0).
If the arity of the so produced partial application is 0, then our code will immediately return with the value $f($currentItem).
Here is the complete code of $fold-right-sc:
let $fold-right-sc-inner := function ($seq as item()*,
$zero as item()*,
$f as function(item(), item()*) as item()*,
$fGetPartial as function(*),
$self as function(*)
) as item()*
{
if(empty($seq)) then $zero
else
if(function-arity($fGetPartial(head($seq), $zero)) eq 0)
then $fGetPartial(head($seq), $zero) ()
else $f(head($seq), $self(tail($seq), $zero, $f, $fGetPartial, $self))
},
$fold-right-sc := function ($seq as item()*,
$zero as item()*,
$f as function(item(), item()*) as item()*,
$fGetPartial as function(*)
) as item()*
{
$fold-right-sc-inner($seq, $zero, $f, $fGetPartial, $fold-right-sc-inner)
},
$fAdd := function($x, $y) {$x + $y},
$fMult := function($x, $y) {if($x eq 0) then 0 else $x * $y},
$fMultGetPartial := function($x, $y)
{
if($x eq 0)
then function() {0}
else function($z) {$x * $z}
}
return
$fold-right-sc((1 to 1000000) ! function($x){$x - 3}(.),
1,
$fMult, $fMultGetPartial)
Do note:
If the current item (the head of the sequence) is 0, then $fMultGetPartial returns a function with 0 arguments (constant) that produces 0.
$fold-right-sc (inner) treats differently a partial application of arity 0 from a partial application with arity 1. In the former case it simply produces the expected constant value without recursing further. Here is the relevant code fragment:
if(empty($seq)) then $zero
else
if(function-arity($fGetPartial(head($seq), $zero)) eq 0)
then $fGetPartial(head($seq), $zero) ()
else $f(head($seq), $self(tail($seq), $zero, $f, $fGetPartial, $self))
And now BaseX has no problems with the evaluation, even though the input sequence is of size 1M. The complete evaluation takes just a fraction of a millisecond (0.04 ms):
With Saxon things are not so good. Even though Saxon produces the correct result, evaluating the expression with an input sequence of size 1M takes 0.5 seconds (half a second), and evaluating the expression with an input sequence of 10M takes 5 seconds (10 times as long):
What is happening?
Even though Saxon performs much faster than the previous 261 seconds, due to detecting the short-circuiting possibility and performing the short-circuit, Saxon still processes all 10M items when evaluating this subexpression (which obviously the more optimized BaseX doesn’t do in advance):
(1 to 10000000) ! function($x){$x - 3}(.)
Therefore, we have one remaining problem: How to prevent long sequences (or arrays) from being fully materialized before starting the evaluation of $fold-right-sc ?
4. The fix: Step 3 – replacing collections with generators
Generators are well known and provided out of the box in many programming languages. Per Wikipedia:
“In computer science, a generator is a routine that can be used to control the iteration behaviour of a loop. All generators are also iterators.[1] A generator is very similar to a function that returns an array, in that a generator has parameters, can be called, and generates a sequence of values. However, instead of building an array containing all the values and returning them all at once, a generator yields the values one at a time, which requires less memory and allows the caller to get started processing the first few values immediately. In short, a generator looks like a function but behaves like an iterator.”
A full-fledged generator (such as implemented in C#) is an instance of a Finite State Machine(FSM), and implementing it in full generality goes beyond the topic and goals of this article. Expect another article soon that will provide this.
Here we will implement a simple kind of generator, that when passed an integer index $N, produces the $Nth item of a specific sequence. Although this is probably the simplest form of a generator, it can be useful in many cases and is a good illustrative solution to our current problem. The whole approach of replacing “something” with a function that must be called to produce this “something” is known as “lifting”
First, we will add to our $fold-right just the use of generators, without the detection and performing of short-circuiting:
let $fold-right-lifted-inner := function ($seqGen as function(xs:integer) as array(*),
$index as xs:integer,
$zero as item()*,
$f as function(item(), item()*) as item()* ,
$self as function(*)
) as item()*
{
let $nextSeqResult := $seqGen($index),
$isEndOfSeq := $nextSeqResult(1),
$seqItem := $nextSeqResult(2)
return
if($isEndOfSeq) then $zero
else
$f($seqItem, $self($seqGen, $index+1, $zero, $f, $self))
},
$fold-right-lifted := function ($seqGen as function(xs:integer) as array(*),
$zero as item()*,
$f as function(item(), item()*) as item()*
) as item()*
{
$fold-right-lifted-inner($seqGen, 1, $zero, $f, $fold-right-lifted-inner)
},
$NaN := xs:double('NaN'),
$fSeq1ToN := function($ind as xs:integer,
$indStart as xs:integer,
$indEnd as xs:integer) as array(*)
{
if($ind lt $indStart or $ind gt $indEnd)
then array{true(), $NaN}
else array{false(), $ind}
},
$fSeq-1-6 := $fSeq1ToN(?, 1, 6),
$fAdd := function($x, $y) {$x + $y},
$fMult := function($x, $y) {$x * $y}
return
$fold-right-lifted($fSeq-1-6, 1, $fMult)
Here we see an example of a simple generator – the function $fSeq1ToN.
This function returns an array with two members: a Boolean, which if true() indicates the end of the sequence, and the 2nd member is the current head of the simulated sequence. The generator has two other parameters which are the values (inclusive) for the start-index and the end-index. Whenever the passed value of $ind is outside of this specified range, $fSeq1ToN returns a result array with its first member set to true() (the 2nd member of the result must be ignored in this case), which indicates end-of sequence. Otherwise it returns array{false(), $ind} . It is the responsibility of the caller to stop calling the generator:
$fSeq1ToN := function($ind as xs:integer,
$indStart as xs:integer,
$indEnd as xs:integer) as array(*)
{
if($ind lt $indStart or $ind gt $indEnd)
then array{true(), $NaN}
else array{false(), $ind}
}
Evaluating the complete XPath expression above produces the correct result both in BaseX and in Saxon: the product of the integers 1 to 6:
Now that we have successfully implemented the last missing piece of our complete solution, let us put everything together:
5. The fix: Step 4 – putting it all together
Finally we can replace the input sequence in $fold-right-sc with a generator:
let $fold-right-sc-lifted-inner :=
function ($seqGen as function(xs:integer) as array(*),
$index as xs:integer,
$zero as item()*,
$f as function(item(), item()*) as item()* ,
$fGetPartial as function(*),
$self as function(*)
) as item()*
{
let $nextSeqResult := $seqGen($index),
$isEndOfSeq := $nextSeqResult(1),
$seqItem := $nextSeqResult(2)
return
if($isEndOfSeq) then $zero
else
if(function-arity($fGetPartial($seqItem, $zero)) eq 0)
then $fGetPartial($seqItem, $zero) ()
else $f($seqItem, $self($seqGen, $index+1, $zero, $f, $fGetPartial, $self))
},
$fold-right-sc-lifted := function ($seqGen as function(xs:integer) as array(*),
$zero as item()*,
$f as function(item(), item()*) as item()*,
$fGetPartial as function(*)
) as item()*
{
$fold-right-sc-lifted-inner($seqGen,
1,
$zero,
$f,
$fGetPartial, $fold-right-sc-lifted-inner)
},
$NaN := xs:double('NaN'),
$fSeq1ToN :=
function($ind as xs:integer, $indStart as xs:integer, $indEnd as xs:integer)
as array(*)
{
if($ind lt $indStart or $ind gt $indEnd)
then array{true(), $NaN}
else array{false(), $ind}
},
$fSeq-1-6 := $fSeq1ToN(?, 1, 6),
$fSeq-1-1M := $fSeq1ToN(?, 1, 1000000),
$fSeq-1-1M-minus-3 := function($n as xs:integer)
{
array{$fSeq-1-1M($n)(1), $fSeq-1-1M($n)(2) -3}
},
$fAdd := function($x, $y) {$x + $y},
$fMult := function($x, $y) {$x * $y},
$fMultGetPartial := function($x, $y)
{
if($x eq 0)
then function() {0}
else function($z) {$x * $z}
}
return
$fold-right-sc-lifted($fSeq-1-1M-minus-3, 1, $fMult, $fMultGetPartial)
Now this expression (and even one involving a sequence of 10M items take 0 seconds to be evaluated in both BaseX and Saxon, producing the correct result 0:
Summary
This article demonstrated the problems inherent to the standard XPath fn:fold-right and correctly determined the root causes for these problems: no short-circuiting and no collection generators.
Then a step-by-step solution was built that shows how to implement lazy evaluation in XPath based on short-circuiting and collection generators. This fixed the error raised by BaseX and dramatically reduced the evaluation time of Saxon from 261 seconds to 0 seconds.
The new function produced can be called $fold-lazy and is a good candidate for inclusion in the XPath 4.0 standard functions.
A complete design and implementation of a general collection-generator will be published in a separate article.
Because a possibility exists to be able to ignore the evaluation of $y, it is logical to delay the evaluation of $y until the actual arity of $f($x) is known.
The current XPath 4.0 evaluation rules do not require an implementation to base its decision whether or not to evaluate $y on the actual arity of the function produced by $f($x), thus at present an implementation could decide to evaluate $y regardless of the actual arity of the function produced by $f($x).
This is where a lazy hint comes: it indicates to the XPath processor that it is logical to make the decision about evaluation of $y based on the actual arity of the function returned by $f($x).
A rewrite of the above expression using a lazy hint looks like this:
let $f := function($arg1 as item()*, $arg2 as item()*) as function(item()*) as item()*
{ (: Some code here :) }
return
$f($x) (lazy $y)
Here is one example of a function with short-cutting and calling it with a lazy hint:
let $fAnd := function($x as xs:boolean, $y as xs:boolean) as xs:boolean
{
let $partial := function($x as xs:boolean) as function(xs:boolean) as xs:boolean
{
if(not($x)) then ->(){false()}
else ->($t) {$t}
}
return $partial($x)($y)
}
return
$fAnd($x (: possibly false() :), lazy $SomeVeryComplexAndSlowComputedExpression)
Without the lazy hint in the above example, it is perfectly possible that an XPath implementation, unrestricted by the current rules, would evaluate $SomeVeryComplexAndSlowComputedExpression – something that is unneeded and could be avoided completely.
Formal syntax and semantics
The lazy keyword should immediately precede any argument in a function call. If specified, it means that it is logical to make the decision about evaluation of this argument based on the actual arity of the function in this function call.
Based on this definition, it follows that lazy $argK implies lazy for all arguments following $argK in the function call. Thus specifying more than one lazy hint within a given function call is redundant and an implementation may report this redundancy to the user.
The scope of a lazy keyword specified on an argument is this and all following arguments of (only) the current function call.
It is possible to specify a lazy keyword that is in force for the respective argument(s) of all function calls of the given function. To do this, the lazy keyword must be specified immediately preceding a parameter name in the function definition of that function.
For example, if the function $f is specified as:
let $f := function($arg1 as item()*, lazy $arg2 as item()*, $arg3 as item()*, $arg4 as item()* )
{ (: some code here:) }
return
$someExpression
Then any call of $f in its definition scope that has the form:
$f($x, $y, $z, $t)
is equivalent to:
$f($x, lazy $y, $z, $t)
II. A function’s arity is a guard for its arguments
Let us have a function $f defined as below:
let $f := function($arg1 as item()*, $arg2 as item()*, …, $argN as item()*)
as function(item()*, item()*, …, item()*) as item()*
{
if($cond0($arg1)) then -> () { 123 }
else if($cond1($arg1)) then -> ($Z1 as item()*) {$Z1}
else if($cond2($arg1)) then -> ($Z1 as item()*, $Z2 as item()*) {$Z1 + $Z2}
(: . . . . . . . . :)
else if($condK($arg1)) then -> ($Z1 as item()*, $Z2 as item()*, …, $Zk as item()*)
{$Z1 + $Z2 + … + $Zk}
else ()
}
return
$f($y1, $y2, …, $yN) ($z1, $z2, …, $zk)
A call to $f returns a function whose arity may be any of the numbers: 0, 1, …, K.
Depending on the arity of the returned function (0, 1, …, K), the last (K, K-1, K-2, …, 2, 1, 0) arguments of the function call:
$f($y1, $y2, . . . , $yN) ($z1, $z2, . . . , $zk)
are unneeded and it is logical that they would not need to be evaluated.
So, the actual arity of the result of calling $f is a guard for the arguments of a call to this function-result.
In an expression of the type E(A1, A2, ..., AN) any of the arguments A<sub>K</sub> is guarded by the condition
actual-arity(E) ge K. This rule has the consequence that if the actual arity of E() is less than K then if any argument Am (where m >= K) is evaluated, this must not raise a dynamic error. An implementation may base on the actual arity of E() its decision for the evaluation of the arguments.
XPath has become a really powerful functional language. Here is a recent proof of this.
Let us see how one can construct with XPath 3.1 the PowerSet of a set.
A refresh from set theory, and as per Wikipedia:
"In mathematics, the power set (or powerset) of a set S is the set of all subsets of S, including the empty set and S itself.[1] In axiomatic set theory (as developed, for example, in the ZFC axioms), the existence of the power set of any set is postulated by the axiom of power set.[2] The powerset of S is variously denoted as P(S), 𝒫(S), P(S), or 2^S. The notation 2^S, meaning the set of all functions from S to a given set of two elements (e.g., {0, 1}), is used because the powerset of S can be identified with, equivalent to, or bijective to the set of all the functions from S to the given two elements set.[1]"
As there is no Set datatype yet in XPath, here we will denote a "set" as a sequence of items, the empty set being represented by the empty sequence. If desired, one could use XPath 3.1 arrays instead to represent items that are themselves sets (or "composite sequences").
As our function must return a set of sets, its return type cannot be just a simple sequence, because in XPath sequences are flat and there is no such thing as "sequence of sequences".
I have chosen to represent the result of the powerSet function below as a sequence of arrays, each array representing one subset of the provided set.
Finally, here is the code itself:
let $powerSet := function($set as item()*) as array(*)*
{
fold-right($set, [], function($it as item(), $accum as array(*)*)
{
$accum, $accum ! array:append(., $it)
})
}
return $powerSet((1, 2, 3, 4))
As expected, the result is this set of 16 (2^4) subsets:
So, it is possible to write and use decorators even in XPath 3.1 as above. Then why XPath decorators are as rare as the white peacock?
Photo Via: aboutpetlife.com
The answer is simple: just try to write even the simple decorator in XPath 3.1 and you’ll know how difficult and error-prone this is.
This is why several programming languages provide special support for decorators:
A standard syntax is provided to declare that a function is being decorated by another function. Composition of multiple decorators is supported.
Decorators can be applied not only to methods but also to their parameters (and to classes, constructors, static and instance properties, accessors).
The actual parameters in calling the manipulated method accessed in a standard way as a spread (the opposite of destructuring). The spread syntax is used both for getting the parameters and in providing them in the call to the manipulated method.
Javascript : Almost the same as in Typescript (above)
Goal of this proposal
To provide standard XPath support for decorators, as seen in other languages (above):
Provide syntax for specifying the decoration of a function:
When a decorated function is called, the XPath processor should create from the actual arguments of the call an array $args that holds all positionally-specified arguments in the call, and a map $kw-args that will hold the name – value pairs of all keyword-arguments in the call. Then the decorator will be called with these two arguments: ($args, $kw-args).
When any function is called just with two arguments: ($args, $kw-args) (such as from a decorator), the XPath processor must perform everything necessary in order to call the function in the way it expects to be called. For this purpose, a new overload of fn:apply() is defined:
fn:apply($function as function(*), $array as array(*), $map as map(*)) as item()*
The result of the function is obtained by creating and invoking the same dynamic call that would be the result of a function-call to $function with (positional) arguments taken from the members of the supplied array $array and (keyword arguments) taken from $map.
The decorator and the manipulated function are completely independent of each other and may be written long before / after each other.
They can reside in different code files.
We can have a library of useful decorator functions and can append them to decorate any wanted function.
As the updated Rule 72 above suggests, one can specify a chain of decorators manipulating a specific function. The inner-most decorator is passed to the next-inner-most-decorator, and so on…, which is passed … to the outer-most decorator. The different decorators specified don’t know about each other, are completely independent and may be written by different authors at any times and reside in different, unrelated function libraries.
This content was presented as a proposal for inclusion in XPath 4.0 here
Maps with Infinite Number of Keys: Total Maps and Decorated maps
1. Total Maps
Maps have become one of the most useful tools for creating readable, short and efficient XPath code. However, a significant limitation of this datatype is that a map can have only a finite number of keys. In many cases we might want to implement a map that can have more than a fixed, finite number of arguments.
Here is a typical example (Example 1):
A hotel charges per night differently, depending on how long the customer has been staying. For the first night the price is $100, for the second $90, for the third $80 and for every night after the third $75. We can immediately try to express this pricing data as a map, like this:
map {
1 : 100,
2 : 90,
3 : 80
(: ??? How to express the price for all eventual next nights? :)
}
We could, if we had a special key, something like "TheRest", which means any other key-value, which is not one of the already specified key-values.
Here comes the first part of this proposal:
We introduce a special key value, which, when specified in a map means: any possible key, different from the other keys, specified for the map. For this purpose we use the string: "\"
Adding such a "discard symbol" makes the map a total function on the set of any possible XPath atomic items.
Now we can easily express the hotel-price data as a map:
map {
1 : 100,
2 : 90,
3 : 80
'\' : 75
}
Another useful Example (2) is that now we can express any XPath item, or sequence of items as a map. Let’s do this for a simple constant, like π:
the map above is empty (has no regular keys) and specifies that for any other key-value $k it holds that $π($k) eq math:pi()
Going further, we can express even the empty sequence (Example 3) as the following map:
let $Φ := map {
'\' : ()
}
return $Φ?* (: produces the empty sequence :)
Using this representation of the empty sequence, we can provide a solution for the "Forgiveness problem" raised by Jarno Jelovirta in the XML.Com #general channel in March 2021:
This expression will raise an error:
[map {"k0": 1}, map{"k0": [1, 2, 3]}]?*?("k0")?*
[XPTY0004] Input of lookup operator must be map or array: 1.
To prevent ("forgive", thus "Forgiveness Problem") the raising of such errors we could accept the rule that in XPath 4.0 any expression that evaluates to something different than a map or an array, could be coerced to the following map, which returns the empty sequence as the corresponding value for any key requested in a lookup:
map {
'\' : ()
} (: produces the empty sequence for any lookup:)
To summarize, what we have achieved so far:
The map constructed in Example 1 is now a total function over the domain ℕ of all natural numbers. Any map with a "\" (discard key) is a total function over the value-space of all xs:anyAtomicType values
We can represent any XPath 4.0 item or sequence in an easy and intuitive way as a map.
It is now straight-forward to solve the "Forgiveness Problem" by introducing the natural and intuitive rule for coercing any non-map value to the empty map, and this allows to use anywhere the lookup operator ? without raising an error.
2. Decorated Maps
Although we already achieved a lot in the first part, there are still use-cases for which we don’t have an adequate map solution:
In the example (1) of expressing the hotel prices, we probably shouldn’t get $75 for a key such as -1 or even "blah-blah-blah"
But the XPath 4.0 language specification allows any atomic values to be possible keys and thus to be the argument to the map:get() function. If we want validation for the actually-allowed key-values for a specific given map, we need to have additional processing/functionality.
With a discard symbol we can express only one infinite set of possible keys and group them under the same corresponding value. However, there are problems, the data for which needs several infinite sets of key-values to be projected onto different values. Here is one such problem:
Imagine we are the organizers of a very simple lottery, selling many millions of tickets, identified by their number, which is a unique natural number.
We want to grant prizes with this simple strategy.
Any ticket number multiple of 10 wins $10.
Any ticket number multiple of 100 wins $20
Any ticket number multiple of 1000 wins $100
Any ticket number multiple of 5000 wins $1000
Any ticket number which is a prime number wins $25000
Any other ticket number doesn’t win a prize (wins $0)
None of the sets of key-values for each of the 6 categories above can be conveniently expressed with the map that we have so far, although we have merely 6 different cases!
How can we solve this kind of problem still using maps?
Decorators to the rescue…
What is decorator, what is the decorator pattern and when it is good to use one? According to Wikipedia:
What solution does it describe?
Define Decorator objects that
implement the interface of the extended (decorated) object (Component) transparently by forwarding all requests to it
perform additional functionality before/after forwarding a request.
This allows working with different Decorator objects to extend the functionality of an object dynamically at run-time.
The idea is to couple a map with a function (the decorator) which can perform any needed preprocessing, such as validation or projection of a supplied value onto one of a predefined small set of values (that are the actual keys of the map). For simplicity, we are not discussing post-processing here, though this can also be part of a decorator, if needed.
Let us see how a decorated-map solution to the lottery problem looks like:
let $prize-table := map {
"ten" : 10,
"hundred" : 20,
"thousand" : 100,
"five-thousand" : 1000,
"prime" : 25000,
"\" : 0
},
$isPrime := function($input as xs:integer) as xs:boolean
{
exists(index-of((2, 3, 5, 7, 11, 13, 17, 19, 23), $input)) (: simplified primality checker :)
},
$decorated-map := function($base-map as map(*), $input as xs:anyAtomicType) as item()*
{
let $raw-result :=
(
let $key :=
if(not($input castable as xs:positiveInteger)) then '\' (: we can call the error() function here :)
else if($input mod 5000 eq 0) then 'five-thousand'
else if($input mod 1000 eq 0) then 'thousand'
else if($input mod 100 eq 0) then 'hundred'
else if($input mod 10 eq 0) then 'ten'
else if($isPrime($input)) then 'prime'
else "\"
return $base-map($key)
),
$post-process := function($x) {$x}, (: using identity here for simplicity :)
$post-processed := $post-process($raw-result)
return $post-processed
},
$prizeForTicket := $decorated-map($prize-table, ?), (: Note: this is exactly the lookup operator ? :)
$ticketNumbers := (1, 10, 100, 1000, 5000, 19, -3, "blah-blah-blah")
return $ticketNumbers ! $prizeForTicket(.) (: produces 0, 10, 20, 100, 1000, 25000, 0, 0 :)
Conclusion
In the 2nd part of this proposal, a new type/function — the decorated-map was described.
We defined the signature of a decorated-map and gave an example how to construct and use one in solving a specific problem.
Finally, we showed that the lookup operator ? on a decorated map $dm is identical to $dm($base-map, ?)
What remains to be done?
The topic of decorators is extremely important, as a decorator may and should be possible to define on any function, not just on maps. This would be addressed in one or more new proposals. Stay tuned 😊
This content was presented as a proposal for inclusion in XPath 4.0 here:
In my first post about implementing recursion with anonymous functions I provided the following example:
let $f := function($n as xs:integer,
$f1 as function(xs:integer,
function()) as xs:integer
) as xs:integer
{if($n eq 0)
then 1
else $n * $f1($n -1, $f1)
},
$F := function($n as xs:integer) as xs:integer
{
$f($n, $f)
}
return
$F(5)
While this technique works well with relatively small values for n, we run into problems when n becomes bigger.
Let’s see this based on another example:
let $f := function($nums as xs:double*,
$f1 as function(xs:double*,
function()) as xs:double
) as xs:double
{
if(not($nums[1]))
then 0
else $nums[1] + $f1(subsequence($nums,2), $f1)
},
$F := function($nums as xs:double*) as xs:double
{
$f($nums, $f)
}
return
$F(1 to 10)
This calculates correctly the sum of the numbers 1 to 10 — the result is:
55
However, if we try:
$F(1 to 100)
the result is the following Saxon 9.4.6EE exception:
Error on line 22 Too many nested function calls. May be due to infinite recursion. Transformation failed: Run-time errors were reported
So, what happens here? Most readers would have guessed by now — our old Stack Overflow (not the site) exception.
Is there any way to avoid this exception?
One could rely on the smartness of the XSLT processor to do this. A slight fraction of XSLT processors recognize a limited kind of tail recursion and implement it using iteration, thus avoiding recursion.
The above code isn’t tail-recursive. Let us refactor it into the following tail-recursive code:
let $f := function($nums as xs:double*,
$accum as xs:double,
$f1 as
function(xs:double*, xs:double, function())
as xs:double
) as xs:double
{
if(not($nums[1]))
then $accum
else $f1(subsequence($nums,2), $accum+$nums[1], $f1)
},
$F := function($nums as xs:double*) as xs:double
{
$f($nums, 0, $f)
}
return
$F(1 to 100)
Saxon is one of the few intelligent processors that recognizes tail recursion, however it still raises the stack-overflow exception — even for the above tail-recursive code . Why?
Here is the Wikipedia definition of tail recursion:
In computer science, a tail call is a subroutine call that happens inside another procedure as its final action; it may produce a return value which is then immediately returned by the calling procedure. The call site is then said to be in tail position, i.e. at the end of the calling procedure. If any call that a subroutine performs, such that it might eventually lead to this same subroutine being called again down the call chain, is in tail position, such a subroutine is said to be tail-recursive.
At present, the XSLT/XPath processors that do recognize some kind of tail recursion only do so if a function/template calls itself by name.
None of them handles the case when the tail call is to another function (Michael Kay, author of Saxon, shared on the Saxon mailing list that Saxon correctly handles any tail calls for templates, but not for functions).
So, what can we do in this situation? One decision is to wait until some processor starts handling any type of tail call inside functions.
Another, is to use the DVC (Divide and Conquer) technique for minimizing the maximum depth of nested recursion calls.
The idea is to split the sequence into subsequences (usually two) of roughly the same length, recursively process each subsequence, and then combine the results of processing each individual subsequence.
Here is the above code, re-written to use DVC:
let $f := function($nums as xs:double*,
$f1 as function(xs:double*, function())
as xs:double
) as xs:double
{if(not($nums[1]))
then 0
else if(not($nums[2]))
then $nums[1]
else
let $half := count($nums) idiv 2
return
$f1(subsequence($nums,1, $half), $f1)
+
$f1(subsequence($nums, $half+1), $f1)
},
$F := function($nums as xs:double*) as xs:double
{
$f($nums, $f)
}
return
$F(1 to 10000)
Sure enough, this time we get the result:
5.0005E7
Using this technique, the maximum recursion depth is Log2(N) — thus for processing a sequence with 1M (one million elements) the maximum recursion depth is just 19.
Conclusion: The DVC technique is a tool that can be immediately used to circumvent the lack of intelligence of current XPath 3.0 processors when dealing with tail-call optimization.
Acknowledgement: To Brandon, the person who attracted my attention to this problem.
From Wikipedia, the free encyclopedia:
A word ladder (also known as a doublets, word-links, or Word golf) is a word game invented by Lewis Carroll. A word ladder puzzle begins with two given words, and to solve the puzzle one must find the shortest chain of other words to link the two given words, in which chain every two adjacent words (that is, words in successive steps) differ by exactly by one letter.
As with the original game of Lewis Carroll, each step consists of a single letter substitution.
My struggle to find a solution to this problem processed into these stages:
1.Total lack of understanding and trying to apply brute force approaches, only to realize what astronomical effort was involved and that “brute force” wasn’t readily definable.
2.“Discovering” the idea that when playing with four-letter words we only need the 4-letter words part of a dictionary.
3.Thinking hard how to pre-process an N-letter projection of a dictionary into a structure that would be more suitable for solving word-ladders.
4.Finally being told that the structure I was trying to invent is called a graph…
So, the main idea is that the set of N-letter words from an English dictionary is represented as a graph, where every node is a word from the dictionary, and there is an arc between two nodes exactly when the two words in these nodes differ only in a single letter.
Obviously, any such graph is undirected – if there is an arc between node N1 and N2, then there is also an arc between N2 and N1.
Finding the shortest chain of words is finding the shortest path in this graph that connects the two nodes. This problem has a well-known solution, called BFS (Breadth-First Search).
What may be new here is that the solution we have here is implemented in XSLT.
There were a number of subtasks:
ST1: Split a dictionary into a set of dictionaries, each containing only words of the same size N, where N = 1, 2, 3, 4, …
<xsl:sequence select= “if($pNode) then (my:enumerate($pNode/parent/node), $pNode/value) else ()“/> </xsl:function>
</xsl:stylesheet>
And sure enough, we get this result:
evil ==> emil ==> emir ==> amir ==> abir ==> abie ==> able ==> aile ==> nile ==> nice
The first variant of this solution seems encouraging. But it takes a while – especially on my 9-year old Pc, which has 2GB of RAM, and a tiny cache. For example, the 8-parts chain connecting thus to else took 118 seconds (26 seconds on my newer, 2-year old PC).
Therefore, we are clearly in need of:
ST3: Optimizations:
Optimization1: Order the arc-words in increasing number of their own arcs. This means that we will first try the neighbor-node with the fewest number of neighbors.
To implement this optimization, we modify this part of the AddNeighborsNaive.xsl:
Here I am using FXSL – the f:zipWith() function, as well as the function implementing the Xpath eq operator and the FXSL HOF analogue of the standard Xpath function string-to-codepoints().
In order for this to compile, one must add the following (or similar) imports:
<xsl:sequence select=
“if(not(key(‘kFindWord’, $pStartWord, $vDictGraph)) or not(key(‘kFindWord’, $pEndWord, $vDictGraph)) ) then error((), ‘A word-argument isn`t found in the dictionary.’) else () “/>
“point” to “given” (13-parts chain): 137 sec. before the optimization, 118 seconds after the optimization.
That is: another 14% increase of efficiency. The combined effect of the two optimizations is speeding up the initial transformation with about 23%.
As I mentioned, my newer PC is about 4 times faster, which means that the maximum time for discovering a 5-letters shortest chain with Saxon 9.1.05 on a modern PC would be less than 35 seconds.
Another interesting fact is that these transformations take approximately 50% less time when run with XQSharp (XmlPrime), which lowers the maximum transformation time to 15 – 16 seconds.
Finally, here is the longest word chain I have found so far between 5-letter words (angry to happy):
Hi Folks
Is it possible to do recursion in an anonymous function?
Example: I would like to implement an "until" function. It has
three arguments:
1. p is a boolean function
2. f is a function on x
3. x is the value being processed
Read the following function call as: decrement 3 until
it is negative
$until ($isNegative, $decrement, 3)
where
$isNegative := function($x as xs:integer) {$x lt 0}
$decrement := function($x as xs:integer) {$x - 1}
Here's how I attempted to implement function until:
$until := function(
$p as function(item()*) as xs:boolean,
$f as function(item()*) as item()*,
$x as item()*
) as item()*
{
if ($p($x))
then
$x
else
$until($p, $f, $f($x)) <-- RECURSE ...THIS IS
NOT ALLOWED, I THINK
}
Is there a way to implement function until in XPath 3.0?
(I know how to implement it in XSLT 3.0)
Roger is strictly speaking correct – because an anonymous function cannot call itself by name – it just doesn’t have a name …
However, we can still implement recursion using only inline function(s).
Here is my first attempt on a factorial inline function:
let $f := function($n as xs:integer,
$f1 as function(xs:integer) as xs:integer
) as xs:integer
{if($n eq 0)
then 1
else $n * $f1($n -1, $f1)
}
return
$f(5, $f)
The result we get is correct:
120
OK, what happens here?
An inline function cannot call itself, because it doesn’t know its name and in this respect behaves like an Alzheimer disease victim.
The idea is to give this sick person a written note identifying the person to whom he has to pass the remainder of the task. And if he himself happens to be on this note, he will pass the task to himself (and forget immediately it was him doing the previous step).
The only special thing to notice here is how the processing is initiated:
$f(5, $f)
calling the function and passing itself to itself.
This initiation may seem weird to a client and is also error-prone. This is why we can further improve the solution so that no weirdness remains on the surface:
let $f := function($n as xs:integer,
$f1 as function(xs:integer,
function()) as xs:integer
) as xs:integer
{if($n eq 0)
then 1
else $n * $f1($n -1, $f1)
},
$F := function($n as xs:integer) as xs:integer
{
$f($n, $f)
}
return
$F(5)
Now we produced an inline, anonymous function $F, which given an argument $n, produces $n!
There are two interesting sides of this story:
We show how elegant and powerful XPath 3.0 HOFs are.
More than ever it is clear now that XPath 3.0 is emerging as a full-pledged, stand-alone functional programming language in its own right that doesn’t need to be hosted by another language, such as XSLT or XQuery.
Some nice features we might still need, that could be just after the turn of the road (Read: In a post – 3.0 XPath version):
Stand-alone XPath processors.
Import/include directives for XPath-only files.
Separate packaging/compilation of XPath-only programs.
New data structures such as tuples.
Generics – parametric data types.
I have been dreaming about this since the time I shared in this blog the XPath-only implementation of the Binary Search tree and the Set datatype.
Photo Via: aboutpetlife.com
XSLT: Riding the challenge 