XPath: Short-circuiting Functions and Lazy Evaluation Hints

[dnovatchev]

Short-circuiting Functions and Lazy Evaluation Hints

1. Introduction

As shown in Wikipedia, most contemporary programming languages offer reasonable support for short-circuit evaluation
(also known as minimal or McCarthy evaluation), including several standard language short-circuit operators.

Short-circuiting, as we will call the above in this document, is commonly used to achieve:

1. Avoiding undesired side effects of evaluating the second argument, such as
   excessive evaluation time or throwing an error

Usual example, using a C-based language:

   int denom = 0;
   if (denom != 0 && num / denom)
   {
   ...//ensures that calculating num/denom never results in divide-by-zero error
   }

Consider the following example:

   int a = 0;
   if (a != 0 && myfunc(b))
   {
     do_something();
   }

In this example, short-circuit evaluation guarantees that myfunc(b) is never called. This is because a != 0 evaluates to false. This feature permits two useful programming constructs.

1. If the first sub-expression checks whether an expensive computation is needed and the check evaluates to false, one can eliminate expensive computation in the second argument.

2. It permits a construct where the first expression guarantees a condition without which the second expression may cause a run-time error.

3. Idiomatic conditional construct

Perl idioms:

   some_condition or die; # Abort execution if some_condition is false

   some_condition and die; # Abort execution if some_condition is true

2. Short-circuiting in XPath

In short (pun intended) there is no such thing mentioned in any officially-published W3C version (<= 3.1) of XPath.

This topic was briefly mentioned in the discussion of another proposal: that of providing the capability to specify strictly the order of evaluation.

Aspects of incorporating hints for lazy evaluation (a topic related to short-cutting) were discussed also in the thread to this question on the Xml.com Slack.

The situation at present is that the XPath processor that is being used decides whether or not to perform shortcutting, even in obvious cases. Thus, varying from one XPath processor to another, the differences in performance evaluation could be dramatic. For example, the following XPath expression is evaluated on BaseX (ver. >= 10.3) for 0 seconds, and the same expression is evaluated by Saxon ver. 11 for about 100 seconds.

let $fnAnd := function($x)
   {
     function($y)
     {
      if(not($x)) then false()
                  else $y
     }
   }
   return
      $fnAnd(false())(some $b in ( ((1 to 1000000000000000000) !true()) )  satisfies not($b)   )

3. Analysis

We can define the term “function with shortcutting” (just for a 2-argument function, but this can be extended for N-argument function where N >= 2) in the following way:

Given a function $f($x, $y), we denote in XPath its partial application for a given value of $x (say let $x := $t) as:

$f($t, ?)

The above is a function of one argument. By definition:

$f($x, $y) is equivalent to $f($x, ?) ($y), for every pair $x and $y.

That is, the partial application of the 2-argument function $f with fixed 1st argument is another function $g which when applied on the 2nd argument ($y) of $f($x, $y) produces the same value as $f($x, $y):

If $g is defined as $f($x, ?), then $g($y) produces the same value as $f($x, $y) for every pair $x and $y.

Let us take a specific function:

let $fAnd := function($x as xs:boolean, $y as xs:boolean) as xs:boolean
                     { $x and $y}

Then one equivalent way of defining $fAnd is:

let $fAnd := function($x as xs:boolean, $y as xs:boolean) as xs:boolean
                     {
                       let $partial := function($x as xs:boolean) as function(xs:boolean) as xs:boolean
                                               {
                                                  if(not($x)) then ->(){false()}
                                                              else ->($t) {$t}
                                               }
                         return $partial($x)($y)
                    }
   return
       $fAnd(false(), true())

The $partial function is the result of the partial application $fAnd($x, ?) and by definition this is a function of arity 1, which when applied on the 2nd argument of $fAnd, produces the same result as $fAnd($x, $y)

From the code above we see that actually there exists a value of $x (the value false() ) for which $fAnd($x, ?) is not a function of one argument, but a constant function (of 0 arguments) – that produces the value false().

Definition:

We say that a function f(x, y) allows shortcutting if there exists at least one value t such that

f(t, ?) is a constant.

