Another day in the ordeal of cartesianProduct

[Peter Alexander]

On Monday, 29 October 2012 at 15:48:11 UTC, Andrei Alexandrescu 
wrote:
> On 10/28/12 8:28 AM, Peter Alexander wrote:
>> For example, here's what happened with bug 8900 mentioned in 
>> the OP:
>>
>> std.range.zip creates a Zip object, which has a Tuple member. 
>> Tuple has
>> a toString function, which calls formatElement, which calls 
>> formatValue,
>> which calls formatRange, which (when there's a range of 
>> characters) has
>> a code path for right-aligning the range. To right-align the 
>> range it
>> needs to call walkLength.
>>
>> The problem arises when you zip an infinite range of 
>> characters e.g.
>> repeat('a').
>
> This proves nothing at all. So this has to do with invoking 
> walkLength against an infinite range. At the time I wrote 
> walkLength, infinite ranges were an experimental notion that I 
> was ready to remove if there wasn't enough practical support 
> for it. So I didn't even think of the connection, which means 
> the restriction wouldn't have likely made it into the 
> definition of walkLength regardless of the formalism used.

You're misunderstanding. walkLength used to allow infinite 
ranges. Recently, a commit added a constraint to walkLength to 
disallow infinite ranges. After this commit, all the unit tests 
still passed, but at least one bug was introduced (bug 8900).

That's the problem: a change occurred that introduced a bug, but 
the type system failed to catch it before the change was 
committed. Something like typeclasses would have caught the bug 
before commit and without unit tests.


> The connection is obvious and is independent qualitatively of 
> other cases of "if you change A and B uses it, B may change in 
> behavior too". It's a pattern old as dust in programming.
>
> Anyway, I'm not sure whether this is clear as day: expressing 
> constraints as Booleans or "C++ concepts" style or Gangnam 
> style doesn't influence this case in the least.

If I change A and B uses it, I expect B to give an error or at 
least a warning at compile time where possible. This doesn't 
happen. With template constraints, you don't get an error until 
you try to instantiate the template. This is too late in my 
opinion.

I would like this to give an error:

void foo(R)(R r) if (isForwardRange!R) { r.popBack(); }

It doesn't, not until you try to use it at least, and even then 
it only gives you an error if you try it with a non-bidirectional 
forward range. If this did give an error, bug 8900 (any many 
others) would never have happened.

The problem with constraints vs. something like typeclasses or 
C++ concepts is that constraint predicates are not possible to 
enforce pre-instantiation. They have too much freedom of 
expression.


>> Working well in this case would look like this:
>>
>> - The person that put together pull request 880 would add the 
>> template
>> constraint to walkLength.
>> - On the next compile he would get this error: "formatRange 
>> potentially
>> calls walkLength with an infinite range." (or something along 
>> those lines).
>> - The person fixes formatRange, and all is well.
>>
>> No need for unit tests, it's all caught as soon as possible 
>> without need
>> for instantiation.
>
> But this works today and has nothing to do with "retrofitting 
> structure to templates". Nothing. Nothing.

It doesn't work today.

This isn't a fabricated example. This happened. walkLength 
changed its constraint, everything still compiled, and all the 
unit tests passed. There was no error, no hint that things were 
broken, nothing. Problems only started to arise when the poor OP 
tried to implement cartesianProduct.

This should never have happened. Typeclasses or C++ concepts 
wouldn't have allowed it to happen. This is the kind of structure 
that templates need.