Dconf 2015 talks...

[Joseph Rushton Wakeling via Digitalmars-d]

On Monday, 25 January 2016 at 21:30:47 UTC, Era Scarecrow wrote:
>  So in short, the RNG shouldn't be a range at all. Of course it 
> could be a struct (for sanity and other reasons), but not a 
> range.
>
>  I wonder then, assuming we remove RNG from being a range, the 
> a RNG could give out a delegate of it's current data, and that 
> delegate get passed to a range-like wrapper? Or maybe the RNG 
> returns a Voldemort range that referrs to the original RNG 
> which isn't a range anymore... Actually that sounds promising. 
> Aliasing could deal with it automatically converting/creating 
> the range.

Well, an idea that was suggested to me at DConf (by several 
people; thanks in particular to Steve S. and to DiceBot!) was 
indeed to separate RNG state from the range interface, and to 
disable copy-by-value for the state data structure.

One option would be to implement the basic RNG data structor à la 
C++, as a functor: so it'd be something like:

     struct SomeRNG(UIntType, ...)
     {
       private:
         // the RNG state variables

       public:
         UIntType opCall()
         {
             // returns a random variate
         }
     }

... and again, you'd disable copy-by-value for this entity.  I 
had some fun a while ago playing with this and the appropriate 
technique to wrap it into a range (it's not as trivial as you 
think, because you need to use some tricks to ensure truly lazy 
evaluation of the range, where D ranges typically evaluate the 
first element eagerly).

Where I ran into trouble was considering how to extend this 
approach in a viable way to stuff like randomSample, i.e. the 
stuff which wraps randomness, which also needs to ensure its 
internal state is never copied by value, and yet which needs 
(ideally) to fit nicely into a UFCS chain of ranges:

     someInput.filter!(WHATEVER).randomSample(n, 
rng).map!(...).writeln;

I suppose it might be possible to implement a functor-based 
approach for this, that could be wrapped in a range, but it feels 
nasty for something which really ought to fit more naturally into 
the range syntax: a random sample is just an algorithm (similar 
to those in std.algorithm), but one whose elements need to be 
truly lazily evaluated and whose values are not deterministic but 
depend on a source of randomness.

The entire complication comes out of the fact that in order to 
play nice in a statistical sense, you need the RandomSample range 
to be a reference type, but in order to play nice with the kind 
of in-the-middle-of-the-inner-loop use above, you need it to be 
cheap and quick to instantiate and destroy (so classes and heap 
allocation are a problem).

Basically, what you probably want is for RandomSample to be a 
struct, but with a reference-type internal state that is 
nevertheless allocated on the stack and that is cheap to create 
and let go of when you're done with it.