4. Solution

How can an XPath processor treat a function with shortcutting?

Obviously, if the XPath processor knows that f(x, y) allows shortcutting, then it becomes possible to delay the evaluation of the 2nd argument y and only perform this evaluation if the arity of the function returned by f(t, ?) is 1, and not 0.

How can an XPath processor know that a given function allows shortcutting?

• One way to obtain this knowledge is to evaluate f(t, ?) and get the arity of the resulting function. XPath 3.1 allows getting the arity of any function item with the function fn:function-arity(). However, doing this on every function call could be expensive and deteriorate performance.

• Another way of informing the XPath processor that a given function f(x, y) allows shortcutting is if the language provides hints for lazy evaluation:
  
  let $fAnd := function($x as xs:boolean, lazy $y as xs:boolean) as xs:boolean
  
  Only in the case when there is a lazy hint specified the XPath processor will check the arity of f(x, ?) and will not need to evaluate the y argument if this arity is 0.

Let us return to the original example:

let $fAnd := function($x as xs:boolean, $y as xs:boolean) as xs:boolean
                     {
                       let $partial := function($x as xs:boolean) as function(xs:boolean) as xs:boolean
                                               {
                                                  if(not($x)) then ->(){false()}
                                                              else ->($t) {$t}
                                               }
                         return $partial($x)($y)
                    }
   return
       $fAnd(false(), true())

Executing this with an Xpath 3.1 processor, an error is raised: “1 argument supplied, 0 expected: function() as xs:boolean { false() }.”

But according to the updated “Coercion Rules / Function Coercion” in Xpath 4.0, no error will occur:

“If F has lower arity than the expected type, then F is wrapped in a new function that declares and ignores the additional argument; the following steps are then applied to this new function.

For example, if the expected type is function(node(), xs:boolean) as xs:string, and the supplied function is fn:name#1, then the supplied function is effectively replaced by function($n as node(), $b as xs:boolean) as xs:string {fn:name($n)}”

This is exactly the place where the XPath processor will call the lower-arity function without providing to it the ignored, and not needed to be evaluated, additional argument.

Thus, according to this rule, an XPath 4.0 processor will successfully evaluate the above expression and will not issue the error shown above.

Finally, we can put the lazy hint on a function declaration or on a function call, or on both places:

let $fAnd := function($x as xs:boolean, lazy $y as xs:boolean) as  xs:boolean
   {
     let $partial := function($x as xs:boolean) as function(lazy xs:boolean) as xs:boolean
                           {
                              if(not($x)) then ->(){false()}
                                          else ->($t) {$t}
                           }
      return $partial($x)( lazy $y)
   }
   return
       $fAnd(false(), lazy true())

How to write short-circuiting functions?

The code above is a good example how one can write a short-circuiting function evaluating which the XPath processor would be aware that a short-circuit is happening but instead of signaling arity error as an XPath 3.1 processor does, will logically ignore the unneeded 2nd argument.

[michaelhkay]

One way to obtain this knowledge is to evaluate f(t, ?) and get the arity of the resulting function.

I don't understand this. The arity of f(t, ?) is surely always 1 by definition: specifically the arity of a function produced by partial evaluation is always equal to the number of "placeholders".

I think your intent is probably captured by the definition: there exists at least one value t such that f(t, ?) is a constant. That is to say, it's a function whose result doesn't depend on the value of its argument. I think we can understand intuitively what this means, but I'm not sure how we define it precisely.

I can think of other ways of formalising lazy evaluation that might work better. For example we could say that when an argument is declared as lazy $x as xs:integer then the supplied argument expression is wrapped as a zero-arity function, and a variable reference $x is interpreted as a request to evaluate this zero-arity function. Unfortunately I'm not sure this achieves anything because there's nothing to constrain WHEN the function body should evaluate this function.

Consider the function

f($x, $y) {
  if ($x = 0) then 0
  else if ($x = 1) then $y + 1
  else if ($x = 2) then ($y + 1) * 2
}

and suppose this is called as let $X = 0 return f($X, 10 div $X). Is there any way we can ensure this doesn't throw a dynamic error?

