On 5/31/16 10:46 AM, Dicebot wrote:
On Monday, 30 May 2016 at 12:53:07 UTC, Steven Schveighoffer wrote:
On 5/30/16 5:35 AM, Dicebot wrote:
On Sunday, 29 May 2016 at 17:25:47 UTC, Steven Schveighoffer wrote:
What problems are solvable only by not caching the front element? I
can't think of any.
As far as I know, currently it is done mostly for performance reasons -
if result is fitting in the register there is no need to allocate stack
space for the cache, or something like that. One of most annoying
examples is map which calls lambda on each `front` call :
https://github.com/dlang/phobos/blob/master/std/algorithm/iteration.d#L587-L590
Maybe my understanding of your post is incorrect. You said "It is
impossible to correctly define input range without caching front which
may not be always possible and may have negative performance impact."
I'm trying to figure out which cases caching makes the solution
impossible.
There are two separate points here:
1) Current definition of input range (most importantly, the fact `front`
has to be @property-like) implies `front` to always return the same
result until `popFront` is called.
Regardless of property-like or not, this should be the case. Otherwise,
popFront makes no sense.
2) For ranges that call predicates on elements to evaluate next element
this can only be achieved by caching - predicates are never required to
be pure.
Or, by not returning different things from your predicate.
This is like saying RedBlackTree is broken when I give it a predicate of
"a == b".
3) But caching is sub-optimal performance wise and thus bunch of Phobos
algorithms violate `front` consistency / cheapness expectation
evaluating predicates each time it is called (liked map).
I don't think anything defensively caches front in case the next call to
front is different, unless that's specifically the reason for the range.
I don't really care about concept of transient ranges, it is the fact
there is no guarantee of front stability for plain input ranges which
worries me.
But this is inherent in languages which support mutable data. If you
want data that doesn't change, require copied/unique data, or
immutable data.
This has nothing to do with mutability, look at this totally broken
example:
import std.random;
import std.algorithm;
import std.stdio;
import std.range;
void main ( )
{
auto range = only(0).map!(x => uniform(0, 10));
writeln(range.front);
writeln(range.front);
writeln(range.front);
}
I think we should be aware that the range API doesn't prevent bugs of
all kinds. There's only so much analysis the compiler can do.
-Steve
