1. The Problem

In some cases we need to generate or process a huge, potentially unlimited number of XPath [XPath 3.1 - Spec] items and sequences, referred here as collection of values or simply collection. Typically, not all of these may be needed at a specific point of the evaluation. There are at least two issues that we need to address:

A. We are not sure of the amount of memory that would be needed to contain the collection. We would like only the next member of the collection to be “materialized” and provided only on demand, when we actually need it.
B. Even if issue A. was not present, and we are confident that all members of the collection can be contained in memory, how do we ensure the early exit from processing and not continuing to obtain/generate and traverse all members of the collection? Ideally, the caller should be empowered so that they may only issue the minimum necessary number of requests to meet their processing requirements.

It is also possible to foresee a potential third issue, where the caller needs to be able to dynamically define a short-circuiting strategy [Laziness - XPath] to prevent from hanging an aggregating operation; such as folding, over an infinite collection of members. One can argue that different vendors of XPath processors already provide some mechanisms to some of these issues. Unfortunately, such solutions [Saxon - Laziness] are limited, incomplete, and vary from one vendor to the other (See Appendix I.), which results in confusion for the XPath programmer, and vendor dependency and lock-in. More critically, as such solutions are not required by the XPath standard, nothing prevents a vendor from removing such a mechanism from their product and thus breaking invisibly a user’s existing XPath code.

In contrast, we need a solution that is implementation-independent and that puts us – the XPath programmers in full control.

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 [1] 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:

  1. state-data - an array with information required for the provider to compute its next result, and

  2. 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:

  1. It is a convention that on the initial/first call to the provider, the caller should pass an empty $state array.

  2. 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.

  3. 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:

  • describing a computation, and

  • executing a computation

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:

  • very large, or

  • infinite

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:

  1. Fetching all items from all feeds

  2. Producing a single, combined sequence of all results

  3. Sorting the combined sequence

  4. Filtering irrelevant items

  5. 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.

Acknowledgements

The author expresses his gratitude to Adam Retter and Alan Painter for their help with the English language and style of this paper, and to Liam Quin for his encouragement.

Many thanks to the three anonymous Balisage reviewers for their comments, questions and suggestions.

Appendix I. An example of "implementation-dependence magic" in current XPath processors

This is an example of an expression that is evaluated instantly in BaseX, but takes 591 seconds in Saxon, as can be seen in the screenshot below. 

                     
let $product := function($m as xs:decimal, $n as xs:decimal)  as xs:decimal {$m * $n} ,
    $factorial := function($n as xs:decimal)  as xs:decimal {fold-left(1 to $n, 1, $product)},
    $f := function($n) {$factorial($n) div $factorial($n -2)}
 return
    (1 to 100000000)[$f(20)]

In order to be able to write really portable XPath code, we need something that would eliminate the risk of surprizes from such implementation-dependence magic.

References

[Atom - Spec] The Atom Syndication Format, https://datatracker.ietf.org/doc/html/rfc4287

[DefEval - Msft] Deferred execution and lazy evaluation, https://learn.microsoft.com/en-us/dotnet/standard/linq/deferred-execution-lazy-evaluation

[DowJones - RSS] Dow Jones RSS newsfeed, https://feeds.content.dowjones.io/public/rss/RSSWorldNews

[Eager - Wikipedia] Evaluation-Strategy/Strict-Evaluation, https://en.wikipedia.org/wiki/Evaluation_strategy#Eager_evaluation

[e - Wikipedia] e (mathematical constant), https://en.wikipedia.org/wiki/E_(mathematical_constant)

[Fibonacci - Wikipedia] Fibonacci Sequence, https://en.wikipedia.org/wiki/Fibonacci_sequence

[Generators - Wikipedia] Generator (computer programming), https://en.wikipedia.org/wiki/Generator_(computer_programming)

[Generators - Formal] Generators in XPath - Formal Semantics – Executable XPath/XQuery 4 and 3.1 code, https://github.com/dnovatchev/generators

[Generators - Usecase] Use Case for Generators: News Feeds Aggregation using Generators, https://github.com/qt4cg/qtspecs/discussions/2557

[Generators - XPath3] Generators Implementation in XPath 3, https://medium.com/@dimitrenovatchev/generators-in-xpath-987a609cfbd5?sk=6334d48f9565f78eba90b212e461243b

[Laziness - XPath] Laziness in XPath. The trouble with fn:fold-right, https://medium.com/@dimitrenovatchev/laziness-in-xpath-the-trouble-with-fn-fold-right-cbb1cc654d1c?sk=872244cf80bfcb52d67bcb8b359478ff

[Lazy - Wikipedia] Lazy Evaluation, https://en.wikipedia.org/wiki/Lazy_evaluation

[N-Way-Merge - Wikipedia] K-way merging, https://en.wikipedia.org/wiki/Merge_algorithm#K-way_merging

[Recursion - Wikipedia] Recursion - In Computer Science, https://en.wikipedia.org/wiki/Recursion#In_computer_science

[RSS - Spec] RSS 2.0 Specification, https://www.rssboard.org/rss-specification

[Saxon - Laziness] Michael Kay, Lazy Evaluation, https://blog.saxonica.com/mike/2015/06/lazy-evaluation.html

[RSS - TopFeeds] Top 100 World News RSS Feeds, https://rss.feedspot.com/world_news_rss_feeds/

[XPath 3.1 - Spec] XML Path Language (XPath) 3.1, https://www.w3.org/TR/xpath-31/

[XPath 4 - Draft] XPath 4.0 WG Review Draft, https://qt4cg.org/specifications/xquery-40/xpath-40.html


[1] The record type has been introduced in XPath 4 and may undergo changes in its semantics. The author will update the text of the article and the executable, formal definitions if new changes in the generator type are introduced.

Author's keywords for this paper:
XPath; Deferred Evaluation; Generators