To do this, we would not only need some way of prescribing that the expression passed to $y is not evaluated until its value is needed. We would also need to prevent the optimizer eliminating common sub-expressions by pre-evaluating ($y + 1) outside the conditional.

Generally I don't think it's a good idea to try and impose such constraints on the implementation. Apart from anything else, I think we lack the formal semantic machinery to describe such constraints in rigorous language. We're also in grave danger of prohibiting optimisations that existing code unknowingly relies upon.

I think the changes we have already made, to define certain constructs as having "guarded" subexpressions, are sufficient to meet the requirement.

[dnovatchev]

I don't understand this. The arity of f(t, ?) is surely always 1 by definition: specifically the arity of a function produced by partial evaluation is always equal to the number of "placeholders".

@michaelhkay ,

We have a specific example in the text, when XPath 3.1 processors raise an arity-mismatch dynamic error, because an 1-argument function was expected, but a 0-argument function was provided.

So even today's XPath 3.1 processors can dynamically determine this case, this is possible.

And in this case the XPath 4 processor, implementing the updated function coercion rules, it knows that it has to evaluate the provided 0-argument function and to ignore the argument.

This will be done in all cases in XPath 4 because the rules dictate so. The lazy hint is what it is - a "hint" - telling the XPath processor that it will not be necessary in this case to evaluate the argument that is not used.

As for:

"The arity of f(t, ?) is surely always 1 by definition", here we are not after the automatic knowledge, but we do have to evaluate $f($someT, ?) and check the arity of the returned function. Why we must evaluate this? Because the lazy keyword tells us to do so.

If we write our function in the way shown in the proposal, then no hint would be needed because the XPath processor does find the fact that it was passed a 0-arg function when an 1-arg function was expected.

But if our function body was just: {$t and $y} then this would not happen. In this case, if the lazy hint has been provided, then the XPath processor would evaluate $f($t, ?) and get an actual returned function, and determine that its arity is 0.

[michaelhkay]

I think it's also worth pointing out that the term "lazy evaluation" is used in two different senses. The first sense, which you seem to be using, is: the expression supplied as an actual function argument is not evaluated unless and until the value of the argument is actually required. The second sense is that when the expression evaluates to a sequence, it is evaluated incrementally, and we only evaluate as much of the sequence as is actually needed. For example, if the only reference is to $x[1], then items in $x after the first are never evaluated. This of course is even harder to formalise.

And what does it mean for the value to be "actually required"? Is the value "actually required" if it is passed as an argument to another function? Or if it is returned as the result of the function? Or if it is used in an "instance of" expression that can be evaluated by knowing the type of the value, but not the actual value?

We could, of course, fudge this all by saying that the "lazy" keyword is just a hint and processors can use it or ignore it as they choose. But I think from experience with other hints such as "unordered", we would find that most implementations end up ignoring it, and as a result few users trouble to use it.

[michaelhkay]

We have a specific example in the text

It seems I didn't make myself clear. The arity of the function f(t, ?) is 1 by definition, you know that statically, and it can never be 0. It doesn't need a dynamic test of function-arity() to determine this, you can infer it statically from the number of question marks.

It might be a function that returns the same result regardless of the value of its argument, but it is still an arity-1 function.

[dnovatchev]

We have a specific example in the text

It seems I didn't make myself clear. The arity of the function f(t, ?) is 1 by definition, you know that statically, and it can never be 0. It doesn't need a dynamic test of function-arity() to determine this, you can infer it statically from the number of question marks.

It might be a function that returns the same result regardless of the value of its argument, but it is still an arity-1 function.

Actually it isn't. It is a 0-arguments function and both BaseX and Saxon flag this as error in XPath 3.1

Also, please see my additional edits to my reply to your 1st comment.

[michaelhkay]

Could you give the precise expression that is flagged as an error?

[dnovatchev]

Could you give the precise expression that is flagged as an error?

let $fAnd := function($x as xs:boolean, $y as xs:boolean) as xs:boolean
                     {
                       let $partial := function($x as xs:boolean) as function(xs:boolean) as xs:boolean
                                               {
                                                  if(not($x)) then ->(){false()}
                                                              else ->($t) {$t}
                                               }
                         return $partial($x)($y)
                    }
   return
       $fAnd(false(), true())

