On Thursday, 24 November 2016 at 12:02:22 UTC, John Colvin wrote:
> Because it's correct. If a.length is larger than int.max then cast(int)a.length will half the time be negative and therefore a simple rightshift would not be equivalent to division by 2.

It can't be possibly correct when a.length is larger than int.max because it doesn't recover information lost in a narrowing conversion.

On Thursday, 24 November 2016 at 13:45:40 UTC, Jonathan M Davis wrote:
> How so? Because someone might call range.front again without bothering to call popFront?

That's what everything in std.algorithm does.

On Thursday, November 24, 2016 13:54:50 Kagamin via Digitalmars-d wrote:
> On Thursday, 24 November 2016 at 13:45:40 UTC, Jonathan M Davis
>
> wrote:
> > How so? Because someone might call range.front again without bothering to call popFront?
>
> That's what everything in std.algorithm does.

Then call popFront or drop before passing it along if you're paranoid about it. If it's a serious concern that this be fixed in general, then the obvious fix to that would be to make it so that rndGen() just called popFront before returning it. Heck, if rndGen() were guaranteed to call popFront when it was called rather than simply returning the range, then you could just do rndGen().front whenever you wanted the equivalent of rand(), making it trivial to use rndGen() both for cases where you wanted a single number and for cases where you wanted a range of them - and without worrying about front being stale.

- Jonathan M Davis

On Thursday, 24 November 2016 at 13:45:40 UTC, Jonathan M Davis wrote:
> Alternatively, you could just do rndGen().take(1).front, and as long as rndGen() gives you a reference type, it works just fine. Unfortunately, std.random did not use reference types for its ranges. _That_ is the big mistake of std.random and the main item that needs to be fixed. There are some other subtleties (e.g. it's useful to be able to save the state of a random number generating range, but you don't necessarily really want it to be a forward range), but those are minor in comparison to the mistake of std.random using value types rather than reference types for ranges.
>
> - Jonathan M Davis

The fix is opCall syntax. Reference types are classes, which would not work without linking DRuntime and Phobos (BetterC). Refcounting is to slow to implement for users.
Note, that Engines is only backend RNGs. There are also nonuniform distributions (WIP). See the example of users code: https://forum.dlang.org/post/nyvtoejvmsaolzaqyche@forum.dlang.org .

It is very difficult to implement both user random variable and Engine using Range API. Note, that code should work without DRuntime and should be simple (the example is user code).

Ilya

On Thursday, 24 November 2016 at 16:09:23 UTC, Ilya Yaroshenko wrote:
> On Thursday, 24 November 2016 at 13:45:40 UTC, Jonathan M Davis wrote:
>> Alternatively, you could just do rndGen().take(1).front, and as long as rndGen() gives you a reference type, it works just fine. Unfortunately, std.random did not use reference types for its ranges. _That_ is the big mistake of std.random and the main item that needs to be fixed. There are some other subtleties (e.g. it's useful to be able to save the state of a random number generating range, but you don't necessarily really want it to be a forward range), but those are minor in comparison to the mistake of std.random using value types rather than reference types for ranges.
>>
>> - Jonathan M Davis
>
> The fix is opCall syntax. Reference types are classes, which would not work without linking DRuntime and Phobos (BetterC).

If druntime was initialised by default using __attribute__((constructor)) for static and linker .init for shared libraries, would that be good enough for you*? I feel like you're limiting your design choices because of a relatively small and simple implementation shortcoming.

* remember, we don't currently guarantee ABI compatibility between compiler versions even if you don't use druntime/phobos.

On Thursday, 24 November 2016 at 17:04:43 UTC, John Colvin wrote:
>
> If druntime was initialised by default using __attribute__((constructor)) for static and linker .init for shared libraries, would that be good enough for you*? I feel like you're limiting your design choices because of a relatively small and simple implementation shortcoming.
>
> * remember, we don't currently guarantee ABI compatibility between compiler versions even if you don't use druntime/phobos.

