2. The Solution - Generators
The solution we propose to these issues is based on the concept of Generators.
Generators [Generators - Wikipedia] are wellknown
and integrated within 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.
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.”
2.1 The Generator Record
We define the Generator record
in the following way:
declare namespace f = "http://www.w3.org/2005/xpath-functions-2025";
declare record f:generator
( initialized as xs:boolean,
end-reached as xs:boolean,
get-current as fn($this as f:generator) as item()*,
move-next as fn($this as f:generator) as f:generator,
state as map(*)
);
The f:generator record has 5 fields, two of which are methods.
Procedural languages and XPath differ fundamentally in their treatment of state.
In a procedural language, a variable's value can change during execution.
XPath variables, however, are immutable.
Therefore, what would be represented as a single state-changing generator object in
a procedural language
must be represented in XPath as a sequence of generator instances.
Each instance corresponds to exactly one state.
Note that the sequence of generator instances produced by consecutively applying the
move-next method can be finite, ending with a final generator instance,
or it could be infinite and have no such a final generator instance.
-
get-current
Normally, the value associated with a given generator instance is obtained
by calling the get-current method.
If the current generator instance is the final generation instance,
or is not initialized (see below), get-current raises an error.
-
move-next
Normally, the method move-next produces the next generator
instance and calling the get-current method
on this next generation instance produces the value represented
in this next-generation instance.
If the current generator instance is the final generation instance
(see below),
move-next raises an error.
-
state
This map contains all key-value map-entries that are necessary for the work of the
two methods:
get-current and move-next.
-
initialized
The initialized flag
allows generators to defer computation of the first value.
A generator instance having initialized eq false() must be advanced via
move-next before a value can be retrieved.
Note: trying to evaluate get-current
on a non-initialized generator instance (having initialized eq false()) raises an error.
-
end-reached
If the sequence of generator instances produced by consecutively applying the move-next method
is a finite one, the final generator instance has no associated
value.
The boolean field end-reached
is used to indicate that this is the final generator instance, having no value
and not allowing to produce a next generator instance by applying on it the method
move-next. Thus, by definition, end-reached is
true() only on the final generator instance, and false() on all other,
non-final, generator instances.
Note: trying to evaluate get-current
or move-next
upon the final (empty) generator raises an error.
2.2 Definitions
Definition1: Empty generator: Any generator
instance whose end-reached value is true().
Definition2: Yield of a generator.
Starting from an initialized generator instance G1,
repeated application of move-next produces
a sequence of generator instances G2,
G3, …, Gn, …
The yield of the generator is the sequence of values obtained by applying
get-current to each of these instances, until an instance with
end-reached eq true() is encountered (or indefinitely, for infinite generators).
Note: The yield is empty,
if $G1?end-reached eq true()
and the yield is infinite if neither
$G1?end-reached eq true()
nor any of the consecutive applications of move-next produces
a generator-instance $Gx, such that
$Gx?end-reached eq true() .
2.3 Examples
Example1:
Given this example XML document:
<x>
<y>
<z/>
</y>
</x>
Below is a generator that will yield the names of the first in document-order leaf-node
in the XML document and of its consecutive ancestors,
with `\` as the “name” of the document-node():
let $genLeafAndAncestorNames :=
f:generator(initialized := true(),
end-reached := false(),
get-current := fn($this as f:generator)
{ let $current := $this?state?currentNode
return
if($current instance of document-node()) then '/'
else $current/name()
},
move-next := fn($this as f:generator)
{
if(empty($this?state?currentNode/..))
then map:put($this, "end-reached", true())
else map:put($this, "state",
map{"currentNode": $this?state?currentNode/..})
},
state := map{"currentNode" :
(parse-xml(
'<x>
<y>
<z/>
</y>
</x>')//*[not(*)]
)[1]
}
$genLeafAndAncestorNames is a generator-instance with a finite yield.
This yield is the ordered collection of values – the names of the first in document
order leaf node
and its ancestor-nodes: "z", "y", "x", / .
Example2:
$genFibo := f:generator(initialized := true(), end-reached := false(),
get-current := fn($this as f:generator)
{$this?state?current},
move-next := fn($this as f:generator)
{map:put($this, "state",
map{"current": $this?state?next,
"next": $this?state?current
+ $this?state?next}
)},
state := map{"current": 0, "next": 1}
)
$genFibo is a generator-instance with an infinite yield.
This yield is the ordered collection of the numbers comprising the Fibonacci sequence
[
Fibonacci - Wikipedia]:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, …, …
3. Functions on Generators
The functions defined in this section can be referenced with a conventional namespace
prefix
"gn", which is bound to the namespace URI “http://www.w3.org/2005/xpath-functions/generator”.
They are listed under the following categories, based on the type of the function
result:
| a. |
Functions returning a specific yield-value: an item() or a sequence.
|
| b. |
Functions that produce another generator from existing generators. |
| c. |
Functions that produce a generator from data by a data-provider. |
| d. |
Functions that completely materialize the yield of a generator as an XPath array,
sequence, or map.
|
The functions in group a., b., and c. (above) do not eagerly evaluate the yield of
any of their generator-arguments.
A single value from a yield is produced only if explicitly requested by evaluating
the methods
move-next and get-current. At no point in the computation
is it necessary to have all values of a yield available. In most cases, at any point
in the evaluation, a function would only need
one or possibly a few values to be yielded. No unnecessary computation of a value
from a yield is done and no memory is used
to hold such unnecessary values at any point in the computation.
This is why the evaluation of the functions defined here is referred to as "Deferred Evaluation".
The functions in group a. (above) return a single yield value – an item() or an XPath sequence - that may be the result
of a query or aggregation.
Any function from group b. (above) takes a generator as its first argument and returns a generator.
This allows the chaining of function calls to produce a generator whose yield is a complex transformation
of the yields of the generators that are supplied as arguments.
The functions in group c. (above) produce a generator whose yield is comprised of the values
supplied by an external data provider. An external data provider is a function that communicates
with its caller via strictly defined contract around its argument and its return value.
The user can define their own external data providers for any desired data source,
such as a file, a database, a web-service, …, etc.
The functions in group d. (above) materialize the complete yield of the provided generator
and are provided as a convenience to assist the user in debugging or testing their
code.
Next we briefly describe the functions from each of these four groups.
Complete and executable XPath/XQuery 4.0 formal definitions are provided on the author’s
Github [Generators - Formal].
3.1 Functions returning a specific value: an XPath item() or a sequence
This group of functions returns a single value based on the yield of a supplied generator.
Each function inspects the yield only as far as necessary to obtain that value:
Table I
Functions returning a specific value
| Function |
Meaning |
gn:at |
Returns the $k-th value from the yield of the $generator |
gn:contains |
Returns true() if the $value is contained in the yield of the generator,
and false() otherwise. The comparisons are done using fn:deep-equal.
|
gn:first-where |
Returns the first $value in the yield of the generator for which
$predicate($value) is true(). If the generator's yield doesn't contain any such item, an error is raised.
|
gn:fold-left |
Processes consecutively the values of the yield of the supplied generator,
applying the supplied function repeatedly to each value in turn,
together with an accumulated result value.
|
gn:fold-right |
Processes consecutively from right-to-left the values of the yield of the supplied
generator,
applying the supplied function repeatedly to each value in turn,
together with an accumulated result value.
|
gn:fold-lazy |
Produces the same result as gn:fold-right on the entire yield of the $generator
with the operation specified by $action but also performs short-circuiting
if detected by the supplied $short-circuit-detector function.
|
gn:head |
Produces the first value contained in the yield of the $generator |
gn:some |
Returns true() if and only if the generator is initialized and its yield contains at least one value.
|
gn:some-where |
Returns true() if the generator is initialized and its yield contains any value
upon which evaluating the supplied $predicate returns true(). Otherwise, false() is returned.
|
gn:value |
Produces the value contained in this generator-instance. |
3.2 Functions that produce another generator from existing generators
Any function in this group takes a generator as its first argument and returns a generator.
This allows chaining of function calls to produce a generator
whose yield is a complex transformation of the yields of the generators that are supplied
as arguments.
Table II
Functions that produce another generator from existing generators
| Function |
Meaning |
gn:chunk |
Returns a new generator each of whose yield values is a "chunk" of consecutive values
of the yield of the supplied $generator held in an array of size $size,
with the possible exception that the size of the array containing
the last "chunk" could be smaller.
|
gn:concat |
Returns a new generator whose yield consists of the yield of $generator followed by the yield
of $generator2.
|
gn:distinct |
Returns a new generator whose yield contains only the distinct values from the original
generator, in their original order.
|
gn:filter |
Returns a new generator whose yield contains exactly those values from the yield of
the original generator,
upon which the supplied predicate returns true(), in their original order.
|
gn:for-each |
Produces a new generator, in the yield of which each value is the result of applying
the function item
$action on the corresponding value of the yield of the original $generator, in their original order.
|
gn:for-each-pair |
Produces a new generator, in the yield of which each value is the result of applying
the function item
$action on the corresponding values of the yields of $generator1
and $generator2, in their original order.
|
gn:insert-at |
Returns a generator whose yield contains the first $position - 1 values of the yield of $generator,
followed by the supplied $value, followed by all the values of the yield of $generator
starting from position $position.
|
gn:merge-sorted-generators |
Produces a new generator from a generator each of whose yield values is itself a generator
that has a yield of sorted values.
|
gn:next |
Produces the next state/generator-instance obtained from the current generator-instance
$generator.
|
gn:prepend |
Returns a generator, whose yield is the supplied $value followed by the values of the yield
of the supplied $generator.
|
gn:remove-at |
Returns a generator, whose yield is the result of removing the $positionth value
from the yield of the supplied $generator.
|
gn:remove-where |
Returns a generator, whose yield is the result of removing from the yield of the supplied
$generator
all values upon which the supplied $predicate is true().
|
gn:replace |
Returns a generator, whose yield is the result of replacing in the yield of the supplied
$generator
the first value upon which the application of the supplied $predicate returns true()
with the supplied $replacement.
|
gn:reverse |
Returns a generator, the values of whose yield are the ones in the yield of the supplied
$generator but in reverse order.
|
gn:scan-left |
Returns a generator whose yield contains the partial results of the evaluation of
the gn:fold-left function with the same arguments.
|
gn:scan-right |
Returns a generator whose yield contains the partial results of the evaluation of
the gn:fold-right function with the same arguments.
|
gn:skip |
Returns a generator whose yield contains only the values of the yield of the supplied
$generator
after the $nth one and in their original order.
|
gn:skip-strict |
Returns a generator whose yield contains only the values of the yield of the supplied
$generator
after the $nth one and in their original order.
If the yield of the supplied $generator contains less than $n values,
and the supplied argument $raise-error-on-empty is true() then an error is raised.
|
gn:skip-while |
Returns a new generator whose yield contains all the values from the yield of the
supplied $generator,
having removed the longest leading segment of values on which the
supplied $predicate returns true().
|
gn:subrange |
Returns a new generator whose yield contains the values from the yield of the original
$generator,
from position $start to position $end in their original order.
|
gn:tail |
Returns a new generator whose yield contains all the values but the first from the
yield of the original $generator
or raises an error if the supplied generator's yield is empty.
|
gn:take |
Returns a new generator whose yield is the leading segment with length $n from the yield of the original
$generator or, in case the supplied generator's yield length is not bigger than $n,
then the result is a generator that has exactly the supplied generator's
yield.
|
gn:take-while |
Returns a new generator whose yield contains the longest leading segment from the
yield of the original $generator
on all values of which the provided function $predicate returns true().
|
gn:zip |
Returns a new generator the kth value of whose yield is an array having two members:
the kth value of the yield of $generator1
and the kth value of the yield of $generator2,
where k does not exceed the smaller of the lengths of the yields of the two generators.
|
3.3 Functions that produce a generator from data provided by a data-provider
The functions in this group construct a generator whose yield is supplied one value
at a time
by an external-provider function. Providers allow generators to expose yields that are too large
to fit into memory, must be computed incrementally, or require access to external
systems (such as files, databases, or web services).
A provider function must adhere to a contract with its client (generator) and is responsible
for producing, on each invocation, both:
-
state-data - an array with information required for the provider to compute its next result,
and
-
result-data - an array either containing a single yield-value or empty - to signal
that the data for producing the yield has been exhausted.
The generator returned by these functions behaves identically to any other generator:
values are not computed eagerly
but are obtained only as result of evaluating the method get-current
on the generator-instance produced by move-next.
There is also an additional function in this group: gn:empty-generator. It simply produces a new generator
whose yield does not contain any values and this function hasn’t a data-provider parameter.
Table III
Functions that produce a generator from data provided by a data-provider
| Function |
Meaning |
gn:make-generator |
Returns a generator, the values of whose yield are obtained by consecutive calls
to a supplied $provider function.
|
gn:make-generator-from-array |
Returns a generator, the values of whose yield are the values of the supplied $input array.
|
gn:make-generator-from-sequence |
Returns a generator, the values of whose yield are the values of the supplied $input sequence.
|
gn:make-generator-from-map |
Returns a generator, whose yield is the sequence of all single map entries of the
supplied $input map.
|
gn:empty-generator |
Returns a new generator whose yield does not contain any values. |
3.4 Functions that materialize the complete yield of a generator
The three functions in this group: gn:to-array, gn:to-sequence, and gn:to-map
are provided to help users debug their own generators and functions on generators.
Table IV
Functions that materialize the complete yield of a generator to array, to sequence
or to map
| Function |
Meaning |
gn:to-array |
Returns an array, whose members are the values of the yield of the supplied $generator.
|
gn:to-sequence |
Returns a sequence, whose items are obtained from the values of the yield of the supplied
$generator.
Any yield value that is an empty sequence is not represented in the
result.
|
gn:to-map |
Returns a map, whose single entries (key-value pairs) are obtained from the values
of the yield of the supplied $generator.
|
4. Examples
In the examples we use a few predefined generators and functions. The generators $genFibo and $genLeafAndAncestorNames
have already been defined in this paper. We also will use this generator:
let $gen2ToInf := f:generator(initialized := true(),
end-reached := false(),
get-current := fn($this as f:generator)
{$this?state?last +1},
move-next := fn($this as f:generator)
{
map:put($this, "state",
map{"last": $this?state?last + 1})
},
state := map{"last" : 1}
)
get-current produces $this?state?last +1. Because $this?state?last is initially defined as 1,
the first value of the yield, before move-next is called, is 2.
Each call to move-next produces a new generator instance in which the value of $this?state?last
is the incremented value of $this?state?last from the previous instance.
Thus the values of the yield of $gen2ToInf are all natural numbers, excluding the number one:
2, 3, 4, 5, 6, 7, …, …
It is important to point out here how the user can determine if the yield is finite
or infinite.
As end-reached is false() and there is nothing in the methods’ code that sets
end-reached to true(), the user can deduce that this yield is indeed infinite.
This generator ($gen0ToInf) is very similar to $gen2ToInf but its yield starts from 0 and contains all non-negative integers:
let $gen0ToInf := f:generator(initialized := true(),
end-reached := false(),
get-current := fn($this as f:generator)
{$this?state?last +1},
move-next := fn($this as f:generator)
{
map:put($this, "state",
map{"last": $this?state?last + 1})
},
state := map{"last" : -1}
)
And one more similar generator, this time defined as a modification of $gen2ToInf :
let $genN := $gen2ToInf => map:put("state", map{"last": 0})
We will also use a few functions.
$double returns twice its argument:
$double := fn($n) {2*$n}
$sum2 returns the sum of its two arguments:
$sum2 := fn($m, $n) {$m + $n}
$product returns the product of the two numbers $x and $y:
$product := fn($x, $y) {$x * $y}
$factorial returns the factorial of the number $n :
$factorial := fn($n) {fold-left(1 to $n, 1, $product)}
4.1 Using gn:to-array, gn:take, gn:value and gn:next
$gen2ToInf => gn:take(3) => gn:to-array()
Produces:
[2,3,4]
The first step in the chain: $gen2ToInf => gn:take(3) produces a new generator,
whose yield consists of the first three values of the yield of $gen2ToInf.
The final step in the chain => gn:to-array() takes this intermediate result (generator)
and materializes its complete yield as the XPath array [2,3,4].
Let us now materialize the yield of the generator already defined as $genLeafAndAncestorNames:
$genLeafAndAncestorNames => gn:to-array()
Produces the array:
["z","y","x","/"]
The functions gn:value and gn:next are synonyms for the methods get-current
and move-next
but have lower precedence than method calls and can be chained with the => operator without requiring parenthesis.
$gen2ToInf => gn:take(3) => gn:value()
is equivalent to (note the additional parenthesis):
($gen2ToInf => gn:take(3) ) =?> get-current()
and
$gen2ToInf => gn:take(3) => gn:next()
is equivalent to (note the additional parenthesis):
( $gen2ToInf => gn:take(3) ) =?> move-next()
4.2 Using gn:fold-left, gn:fold-right, gn:scan-left and gn:scan-right
The expression:
$gen2ToInf => gn:take(5) => gn:fold-left(0, fn($x, $y){$x + $y})
Produces:
20
The expression:
$gen2ToInf => gn:take(5) => gn:fold-right(0, fn($x, $y){$x + $y})
Produces:
20
The expression:
$gen2ToInf => gn:take(5) => gn:scan-left(0, fn($x, $y){$x + $y}) => gn:to-array()
Produces:
[0, 2, 5, 9, 14, 20]
The expression:
$genN => gn:take(10) => gn:scan-right(0, fn($x, $y){$x + $y}) => gn:to-array()
Produces:
[55, 54, 52, 49, 45, 40, 34, 27, 19, 10, 0]
4.3 Using gn:subrange, gn:at, gn:head and gn:tail
The expression:
$gen2ToInf => gn:subrange(4, 6) => gn:to-array()
Produces:
[5, 6, 7]
$gen2ToInf => gn:at(5)
Produces:
6
$gen2ToInf => gn:subrange(4, 6) => gn:head()
Produces:
5
$gen2ToInf => gn:subrange(4, 6) => gn:tail() => gn:to-array()
Produces:
[6, 7]
$gen2ToInf => gn:tail()=> gn:head()
Produces:
3
4.4 Using gn:for-each, gn:for-each-pair, and gn:filter
This expression:
$gen2ToInf => gn:for-each($double) => gn:take(5) => gn:to-array()
Produces:
[4, 6, 8, 10, 12]
This expression:
$gen2ToInf => gn:filter(fn($n){$n mod 2 eq 1}) => gn:take(10) => gn:to-array()
Produces:
[3, 5, 7, 9, 11, 13, 15, 17, 19, 21]
This expression:
$gen2ToInf => gn:for-each-pair($gen2ToInf, $sum2) => gn:take(5) => gn:to-array()
Produces:
[4, 6, 8, 10, 12]
This expression:
$gen0toInf => gn:for-each(fn($n){(2*$n + 1) div $factorial(2*xs:decimal($n))})
=> gn:take(8) => gn:fold-left(0, fn($x, $y){$x + $y})
Produces:
2.718281828458229747 (: Euler’s number
e [
e - Wikipedia]
with 11 correct decimal digits :)
This expression:
$gen0toInf => gn:for-each(fn($n){(2*$n + 1) div $factorial(2*xs:decimal($n))}) =>
gn:take(8) => gn:scan-left(0, fn($x, $y){$x + $y}) => gn:to-array()
Produces an array of all intermediate fold results in reaching the result of the previous
example:
[0, 1, 2.5, 2.708333333333333333, 2.718055555555555555, 2.718278769841269841, 2.718281801146384479,
2.718281828286168563,2.718281828458229747]
4.5 Using gn:skip, gn:skip-while, and gn:take-while
The expression:
$gen2ToInf => gn:take(10) => gn:skip(3) => gn:to-array()
Produces:
[5, 6, 7, 8, 9, 10, 11]
The expression:
$gen2ToInf => gn:skip(3) => gn:take(10) => gn:to-array()
Produces:
[5, 6, 7, 8, 9, 10, 11, 12, 13, 14]
The expression:
$gen2ToInf => gn:skip-while(fn($n){$n lt 11}) => gn:take(5) => gn:to-array()
Produces:
[11, 12, 13, 14, 15]
The expression:
$gen2ToInf => gn:take-while(fn($n){$n lt 11}) => gn:to-array()
Produces:
[2, 3, 4, 5, 6, 7, 8, 9, 10]
The expression:
$gen2ToInf => gn:take-while(fn($n){$n lt 100000000}) => gn:value()
Produces (instantly):
2
4.6 Using gn:chunk
The expression:
$gen2ToInf => gn:chunk(10) => gn:value()
Produces:
[2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
The expression:
$gen2ToInf => gn:take(10) => gn:chunk(4) => gn:to-array()
Produces:
[[2,3,4,5],[6,7,8,9],[10,11]]
The expression:
$gen2ToInf => gn:take(10) => gn:chunk(4) => gn:for-each(fn($arr) {array-size($arr)})
=> gn:to-array()
Produces:
[4, 4, 2]
4.7 Using gn:concat, gn:append, gn:prepend, gn:replace, gn:insert-at, gn:remove-at
The expression:
$gen2ToInf => gn:subrange(10, 15) => gn:concat($gen2ToInf => gn:subrange(1, 9))
=> gn:to-array()
Produces:
[11, 12, 13, 14, 15, 16, 2, 3, 4, 5, 6, 7, 8, 9, 10]
The expression:
$gen2ToInf => gn:subrange(1, 5) => gn:append(101) => gn:to-array()
Produces:
[2, 3, 4, 5, 6, 101]
The expression:
$gen2ToInf => gn:subrange(1, 5) => gn:prepend(101) => gn:to-array()
Produces:
[101, 2, 3, 4, 5, 6]
The expression:
$gen2ToInf => gn:replace(fn($x){$x gt 4}, "Replacement") => gn:take(10)
=> gn:to-array()
Produces:
[2, 3, 4, "Replacement", 6, 7, 8, 9, 10, 11]
The expression:
$gen2ToInf => gn:insert-at(3, "XYZ") => gn:take(10) => gn:to-array()
Produces:
[2, 3, "XYZ", 4, 5, 6, 7, 8, 9, 10]
The expression:
$gen2ToInf => gn:remove-at(3) => gn:take(10) => gn:to-array()
Produces:
[2, 3, 5, 6, 7, 8, 9, 10, 11, 12] (: The number 4 has been removed :)
4.8 Using gn:empty-generator, gn:contains, gn:some, gn:some-where, gn:first-where, gn:remove-where
The expression:
$gen2ToInf => gn:take(10) => gn:contains(3)
Produces:
true()
The expression:
$gen2ToInf => gn:take(10) => gn:contains(20)
Produces:
false()
The expression:
$gen2ToInf => gn:contains(100)
Produces:
true()
The expression:
$gen2ToInf => gn:some()
Produces:
true()
The expression:
gn:empty-generator => gn:some()
Produces:
false()
The expression:
$gen2ToInf => gn:take(5) => gn:filter(fn($n){$n ge 7}) => gn:some()
Produces:
false()
The expression:
$gen2ToInf => gn:take(5) => gn:some-where(fn($n){$n ge 7})
Produces:
false()
The expression:
$gen2ToInf => gn:take(5) => gn:some-where(fn($n){$n ge 6})
Produces:
true()
The expression:
$gen2ToInf => gn:first-where(fn($n){$n gt 10})
Produces:
11
The expression:
$gen2ToInf => gn:chunk(10)
=> gn:first-where(fn($arr as array(*)){$arr(1) le 33 and $arr(10) ge 33})
Produces:
[32,33,34,35,36,37,38,39,40,41]
The expression:
$gen2ToInf => gn:remove-where(fn($x){$x mod 3 eq 0}) => gn:take(10) => gn:to-array()
Produces:
[2, 4, 5, 7, 8, 10, 11, 13, 14, 16]
4.9 Using gn:distinct, gn:zip
The expression:
$gen2ToInf => gn:for-each(fn($n){$n idiv 10}) => gn:distinct() => gn:take(15)
=> gn:to-array()
Produces:
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]
The expression:
let $genSeqE := ($gen0toInf
=> gn:for-each(fn($n)
{(2*$n + 1) div $factorial(2*xs:decimal($n))}
)
=> gn:take(8)) => gn:scan-left(0, fn($x, $y){$x + $y}),
$genSeqE-Next := $genSeqE => gn:tail(),
$genZipped := $genSeqE => gn:zip($genSeqE-Next)
return
($genZipped => gn:first-where(fn($pair){abs($pair(1) - $pair(2)) lt 0.000001}))(2)
Produces:
2.718281828286168563 (: The first value in the sequence calculating
e,
which is less than
0.000001 different from the previous value :)
4.10 Using gn:make-generator, gn:make-generator-from-array, gn:make-generator-from-sequence
The expression:
gn:make-generator(fn($state as array(*))
{
let $numGenerated := if(array:empty($state)) then 0
else $state(1)
return
if($numGenerated le 9)
then [ [$numGenerated + 1], [$numGenerated + 1] ]
else [[-1], []]
}
) => gn:to-array()
Produces:
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
Let us try to understand the above example.
The call to gn:make-generator above passes to it a “provider function” that accepts as its only argument
a $state array. This $state array contains a single member,
which is the last state reached by the provider and allows the provider to continue
forward from this state.
In calling a provider-function, there are three rules/conventions to comply with:
-
It is a convention that on the initial/first call to the provider, the caller should
pass an empty $state array.
-
The provider must return an array with two members, each of them arrays. The first
member of the result is an array
containing as its only member the last state reached by the provider.
The second member of the returned result-array is an array that contains the latest
value from the data source -
the value (returned by get-current) of the generator instance.
-
Another rule is that when the data source is exhausted and there are no more values
to be returned,
the provider returns an empty array as the second member of the result-array.
In this case the contents of the first member of the result-array is unimportant as
it will be ignored.
In the example above the provider must return on each call the numbers from 1 to 10.
The contents of the $state array is the last number that was returned.
If the last number returned was greater than 9 (this is the exceptional case), then the provider signals
that the data-source has been exhausted – by returning a result array of [[-1], []]
where the second member that should contain the next returned value actually contains
nothing.
In the “normal case” when the last number returned is not bigger than 9,
the provider returns the incremented value of this last number [ [$numGenerated + 1], [$numGenerated + 1] ] -
both as its next state and as the next value to be used by the generator.
In the next example, the provider-function produces all natural numbers: 1, 2, 3, … and never sets the second member
of its result-array to an empty array. The resulting generator instance has an infinite yield,
but we may still obtain its current value, or a subrange of the values of its yield:
let $allNumbers := gn:make-generator(fn($state as array(*))
{
let $numGenerated := if(array:empty($state))
then 0
else $state(1)
return
[ [$numGenerated + 1], [$numGenerated + 1] ]
})
return ($allNumbers => gn:value(),
$allNumbers => gn:subrange(10, 15) => gn:to-array())
Produces:
1, [10, 11, 12, 13, 14, 15]
This expression:
gn:make-generator-from-array([1, 4, 9, 16, 25]) => gn:to-array()
Produces:
[1, 4, 9, 16, 25]
This expression:
gn:make-generator-from-array([]) => gn:to-array()
Produces:
[]
This expression:
gn:make-generator-from-sequence((1, 8, 27, 64, 125)) => gn:to-array()
Produces:
[1, 8, 27, 64, 125]
4.11 N-way merge of generators with sorted yields: gn:merge-sorted-generators
The N-way merge of data sources is essential in implementing external sort. The following
examples show its use,
including in the last example the merge of three generators with infinite yields.
This expression:
let $ar1 := [-100, -4, 1, 3, 5, 7, 9, 11],
$ar2 := [-100, -90, -80, -70, -60, -50],
$ar3 := [-10, -8, -6, -4, -2, 0, 15],
$gn1 := gn:make-generator-from-array($ar1),
$gn2 := gn:make-generator-from-array($ar2),
$gn3 := gn:make-generator-from-array($ar3),
$genOfGens := gn:make-generator-from-array([$gn1, $gn2, $gn3])
return
gn:merge-sorted-generators($genOfGens) => gn:to-array()
Produces:
[-100,-100,-90,-80,-70,-60,-50,-10,-8,-6,-4,-4,-2,0,1,3,5,7,9,11,15]
This expression:
let $ar1 := array {1 to 100_000_000_000},
$ar2 := array {2 to 100_000_000_001},
$ar3 := array {3 to 100_000_000_002},
$gn1 := gn:make-generator-from-array($ar1),
$gn2 := gn:make-generator-from-array($ar2),
$gn3 := gn:make-generator-from-array($ar3),
$genOfGens := gn:make-generator-from-array([$gn1, $gn2, $gn3])
return
gn:merge-sorted-generators($genOfGens) => gn:subrange(1, 30)
=> gn:to-array()
Produces:
[1,2,2,3,3,3,4,4,4,5,5,5,6,6,6,7,7,7,8,8,8,9,9,9,10,10,10,11,11,11]
This expression:
let $gn1 := gn:make-generator(fn($state as array(*))
{
let $numGenerated := if(array:empty($state))
then 0
else $state[1]
return
[ [$numGenerated + 2], [$numGenerated + 2] ]
}
),
$gn2 := gn:make-generator(fn($state as array(*))
{
let $numGenerated := if(array:empty($state))
then 0
else $state[1]
return
[ [$numGenerated + 3], [$numGenerated + 3] ]
}
),
$gn3 := gn:make-generator(fn($state as array(*))
{
let $numGenerated := if(array:empty($state))
then 0
else $state[1]
return
[ [$numGenerated + 5], [$numGenerated + 5] ]
}
),
$genOfGens := gn:make-generator-from-array([$gn1, $gn2, $gn3])
return
gn:merge-sorted-generators($genOfGens) => gn:subrange(1, 40)
=> gn:to-array()
Produces:
[2,3,4,5,6,6,8,9,10,10,12,12,14,15,15,16,18,18,20,20,21,22,24,24,25,26,27,28,30,30,30,32,33,34,35,36,36,38,39,40]
5. The Deferred-Evaluation Programming style
The introduction of generators into XPath enables a fundamentally different programming
style, referred to here
as deferred evaluation [DefEval - Msft] [Lazy - Wikipedia].
This style departs from the traditional,
sequence-oriented evaluation model of XPath, where expressions are typically evaluated
eagerly
and results are materialized as complete sequences.
At the core of deferred evaluation is the observation that, at any given point in
the evaluation,
a generator instance represents at most one value from its yield.
The remainder of the yield is not computed in advance, nor is it required to exist
in memory.
Instead, the computation of subsequent values is deferred until explicitly requested.
5.1 Demand-Driven Computation
With deferred-evaluation, values are produced only on demand.
A generator does not compute its entire yield. Rather, it defines how to compute the
next value, should such a request occur.
The method move-next realizes this potential for future computation.
Importantly, this method is not invoked automatically; it is invoked only when the
consumer of the generator explicitly requests the next value.
As a consequence, it is entirely possible—and often desirable—that only a finite prefix
of a potentially infinite yield is ever computed.
In many cases, only the first value is required, and no further computation takes
place.
5.2 Separation of Description from Execution
A key characteristic of this programming style is the separation between:
When composing generator-based expressions, the programmer specifies
what should happen if further values are requested, but does not cause those requests to occur.
In this sense, a generator-based expression does not directly compute a result.
Instead, it constructs a computational process — a description of how yield-values may be produced in the future.
The actual execution of this process is controlled externally, by the consumer of
the generator.
This leads to an important conceptual shift:
A generator-based program is not merely a program that computes values, but a program
that constructs another program—namely, a deferred computation.
5.3 Controlled Evaluation and Early Termination
Because evaluation is demand-driven, the consumer of a generator has full control
over how much of the yield is explored.
Functions that produce only a single yield-value (such as gn:head, gn:first-where, or gn:at)
evaluate only as much of the yield as is necessary to produce that value. Once the
result is obtained, no further yield-values are generated.
This enables early termination of computations in a natural and composable way,
without requiring special control constructs. In particular, it allows safe and practical
interaction with generators whose yields are:
5.4 Deferred Evaluation vs Recursion
Deferred evaluation should not be confused with recursion [Recursion - Wikipedia] .
In XPath, recursive functions are typically evaluated eagerly: each recursive call
contributes to the construction
of a fully materialized result. Even when tail-call optimization is available, the
evaluation strategy remains fundamentally eager.
In contrast, generator-based computation does not build a complete resulting yield.
Instead, it defines a stepwise process in which each step produces at most one yield-value
and a description of the next step.
Thus, while evaluation of recursion traverses a structure,
evaluation of a generator’s move-next method creates a
description how to produce a structure incrementally.
5.5 Minimal State and Memory Efficiency
At any point during evaluation, only the current generator instance and its associated
state is required.
No storage is needed for previously produced values unless explicitly retained by
the user.
This results in:
-
constant memory usage for many classes of problems
-
the ability to process unbounded or infinite data sources
-
elimination of unnecessary intermediate materialization
5.6 Composability of Deferred Computations
Generator-transforming functions (such as gn:filter, gn:for-each, and gn:take)
defined in section “3.2 Functions that produce another generator from existing generators” do not simply evaluate
their input generators. Instead, they construct new generators that incorporate additional
behavior into the deferred computation.
This allows arbitrarily long chains of transformations to be defined without triggering
evaluation.
The entire chain remains dormant until a yield-value is explicitly requested.
As a result, complex data-processing pipelines can be expressed declaratively while
retaining precise control over evaluation.
5.7 Summary
Deferred evaluation in XPath, as enabled by generators, introduces a programming model
characterized by:
-
separation of computation description from execution
-
demand-driven computation
-
explicit control over evaluation
-
efficient handling of large or infinite data
-
high composability of transformations
This model complements the existing sequence-based approach in XPath, extending the
language with a powerful abstraction
for incremental and resource-efficient computation.
The table below is a comparison between typical eager XPath evaluation and generator-based,
deferred evaluation:
Table V
Comparison between typical eager XPath evaluation and generator-based, deferred evaluation
| Feature |
Eager XPath |
Deferred |
| Evaluation |
Immediate |
Deferred |
| Memory |
Full sequence |
Incremental |
| Infinite/Unbounded data |
Impossible |
Natural |
| Control |
Implicit |
Explicit |
6. A Real World Use-Case
The generator abstraction introduced in this paper is not merely a theoretical construct,
but a practical tool for addressing
real-world data-processing problems that involve large, unbounded, or externally provided
data sources.
This section presents a representative use case [Generators - Usecase] : the aggregation of multiple news feeds.
This scenario highlights the advantages of deferred evaluation, composability, and
integration with external data providers.
6.1 The Problem: Aggregation of Multiple News Feeds
Consider the problem of aggregating multiple news feeds, such as RSS [RSS - Spec]
or Atom [Atom - Spec] sources,
into a single, unified stream of entries.
Each feed may contain a large number of items and may be updated independently over
time.
A typical requirement is to present the most recent entries across all feeds, possibly
filtered by relevance,
and limited to a fixed number of results (e.g., the most recent 20 items).
This problem raises several challenges:
-
Each feed may be large or conceptually unbounded.
-
Accessing a feed may require communication with an external system (e.g., over HTTP).
-
The combined result must be ordered (e.g., by publication date-time).
-
Only a small prefix of the combined result is typically needed.
-
Early termination is essential to avoid unnecessary data retrieval and processing.
In a purely sequence-based approach in XPath, all input feeds would need to be fully
materialized before merging,
sorting, and filtering could be performed. This approach is inefficient and, in some
cases, infeasible.
One can have a glimpse at the “Top 100 World News RSS Feeds” [RSS - TopFeeds]. Each news-feed may contain 20 or more news-items,
and each news-item may point to an external html document, or may contain the content
inline.
Even if we only process the top 15 news feeds, we may have to deal with more than
300 news-items and related documents.
And the Mar. 26th Dow Jones RSS newsfeed [DowJones - RSS] alone contained not 20 but 75 <item> elements.
6.2 Generator-Based Solution
Using generators, each news feed can be represented as a generator whose yield consists
of the items in that feed,
obtained incrementally via an external provider
A typical processing pipeline can be expressed as follows:
$feedLocations
=> gn:for-each($fetch-feed)
=> gn:merge-sorted-generators()
=> gn:filter($is-relevant)
=> gn:take(20)
=> gn:to-array()
In this pipeline:
-
$feedLocations is a generator whose yield is a collection of feed descriptors (e.g., URLs).
-
$fetch-feed is a function that, given a feed descriptor, returns a generator backed
by an external provider that retrieves feed items incrementally.
-
gn:merge-sorted-generators merges multiple generators whose yields are already sorted (e.g., by publication
date),
producing a single sorted generator.
-
gn:filter removes items that are not relevant according to a specified predicate.
-
gn:take(20) limits the result to the first 20 items.
-
gn:to-array() materializes the result for presentation.
The expression, preceding “
=> gn:to-array()” defines a complete data-processing pipeline
without forcing the evaluation of any intermediate results. The evaluation and production
of results starts only
within the call to
gn:to-array().
6.3 Incremental Evaluation and Early Termination
A key advantage of this approach is that evaluation proceeds incrementally and only
as far as necessary.
In the example above, once 20 items are produced as specified by gn:take(20),
no further values are requested from the upstream generators. As a result:
-
Each feed is accessed only as much as required to contribute to the first 20 results.
-
No unnecessary network requests are made.
-
No excess data is retained in memory.
This behavior is particularly important when dealing with large or continuously updated
feeds,
where the total number of available items may be very large or effectively unbounded.
6.4 External Data Providers
The integration of generators with external data providers is essential in this scenario.
Each feed generator is constructed using a provider function that encapsulates:
-
the state required to continue fetching items (e.g., pagination tokens and items transmitted
within the current page), and
-
the logic for retrieving the next item from the feed
The provider communicates with the generator through the contract defined in Section
3.3,
returning both updated state and the next available item (if any). This allows the
generator to present a uniform interface
regardless of the underlying data source.
By abstracting external access in this way, generators enable XPath expressions to
interact seamlessly with:
-
remote feeds (HTTP-based APIs),
-
databases (streaming query result sets or via cursor-like mechanisms),
-
file streams, and
-
other incremental data sources.
6.5 Comparison with Eager Evaluation
To better understand the benefits of the generator-based approach, it is useful to
contrast it with a traditional eager evaluation strategy.
In an eager approach, the processing would conceptually involve:
-
Fetching all items from all feeds
-
Producing a single, combined sequence of all results
-
Sorting the combined sequence
-
Filtering irrelevant items
-
Selecting the first 20 entries
This approach requires full materialization of all intermediate results and does not
support early termination.
In contrast, the generator-based approach:
-
fetches items lazily,
-
merges them incrementally,
-
applies filtering on demand, and
-
stops as soon as the required number of results has been obtained.
This results in significantly improved efficiency and scalability.
6.6 Generalization
Although presented in the context of news feed aggregation, the same pattern applies
to a wide range of problems, including:
-
processing large XML documents in a streaming fashion,
-
merging sorted data from multiple databases,
-
consuming paginated web APIs,
-
analyzing log streams, and
-
performing computations over infinite or computationally generated sequences.
In all these cases, generators provide a uniform and composable abstraction for deferred,
incremental computation.
6.7 Summary
This use case demonstrates how generators enable:
-
efficient processing of large and external data sources,
-
precise control over evaluation and resource usage, and
-
clear and composable expression of complex data-processing pipelines.
By combining deferred evaluation with a strictly-defined protocol for external data
providers,
generators extend XPath's power with capabilities that are difficult or near-impossible
to achieve
using traditional sequence-based techniques alone.
7. Conclusion
This paper introduced a generator-based model for deferred evaluation in XPath 4.
Generators address a fundamental omission in the language specification:
the agency to efficiently and uniformly process large, unbounded, or externally provided
collections of data.
The proposed solution is centered on a simple but expressive abstraction that is widely
used in other programming languages - the Generator Record.
Alongside which we propose a composable set of functions that operate without requiring
the full materialization of intermediate results.
This enables a programming style that is fundamentally different from traditional
XPath evaluation:
one that is demand-driven, incremental, memory-sensitive and externally controllable.
Two key contributions distinguish this work:
-
A composable generator library, allowing complex transformations to be expressed as chains of generator-producing
functions,
without loss of laziness or control over evaluation.
-
A strictly-defined protocol for external data providers, enabling generators to seamlessly integrate with data sources
such as web services, files, and databases, while preserving the declarative nature
of XPath.
The resulting model allows XPath programs to:
-
operate over infinite or unbounded data,
-
terminate early without unnecessary computation,
-
maintain constant or bounded memory usage, and
-
express complex data-processing pipelines in a clear and modular way.
Importantly, this approach is implementation-independent. It does not rely on vendor-specific optimizations
or extensions, but instead provides a portable, formally defined mechanism that is
implemented within the XPath language itself.
Anyone can grab the existing pure XPath 4 implementation from [Generators - Formal],
run with BaseX the more than 140 test-cases, and immediately start writing their own
generators.
The generator abstraction complements, rather than replaces, the existing sequence-based
model of XPath.
While sequences remain appropriate for finite and fully materialized data, generators
extend the usability of XPath
into domains traditionally associated with streaming, and functional programming systems.
Future work may explore:
-
formal integration of generators into the XPath and XQuery specifications,
-
optimization strategies for generator-based pipelines,
-
static analysis of generator expressions, and
-
additional abstractions built on top of generators.
By introducing deferred evaluation as a first-class programming style, this work expands
the expressive power of XPath
and opens the door to new classes of applications that were previously difficult or
impractical to implement.
