Version 1.4 of ais/ai-00089.txt

Unformatted version of ais/ai-00089.txt version 1.4
Other versions for file ais/ai-00089.txt

!standard RM-A.5.2 (40)          00-04-11 AI95-00089/06
!class binding interpretation 96-09-05
!status Corrigendum 2000 99-05-25
!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
!qualifier Clarification
!subject Float_Random.Value, Discrete_Random.Value
!summary
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
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
(See summary.)
!wording
(See corrigendum.)
!discussion
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.
!corrigendum A.05.02(40)
Replace the paragraph:
Invoking Value with a string that is not the image of any generator state raises Constraint_Error.
by:
Bounded (Run-Time) Errors

It is a bounded error to invoke Value with a string that is not the image of any generator state. 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 implementation requirements of this clause.
!ACATS test
Existing ACATS test CXA5012 covers this case.
!appendix

!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...

****************************************************************

Questions? Ask the ACAA Technical Agent