Does D have too many features?

[Alex Rønne Petersen]

On 01-05-2012 19:09, Jonathan M Davis wrote:
> On Tuesday, May 01, 2012 16:31:25 Alex Rønne Petersen wrote:
>> 1) So because some people might use a feature incorrectly due to lack of
>> knowledge in algorithms and data structures, we should cripple the language?
>
> If in is not restricted to a particular level Big-O complexity, then you
> cannot safely use it in generic code. That's why all of the functions in
> std.container give their Big-O complexity.

I don't think 'in' is actually used in any generic code (other than code 
specifically written for AAs, in which it *does* have a specific 
complexity in any case).

I know I wouldn't use 'in' in truly generic code in any case, exactly 
because it has no defined complexity (even today; it's overloadable just 
like most other binary operators).

>
> In C++ [] is supposed to be O(log n) at worst. I would expect it to be the
> same in D, and since in is doing essentially the same operation, I would
> expect it to have the same Big-O complexity.

This is a good point, but not one I would subscribe to; it only holds 
true if you consider 'in' to be an operation purely limited to AAs. But 
this is already not the case given that it can be overloaded. So, I 
don't think that it having different complexity for arrays is a big deal.

Personally, I consider 'in' to be syntax sugar for the language user. To 
me, it does not seem like a feature that a library of generic algorithms 
should be using at all.

>
> No, nothing is stopping a programmer from giving it horrible complexity, but
> the standard library and language should _definitely_ stick to O(log n) worst
> case for in and []. It would be a disaster for generic algorithms if in worked
> on normal arrays, because it would not be possible to maintain the required
> Big-O complexity.

I agree that any overload of [] and 'in' that Phobos does should stick 
to that constraint when possible (I say when possible, because sometimes 
innovative uses of these operators can't stick to this rather strict and 
mundane constraint; consider for example interaction with a database or 
what do I know...).

But again, I don't think 'in' is something a generic algorithm should be 
using. We have the functions in std.algorithm and std.container if we 
need to write generic code.

Also, I don't think language design should be *too* biased by the 
standard library's preferences. Not everyone agrees with Phobos 
conventions and we have to respect that IMHO. Just because it's a 
standard library doesn't mean that it should dictate users of the 
language who don't use the standard library.

>
> - Jonathan M Davis

-- 
- Alex