[xp31] Function signature of a map

[michaelhkay]

See also https://github.com/w3c/qt3tests/issues/28

Consider the expression $M instance of function(P) as R, where $M is a map.

§2.5.5.7 tells us "A TypedFunctionTest matches an item if it is a functionDM31 and the function's type signature (as defined in Section 2.8.1 Functions DM31) is a subtype of the TypedFunctionTest."

We know that $M is a function, but what is the type signature of this function?

§2.5.5.8 tells us "The function signature of a map matching type map(K, V), treated as a function, is function(xs:anyAtomicType) as V?. "

But a map matches many different map types. As an extreme case, the empty map matches map(K, V) for all possible values of K and V. So what is the function signature of an empty map?

If $M is an empty map, then (a) the function call $M(A) is permitted provided A is an atomic value, and (b) the result will always be an empty sequence. So from first principles, map{} is an instance of F(P) as R if (a) P is a subtype of xs:anyAtomicType, and (b) the empty sequence is an instance of R.

I believe the rule in §2.5.5.7, insofar as it applies to maps, needs to be replaced by:

A map M matches a TypedFunctionTest function(P) as R if (a) P is a subtype of xs:anyAtomicType, (b) every value in M is n instance of R, and (c) the empty sequence is an instance of R.

In XDM, however, §2.8.1 says that every function has a signature, so we still need to say what the function signature of a map is. We could try: the function signature of a map is function(anyAtomicType) as R, where R is the lowest common supertype of (a) the values appearing in the map, and (b) empty-sequence(). Unfortunately, though, we don't define a concept of lowest common supertype. We did define such a concept at one time, but we removed it, and with good reason: types form a lattice, not a hierarchy, so the concept is not well defined. I think the only answer to this is to say that the function signature of a map is function(anyAtomicType) as item()*, and then to avoid using the concept when defining whether a map is an instance of a given function type.

[jmdyck]

I wonder if you get the same result if you say:

• A map, considered as a function, has not one but many type signatures; and
• In §2.5.5.7, there's a match if any of those signatures is a subtype of the TypedFunctionTest.

[michaelhkay]

Also note, the statement in §2.5.5.8, specifically "The function signature of a map matching type map(K, V), treated as a function, is function(xs:anyAtomicType) as V?. ", is clearly buggy, because V is a SequenceType not an ItemType, so you can't just suffix it with "?" and expect the result to be a valid SequenceType.

[michaelhkay]

@jmdyck Yes, I think that's another way out of the hole. But I don't like having to change the data model, which asserts that every function has a signature.

[michaelhkay]

Over at https://github.com/w3c/qt3tests/issues/28, Abel Braaksma points us to F&O §17.1, which states:

The function corresponding to the map has the signature function($key as xs:anyAtomicValue) as item()*

So I think the fix for this problem is (a) to bring the language spec at §2.5.5.8 into line with F&O §17.1, and (b) in the language spec §2.5.5.7, add rules for a function test matching a map as proposed above.

[benibela]

I am also confused by rule 28 of subtype-itemtype

Rule 26 explains in detail that return types are covariant and arguments of functions are contravariant

But in rule 28 the map keys (which would be the argumernts) are covariant

[michaelhkay]

Rule 28 says that map(xs:decimal, xs:NCName) is substitutable for map(xs:integer, xs:string). I think that's OK, because the type map(xs:integer, xs:string) implies that $M?N (where N is an integer) will either return a string or nothing, and that's true for a map whose keys are all xs:decimal and whose values are all xs:NCName. It's only when you get into the domain of function types that contravariance becomes an issue.

[benibela]

Rule 28 says that map(xs:decimal, xs:NCName) is substitutable for map(xs:integer, xs:string).

Wouldn't it be map(xs:integer, xs:NCName) for map(xs:decimal, xs:string)?

[adamretter]

Over at w3c/qt3tests#28, Abel Braaksma points us to F&O §17.1, which states:

The function corresponding to the map has the signature function($key as xs:anyAtomicValue) as item()*

From an implementation perspective, that seems pretty sensible to me as the super-type for a map, as it handles every map empty or otherwise.