[michaelhkay]

But there's no partial function application of the form f(t, ?) here, so I can't see how this addresses my point that the arity of f(t, ?) is necessarily 1.

The query fails in Saxon with the error:

XPTY0004 The supplied function (function(){false()}) has 0 arguments - expected 1

Under the proposed coercion rules this query would become legal; under the proposed rules the zero-arity function function(){false()} (which can equally be written false#0) will be accepted where the expected type is function(xs:boolean) as xs:boolean.

[dnovatchev]

@michaelhkay

Maybe even better this expression:

let $partial_fAnd_1 := function($x as xs:boolean) as function(xs:boolean) as xs:boolean
                       {
                          if(not($x)) then ->(){false()}
                                      else ->($t) {$t}
                       },

$fAnd := function($x as xs:boolean) as function(xs:boolean) as xs:boolean
                     {
                         $partial_fAnd_1($x)
                      }
   return
       $fAnd(false())( true())

[dnovatchev]

But there's no partial function application of the form f(t, ?) here, so I can't see how this addresses my point that the arity of f(t, ?) is necessarily 1.

I see what you mean.

Still the provided expressions that result in arity mismathch in Xpath 3.1, do show us how to write functions with shortcutting.

Maybe we need a new language construct that would allow us to specify the exact code implementation of a specific partial application function for a given function. Something like this:

let $f := ->($x, $y) {$x and $y}
                with partial_arg1 := function($x as xs:boolean) as function(xs:boolean) as xs:boolean
                                               {
                                                  if(not($x)) then ->(){false()}
                                                              else ->($t) {$t}
                                               }

Then the processor will know that there was a specified partial application specified, and if there was a lazy hint will invoke this specified partial application ($f_$$partial_arg1 or any established convention for the name) and test the arity of the function that it returns.

[dnovatchev]

Under the proposed coercion rules this query would become legal; under the proposed rules the zero-arity function function(){false()} (which can equally be written false#0) will be accepted where the expected type is function(xs:boolean) as xs:boolean.

But the actual arity of false#0 is 0

[dnovatchev]

So, we have: declared (or presumed) arity and actual arity

I am referring to the actual arity.

[dnovatchev]

Let us have this expression:

$f($x) ($y)

Evaluating $f($x) produces a function. The actual arity of this resulting function can be any number N >= 0.

If N > 1 there would be arity mismatch error, as only one argument $y is provided in the expression.

If N <= 1 the final function call can be evaluated, and depending on the value of N, the argument $y must be evaluated (N eq 1) or can be safely ignored (N eq 0).

Because a possibility exists to be able to ignore the evaluation of $y, it seems logical to delay the evaluation of $y until the actual arity of $f($x) is known.

It is not clear to me whether or not the current evaluation rules require such delay in deciding whether or not to evaluate $y.

If the current rules don't require such delayed decision, then this is where a lazy hint comes: it indicates to the XPath processor that it is logical to make the decision about evaluation of $y based on the arity of the function returned by $f($x).

[ChristianGruen]

@dnovatchev Sorry, but this discussion feels very theoretical to me. I can't recollect any user having asked for explicit hints (options, pragmas) to control the laziness/eagerness of XQuery code evaluation. Instead, the expectation of the vast majority is to have the processor choose the best evaluation strategy.

Could you please add at least one practical use case to this discussion in which the behavior of the available query processors behaves in an unsatisfactory way without evaluation hints?

[dnovatchev]

Could you please add at least one practical use case to this discussion in which the behavior of the available query processors behaves in an unsatisfactory way without evaluation hints?

Sure, immediately.

This was already shown in the main post. Evaluation time of 100 seconds using one XPath processor vs. 0 seconds using another.

To quote again the main post:

The situation at present is that the XPath processor that is being used decides whether or not to perform shortcutting, even in obvious cases. Thus, varying from one XPath processor to another, the differences in performance evaluation could be dramatic. For example, the following XPath expression is evaluated on BaseX (ver. >= 10.3) for 0 seconds, and the same expression is evaluated by Saxon ver. 11 for about 100 seconds.

let $fnAnd := function($x)
   {
     function($y)
     {
      if(not($x)) then false()
                  else $y
     }
   }
   return
      $fnAnd(false())(some $b in ( ((1 to 1000000000000000000) !true()) )  satisfies not($b)   )

[ChristianGruen]

This was already shown in the main post. Evaluation time of 100 seconds using one XPath processor vs. 0 seconds using another.

I’ve seen that example, but counting from 1 to 1000000000000000000 isn’t something that’s done a lot in practice. I was wondering if we can find at least one use case that we can regard as a real-world challenge.

[dnovatchev]

This was already shown in the main post. Evaluation time of 100 seconds using one XPath processor vs. 0 seconds using another.

I’ve seen that example, but counting from 1 to 1000000000000000000 isn’t something that’s done a lot in practice. I was wondering if we can find at least one use case that we can regard as a real-world challenge.

It can be substituted with any heavy-computation work -- there's plenty of that "in practice", isn't there?

Just as an idea, imagine crypto-mining 😄 Or put here any known practical task that is NP-complete.

With the lazy hints being followed what was prohibitively expensive (close to impossible) before, becomes now realistic in any shortcutting cases, independent of what XPath processor is being used.

[ChristianGruen]

It can be substituted with any heavy-computation work -- there's plenty of that "in practice", isn't there?

I’ll still be happy to get convinced. Let’s take the given example for BaseX:

1. If you look closer at the optimization output, you’ll notice that no short-circuiting takes place.
2. Why should we introduce any additional hints if the code you demonstrated is evaluated fast enough anyway?

If there are plenty of examples, I think we should be able to make at least one of them replicable.

[michaelhkay]

This was already shown in the main post. Evaluation time of 100 seconds using one XPath processor vs. 0 seconds using another.

This is always going to be the case with a declarative language. Consider join queries, such as //x[y = //z]. Some processors are going to implement sophisticated hash-join optimization for such queries, others aren't. I firmly believe that performance is a matter for implementations, not for the specification.

Of course, XSLT provides xsl:key to allow users to "hand-optimize" such queries. XML database products provide their own mechanisms to define whether constructs should be indexed or not. But with lazy evaluation, I think implementors are almost certainly better at knowing when to use this technique than 99% of users are.

It's worth pointing out that when the poor performance of this query was pointed out to us, we were able to fix the problem very easily without any major design change, and without any need to change the query, let alone the specification.

I also believe strongly in something I was taught as a student 50 years ago: the optimization decisions a compiler makes should always be driven by studying real workloads - the programs that typical users actually write. For a product implementor, it's a business decision where to put their R&D investment, and they have a better understanding than standards committees of where that investment is going to get a return. We know, for example, that a small improvement in some operations on XML trees (for example, copying subtrees) is going to benefit a lot more users than a large improvement in operations on arrays. That has to be our decision.

[dnovatchev]

But with lazy evaluation, I think implementors are almost certainly better at knowing when to use this technique than 99% of users are.

Alas, we have the real example where from two major XPath processors one fails to perform what can be considered "an almost obvious optimization". That is failure in 50% of a user's possible choice of an XPath processor.

If I as an user can choose between two XPath processors one of which is known to perform a certain task in 0 seconds and the other is known to perform the same task in 100 seconds, I will obviously choose to use Processor 1.

If, on the other side, I am able to direct Processor 2 how to perform much better in such cases, then I have a richer choice of tools (XPath processors) and even could use them interchangeably.

Imagine you are inside a moving fully-autonomous car that has a bug and is colliding with an obstacle, and you could take the wheel and handle the dangerous situation, but you are not allowed to do so because "implementors are almost certainly better at knowing when to use this technique than 99% of users are" and you watch the bad things happening right in front of your eyes...

It should be absolutely clear which alternative is the better one.

[dnovatchev]

I’ll still be happy to get convinced.

@ChristianGruen if about 50 PLs, among them almost all Functional PLs, implement several kinds of short-circuiting operators, are you not convinced that they had sound practical reasons for doing so?

Maybe they were all wrong and you are right. I would not comment further on this.

[sashafirsov]

Proposed chain-able calls looks fine while the each returned function arguments would match its following invocation(arity).

let $fn0_2 := function()
   {
     return function($p1)
     {
          return function( $p2, $p3 ){}
     }
   }

The sequence $fn0_2() ($x) ($y,$z) is always expect 0, then 1, then 2 arguments. I guess no disagreement on lazy evaluation on each chain call: none, then $x then $y, $z.

What happen if the return type would depend of argument?

let $fnI := function( $i )
{
     switch( $i )
     {    case 0: return function (){ ... }
          case 1: return function ($p1){ ... }
          case 2: return function ($p1, $p2){ ... }
          default return $i
     }
}

• $fnI(0)() valid
• $fnI(1)() invalid
• $fnI(1)($x) valid
• $fnI(2)($x,$y) valid, and broken $fnI(2)($y), $fnI(2)()

When arity of returned function does not match arguments count (or arg types ) we could

• throw error
• throw an error if number of arguments is not sufficient
• pass (and evaluate?) arguments sufficient for a call, ignore evaluation of extra arguments ( @dnovatchev , it is your sample arity 0 should not evaluate args )
• pass missing args with undefined(or whetever) values
• or proposing to give a collection of arguments so interpreter can pick the one which matches the caller

The syntax of proposed collection as arguments set could vary, one of is to pass as union of arguments.

$fnI( $i )( () | ($x) | ($y,$z) )

The trick is to delay evaluation till the moment the arity is known. This concept also applicable for types transformation if in addition to arity the argument types are available.

$getScrollPos( $i )( () | ( $offset($xy) ) | ( $point($x,$y) )

[michaelhkay]

At the call yesterday, I think Dimitre asked two questions, and I'd like to expand on the answers.

Given an expression like f($x)($y), and given the current specification,

(a) is there a guarantee that f($x) will be evaluated before $y is evaluated

(b) if f($x) evaluates to a zero-arity function Z, do the new rules for function coercion kick in, causing Z to be called with no arguments (and causing $y to be ignored).

I think we can simplify the discussion by considering the dynamic function call X(Y) where X and Y are arbitrary expressions; the case where X is a function call are no different from the general rules.

The rules are given in §4.4.2.1 Dynamic Function Calls:

1. X is evaluated, and a type error XPTY0004 is raised if the result is not an arity-1 function F.
2. Y is evaluated
3. The result of evaluating Y is coerced to the type required by the function signature of F.

Is it required that the steps be performed in the order prescribed? No, but it is required that the outcome is the same as if they were performed in the order prescribed. For example if Y is the expression 2+2, it's perfectly OK to evaluate it at compile time and substitute the value 4. But if this evaluation fails, the processor can't throw a static error; it must behave as if it had evaluated the expression at the appropriate time.

Where is this stated? Well, we don't state it very formally. The closest we come is probably in §2.3.3 "Within each phase, an implementation is free to use any strategy or algorithm whose result conforms to the specifications in this document." which essentially says you can do what you like to evaluate X(Y) so long as the outcome is the same as following the steps laid down in §4.4.2.1. And of course the infamous §2.4.4 on errors and optimization also gives you license in some cases to deliver a different outcome by, for example, skipping evaluation whose only purpose is to probe for errors.

Is function coercion invoked? On the current rules, no. The coercion rules are only invoked in particular specified circumstances (§4.4.3 the situations in which the rules apply are defined elsewhere...) and the rules for dynamic function calls do not invoke them. In general, coercion rules are only invoked where there is an explicit user-declared required type (†), defined for example in a function signature or a variable declaration, and that is not the case here. We could change the rules so that X(Y) instead of raising an error when X returns a zero-arity function, instead calls X with no arguments and calls Y; but that would be a change to the current specification.

† I think there are cases in XSLT where the coercion rules are invoked where the required type is system-defined, e.g. the value of xsl:evaluate/@xpath is converted to a string by applying the coercion rules. I'm not aware of any such cases in XPath or XQuery.

[dnovatchev]

@michaelhkay Thank you for the detailed explanation:

I think we can simplify the discussion by considering the dynamic function call X(Y) where X and Y are arbitrary expressions; the case where X is a function call are no different from the general rules.

Actually no, the function $f($x) should be considered as fully defined, including the arity of its return.

If the expression is $f($x) ($y) , then indeed $f must be already declared somewhere, thus the XPath processor has all information about this function, including the type of result it returns and its (the result's) signature and arity.

The rules are given in §4.4.2.1 Dynamic Function Calls:

1. X is evaluated, and a type error XPTY0004 is raised if the result is not an arity-1 function F.
2. Y is evaluated
3. The result of evaluating Y is coerced to the type required by the function signature of F.

I propose that we change 1. to:

X is evaluated, and a if its arity is 0, then the constant function X() is evaluated and the Y argument that follows need not be evaluated.

In case our rules do not include the above phrase ("... and the Y argument that follows need not be evaluated") then this would mean that an implementation could still decide (if it chooses) to evaluate Y. In this case, we can give the XPath programmer the capability to advise the XPath processor using the lazy hint that it is meaningful to postpone the evaluation of Y and that if the arity of X is 0, then it would be logical not to evaluate Y.

Is function coercion invoked? On the current rules, no. The coercion rules are only invoked in particular specified circumstances (§4.4.3 the situations in which the rules apply are defined elsewhere...) and the rules for dynamic function calls do not invoke them. In general, coercion rules are only invoked where there is an explicit user-declared required type (†), defined for example in a function signature or a variable declaration, and that is not the case here.

As I pointed out above, the variable $f certainly must be declared somewhere in the evaluation context, otherwise there would be a static compilation error. Thus, from the above explanation it seems (please, correct me if this is wrong) that the coercion rules should be applied on the result of evaluating $f($x) .

To summarize:

1. $f and its return type, including its arity is declared in the evaluation context, thus the coercion rules on its result should apply.

2. The XPath programmer will benefit from having the capability to hint to the XPath processor that in any such particular case (when there is a possibility that the returned function may be of lesser arity) it is logical to delay the evaluation of the argument and if the argument is going not to be used, then not to evaluate this argument.

[michaelhkay]

Clearly the composability principle means that the rules for evaluating $f($x) are independent of the fact that the result is then used in the expression $f($x)($y). There are two steps, which are completely orthogonal to each other: (a) evaluate $f($x) to produce some result F, (b) evaluate F($x) to produce some result G.

Certainly the type of $f affects the result of evaluating $f($x). But it can't possibly affect the result of evaluating F($y).

[dnovatchev]

Clearly the composability principle means that the rules for evaluating $f($x) are independent of the fact that the result is then used in the expression $f($x)($y). There are two steps, which are completely orthogonal to each other: (a) evaluate $f($x) to produce some result F, (b) evaluate F($x) to produce some result G.

Certainly the type of $f affects the result of evaluating $f($x). But it can't possibly affect the result of evaluating F($y).

It can:

let $f := function($x as xs:boolean) as function(xs:boolean) as xs:boolean
                       {
                         (: Some code here like: 
                          if(not($x)) then ->(){false()}
                                      else ->($t) {$t}
                         :)
                       }

Here from the declaration of $f we know that it returns a function with arity 1 that takes a boolean and returns a boolean.

The XPath programmer also knows that the returned function could be with 0-arity, thus the programmer can indicate this using a lazy hint:

   return
      $f($x) lazy ($y)

[michaelhkay]

Under the current specification, the arity-zero function ()->{false()}, under the rules for function coercion, is wrapped in an arity-one function ($x as xs:boolean) as xs:boolean->{false()}, and the result of $f($x) is this arity-one function. The processor is of course capable of seeing that it never uses the value of its argument.

(Note, I believe that the effect of the rules in §2.4.4 Errors and Optimization is that the function ($x as xs:boolean) as xs:boolean->{false()} is not required to check that the actual argument is of type xs:boolean - the type check is mandatory if $x is evaluated "wholly or in part", but not if it isn't evaluated at all.)

Not evaluating an argument that isn't referenced in the function body is a pretty straightforward optimization, and I'm not sure why you think the hint is useful. It's potentially more useful if the argument is referenced in some but not all execution paths, but I'm still very doubtful that many programmers would use it wisely.

In your example the "lazy" hint is present unconditionally: it also applies if the function to be evaluated turns out to be ->($t) {$t}. For that function lazy evaluation of the argument is pointless - are you expecting the processor to ignore the hint on that path? (The question might not arise of course, because the function might be rewritten out of all recognition).

It might be useful if you wrote a more detailed proposal, in spec prose, defining the syntax and semantics of the new construct: and perhaps a note suggesting advice to users on when to use it.

[michaelhkay]

Actually §2.4.4 appears to contain a bit of a contradiction on this. First it says:

If a processor evaluates an operand E (wholly or in part), then it is required to establish that the actual value of the operand E does not violate any constraints on its cardinality.

Subsequently it says:

Another consequence of these rules is that where none of the items in a sequence contributes to the result of an expression, the processor is not obliged to evaluate any part of the sequence. Again, however, the processor cannot dispense with a required cardinality check: if an empty sequence is not permitted in the relevant context, then the processor must ensure that the operand is not an empty sequence.

The second extract implies that, given the function ->($x as xs:boolean) as xs:boolean->{false()}, even though the value of $x is not needed, the processor is expected to check that the supplied value is a singleton. That seems unreasonable to me (and I'm pretty sure Saxon won't do it).

[dnovatchev]

Actually §2.4.4 appears to contain a bit of a contradiction on this. First it says:

If a processor evaluates an operand E (wholly or in part), then it is required to establish that the actual value of the operand E does not violate any constraints on its cardinality.

That is OK as the processor has established that the argument will not be used, so the processor will not evaluate it (especially if there is a lazy hint)

But I do see some contradiction in this rule: If the processor has evaluated E only "in part", then in the general case it might not be able from the result of this partial evaluation "to establish that the actual value of the operand E does not violate any constraints on its cardinality"

Subsequently it says:

Another consequence of these rules is that where none of the items in a sequence contributes to the result of an expression, the processor is not obliged to evaluate any part of the sequence. Again, however, the processor cannot dispense with a required cardinality check: if an empty sequence is not permitted in the relevant context, then the processor must ensure that the operand is not an empty sequence.

The second extract implies that, given the function ->($x as xs:boolean) as xs:boolean->{false()}, even though the value of $x is not needed, the processor is expected to check that the supplied value is a singleton. That seems unreasonable to me (and I'm pretty sure Saxon won't do it).

I agree, and I also believe that we need to fix this rule not to require/expect the processor to do any checks in this case at all.

[dnovatchev]

Not evaluating an argument that isn't referenced in the function body is a pretty straightforward optimization, and I'm not sure why you think the hint is useful. It's potentially more useful if the argument is referenced in some but not all execution paths, but I'm still very doubtful that many programmers would use it wisely.

Absolutely true!

This is why it is the programmer who decides whether or not to specify the hint, depending on the nature of the problem and the algorithm that is implemented -- it would not be possible for the XPath processor to automatically deduce whether or not a delay in the evaluation is justifiable.

For example, we could assume that the probability of the 1st argument of op("and") to have the value false() is 50% and this may be sufficient to justify a lazy hint. On the other side, if a short-circuiting situation would happen only in one in 10 cases (imagine a 10-valued logic 😄 ), then the programmer may be more inclined not to specify the lazy hint in this case.

Again, the programmer (me 😄) should be in control.

Thank you for the very useful and needed explanation of the current rules!

[dnovatchev]

It might be useful if you wrote a more detailed proposal, in spec prose, defining the syntax and semantics of the new construct: and perhaps a note suggesting advice to users on when to use it.

@michaelhkay Thank you for your guidance and encouragement.

As I have never written such prose till now, would you, please, recommend a specific existing example of such that I could follow?

[dnovatchev]

I am closing this as the comments thread has become too-long.

I have produced the "prose" that @michaelhkay asked for and it is the core of the new issue #299

Thanks to all who provided feedback - this is how the whole idea was refined to its current, more precise form in #299