!standard RM-A.5.2 (40) 96-11-16 AI95-00089/04 !class binding interpretation 96-09-05 !status WG9 approved 96-12-07 !status ARG approved 11-0-0 96-10-07 !status work item (letter ballot was 6-5-1) 96-10-03 !status ARG approved 6-0-2 (subject to letter ballot) 96-06-17 !status work item 96-04-04 !status received 95-09-29 !priority High !difficulty Hard !subject Float_Random.Value, Discrete_Random.Value !summary 96-09-15 It is a bounded error to invoke Value with a string that is not the image of any generator. If the error is detected, Constraint_Error or Program_Error is raised. Otherwise, a call to Reset with the resulting State will produce a Generator such that calls to Random with this Generator will produce a sequence of values of the appropriate subtype, but which might not be random in character. That is, the sequence of values might not fulfill the requirements of A.5.2(41-43). !question 96-09-05 A.5.2(40) says: Invoking Value with a string that is not the image of any generator state raises Constraint_Error. Is it legal to allow some extra flexibility? For example, suppose the Image function returns a representation of the state as a string of hexadecimal digits, with 'A'..'F' in upper case. A string with 'a'..'f' in lower case, but which is otherwise equivalent to a valid image, is not strictly speaking "the image of any generator state". May the Value function nevertheless return a valid state for such a string, or must it raise Constraint_Error? !recommendation 96-09-05 See summary. !wording 96-09-05 !discussion 96-09-15 A.5.2(40) seems to imply that the implementation must detect strings that could not have been produced by Image. However, for some kinds of random number generators, such detection is prohibitively expensive. Therefore, we choose to make this situation a bounded error. If the given string is syntactically malformed, the implementation will probably raise an exception. However, some strings might "look right", but produce a generator state that could never come from a valid seed, and results in non-random numbers. There is no need to make the situation erroneous -- the implementation shouldn't write on random memory locations, or take wild jumps. The worst that can happen is that a non-random sequence of numbers (for example, a sequence of zeros) will be produced. To be portable, the programmer should ensure that every string passed to Value came originally from a call to Image. Note that A.5.2(45) says, "The implementation ... shall document the nature of the strings that Value will accept without raising Constraint_Error." The reason for adding Program_Error to the list of possibilities is simply that 1.1.5(8) says that every bounded error can raise Program_Error. Note that this ruling does not allow calls to Random to raise Constraint_Error or Program_Error. !appendix 96-04-04 !section RM-A.5.2(40) !subject Float_Random.Value, Discrete_Random.Value !reference RM95-A.5.2(40) !from Keith Thompson 95-09-06 !reference as: 95-5268.a Keith Thompson 95-9-6>> !discussion The paragraph in question says Invoking Value with a string that is not the image of any generator state raises Constraint_Error. Is it legal to allow some extra flexibility? For example, suppose the Image function returns a representation of the state as a string of hexadecimal digits, with 'A'..'F' in upper case. A string with 'a'..'f' in lower case, but which is otherwise equivalent to a valid image, is not strictly speaking "the image of any generator state". May the Value function nevertheless return a valid state for such a string, or must it raise Constraint_Error? Alternatively, Image might return a representation of a state as a list of decimal integer values separated by blanks and/or commas (GNAT does this); may Value accept extra or missing blanks, leading zeros, literals in other bases, etc.? I suppose the issue is how flexibly the phrase "the image of" is to be interpreted. If it's taken to mean exactly a string that can be returned by the Image function, no flexibility is allowed. There seems little point to imposing such a strict requirement, though. **************************************************************** !section RM-A.5.2(40) !subject Float_Random.Value, Discrete_Random.Value !reference RM95-A.5.2(40) !reference 95-5268.a Keith Thompson 95-09-06 !from Tucker Taft 95-09-07 !reference as: 95-5269.a Tucker Taft 95-9-7>> !discussion > The paragraph in question says > > Invoking Value with a string that is not the image of any generator > state raises Constraint_Error. > > Is it legal to allow some extra flexibility? No, though as a pragmatic matter, some flexibility might creep in due to flaws in the Value algorithm. > ...For example, suppose > the Image function returns a representation of the state as a string > of hexadecimal digits, with 'A'..'F' in upper case. A string with > 'a'..'f' in lower case, but which is otherwise equivalent to a valid > image, is not strictly speaking "the image of any generator state". > May the Value function nevertheless return a valid state for such a > string, or must it raise Constraint_Error? It must raise Constraint_Error. > Alternatively, Image might return a representation of a state as a list > of decimal integer values separated by blanks and/or commas (GNAT does > this); may Value accept extra or missing blanks, leading zeros, literals > in other bases, etc.? No. > I suppose the issue is how flexibly the phrase "the image of" is to > be interpreted. If it's taken to mean exactly a string that can be > returned by the Image function, no flexibility is allowed. There seems > little point to imposing such a strict requirement, though. The point is for portability. If one compiler allows "slop" in the input to Value, and another does not, then clearly you are creating a portability problem. Even though the exact form of the image is already implementation dependent, the requirement to exactly match the output of Image in the input to Value is not implementation dependent, and there seems no reason to encourage implementation dependence in this area. -Tuck **************************************************************** !section RM-A.5.2(40) !subject Float_Random.Value, Discrete_Random.Value !reference RM95-A.5.2(40) !reference 95-5268.a Keith Thompson 95-9-6 !from Robert I. Eachus 95-09-07 !reference as: 95-5271.a Robert I. Eachus 95-9-7>> !discussion > The paragraph in question says > Invoking Value with a string that is not the image of any generator > state raises Constraint_Error. Oo! Ouch, how did I miss that? You certainly want permission to raise Constraint_Error, but there are many good generators where the cost of determining whether or not the generator state is valid is costly. Calling Value with a string not returned by Image is at best implementation dependent, and if the string is invalid, the program should probably be considered erroneous if the generator is used. (The generator may continue to chunk out numbers, but they may not be random. For the generators I use, the checks are easy, but for add with carry and subtract with borrow generators, I don't know of a good test other than analyzing the generator output.) > Is it legal to allow some extra flexibility? For example, suppose > the Image function returns a representation of the state as a string > of hexadecimal digits, with 'A'..'F' in upper case. A string with > 'a'..'f' in lower case, but which is otherwise equivalent to a valid > image, is not strictly speaking "the image of any generator state". > May the Value function nevertheless return a valid state for such a > string, or must it raise Constraint_Error?... The best fix would seem to be to say that the input must have "the form" of an output string from Image, and to say that if the string corresponds to an illegal state, further execution is erroneous. The minimum fix is to say that calling Value with a string not received from the same implementation of Image is pathological. **************************************************************** !section RM-A.5.2(40) !subject Float_Random.Value, Discrete_Random.Value !reference RM95-A.5.2(40) !reference 95-5268.a Keith Thompson 95-09-06 !reference 95-5269.a Tucker Taft 95-9-7 !reference 95-5271.a Robert I. Eachus 95-9-7 !from Keith Thompson 95-09-08 !reference as: 95-5273.a Keith Thompson 95-9-8>> !discussion Tucker Taft said: > The point is for portability. If one compiler allows "slop" in > the input to Value, and another does not, then clearly you are > creating a portability problem. Even though the exact form of the > image is already implementation dependent, the requirement to exactly > match the output of Image in the input to Value is not implementation > dependent, and there seems no reason to encourage implementation dependence > in this area. I don't see how allowing a little "slop" in the input to Value creates any more of a portability problem than already exists. Any program that attempts to build a random state image by any method other than calling the Image function with an existing state is clearly dangerously non-portable, and deserves the infinite sequence of 42's that it's likely to get. The only legitimate use for the Value function, IMHO, is to restore a previous state recorded in the result of the Image function. Based on that, I agree that an implementation that uses a string of hexadecimal digits for an image shouldn't go out of its way to accept both upper and lower case, for example. However, I see little point in requiring an implementation to expend extra (and possibly prohibitive) effort to detect and reject seemingly valid arguments to Value that in fact can never have been produced by the Image function. Image and Value should be relatively simple functions. The Value function shouldn't go out of its way to accept variations (leading and trailing blanks, upper vs. lower case, etc.), but it shouldn't be required to go too far out of its way to detect invalid variations. Such an effort does not benefit the user. As Robert Eachus pointed out: > You certainly want permission to raise Constraint_Error, but there are > many good generators where the cost of determining whether or not the > generator state is valid is costly. The Integer'Image and Integer'Value functions are a possible analogy; Integer'Value certainly accepts many strings that can never be produced by Integer'Image. This analogy is admittedly weak, though, since Integer'Value is intended to work on values from outside the program, while the random Image functions are not. If the language weren't standardized yet, I'd suggest that calling Value with a string other than the result of a previous call to the corresponding Image function in the same implementation is a bounded error. The allowable results are raising Constraint_Error, returning a state which yields a non-random sequence, and returning a state which yields a valid random sequence. I don't know whether this is too radical for a binding interpretation at this late stage. **************************************************************** !section RM-A.5.2(40) !subject Float_Random.Value, Discrete_Random.Value !reference RM95-A.5.2(40) !reference 95-5268.a Keith Thompson 95-09-06 !reference 95-5269.a Tucker Taft 95-9-7 !from Norman Cohen 95-09-08 !reference as: 95-5274.a Norman H. Cohen 95-9-8>> !discussion KST> The paragraph in question says KST> KST> Invoking Value with a string that is not the image of any generator KST> state raises Constraint_Error. KST> KST> Is it legal to allow some extra flexibility? STT> No, though as a pragmatic matter, some flexibility might creep in STT> due to flaws in the Value algorithm. I think Keith asked the wrong question. A.5.2(38) states that an image is "a representation of a state encoded (in an implementation-defined way) as a string". The question should have been, "Is the implementation allowed to define a nondeterministic encoding, as long as the identity Value(Image(S))=S is satisfied?" If that question is answered in the affirmative, as I believe it should be, it provides Keith with all the flexibility he needs, without winking and muttering that a useful "flaw" crept in to his compiler. KST> ...For example, suppose KST> the Image function returns a representation of the state as a string KST> of hexadecimal digits, with 'A'..'F' in upper case. A string with KST> 'a'..'f' in lower case, but which is otherwise equivalent to a valid KST> image, is not strictly speaking "the image of any generator state". Ah, but if the implementation defines the encoding as "a hexadecimal number in which upper case and lower case are considered equivalent", then a string with lowercase hex digits is, strictly speaking, the image (or better, AN image) of some generator state. KST> May the Value function nevertheless return a valid state for such a KST> string, or must it raise Constraint_Error? STT> It must raise Constraint_Error. KST> Alternatively, Image might return a representation of a state as a list KST> of decimal integer values separated by blanks and/or commas (GNAT does KST> this); may Value accept extra or missing blanks, leading zeros, literals KST> in other bases, etc.? STT> No. Suppose the list of numbers is used by the generator as an unordered set. Image strings with the same numbers listed in different orders might arise from different histories, but they should all be viewed as representations of the same state because they induce the same sequence of random numbers. That is, the same state has many valid images. It might be that some particular order for the numbers does not arise from any possible history, and is thus never the result of a call on Image, but Value ought to be allowed to accept it in the same manner as it accepts the other permutations of those numbers. KST> I suppose the issue is how flexibly the phrase "the image of" is to KST> be interpreted. If it's taken to mean exactly a string that can be KST> returned by the Image function, no flexibility is allowed. There seems KST> little point to imposing such a strict requirement, though. I agree. If the implementation-defined semantics of the function can be defined nondeterministically, it should not matter that the actual Image function, as implemented, is one deterministic fulfillment of the nondeterministic specification. STT> The point is for portability. If one compiler allows "slop" in STT> the input to Value, and another does not, then clearly you are STT> creating a portability problem. This is not clear at all, since (as STT observes in the next sentence) the input to Value is already implementation-dependent. STT> Even though the exact form of the STT> image is already implementation dependent, the requirement to exactly STT> match the output of Image in the input to Value is not implementation STT> dependent, and there seems no reason to encourage implementation dependence STT> in this area. The important property to satisfy is Value(Image(S))=S for all S and for all possible values of Image(S). The phrase "for all possible values of Image(S)" means "for any result value that would satisfy the specification of Image", even if Image actually generates some but not all of the strings that would satisfy its specification. Thus the requirement "to exactly match the output of Image in the input to Value" remains intact; we just define what we mean by "the output of Image" more liberally. I see no pragmatic harm resulting from this increased flexibility, and I can think of some scenarios in which the flexibility is useful. **************************************************************** !section RM-A.5.2(40) !subject Float_Random.Value, Discrete_Random.Value !reference RM95-A.5.2(40) !reference 95-5268.a Keith Thompson 95-09-06 !reference 95-5269.a Tucker Taft 95-9-7 !reference 95-5271.a Robert I. Eachus 95-9-7 !reference 95-5273.a Keith Thompson 95-09-08 !from Mark Biggar 95-09-09 !reference as: 95-5280.a Mark A Biggar 95-9-9>> !discussion >Tucker Taft said: >> The point is for portability. If one compiler allows "slop" in >> the input to Value, and another does not, then clearly you are >> creating a portability problem. Even though the exact form of the >> image is already implementation dependent, the requirement to exactly >> match the output of Image in the input to Value is not implementation >> dependent, and there seems no reason to encourage implementation dependence >> in this area. >I don't see how allowing a little "slop" in the input to Value creates >any more of a portability problem than already exists. Any program >that attempts to build a random state image by any method other than >calling the Image function with an existing state is clearly dangerously >non-portable, and deserves the infinite sequence of 42's that it's likely >to get. The only legitimate use for the Value function, IMHO, is to >restore a previous state recorded in the result of the Image function. >Based on that, I agree that an implementation that uses a string of >hexadecimal digits for an image shouldn't go out of its way to accept >both upper and lower case, for example. >However, I see little point in requiring an implementation to expend >extra (and possibly prohibitive) effort to detect and reject seemingly >valid arguments to Value that in fact can never have been produced by the >Image function. Image and Value should be relatively simple functions. >The Value function shouldn't go out of its way to accept variations >(leading and trailing blanks, upper vs. lower case, etc.), but it >shouldn't be required to go too far out of its way to detect invalid >variations. Such an effort does not benefit the user. As Robert Eachus >pointed out: Just to throw some more oil on the fire. Note that there are other IMAGE VALUE pairs that allow VALUE to except strings that will never be produced by IMAGE. E.G. FLOAT'IMAGE(O.1) will never produce the string ".1", but that's a legal input to FLOAT'VALUE. Again INTEGER'VALUE("2#1010#") is legal but INTEGER'IMAGE(10) will never equal "2#1010#". As other pairs are already allowed to be "sloppy" in just the way asked for the Random generators, I think it should be allows for them as well. -- Mark Biggar mab@wdl.loral.com **************************************************************** !section A.5.2(40) !subject Float_Random.Value, Discrete_Random.Value !reference RM95-A.5.2(40) !reference 95-5268.a Keith Thompson 95-09-07 !reference 95-5269.a Tucker Taft 95-09-07 !reference 95-5271.a Robert I. Eachus 95-09-07 !reference 95-5273.a Keith Thompson 95-09-08 !reference 95-5274.a Norman H. Cohen 95-09-08 !reference 95-5280.a Mark A Biggar 95-09-09 !reference AI95-00089/00 !from Robert I. Eachus 96-01-17 !reference 96-5425.a Robert I. Eachus 96-1-17>> !discussion I had thought that my earlier message on this topic would have been convincing, but the AI writeup in the database is as a confirmation. I've been trying to reimplement my RNG in Ada 95 and in conformance to this draft AI and find it incredibly painful, but for all the wrong reasons. The draft responce says: "The paragraph in question clearly states that no extra flexibility is allowed. The Value function raises Constraint_Error if the given string is not a string that could have been returned by Image." The upper/lower case and spacing issues are not even a trivial problem. Use the state read in to create a generator, then take its Image. If the two don't compare equal, raise Constraint_Error. I think it is foolish to require this particular check, but it is not something I care seriously about. But the fact that not all possible generator states can be reached from normal seeds is a major hassle. In my case, the only test for whether or not this is one of those states requires computing X to the N mod P for large N--on the order of 64 bits. Using the built-in exponentiation is unlikely to produce acceptable performance, so I have to expand the power series by hand. All this to find out if U1 and U2 are the "right" values, or values with the same squares mod P and mod Q--and which therefore generate the exact same sequence. (In every case there is exactly one right and one wrong value, and no easier way to determine whether or not the right one was supplied without the exponentiation.) In the case of Add with Carry and Subtract with Borrow generators, the situation is worse. By writing an iteration count out, as well as the starting seed values, I can limit the time required to raise Constraint_Error. (AWC and SWB generators have very long periods.) But to validate the numbers efficiently requires implementing multi-precision arithmetic, and one of the advantages of AWC and SWB generators is that you don't need multiprecision arithmetic. If you are using a linear congruential generator, the situation is much simpler--if you know that the generator is full period. But a generator which allowed multiple periods would fall into the same problems as the AWC case. There is no easy way to test a modulus to see if it leads to a full-period generator. There is another workaround, and this one is definitely one we don't want. I can decide to use the string as read as the generator state with no checking, and just remember the string in case the next call on the generator is a call of Image. Now any string read by Value is one that "could have been returned by Image." I suggest a new writeup which confirms that the INTENT is that implementations validate the strings passed to Value, but recognizing that calls to Value may set the generator to a state which cannot be reached in any other way. This is not a bad thing. When developing and testing generators I normally keep more of the information in the state and less in the implementation, to allow testing different versions of an algorithm. For example, an LCG implementation might use 16807 as the multiplier and 2**31-1 as the modulus by default, but allow these to be set to other values using Value. Robert I. Eachus with Standard_Disclaimer; use Standard_Disclaimer; function Message (Text: in Clever_Ideas) return Better_Ideas is... ****************************************************************