No, it should work without DRuntime. Nicholas wrote that it will work on GPU using dcompute :-) BetterC is the goal for the future Mir-Phobos, hehe

On 24.11.2016 14:50, Kagamin wrote:
> On Thursday, 24 November 2016 at 12:02:22 UTC, John Colvin wrote:
>> Because it's correct. If a.length is larger than int.max then
>> cast(int)a.length will half the time be negative and therefore a
>> simple rightshift would not be equivalent to division by 2.
>
> It can't be possibly correct when a.length is larger than int.max
> because it doesn't recover information lost in a narrowing conversion.

The code does not specify that this information should be recovered. Why is this the compiler's problem?

On Thursday, 24 November 2016 at 08:36:41 UTC, Andrea Fontana wrote:
> On Wednesday, 23 November 2016 at 17:31:58 UTC, Kagamin wrote:
>> On Wednesday, 23 November 2016 at 01:28:11 UTC, Andrei Alexandrescu wrote:
>>> Interesting. Could you please add a couple of links about that? -- Andrei
>>
>> http://xoroshiro.di.unimi.it/
>
> Very short public domain implementation:
> http://xoroshiro.di.unimi.it/xoroshiro128plus.c

Implementation in D, written during DConf 2016 ;-)
https://github.com/WebDrake/dxorshift

On Wednesday, 23 November 2016 at 21:19:51 UTC, Jonathan M Davis wrote:
> It's quite feasible if you don't calculate front until it's called or popFront is called, and then you cache the result so that subsequent calls to front prior to the call to popFront return the same result, but it creates additional overhead, because then every call to front and popFront has to check whether the value has been calculated yet. And if every range in the chain of ranges has to do that, then that additional overhead is going to add up.

Yes, indeed.  I actually came up with a general purpose solution for that a while back via template mixin (although the version in the post linked to is not the final version: I updated it to use HaraldZealot's suggestion of making the frontImplementation and popFrontImplementation the template parameters):
https://forum.dlang.org/post/mailman.263.1439926667.13986.digitalmars-d@puremagic.com

> In general, it's just cleaner to either calculate front on every call to front (which doesn't make sense in the case of random number generators) or to calculate the first front upon construction and be done with it.

In some ways I think it's cleaner to not privilege the first front value and go for "true" laziness for all front values -- particularly when dealing with stuff like RandomSample.

The downside is that `.front` becomes non-const.  Sometimes I wonder whether it wouldn't have been better to require that `popFront()` be called before even the first call to `.front`, and place the onus on `popFront()` to handle any special-casing of the first `.front` value.

> And I think that the general consensus has been that calculating front in the constructor and popFront and caching works better than calculating it on every call to front, but that doesn't always work (e.g. map), and that caching does cause issues occasionally.

The case I always think of is: what if your input range is designed to correspond to sensor observations made at a particular time?  This is a case where cacheing the first value on construction is very problematic.

For RNGs it's really not such a big deal so long as successive variates are independent, but for random algorithms I think the laziness matters, since their popFront is essentially IO-dependent (in the Haskell-style sense that randomness is IO).

On Friday, November 25, 2016 08:32:07 Joseph Rushton Wakeling via Digitalmars-d wrote:
> On Wednesday, 23 November 2016 at 21:19:51 UTC, Jonathan M Davis
>
> wrote:
> > It's quite feasible if you don't calculate front until it's called or popFront is called, and then you cache the result so that subsequent calls to front prior to the call to popFront return the same result, but it creates additional overhead, because then every call to front and popFront has to check whether the value has been calculated yet. And if every range in the chain of ranges has to do that, then that additional overhead is going to add up.
>
> Yes, indeed.  I actually came up with a general purpose solution
> for that a while back via template mixin (although the version in
> the post linked to is not the final version: I updated it to use
> HaraldZealot's suggestion of making the frontImplementation and
> popFrontImplementation the template parameters):
> https://forum.dlang.org/post/mailman.263.1439926667.13986.digitalmars-d@pu
> remagic.com
> > In general, it's just cleaner to either calculate front on every call to front (which doesn't make sense in the case of random number generators) or to calculate the first front upon construction and be done with it.
>
> In some ways I think it's cleaner to not privilege the first front value and go for "true" laziness for all front values -- particularly when dealing with stuff like RandomSample.

