[Bug 10205] New: Issues in section 16.2 Basic higher-order functions

http://www.w3.org/Bugs/Public/show_bug.cgi?id=10205

           Summary: Issues in section 16.2 Basic higher-order functions
           Product: XPath / XQuery / XSLT
           Version: Member-only Editors Drafts
          Platform: All
               URL: http://www.w3.org/XML/Group/qtspecs/specifications/xpa
                    th-functions-11/html/Overview-diff.html#basic-hofs
        OS/Version: All
            Status: NEW
          Severity: normal
          Priority: P2
         Component: Functions and Operators 1.1
        AssignedTo: mike@saxonica.com
        ReportedBy: dnovatchev@gmail.com
         QAContact: public-qt-comments@w3.org


The following more obvious issues exist in the definition of the “Basic
higher-order functions”, section 16.2.

(1)     Summary of the section. The first sentence says: 
“The following functions take function items as an argument.”

This does not serve as a good distinction from the functions of the previous
group (16.1 Functions on functions) that are summarized as:

“The following functions operate on function items, that is, values referring
to a function”

Proposed improvement: Provide a more precise summary for 16.1 that better shows
the necessity to group the functions in 16.1 separately from those in 16.2.

(2)    16.2.1 fn:map
The summary says (emphasis is mine):
“Applies the function item $f to every item from the sequence $seq *in turn*,
returning the concatenation of the resulting sequences in order”.

It is incorrect to define any unnecessary order of processing for fn:map, in
fact, the application of $f to each item of the sequence can be done in
arbitrary order. 

Proposed solution: remove the phrase “in turn” from the summary of fn:map.

(3)    16.2.1 fn:map
The definition of the function makes it *shrinking*. It is possible that the
sequence – result from fn:map has fewer (or no) items than the list-argument of
the function. This is in sharp contrast with the usual definition of map() in
other functional programming languages and is not easily and immediately
visible. 

Also, fn:map is *flattening*, because where a nested sequence would be returned
in other functional languages, here a flat sequence is returned. Not only the
length of the result-list can be greater than the length of the input list, but
it would generally be rather challenging to understand which application of the
$f produced which subsequence of the result-list.

These unusual properties of the function may cause confusion to the programmer.

Proposed solution: Use another name for the function, and explain thoroughly
the unusual properties.

(4)    16.2.1 fn:map. 
No error condition is mentioned, although for fn:map thus defined there can be
a run-time type error.

Proposed solution: Define the error condition(s) that may arise. See also the
general type definition problem defined later (12).

(5)    16.2.1 fn:map and the other three functions.
In the provided XQuery and XSLT implementations the arguments and result of the
functions are not specified. This style of programming has often been cited as
example of not a good programming practice. 

It is not immediately clear if these implementations will not cause a type
error. This issue is present in the proposed implementations of all four
functions.

Proposed solution: Modify the provided implementation code to specify the
result and arguments type.

(6)    16.2.2 fn:filter.
The summary says: 
“Returns those items from the sequence $seq for which the supplied function $f
returns true”

This definition leaves an important detail: what is the order of the returned
items of $seq.

Proposed solution: Specify, that the returned items are ordered in the same way
as they are in  $seq.

(7)    16.2.2 fn:filter.
The following error condition is specified:
“A type error occurs if the supplied function $f returns anything other than a
single xs:boolean item; there is no conversion to an effective boolean value.”

However, the definition of the function is:

fn:filter($f as function(item()) as xs:boolean,  
                   $seq as item()*) as item()*

$f is already defined to return an xs:boolean, therefore the described error
condition cannot occur during runtime and, if found by static type checking, is
not different than any other general static type-checking error, thus such
static type-checking error is not something specific to fn:filter and does not
need to be described here.

Proposed solution: Remove the description of this error condition.

(8)    16.2.3 function fn:fold-left,  and 16.2.4 function fn:fold-right
The summaries of these two functions define that the fn:fold-left processes the
items of its list-argument “from left to right” and that fn:foldl-right
processes the items of its list-argument “from right to left”. This is
generally not true, see Graham Hutton’s fold tutorial for more information:
http://www.cs.nott.ac.uk/~gmh/fold.pdf

(9)    16.2.3 function fn:fold-left
The error condition is specified as: 
“A type error occurs if the supplied function $f cannot be applied to two
arguments, where the first argument is either the value of $zero or the result
of a previous application of $f, and the second is $seq or any trailing
subsequence of $seq”.

In this text the phrase “or the result of a previous application of $f,” is
incorrect. Any result of a previous application of $f  is the value of $zero
when the type error happens.

Proposed solution: Replace the phrase 
“is either the value of $zero or the result of a previous application of $f,”

 With

“is the value of $zero”.

(10)    16.2.4 fn:fold-right
The error condition is specified as: 
“A type error occurs if the supplied function $f cannot be applied to two
arguments, where the first argument is any item in the sequence $seq, and the
second is either the value of $zero or the result of a previous application of
$f.”

This has the same problem as raised in (9) above.

Proposed solution: Replace the phrase 
“is either the value of $zero or the result of a previous application of $f,”

With

“is the value of $zero”.

(11)    16.2.3 function fn:fold-left,  and 16.2.4 function fn:fold-right
No hint is provided why both of these functions are necessary and when to use
one of them instead of the other. This results in confusion and will produce
frequent questions.

Proposed solution: Provide guidance when to use which function. For example, it
is stated in the literature, that with a lazy-evaluating processor the use of
fn:fold-left leads to stack overflow and that fn:fold-right  is to be preferred
in such case. Another example is if the $f function appends or prepends an item
to a sequence. Then, depending which of the prepend or append operation is
optimized by a particular language processor, either fn:fold-left or
fn:fold-right should be recommended.

(12)     All four functions.
The current types specified for the function arguments and results are
extremely general. As a result of this some very important type constraints 
(such as the type of one of the arguments of $f must be the same as the type of
$zero) have to be expressed in words and this is cumbersome and potentially
confusing. 

Proposed improvement: Specify these functions in pseudocode, showing clearly
the type constraints. For example:

fn:filter($f as function(TypeA) as xs:boolean, 
                  $seq as TypeA*) as TypeA*

With the above definition it is not necessary to define verbally that the type
of the first argument of $f must be the same as the type of the items of $seq .

-- 
Configure bugmail: http://www.w3.org/Bugs/Public/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
You are the QA contact for the bug.

Received on Tuesday, 20 July 2010 04:23:51 UTC