[plt-scheme] A curious evaluation order (?) bug

From: Chongkai Zhu (czhu at cs.utah.edu)
Date: Sun Dec 30 17:04:51 EST 2007

Doug Williams wrote:
> On Dec 30, 2007 12:40 PM, Chongkai Zhu <czhu at cs.utah.edu 
> <mailto:czhu at cs.utah.edu>> wrote:
>     >Doug Williams wrote:
>     >> And while we're on the subject, there is another problem with
>     the new
>     >> SRFI 27 implementation I've noticed.  The randomization of
>     >> (random-source-pseudo-randomize! s i j) and
>     >> (random-source-pseudo-randomize! s j i) will always be the
>     same.  The
>     >> code uses equal-hash-code of i and j to come up with a seed and
>     that
>     >> function is symmetric wrt i and j.
>     >>
>     >
>     > DrScheme, version 372-svn12nov2007 [3m]
>     >
>     >(equal-hash-code (list 1 2))
>     >(equal-hash-code (list 2 1))
>     >
>     >(equal-hash-code (list 1 0))
>     >(equal-hash-code (list 0 1))
>     >
>     >=>
>     >
>     >94564159
>     >95385186
>     >94562141
>     >93284415
> My bad on that one.  Sorry.  But, I still don't like compressing the 
> repeatable random space - there are collisions there.

Yes, there are collisions. But the space is still big, so collisions 
will be very rare.

>     >> I think we still need to do some thinking on the
>     implementation.  I
>     >> think we need to either expose the SRFI 27 interface from PLT
>     Scheme
>     >> (and implement the old interface on top of that) or separate them
>     >> completely and go back to the old SRFI 27 implementation.  [There
>     >> would also be some middle ground.  But, I don't think there is
>     >> currently enough of the internal implementation exposed to
>     adequately
>     >> implement SRFI 27 - there are too many kludges in that code now.]
>     >>
>     >The current SRFI 27 implement does the following:
>     >
>     >1. to meet SRFI 27;
>     >2. to be as efficient as possible (i.e., using PLT's random
>     procedures
>     >as much as possible).
>     >I did once tried to connect SRFI 27's default-random-source and PLT's
>     >current-pseudo-random-generator, but that doesn't goes very well,
>     so it
>     >comes the current implement: they are not connected at all. In that
>     >sense, SRFI 27 and PLT's random procedures are completely
>     separated. I
>     >can't see what you are suggestion here.
> I'm not sure what the 'right' answer is, I'm just trying to figure out 
> the best way to keep users from being confused.  [Noel is by no means 
> a novice user and he was confused.]  The best options seem to be at 
> opposite ends of the spectrum.  Either make them the same (and 
> therefore there is nothing to confuse) or make them so different that 
> you lessen the confusion.
> I would rather lean toward making them the same:
> 1) Make both random sources have the same 'type' - i.e. 
> make-pseudo-random-generator from PLT Scheme and make-random-source 
> from SRFI 27 should return objects that can be used in either context 
> because they are the same implementation.
> 2) Make PLT Scheme random routines (like random and random-seed) be 
> able to accept a random-source as an argument.  It seems wasteful to 
> continually parameterize current-pseudo-random-stream to fake passing 
> random (or random-seed) an argument, which is one of the main kludges 
> I was referring to.
> 3) Implement a SRFI 27 pseudo randomize in PLT Scheme (because it is 
> more robust than a single seed) and then implement random-seed in 
> terms of it.  For example, we might define (random-seed s k) as being 
> equivalent to (random-source-pseudo-randomize! s k 0).
> I think that would give us an interface in PLT Scheme that is 
> compatible with (but an extension of) the current implementation and 
> give what is needed to make the SRFI 27 implementation better.
> I don't think there is a good way top reconcile the differences 
> between the default-random-source behavior of SRFI 27 and the 
> current-pseudo-random-generator in PLT Scheme.  SRFI 27 did not 
> anticipate as rich as environment - i.e., with parameters, threads, 
> etc - as PLT Scheme.  Leave them both in as they are - and avoid the 
> temptation to make default-random-stream be a parameter, it's just a 
> global variable.  In essence this is what I did in the science 
> collection by adding a current-random-source parameter.  [It is doing 
> the same for SRFI 27 as current-pseudo-random-generator does for PLT 
> Scheme.]
> The other extreme is to just put the old SRFI 27 implementation back 
> and just say they're different.
> My personal opinion is that the current PLT Scheme random source 
> interface (not the underlying implementation) is inadequate for the 
> work I want to use it for - simulations, in my case.  But, it is more 
> efficient than the old SRFI 27 implementation.  The SRFI 27 interface 
> is suitable for the work - in particular, I can easily specify 
> repeatable, independent random variables.  However, it's 
> implementation was not as efficient as the PLT Scheme implementation.  
> And, because the PLT Scheme implementation doesn't expose enough of 
> the underlying implementation to make a straightforward implementation 
> of SRFI 27 on top of it, I don't have the same confidence in the 
> interface code as I do in either the underlying PLT implementation or 
> the old SRFI implementation.  [For example, the procedure returned by 
> (random-source-make-integers n) may call the underlying PLT Scheme 
> random routine once or twice, depending on the value of n.  Some of 
> those manipulations seem innocuous, but can bias the macro-level 
> behavior of the random sources.]
> In the short term, the best thing for the users of the science 
> collection to remember is that there is no inherent connection between 
> the SRFI 27 random routines (and the science collection distributions, 
> etc) and the built in PLT scheme ones.

The current PLT's SRFI 27 implementation provides all features the 
reference implementation (or, the old SRFI implementation as Doug calls 
it) provides, while being more efficient. Here's the reasons:

1. They both meet the SRFI 27 interface;
2. "default-random-source" in both have nothing to do with PLT's 
current-pseudo-random-generator (or any parameter in PLT).

So there is no reason to bring the old SRFI 27 implementation back.

You SHOULD have the same confidence in the interface code as you do in 
either the underlying PLT implementation or the old SRFI implementation. 
You are right that the procedure returned by 
(random-source-make-integers s) may call the underlying PLT Scheme 
random routine more than once, depending on the value of its input. But 
that's fine (and necessary). I don't think it will bias the macro-level 
behavior of the random sources.


Posted on the users mailing list.