It's much messier from an implementation standpoint. If the constructor checks for empty and caches front if the range it was given was non-empty, then every call to front can just return front, and every call to popFront can just pop the element off and do whatever it does to turn the front from the wrapped range into the front of this range and then cache it. If the constructor doesn't do that work, then every call to front and every call to popFront have to check whether they're the first time that either has been called and _then_ they end up doing all of the same work anyway. So, there's more code, and it's less efficient. And if every range in the chain does that, then you're getting a lot of extra checks just to determine whether it's the first time that front or popFront is being called. Now, if there's never any caching of the front value, and front always calculates it, then that might actually be more efficient if front is only ever called once per element, because you don't get the cost of copying the element to cache it, but if front gets called multiple times (which happens fairly often, I think), then the cost is definitely greater.

You're never going to be able to rely on a fully lazy front anyway unless we specified it as part of the range API that all ranges work that way, and as it stands, very few ranges do.

> The downside is that `.front` becomes non-const.

Well, realistically, as it stands, ranges are utterly useless with const anyway. We'd have to have a standard mechanism for getting a tail-const copy of a range from a const or immutable range, and we don't.

> Sometimes I
> wonder whether it wouldn't have been better to require that
> `popFront()` be called before even the first call to `.front`,
> and place the onus on `popFront()` to handle any special-casing
> of the first `.front` value.

That would be terrible with chaining ranges. It also would be _very_ error-prone. It's also heading into two-phase initialization territory, which is almost always a bad idea.

> > And I think that the general consensus has been that calculating front in the constructor and popFront and caching works better than calculating it on every call to front, but that doesn't always work (e.g. map), and that caching does cause issues occasionally.
>
> The case I always think of is: what if your input range is designed to correspond to sensor observations made at a particular time?  This is a case where cacheing the first value on construction is very problematic.
>
> For RNGs it's really not such a big deal so long as successive variates are independent, but for random algorithms I think the laziness matters, since their popFront is essentially IO-dependent (in the Haskell-style sense that randomness is IO).

Honestly, I don't think that it really works to have a range where the value of its elements depend on when you call front or popFront. The API lets you do it, but you're going to run into plenty of problems if you do unless you don't care about the frequency at which the values are generated. Part of the problem here is that ranges and the algorithms that use them are really designed with arrays in mind. A non-random-access range reduces those capabilities, and a basic input range doesn't actually require that the elements be reproducible aside from multiple calls to front giving the same result, but it's still the case that it's pretty much assumed that a range is a fixed set of values, and pretty much nothing is concerned with how fast front or popFront is called aside for efficiency concerns. So, if someone has a range that calculates a value when front or popFront is called, and that value depends on when the function is called, I think that they're just going to have to deal with the consequences of that. It's already pretty problematic when you have a range that's a basic input range rather than a forward range.

Another thing to consider here is that those sorts of concerns really only apply to basic input ranges. As soon as you have a forward range, the values of the elements need to be completely predictable - or at least completely reproducible - meaning that aside from caching a potentially infinite number of elements to guarantee that save works, nothing that's doing something like grabbing changing values from a sensor is going to be anything but a basic input range. So, maybe we should do something special with regards to basic input ranges and how they're treated in order to better deal with cases like that, but if we went that route, then we pretty much couldn't treat them like forward ranges without save anymore. In many cases, we'd have to have separate implementations that avoided things like caching, and that would become problematic fast.

I think that there always going to be cases where certain things have some funky corner cases with ranges - especially the further that they get from being dynamic arrays. We probably need to do a better job of formalizing some of this stuff to better avoid some of those corner cases, but I think that we're always going to be able to find something that we can define as a range that works in many cases but starts doing weird things if we use it on a large enough range of algorithms.

- Jonathan M Davis