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

From: Doug Williams (m.douglas.williams at gmail.com)
Date: Sun Dec 30 12:41:12 EST 2007

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.

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

Doug

On Dec 30, 2007 10:12 AM, Doug Williams <m.douglas.williams at gmail.com>
wrote:

> I sent an answer to Noel directly, but will post an answer for everyone
> here, too.  I believe Noel expected the code sequence '(random-seed 1234)
> (random-discrete discrete)' to always return the same value - because the
> random source state should be the same.  Unfortunately, it isn't because the
> science collection uses a different default random source than the PLT
> Scheme one.
>
> The science collection random source and distribution routines are built
> on top of SRFI 27.  At the time the science collection was implemented, the
> PLT Scheme random source routines were very naive and, therefore, the SRFI
> 27 implementation was used.  Because of restrictions within SRFI 27
> (including "Note that an assignment to default-random-source does not change
> random or random-real; it is also strongly recommended not to assign a new
> value."), a parameter, current-random-source, was created (in the science
> collection) to mirror the current-pseudo-random-generator in PLT Scheme.
>
> So, back to the '(random-seed 1234) (random-discrete discrete)' sequence.
> The (random-seed 1234) call sets the seed in the PLT Scheme default random
> stream (i.e., current-pseudo-random-generator).  The (random-discrete
> discrete) call is using the current-random-source parameter (from the
> science collection).  So, they are using completely different random
> sources.
>
> Another problem is the difference in philosophy between the PLT Scheme
> random source interface and that of SRFI 27.  For 'seeding' a random source,
> the PLT Scheme philosophy has a single random seed (set by random-seed) [and
> maps directly to the original internal naive implenentation] and SRFI uses a
> 2-dimensional random-source-randomize! described as "Changes the state of
> the random source s into the initial state of the (i, j)-th independent
> random source, where i and j are non-negative integers. This procedure
> provides a mechanism to obtain a large number of independent random sources
> (usually all derived from the same backbone generator), indexed by two
> integers. In contrast to random-source-randomize!, this procedure is
> entirely deterministic."
>
> In the 371 -> 372 transition (I believe at 371.1), the PLT Scheme random
> source routine was changed to use the same algorithm as SRFI 27 and SRFI 27
> itself was reimplemented in terms of the new PLT Scheme implementation.
> There was some breakage to the science collection during that transition,
> but I think it's all been fixed.  [You can look at the change log on PLaneT
> for details.]  However, the random sources are different struct types
> internally and cannot be used interchangeably.  So, we still have the same
> general problem of two different random source implementations - the science
> collection happens to use and extend the SRFI 27 one.
>
> I'm not sure of the best way to eliminate that confusion in the long term
> (other than through documentation), but am open to suggestions.
>
> Doug
>
> On Dec 29, 2007 9:26 AM, Noel Welsh < noelwelsh at gmail.com> wrote:
>
> > Here's something curious.  I have code that samples from a discrete
> > distribution, and it does not behave as I would expect.  The code is
> > thus:
> >
> > (define (sample-cluster-mixture state discrete)
> >  (define clusters (state-clusters state))
> >  (define i (random-discrete discrete))
> >  (printf "SAMPLE CLUSTER MIXTURE ~a\n" i)
> >  (printf "~a ~a\n" (discrete-pdf discrete 0)
> >          (discrete-pdf discrete 1))
> >  (random-seed 1234)
> >  ;(display (random-discrete discrete))
> >  (if (zero? i)
> >      (sample-new-cluster state)
> >      (vector-ref clusters i)))
> >
> > The important thing here is the value of i, which is printed out.
> >
> > I call (random-seed 1234) and run it, and the output is this:
> >
> > SAMPLE CLUSTER MIXTURE 1
> > 0.41176470588235303 0.588235294117647
> > 0
> >
> > So i is 1
> >
> > I uncomment the display line and run it, and get:
> >
> > SAMPLE CLUSTER MIXTURE 0
> > 0.41176470588235303 0.588235294117647
> > 0
> >
> > So now i is 0
> >
> > Note that i is evaluated before the call to display.  All I can think
> > it that this is an optimiser bug, reordering expressions in some
> > illegal way.  I'm using  v371.4 [3m].  I've just svn up'ed and I'll
> > try v4 and 372 to see if there is any difference.  If not I'll try to
> > narrow the bug down.
> >
> > Consider this a preliminary report only.  I was so surprised by this
> > (having spent an few hours debugging) I had to let the world know...
> >
> > N.
> > _________________________________________________
> >  For list-related administrative tasks:
> >   http://list.cs.brown.edu/mailman/listinfo/plt-scheme
> >
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.racket-lang.org/users/archive/attachments/20071230/c927e41b/attachment.html>

Posted on the users mailing list.