Another day in the ordeal of cartesianProduct

[Andrei Alexandrescu]

On 10/29/12 12:21 PM, Peter Alexander wrote:
> 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).

I thought I understood the matter rather well.

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

Yes, but what gets ignored here is that typeclasses have a large 
cognitive cost to everyone involved. I think typeclasses generally don't 
pull their weight. Besides I think template constraints are more 
powerful because they operate on arbitrary Boolean expressions instead 
of types.

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

That's also at compile time, just a tad later.

> This is too late in my opinion.

I think there's a marked difference between compile-time and run-time. 
Instantiation time does not make a big enough difference to bring a big 
gun in the mix.

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

So them a unittest with a minimal mock forward range should be created. 
I understand your concern, but please understand that typeclasses are 
too big a weight for what they do.

> If this did give an error, bug 8900 (any many others) would never have
> happened.

How many others? (Honest question.)

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

Freedom of expression is also a strength. (The problem with C++ concepts 
is that they almost sunk C++.)

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

It's just blown out of proportion.

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

We will not add C++ concepts or typeclasses to D.


Andrei