(Param Sweep) - Stephen Pickles' public comment
Hi all, I took a much closer look at Steve's input on the subject of looping through values ( http://www.ogf.org/gf/docs/comment.php?id=282 ) and, contrary to what I was saying in the teleconf yesterday (which was based on not having given it suitable forethought - big sorry! :( ), before proceding I have the following points relating to Steve's concerns : I'll use this convention throughout : Option (A) : start, step and end values (as per current spec.) Option (B) : start, step and loop count values (Steve's proposal) Point 1 : Following a very small survey on a few local users I received roughly equal preference for each option based on the following principles: Option (A) : Useful when ranges (e.g. physiological ranges) are known, so little or no concern for the number of loops to perform. As per examples ( http://forge.ogf.org/sf/wiki/do/viewPage/projects.jsdl-wg/wiki/ParameterSwee... ) Option (B) : Useful when a specific number of iterations are required, e.g. having 10 values to test. Note: There was some uncertainty, in that a loop count of "n" would generate "n+1" values, i.e, a loop count of 0 will still produce a single loop value! This would require clarification by documentation. Conclusion : We need to ensure that the specification doesn't prevent either of these options for job submission data entry. Point 2 : After reading up about Fortran the best official-looking (i.e. I'm not a Fortran user/expert) explanation I could find is : "3.2 Real & double precision DO variables This was a feature copied from Algol 60 to Fortran 77 at a time when there was a move to relax the strict type rules of Fortran 66. Subsequently it was realized by IFIP that it was a mistake in Algol and the feature did not appear in Algol 68. The problem is that because of the nature of real arithmetic it is not possible, without detailed knowledge of the arithmetic and implementation of a system, to predict the behaviour of a program using this feature. Thus use contradicts the first purpose of the standard, the promotion of portability of programs. Since this deficiency has been known for over twenty years, the feature has been relatively little used in Fortran and programs are readily convertible to use an integer control variable. Fortran should recognize that a mistake was made and the feature should now be deleted from the language." ( http://www.open-std.org/JTC1/SC22/WG5/436 ) Conclusion : Fortran, no doubt as many other programming languages, suffers from non-integer accuracy problems. IMHO though this should be considered a problem solely for implementors to resolve using their own solutions, but it should not however influence the determination of a specification by which grid users want to submit their jobs (i.e. our role). To emphasise the implementation-specific nature Java provides out-of-the-box ability to perform IEEE 754 standard ( http://en.wikipedia.org/wiki/IEEE_754 ), base 10 / decimal arithmetic by use of the BigDecimal class ( http://java.sun.com/j2se/1.5.0/docs/api/java/math/BigDecimal.html ) (note: values of which should be initialised using string representations), which is considerably more accurate than Float or Double classes which use base 2 arithmetic. ( http://www.ddj.com/java/184405721 ) and could meet the accuracy needs of the vast majority of users. In another official-looking document I understand that Fortran has moved towards adopting decimal floating point arithmetic IEEE 754 ( http://grouper.ieee.org/groups/754/email/msg01921.html ) Point 3 : I believe that Option (A) delivers a stronger contract for accuracy by implementations by explicitly specifying three verifiable values, rather than Option (B) which provides just two, i.e. just start and step. Conclusion : Option (A) should take precedence over Option (B) as the former specifies a limit condition (and hence accuracy is explicit) whereas the latter doesn't. Point 4 : We must assume that the user is competent and accurate, although occasionally distracted. Conclusion : It's for implementors to worry about determining suitability of data entered. Overall conclusion: I feel we should stick 100% with the current specification and leave the ability to provide Option (B) input to interface implementations. I'd be very grateful for feedback to this email, particular from Steve Pickles, hence I've Cc'd him. Now that I've managed to document my concerns, and hopefully in a form which is more coherent (and with accessible references) than the views expressed during teleconfs, it'll be easier to see why I remain reluctant to change. Thanks, gef
Dear All, To cut a long story short, I think that Geoff' is talking about a specification of LoopDouble that is subtly different to the one that went to public comment. However, I also think that the specification that Geoff is defending (and has implemented) is actually BETTER than the published draft. I shall first re-iterate why I believe the current specification to be flawed. Then I shall try to explain the kind of changes that would be needed to fix it. Bear with me. Why the current specification is flawed: ---------------------------------------------------- In section 4.3, which is entitled, significantly, "LoopDouble", we read: <blockquote> The LoopDouble function provides an ordered list of double datatype values (corresponding to the IEEE double-precision 64-bit floating point type)... </blockquote> and later: <blockquote> The permissible value range for xsd:double is defined as consisting of "... the values m 2^e, where m is an integer whose absolute value is less than 2^53, and e is an integer between -1075 and 970, inclusive </blockquote> What all this implies (at least to this reader) is that the LoopDouble function deals with _binary_ 64-bit floating point numbers. It would seem therefore, taking the specification at face value, that an implementor of LoopDouble is allowed, even encouraged, to perform the necessary calculations in IEEE binary floating point arithmetic. It follows that conversion between the decimal string representations (xsd:double) and the nearest exact binary floating point must (or at least, is allowed to) happen in both directions. Now, as it is rather exceptional for any floating point decimal to have an exact representation in floating point binary (and vice versa), you end up with the problems I mentioned in my public comments and at a previous JSDL conference call, i.e. (1) how to determine cardinality (2) how to decide whether an exception "hits" the list generated by LoopDouble not to mention problems with reproducibility (across different implementations) that the slightest departure from IEEE compliance can cause. These problems have nothing to do with the accuracy of binary floating point arithmetic - only in infinite precision can you do exact conversions between base 2 and base 10 floating point numbers. Geoff''s comments don't change my position on this. As long as the specification is dealing explicitly or implicitly with binary floating point numbers, you need to change something to recover certainty about cardinality and reproducibility of exception-matching. My suggestion, which Geoff' calls option (B), addresses the cardinality problem only. Why Geoff's way is better ---------------------------------- All the aforesaid problems arise from conversion between decimal and binary floating point. They go away if the xsd:double values in LoopDouble (i.e. both the input parameters and the ordered list of values it returns) are interpreted as exact floating point decimal values, and the arithmetic is performed (with sufficient precision) also in floating point decimal. This offers an alternative resolution to option (B), i.e. to prescribe the use of _decimal_ floating point arithmetic in LoopDouble. Let me call this option (C). Is the JSDL working group willing to prescribe the use of decimal arithmetic? Clearly, Java implementors should have no problem. Implementors in other languages should be OK if they have an equivalent of Java's BigDecimal class. Even without such library support, it should not be too difficult to implement using only integer arithmetic - you don't need the full armoury of arithmetic operations; just extended precision addition and/or subtraction should be sufficient. I've done such things in the past. How to fix the spec for option (C) -------------------------------------------- These are my suggestions for changes to the specification to bring it in line with what Geoff has presumably implemented. 1. Use language that makes it explicit that the values involved are exact floating-point decimals, and that arithmetic MUST be performed in floating-point decimal. Get rid of all mentions of "double" (which conveys 64-bit base-2 floating point arithmetic to most readers). Of course, a user of the parameter sweep extension still can and will convert (approximately) the decimal string into some base-2 internal representation once it reaches their application code. What they do with it is up to them. 2. Change the name of the LoopDouble function to LoopDecimal. (Sorry, Geoff, you would need to change SOME code, even if it's just a tag name.) 3. Include an informational reference to IEEE 754-2008. 4. You could choose to limit the number of significant decimal digits that an implementation must support. 5. You can retain xsd:double to constrain the allowable parameters and return values. Although xsd:double was designed as an approximate decimal string representation of some other binary floating point number, see e.g. http://books.xmlschemata.org/relaxng/ch19-77065.html It has a format that's (almost) exactly what you want. (Although, to be pedantic, you it would be wise to constrain it further to disallow NaN, INF, and -INF as loop start, end and increment values.) 6. Tighten up the language on termination conditions. And negative increments. Disallow zero increments. See my public comments. 7. Once it's clear that you're working in the realm of floating point decimals, you can determine the trip count of an option (A) style loop by inspection. I strongly recommend that you include in the specification a formula for calculating the loop cardinality. I leave this as an exercise for the reader (hint: see the Fortran specification). I hope this is clear. I hope it helps. Stephen PS I noticed some other errors while re-reading the spec: (i) The mention of xsd:decimal in section 4.3 is spurious, misleading and actually incorrect. (ii) There's a lot of jumping over "lay dogs" in the examples, where "lazy dogs" is surely intended.
An afterthought: I told a small lie in my last posting when I said that all the problems of (start, end, increment) loops go away in floating-point decimal. The problems that remain are exactly the ones that led to the deprecation of loops with real limits and stride in Fortran90. They are a consequence of being limited to finite precision. Consider, for example, a loop where the start value is very large (e.g. near the maximum supported by the precision) and the increment value is very small. You can have a situation where adding the small value to the large value won't change the large value in finite precision. Round-off can also break the ideal behaviour of this style of loop in other ways, e.g. computing the trip count (i.e. cardinality) from the start, end, and increment can fail to give the same trip count as actually executing the loop. Of course, you can also construct a pathological loop by specifying start, increment and count. If increment is too small with respect to start, you generate count identical values. So a good quality implementation will need to defend itself against pathological loop limits. This will be true to some extent regardless of whether you choose option (B) or (C) or something else. I therefore suggest providing for an "insufficient precision" fault-type in the specification of the JSDL parameter sweep extension. It can be difficult to tell in advance if a loop will be pathological. Some checks suggest themselves. If the loop generates two consecutive identical values the implementation should terminate the loop and throw a fault. If the loop generates a different cardinality than the pre-computed value, the implementation should throw a fault. A numerical analyst could work out a better set of checks. Best wishes, Stephen 2009/1/19 Stephen Pickles <stephen.m.pickles@googlemail.com>:
Dear All,
To cut a long story short, I think that Geoff' is talking about a specification of LoopDouble that is subtly different to the one that went to public comment.
However, I also think that the specification that Geoff is defending (and has implemented) is actually BETTER than the published draft.
I shall first re-iterate why I believe the current specification to be flawed. Then I shall try to explain the kind of changes that would be needed to fix it.
Bear with me.
Why the current specification is flawed: ----------------------------------------------------
In section 4.3, which is entitled, significantly, "LoopDouble", we read:
<blockquote> The LoopDouble function provides an ordered list of double datatype values (corresponding to the IEEE double-precision 64-bit floating point type)... </blockquote>
and later:
<blockquote> The permissible value range for xsd:double is defined as consisting of "... the values m 2^e, where m is an integer whose absolute value is less than 2^53, and e is an integer between -1075 and 970, inclusive </blockquote>
What all this implies (at least to this reader) is that the LoopDouble function deals with _binary_ 64-bit floating point numbers. It would seem therefore, taking the specification at face value, that an implementor of LoopDouble is allowed, even encouraged, to perform the necessary calculations in IEEE binary floating point arithmetic. It follows that conversion between the decimal string representations (xsd:double) and the nearest exact binary floating point must (or at least, is allowed to) happen in both directions. Now, as it is rather exceptional for any floating point decimal to have an exact representation in floating point binary (and vice versa), you end up with the problems I mentioned in my public comments and at a previous JSDL conference call, i.e. (1) how to determine cardinality (2) how to decide whether an exception "hits" the list generated by LoopDouble not to mention problems with reproducibility (across different implementations) that the slightest departure from IEEE compliance can cause.
These problems have nothing to do with the accuracy of binary floating point arithmetic - only in infinite precision can you do exact conversions between base 2 and base 10 floating point numbers.
Geoff''s comments don't change my position on this. As long as the specification is dealing explicitly or implicitly with binary floating point numbers, you need to change something to recover certainty about cardinality and reproducibility of exception-matching. My suggestion, which Geoff' calls option (B), addresses the cardinality problem only.
Why Geoff's way is better ----------------------------------
All the aforesaid problems arise from conversion between decimal and binary floating point. They go away if the xsd:double values in LoopDouble (i.e. both the input parameters and the ordered list of values it returns) are interpreted as exact floating point decimal values, and the arithmetic is performed (with sufficient precision) also in floating point decimal.
This offers an alternative resolution to option (B), i.e. to prescribe the use of _decimal_ floating point arithmetic in LoopDouble.
Let me call this option (C).
Is the JSDL working group willing to prescribe the use of decimal arithmetic?
Clearly, Java implementors should have no problem. Implementors in other languages should be OK if they have an equivalent of Java's BigDecimal class. Even without such library support, it should not be too difficult to implement using only integer arithmetic - you don't need the full armoury of arithmetic operations; just extended precision addition and/or subtraction should be sufficient. I've done such things in the past.
How to fix the spec for option (C) --------------------------------------------
These are my suggestions for changes to the specification to bring it in line with what Geoff has presumably implemented.
1. Use language that makes it explicit that the values involved are exact floating-point decimals, and that arithmetic MUST be performed in floating-point decimal. Get rid of all mentions of "double" (which conveys 64-bit base-2 floating point arithmetic to most readers).
Of course, a user of the parameter sweep extension still can and will convert (approximately) the decimal string into some base-2 internal representation once it reaches their application code. What they do with it is up to them.
2. Change the name of the LoopDouble function to LoopDecimal. (Sorry, Geoff, you would need to change SOME code, even if it's just a tag name.)
3. Include an informational reference to IEEE 754-2008.
4. You could choose to limit the number of significant decimal digits that an implementation must support.
5. You can retain xsd:double to constrain the allowable parameters and return values. Although xsd:double was designed as an approximate decimal string representation of some other binary floating point number, see e.g. http://books.xmlschemata.org/relaxng/ch19-77065.html It has a format that's (almost) exactly what you want.
(Although, to be pedantic, you it would be wise to constrain it further to disallow NaN, INF, and -INF as loop start, end and increment values.)
6. Tighten up the language on termination conditions. And negative increments. Disallow zero increments. See my public comments.
7. Once it's clear that you're working in the realm of floating point decimals, you can determine the trip count of an option (A) style loop by inspection. I strongly recommend that you include in the specification a formula for calculating the loop cardinality. I leave this as an exercise for the reader (hint: see the Fortran specification).
I hope this is clear. I hope it helps.
Stephen
PS I noticed some other errors while re-reading the spec: (i) The mention of xsd:decimal in section 4.3 is spurious, misleading and actually incorrect. (ii) There's a lot of jumping over "lay dogs" in the examples, where "lazy dogs" is surely intended.
Hi Stephen, Thanks for providing further input, it's much appreciated. I'm sure that there'd be no objection to improving the wording of the specification, as per your suggestions, to ensure that there can be no misinterpretation. We can make sure that the words "decimal" and "double" are clearly explained in context, e.g. that "xsd:double" represents the value range for JSDL sweep xml documents to be considered valid, and recommending the use of "decimal" arithmetic in implementations. Perhaps an additional section (or references to external resources) for implementation guidance for cardinality determination, precision, etc? I don't think that we should change LoopDouble to LoopDecimal though because: 1) primarily that may cause uncertainly from people mistakenly associating "decimal" with xsd:decimal.... which we do not use because it doesn't permit use of scientific notation, and 2) perhaps, although unlikely, someone may eventually choose to loop over xsd:decimal values and won't be able to call it LoopDecimal! To point to some earlier deliberations on name convention and tightening up of the specification you're welcome to look at : http://forge.ogf.org/sf/wiki/do/viewPage/projects.jsdl-wg/wiki/ParameterSwee... I hope to reassure you that quite a few of the issues and concerns you raise have been discussed during teleconfs when preparing the specification. From recollection though there is a concensus that we should avoid "exotic"! xsd, e.g. defining new xsd datatypes/constructs to restrict permissible values, so as to ensure JSDL documents can be handled safely by as many tools as possible. gef Stephen Pickles wrote:
Dear All,
To cut a long story short, I think that Geoff' is talking about a specification of LoopDouble that is subtly different to the one that went to public comment.
However, I also think that the specification that Geoff is defending (and has implemented) is actually BETTER than the published draft.
I shall first re-iterate why I believe the current specification to be flawed. Then I shall try to explain the kind of changes that would be needed to fix it.
Bear with me.
Why the current specification is flawed: ----------------------------------------------------
In section 4.3, which is entitled, significantly, "LoopDouble", we read:
<blockquote> The LoopDouble function provides an ordered list of double datatype values (corresponding to the IEEE double-precision 64-bit floating point type)... </blockquote>
and later:
<blockquote> The permissible value range for xsd:double is defined as consisting of "... the values m 2^e, where m is an integer whose absolute value is less than 2^53, and e is an integer between -1075 and 970, inclusive </blockquote>
What all this implies (at least to this reader) is that the LoopDouble function deals with _binary_ 64-bit floating point numbers. It would seem therefore, taking the specification at face value, that an implementor of LoopDouble is allowed, even encouraged, to perform the necessary calculations in IEEE binary floating point arithmetic. It follows that conversion between the decimal string representations (xsd:double) and the nearest exact binary floating point must (or at least, is allowed to) happen in both directions. Now, as it is rather exceptional for any floating point decimal to have an exact representation in floating point binary (and vice versa), you end up with the problems I mentioned in my public comments and at a previous JSDL conference call, i.e. (1) how to determine cardinality (2) how to decide whether an exception "hits" the list generated by LoopDouble not to mention problems with reproducibility (across different implementations) that the slightest departure from IEEE compliance can cause.
These problems have nothing to do with the accuracy of binary floating point arithmetic - only in infinite precision can you do exact conversions between base 2 and base 10 floating point numbers.
Geoff''s comments don't change my position on this. As long as the specification is dealing explicitly or implicitly with binary floating point numbers, you need to change something to recover certainty about cardinality and reproducibility of exception-matching. My suggestion, which Geoff' calls option (B), addresses the cardinality problem only.
Why Geoff's way is better ----------------------------------
All the aforesaid problems arise from conversion between decimal and binary floating point. They go away if the xsd:double values in LoopDouble (i.e. both the input parameters and the ordered list of values it returns) are interpreted as exact floating point decimal values, and the arithmetic is performed (with sufficient precision) also in floating point decimal.
This offers an alternative resolution to option (B), i.e. to prescribe the use of _decimal_ floating point arithmetic in LoopDouble.
Let me call this option (C).
Is the JSDL working group willing to prescribe the use of decimal arithmetic?
Clearly, Java implementors should have no problem. Implementors in other languages should be OK if they have an equivalent of Java's BigDecimal class. Even without such library support, it should not be too difficult to implement using only integer arithmetic - you don't need the full armoury of arithmetic operations; just extended precision addition and/or subtraction should be sufficient. I've done such things in the past.
How to fix the spec for option (C) --------------------------------------------
These are my suggestions for changes to the specification to bring it in line with what Geoff has presumably implemented.
1. Use language that makes it explicit that the values involved are exact floating-point decimals, and that arithmetic MUST be performed in floating-point decimal. Get rid of all mentions of "double" (which conveys 64-bit base-2 floating point arithmetic to most readers).
Of course, a user of the parameter sweep extension still can and will convert (approximately) the decimal string into some base-2 internal representation once it reaches their application code. What they do with it is up to them.
2. Change the name of the LoopDouble function to LoopDecimal. (Sorry, Geoff, you would need to change SOME code, even if it's just a tag name.)
3. Include an informational reference to IEEE 754-2008.
4. You could choose to limit the number of significant decimal digits that an implementation must support.
5. You can retain xsd:double to constrain the allowable parameters and return values. Although xsd:double was designed as an approximate decimal string representation of some other binary floating point number, see e.g. http://books.xmlschemata.org/relaxng/ch19-77065.html It has a format that's (almost) exactly what you want.
(Although, to be pedantic, you it would be wise to constrain it further to disallow NaN, INF, and -INF as loop start, end and increment values.)
6. Tighten up the language on termination conditions. And negative increments. Disallow zero increments. See my public comments.
7. Once it's clear that you're working in the realm of floating point decimals, you can determine the trip count of an option (A) style loop by inspection. I strongly recommend that you include in the specification a formula for calculating the loop cardinality. I leave this as an exercise for the reader (hint: see the Fortran specification).
I hope this is clear. I hope it helps.
Stephen
PS I noticed some other errors while re-reading the spec: (i) The mention of xsd:decimal in section 4.3 is spurious, misleading and actually incorrect. (ii) There's a lot of jumping over "lay dogs" in the examples, where "lazy dogs" is surely intended.
participants (2)
-
geoff -
Stephen Pickles