[abelbraaksma]

Apparently I reported this before: https://www.w3.org/Bugs/Public/show_bug.cgi?id=30317, but open issues in BugZilla weren't converted into open issues on Github.

That bug report is about returning cardinality zero-or-one V?, which should've been V*. It doesn't mention that V should only ever be item()*.

However:

• map-as-a-function is further declared in 3.11.1.2 in XP31:

  "Maps are functions, and function calls can be used to look up the value associated with a key in a map. If $map is a map and $key is a key, then $map($key) is equivalent to map:get($map, $key)."

• This is repeated in 17.1 in FO31:

  "The function corresponding to the map has the signature function($key as xs:anyAtomicValue) as item()*. Calling the function has the same effect as calling the get function: the expression $map($key) returns the same result as get($map, $key)"

• And in 3.1.5.3 in XP31:

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

• And rule 30 of subtype relationships in 2.5.6.2 of XP31 (which conflicts with rule 35 and 36):

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

Some relevant discussion about defining map-as-a-function normatively as map:get is here: https://www.w3.org/Bugs/Public/show_bug.cgi?id=29683.

If all of the above is true, then it follows that map-as-a-function must have the same signature as map:get (without the first operand), which is:

map:get($map as map(*), $key as xs:anyAtomicType) as item()*

Therefore, the signature of a map when treated as a function is function(xs:anyAtomicType) as item()*.

A function item is covariant on its return type and contravariant on its argument types. Therefore, these are true (assume $map := map { 1: 'Monday' }):

$map instance of function(xs:integer) as item()*
$map instance of function(xs:int) as item()*
$map instance of function(xs:string) as item()*
$map instance of function(xs:token) as item()*
$map instance of function(xs:decimal) as item()*
$map instance of function(xs:anyAtomicType) as item()*

And these are all false;

$map instance of function(element()) as item()*
$map instance of function(item()) as item()*
$map instance of function(xs:decimal) as xs:string*
$map instance of function(xs:anyAtomicType) as xs:anyAtomicType*
$map instance of function(xs:anyAtomicType) as item()
$map instance of function(xs:anyAtomicType) as item()?
$map instance of function(xs:anyAtomicType) as item()+

I think it cannot both be true that $map above is an instance of function(xs:anyAtomicType) as item()* and function(xs:integer) as xs:string*, because that would break transitivity.

None of the above prohibits passing maps-as-a-function as an argument to another function that expects a more specific function type: the function coercion rules allow such scenarios and may throw a runtime type error.

All the above probably applies to arrays equally well.

[benibela]

Rule 28 says that map(xs:decimal, xs:NCName) is substitutable for map(xs:integer, xs:string).

Wouldn't it be map(xs:integer, xs:NCName) for map(xs:decimal, xs:string)?

Also with Rule 26 and 28 and 35 and transitivity combined you could move up and down the type hierarchy choosing any key type for the function signature: map(xs:positiveInteger, xs:string) is an instance of map(xs:nonNegativeInteger, xs:string) is an instance of map(xs:integer, xs:string) is an instance of map(xs:decimal, xs:string) is an instance of function (xs:decimal) as xs:string? is an instance of function (xs:integer) as xs:string? is an instance of function (xs:negativeInteger) as xs:string? is an instance of function (xs:nonPositiveInteger) as xs:string?

[abelbraaksma]

map(xs:decimal, xs:string) is an instance of function (xs:decimal) as xs:string?

I assume this was a "pun intended" post, nevertheless: note that I meant the opposite, the return type is covariant, and being item()* for any map means this cannot happen, which in turn solves the transitivity issues.

[benibela]

map(xs:decimal, xs:string) is an instance of function (xs:decimal) as xs:string?

I assume this was a "punt intended" post, nevertheless: note that I meant the opposite, the return type is covariant, and being item()* for any map means this cannot happen, which in turn solves the transitivity issues.

I was just trying to use rule 35 of xquery 2.5.6.2. Although I forgot a step. map(xs:decimal, xs:string) is an instance of function (xs:anyAtomicType) as xs:string? is an instance of function (xs:decimal) as xs:string?, ...