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:
[-14, -13, -12, -11, -10, -9, -8, -7, -6, -5, -4, -3, -2, -1, 0, 1, 2, 3, …, 999985]
[-14, -13, -12, -11, -10, -9, -8, -7, -6, -5, -4, -3, -2, -1, 0, 1, 2, 3, …, 9999985]
[-14, -13, -12, -11, -10, -9, -8, -7, -6, -5, -4, -3, -2, -1, 0, 1, 2, 3, …, ] — up to infinity.
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$fMultGetPartialreturns a function with0arguments (constant) that produces0. $fold-right-sc(inner) treats differently a partial application of arity0from a partial application with arity1. 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.
XSLT: Riding the challenge 