(Note, this should be an XP rather than XQ bug).

Previous discussion on this topic can be found in a (member-only) email thread, of which perhaps the key message is this one:

https://lists.w3.org/Archives/Member/w3c-xsl-query/2014Jan/0226.html

I believe after re-reading this thread that the spec is written the way it is for good reasons and we should make no change.

(In reply to Michael Kay from comment #1)

> https://lists.w3.org/Archives/Member/w3c-xsl-query/2014Jan/0226.html

Thanks for digging that out.  I'll work through the argument.

I'm unhappy that

map(k, Vm) 

is not a subtype of 

function(xs:anyAtomicType) as Vf, where Vm is a subtype of Vf.

and that

array(Va)

is not a subtype of

function(xs:integer) as Vf, where Vm is a subtype of Vf.

This stems from the text

"The function signature of the map, treated as a function, is always function(xs:anyAtomicType) as item()*, regardless of the actual types of the keys and values in the map. This means that a function item type with a more specific return type, such as function(xs:anyAtomicType) as xs:integer, does not match a map in the sense required to satisfy the instance of operator. However, the rules for function coercion mean that any map can be supplied as a value in a context where such a type is the required type, and a type error will only occur if an actual call on the map (treated as a function) returns a value that is not an instance of the required return type."

This appears to prevent a processor from using static type analysis to avoid unnecessary function coercion.  For example, I think this requires that

function() { 1 } instance of function() as xs:integer

returns false.

(In reply to Michael Kay from comment #1)

> Previous discussion on this topic can be found in a (member-only) email
> thread, of which perhaps the key message is this one:
> 
> https://lists.w3.org/Archives/Member/w3c-xsl-query/2014Jan/0226.html
> 
> I believe after re-reading this thread that the spec is written the way it
> is for good reasons and we should make no change.

I agree.

I agree with Michael Kay - this is a deliberate design decision. In fact, things break if a map type can be a subtype of a function type - as I described in the email referenced.

It may help to think of it like this: The map interface doesn't inherit from the function interface - however all map instances (objects) implement both the map and the function interface.

From a static typing perspective, it's as if an expression that returns a map has two equally valid static types - it's returning a value that is both a map and a function. Implement that as you will, since we aren't standardizing static typing any more.

You need to remember that the type system isn't defined by the SequenceType syntax. That syntax only defines the types you can test for in the language, and what it means to pass or fail those tests.

(In reply to Tim Mills from comment #3)
> This appears to prevent a processor from using static type analysis to avoid
> unnecessary function coercion.  For example, I think this requires that
> 
> function() { 1 } instance of function() as xs:integer
> 
> returns false.

I agree that your expression above should return false. I think it would be reasonable to allow an implementation to determine a stricter return type for the inline function using static typing if it can.

Of course, your own static typing implementation could easily carry two types for the inline function expression - the "official" static type, and a static type for the way it behaves in practice. That would allow you to avoid the function coercion you were worried about.

(In reply to John Snelson from comment #5)
> I agree with Michael Kay - this is a deliberate design decision. In fact,
> things break if a map type can be a subtype of a function type - as I
> described in the email referenced.

The current specification says

"The judgement subtype-itemtype(Ai, Bi) determines if the ItemType Ai is a subtype of the ItemType Bi. Ai is a subtype of Bi if and only if at least one of the following conditions applies:

Ai is map(*) (or, because of the transitivity rules, any other map type), and Bi is function(*)."

and the F&O diagram shows map(*) and array(*) as being derived from function(*).

In the referenced message, you say

"This leads to the inescapable conclusion that even though a map value is 
a function value, a map ItemType is not a function ItemType - they are 
fundamentally different types of test."

I'm missing something here, because this seems contradicatory.  Could you also please elaborate on what breaks?

(In reply to John Snelson from comment #6)
> (In reply to Tim Mills from comment #3)
> > This appears to prevent a processor from using static type analysis to avoid
> > unnecessary function coercion.  For example, I think this requires that
> > 
> > function() { 1 } instance of function() as xs:integer
> > 
> > returns false.
> 
> I agree that your expression above should return false. I think it would be
> reasonable to allow an implementation to determine a stricter return type
> for the inline function using static typing if it can.
> 
> Of course, your own static typing implementation could easily carry two
> types for the inline function expression - the "official" static type, and a
> static type for the way it behaves in practice. That would allow you to
> avoid the function coercion you were worried about.

Unfortunately that would have to permeate down to every expression to get the "right" answer. e.g.

(if (condition()) then function() { 1 }  else function() { 2 }) instance of xs:integer

I'm lobbying to allow 

function() { 1 } instance of function() as xs:integer 

to be true or false, in the same way that 

1.3 + 0.7 instance of xs:integer 

is implementation defined.

(In reply to Tim Mills from comment #7)
> I'm missing something here, because this seems contradicatory.  Could you
> also please elaborate on what breaks?

Map types are not contravariant in the type of their keys, but function types are contravariant in the types of their arguments. Therefore map SequenceTypes cannot be considered to be subtypes of specific (ie: not function(*)) function SequenceTypes.

(In reply to Tim Mills from comment #8)
> I'm lobbying to allow 
> 
> function() { 1 } instance of function() as xs:integer 
> 
> to be true or false, in the same way that 
> 
> 1.3 + 0.7 instance of xs:integer 
> 
> is implementation defined.

That's the change I suggested in comment #6, which I'm fine with making.

(In reply to Tim Mills from comment #8)
> I'm lobbying to allow 
> 
> function() { 1 } instance of function() as xs:integer 
I wrote in today's IRC chat that at present, at least two implementations of XPath (this is an XQ bug but equally applies to XP) return "true" on that query: Saxon and Exselt. I didn't try others.

Also, it is always a safe optimization to make the return type more specific if you can, as anywhere the result of the function is needed, the more specific result is also an instance of the more generic result. I.e., this succeeds:

I.e., the following returns "boo true", even though $g has return type item().

   let $g := function() { 1 }, 
   $f := function($h as function() as xs:decimal) { "boo" } 
   return ($f($g), $g instance of function() as xs:integer)

I think the spec already allows this.

So I don't agree with comments below that this expression should fail.

(In reply to John Snelson from comment #6)
> (In reply to Tim Mills from comment #3)
> > This appears to prevent a processor from using static type analysis to avoid
> > unnecessary function coercion.  For example, I think this requires that
> > 
> > function() { 1 } instance of function() as xs:integer
> > 
> > returns false.
> 
> I agree that your expression above should return false. I think it would be
> reasonable to allow an implementation to determine a stricter return type
> for the inline function using static typing if it can.

I'm not convinced that the specification allows this. Here's what it says about the type of an inline function expression:

<quote>
[Definition: An inline function expression creates an anonymous function defined directly in the inline function expression.] An inline function expression specifies the names and SequenceTypes of the parameters to the function, the SequenceType of the result, and the body of the function. [Definition: An anonymous function is a function created by an inline function expression.]

If a function parameter is declared using a name but no type, its default type is item()*. If the result type is omitted from an inline function expression, its default result type is item()*.
</quote>

For other functions, it's all about the statically known function signatures:

<quote>
[Definition: Statically known function signatures. This is a mapping from (expanded QName, arity) to function signatureDM31. ] The entries in this mapping define the set of functions that are available to be called from a static function call, or referenced from a named function reference. Each such function is uniquely identified by its expanded QName and arity (number of parameters). Given a statically known function's expanded QName and arity, this component supplies the function's signatureDM31, which specifies various static properties of the function, including types and annotations.
</quote>

So for these functions, if you know the QName and arity, you know the return type.


> Of course, your own static typing implementation could easily carry two
> types for the inline function expression - the "official" static type, and a
> static type for the way it behaves in practice. That would allow you to
> avoid the function coercion you were worried about.

Yes, and so far, I think that should be documented as a known incompatibility.

(In reply to Tim Mills from comment #8)
> I'm lobbying to allow 
> 
> function() { 1 } instance of function() as xs:integer 

I would like that.  I would like to find a simple way to do that without breaking anything.  I don't think we have found it yet, so let's keep looking.

(In reply to Abel Braaksma from comment #11)
> I wrote in today's IRC chat that at present, at least two implementations of
> XPath (this is an XQ bug but equally applies to XP) return "true" on that
> query: Saxon and Exselt. I didn't try others.

BaseX returns true.  Tim's implementation presumably returns true.  So a lot of implementations do.  I don't yet know where our specs permit this.  I'm happy to be shown where, or to be shown a simple way to fix this in the specs.
 
> Also, it is always a safe optimization to make the return type more specific
> if you can, as anywhere the result of the function is needed, the more
> specific result is also an instance of the more generic result. I.e., this
> succeeds:
> 
> I.e., the following returns "boo true", even though $g has return type
> item().
> 
>    let $g := function() { 1 }, 
>    $f := function($h as function() as xs:decimal) { "boo" } 
>    return ($f($g), $g instance of function() as xs:integer)

But does our spec say this, or are you going by implementations?

> I think the spec already allows this.

Where does our spec allow this?

I think there's a general principle at stake here. I think we have made many decisions over the years that suggest that we have consensus on this principle, including some very recent decisions on test results. The principle is this:

Where the specification states that the result of an expression is of type X, then it is acceptable for the implementation to return a value of type Y, provided that subtype(Y, X) holds.

A consequence of this principle is that the result of the expression (V instance of Y) is implementation-defined.

For example, when we say "the result of a value comparison is a boolean", then this is shorthand for "the result R of a value comparison satisfies (R instance of xs:boolean). We have nothing to say about whether or not R is an instance of some other more specific type.

We have stated this principle clearly for the result of function calls (both calls on user functions and calls on system functions). I don't believe that we state clearly enough that it applies to all expressions. 

To take an example, if $H is a hat-size, then the specification requires only that the result of +$H is an integer. Since a hat-size is an integer, it is acceptable to return $H as the result of this expression. The result of the expression (+$H instance of hat-size) is therefore implementation-defined.

The same principle applies to expressions that return functions. The specification requires that the result of the expression (function() as xs:decimal {2}) is of type (function() as xs:decimal). Since the type (function() as xs:integer) is a subtype of this, it is therefore implementation-defined whether or not the expression 

(function() as xs:decimal {2}) instance of function() as xs:integer

returns true or false.

Note that this is all about dynamic types; it has nothing to do with static typing.

ACTION A-643-04: JRobie and Tim to draw up a proposal to resolve bug
29586 (funciton item types).


In DM31 2.8.1 Functions, it is stated that a function has the property:

* signature (a FunctionTest of the form Annotation* TypedFunctionTest): The TypedFunctionTestXP31 has one SequenceTypeXP31 for each parameter, and one SequenceType for the function's result. [Definition: A function signature represents the type of a function.] The presence of annotations is language dependent; functions defined in languages, such as XPath, that have no mechanism for defining annotations will create functions in the data model with zero annotations.

This says that the signature is a FunctionTest, but doesn't say that the SequenceType for parameter and return type have to match those written in the function declaration.

As Kike Kay has pointed out, where the specification states that the result of an expression is of type X, then it is acceptable for the implementation to return a value of type Y, provided that subtype(Y, X) holds. i.e. substitutability.

To make it clear that this principal applies to function items, I suggest we look at the text of

* 3.1.5  Evaluating static and dynamic function calls
* 3.1.6  Named Function References
* 3.1.7  Inline Function Expressions


In 3.1.5.1 Evaluating Static and Dynamic Function Calls, there is a description of how partial function application results in the creation of a function item's signature. 

  signature: The signature of F, removing the parameter type at each of the fixed positions.

As a result of partial function application, the processor might be able to narrow the signature prescribed in the above text.  THus the signature is as above or a subtype thereof.



In 3.1.6 Named Function References, there is no description of how the signature of a named function reference is constructed.  Perhaps this is an oversight, but it leaves plenty of wiggle room.  For example, an implementation might want to return a value with signature function(item()*) as xs:nonNegativeInteger for fn:count#1.


In 3.1.7 Inline Function Expressions, there is a description of how the signature is constructed: 

  signature: A FunctionTest constructed from the Annotations and SequenceTypes in the InlineFunctionExpr.

We should state that the signature must be as above or a subtype thereof, as determined by (static?) analysis of the function's implementation (body?).


In 2.5.6.2 The judgement subtype-itemtype(Ai, Bi), add the rules

* Ai is map(K, V), and Bi is function(xs:anyAtomicType) as V?.
* Ai is array(X) and Bi is function(xs:integer) as X.


The text in 3.1.5.3 Function Coercion then needs to be addressed.

"The map $m has a function signature of function(xs:anyAtomicType) as item()*. When the fn:filter() function is called, the following occurs to the function:"

 1. The map $m is treated as function ($f), equivalent to map:get($m,?)."

As we've said above, as a result of partial function application, an implementation may be able to identify a more specific type.  Here, we can say that the following static typing judgement holds.

statEnv |- $m <: map(K, V)
----------------------------
statEnv |- map:($m, ?) : V?

So the implementation is free to treat $m as matching function(xs:anyAtomicType) as V?


In "2.5.5.8 Map Test", replace the text

"The function signature of the map, treated as a function, is always function(xs:anyAtomicType) as item()*, regardless of the actual types of the keys and values in the map. This means that a function item type with a more specific return type, such as function(xs:anyAtomicType) as xs:integer, does not match a map in the sense required to satisfy the instance of operator. However, the rules for function coercion mean that any map can be supplied as a value in a context where such a type is the required type, and a type error will only occur if an actual call on the map (treated as a function) returns a value that is not an instance of the required return type."

with

"The function signature of the map, treated as a function, is always a subtype of function(xs:anyAtomicType) as item()*.  The rules for function coercion mean that any map can be supplied as a value in a context where the required type has a more specific return type, such as function(xs:anyAtomicType) as xs:integer, even when the map does not match in the sense required to satisfy the instance of operator. In such cases, a type error will only occur if an actual call on the map (treated as a function) returns a value that is not an instance of the required return type."

Similarly, in "2.5.5.9 Array Test", replace the text

"The function signature of the array, treated as a function, is always function(xs:integer) as item()*, regardless of the actual member types in the array. This means that a function item type with a more specific return type, such as function(xs:integer) as xs:integer, does not match an array in the sense required to satisfy the instance of operator. However, the rules for function coercion mean that any array can be supplied as a value in a context where such a type is the required type, and a type error will only occur if an actual call on the array (treated as a function) returns a value that is not an instance of the required return type."

with

"The function signature of the array, treated as a function, is always a subtype of function(xs:integer) as item()*.  The rules for function coercion mean that any array can be supplied as a value in a context where the required type has a more specific return type, such as function(xs:integer) as xs:integer, evnm when the array does not match in the sense required to satisfy the instance of operator. In such cases, a type error will only occur if an actual call on the array (treated as a function) returns a value that is not an instance of the required return type."

In "2.5.5.8 Map Test", replace the text

"The function signature of the map, ... the required return type."

with

"The function signature of a map matching type map(K, V), treated as a function, is function(xs:anyAtomicType) as V?.  It is thus always a subtype of function(xs:anyAtomicType) as item()* regardless of the actual types of the keys and values in the map.  The rules for function coercion mean that any map can be supplied as a value in a context where the required type has a more specific return type, such as function(xs:anyAtomicType) as xs:integer, even when the map does not match in the sense required to satisfy the instance of operator. In such cases, a type error will only occur if an actual call on the map (treated as a function) returns a value that is not an instance of the required return type."

Similarly, in "2.5.5.9 Array Test", replace the text

"The function signature of the array, ... the required return type."

with

"The function signature of an array matching array(X), treated as a function, is function(xs:integer) as X.  It is thus always a subtype of function(xs:integer) as item()* regardless of the actual member types in the array.  The rules for function coercion mean that any array can be supplied as a value in a context where the required type has a more specific return type, such as function(xs:integer) as xs:integer, evnm when the array does not match in the sense required to satisfy the instance of operator. In such cases, a type error will only occur if an actual call on the array (treated as a function) returns a value that is not an instance of the required return type."

(In reply to Tim Mills from comment #16)
> In "2.5.5.8 Map Test", replace the text
> 
> "The function signature of the map, ... the required return type."
> 
> with
> 
> "The function signature of a map matching type map(K, V), treated as a
> function, is function(xs:anyAtomicType) as V?.  It is thus always a subtype
> of function(xs:anyAtomicType) as item()* regardless of the actual types of
> the keys and values in the map.

I think this text is unclear what to do in the case where no static typing information is available. We need that case to be the default, and for the text to allow a better type (a subtype of map(K,V)).

(In reply to John Snelson from comment #17)
> (In reply to Tim Mills from comment #16)
> > In "2.5.5.8 Map Test", replace the text
> > 
> > "The function signature of the map, ... the required return type."
> > 
> > with
> > 
> > "The function signature of a map matching type map(K, V), treated as a
> > function, is function(xs:anyAtomicType) as V?.  It is thus always a subtype
> > of function(xs:anyAtomicType) as item()* regardless of the actual types of
> > the keys and values in the map.
> 
> I think this text is unclear what to do in the case where no static typing
> information is available. We need that case to be the default, and for the
> text to allow a better type (a subtype of map(K,V)).

If the processor has sufficient information available (e.g. it knows that the item matches type map(K, V), it can avoid coercion.  Otherwise (it only knows that the item is map(*), it has to be pessimitic and introduce coercion.  However, from the point of view of the user, there is no observable difference.

(In reply to Tim Mills from comment #18)
> (In reply to John Snelson from comment #17)
> > (In reply to Tim Mills from comment #16)
> > > In "2.5.5.8 Map Test", replace the text
> > > 
> > > "The function signature of the map, ... the required return type."
> > > 
> > > with
> > > 
> > > "The function signature of a map matching type map(K, V), treated as a
> > > function, is function(xs:anyAtomicType) as V?.  It is thus always a subtype
> > > of function(xs:anyAtomicType) as item()* regardless of the actual types of
> > > the keys and values in the map.
> > 
> > I think this text is unclear what to do in the case where no static typing
> > information is available. We need that case to be the default, and for the
> > text to allow a better type (a subtype of map(K,V)).
> 
> If the processor has sufficient information available (e.g. it knows that
> the item matches type map(K, V), it can avoid coercion.  Otherwise (it only
> knows that the item is map(*), it has to be pessimitic and introduce
> coercion.  However, from the point of view of the user, there is no
> observable difference.

I think we agree on the principle. I just think the text doesn't explain it very well.

Would you be able to suggest an alternative?

(ACTION A-646-05)

3.1.5.1 Evaluating Static and Dynamic Function Calls

signature: The signature of F, removing the parameter type at each of the fixed positions. <INS>An implementation which can determine a more specific signature (for example, through use of type analysis) is permitted to do so.</INS>


3.1.7 Inline Function Expressions

signature: A FunctionTest constructed from the Annotations and SequenceTypes in the InlineFunctionExpr.  <INS>An implementation which can determine a more specific signature (for example, through use of type analysis of the function's body) is permitted to do so.</INS>


2.5.6.2 The judgement subtype-itemtype(Ai, Bi)

<INS>
* Ai is map(K, V), and Bi is function(xs:anyAtomicType) as V?.
* Ai is array(X) and Bi is function(xs:integer) as X.
</INS>

2.5.5.8 Map Test

<DEL>
The function signature of the map, treated as a function, is always function(xs:anyAtomicType) as item()*, regardless of the actual types of the keys and values in the map. This means that a function item type with a more specific return type, such as function(xs:anyAtomicType) as xs:integer, does not match a map in the sense required to satisfy the instance of operator. However, the rules for function coercion mean that any map can be supplied as a value in a context where such a type is the required type, and a type error will only occur if an actual call on the map (treated as a function) returns a value that is not an instance of the required return type.
</DEL>

<INS>
The function signature of a map matching type map(K, V), treated as a function, is function(xs:anyAtomicType) as V?.  It is thus always a subtype of function(xs:anyAtomicType) as item()* regardless of the actual types of the keys and values in the map.  The rules for function coercion mean that any map can be supplied as a value in a context where the required type has a more specific return type, such as function(xs:anyAtomicType) as xs:integer, even when the map does not match in the sense required to satisfy the instance of operator. In such cases, a type error will only occur if an actual call on the map (treated as a function) returns a value that is not an instance of the required return type.
</INS>

2.5.5.9 Array Test

<DEL>
The function signature of the array, treated as a function, is always function(xs:integer) as item()*, regardless of the actual member types in the array. This means that a function item type with a more specific return type, such as function(xs:integer) as xs:integer, does not match an array in the sense required to satisfy the instance of operator. However, the rules for function coercion mean that any array can be supplied as a value in a context where such a type is the required type, and a type error will only occur if an actual call on the array (treated as a function) returns a value that is not an instance of the required return type.
</DEL>

<INS>
The function signature of an array matching array(X), treated as a function, is function(xs:integer) as X.  It is thus always a subtype of function(xs:integer) as item()* regardless of the actual member types in the array.  The rules for function coercion mean that any array can be supplied as a value in a context where the required type has a more specific return type, such as function(xs:integer) as xs:integer, evnm when the array does not match in the sense required to satisfy the instance of operator. In such cases, a type error will only occur if an actual call on the array (treated as a function) returns a value that is not an instance of the required return type.
</INS>

At the meeting on 2016-06-21, the WG agreed to adopt the proposal in comment #21.
Action A-647-07 was raised to track this.