On Saturday, 28 December 2013 at 15:36:56 UTC, Ola Fosheim Grøstad wrote:
> On Saturday, 28 December 2013 at 14:32:20 UTC, Jacob Carlborg wrote:
>> Originally @ was added for some new keywords to get a new "namespace" for keywords. There was no risk of conflict with
>
> Understand. Objective-C and Python also suffers from the arbitrary "@" syntax. Basically what I would like to see is "@keyword" on stuff that can be hidden without making the semantics less clear (so you could have a "hide/show" button in your editor).

It should be #keyword than, as existing #line is closest thing to what you describe

> // allocate simd-aligned and 0-padded string by sacrificing memory for efficiency,
> // if supported
>
> @simd string

Bad example - it impacts program semantics a lot.

> // force loop-unrolling modulo 4 in order to trigger SIMD optimizations
>
> @unroll(4) for(…) {}

Same here. Such stuff is done by compiler-specific attributes or pragmas. It has no similarities with stuff like #foldregion and should not be treated same.

On Saturday, 28 December 2013 at 13:03:30 UTC, Ola Fosheim Grøstad wrote:
> On Saturday, 28 December 2013 at 11:58:48 UTC, Jakob Ovrum wrote:
>> This is a terrible example - in D it's generally accepted that such a `length` function should NOT be provided at all.
>
> Correction: in the D-community it is generally accepted.

No.

I have *no* idea where you got this idea from. D and its standard library follows in the footsteps of STL when it comes to the algorithmic complexity of primitives, and this has been an important tenet from *at least* the early days of D2. A few examples include std.container's maximum complexity requirement for primitives (including `length`) and the existence of std.range.walkLength. A recent example of enforcement includes the rejection of adding binary `in` functionality for non-associative arrays.

> @disable and (@obsolete) etc can safely be ignored for a sound program, it is a hint for the compiler to check the integrity of the logic, but it does not affect the semantics of a sound program.

You could say this about any restriction in the type system.

(`@obsolete`? Did you mean `deprecated`?)

On Saturday, 28 December 2013 at 15:40:41 UTC, Dicebot wrote:
> This is a solid approach and rationale behind trying to minimize warnings in D as much as possible (and potentially remove at all once standard lint-like tool will appear).

Not sure what "This" refers to, but if you can change semantics by adding a new function to a class without using it yourself, then you have potential for debugging hell when using large frameworks written by others. Therefore I dislike @disable, I thought it worked like a @forbid would.

> Anything that directly impacts basic semantical correctness of program is business of compiler core.

Invariants should not impact correctness. They detect lack of correctness.

> used only by lints may be useful but is not worth discussing until at least on such tool will mature.

The language/compiler should do the job of lint. Having a separate tool just makes IDE integration more troublesome and few programmers will bother with it.

On Saturday, 28 December 2013 at 15:45:16 UTC, Dicebot wrote:
> It should be #keyword than, as existing #line is closest thing to what you describe

Does it matter? I don't think #line is particularly close, it is just an annotation.

>> // allocate simd-aligned and 0-padded string by sacrificing memory for efficiency,
>> // if supported
>>
>> @simd string
>
> Bad example - it impacts program semantics a lot.

Not if done properly. Why would it?

>> // force loop-unrolling modulo 4 in order to trigger SIMD optimizations
>>
>> @unroll(4) for(…) {}
>
> Same here. Such stuff is done by compiler-specific attributes or pragmas. It has no similarities with stuff like #foldregion and should not be treated same.

Pragmas and compiler-specific attributes suck and makes code less readable. Inlining and unrolling is common enough to warrant support, otherwise programmers will do manual unrolling in inner-loops in order to get portable code.

On Saturday, 28 December 2013 at 16:35:41 UTC, Jakob Ovrum wrote:
> I have *no* idea where you got this idea from. D and its standard library follows in the footsteps of STL when it comes to the algorithmic complexity of primitives

STL is not great, has never been great, and probably will never be great. Cool idea, bad execution for the language it was implemented in. So they had to change C++ to support i better! :-P

How much time does a committee need to agree on a hash-table implementation? Or should I say decades? STL is so designed-by-a-committee that it hurts. It is not a shining star! Not at all.

STL is ok for early prototyping with C++11, but if you care about performance you roll your own.

> an important tenet from *at least* the early days of D2. A few examples include std.container's maximum complexity requirement for primitives (including `length`) and the existence of

Single linked lists is very useful for situations where you want lists that are mostly empty or short, but where you do not want to impose an upperbound. O(N) on length() does not matter much in many real-world scenarios.

What you want is a (mild) warning if you use a templated algorithm and that algorithm use a O(N) primitive where it is invisible to the library user. A warning you should be able to suppress (basically telling the compiler "trust me, this is deliberate").

> std.range.walkLength. A recent example of enforcement includes the rejection of adding binary `in` functionality for non-associative arrays.

Why is that?  If your non-associative array on average is of length 3-4 then it might outperform an associative array.

Just like insertion sort will outperform other sorts for mostly-sorted arrays where the elements are offset by jitter (so they are 3-4 elements out-of-place). O(N*N) can easily beat O(N) if the dataset is a good fit. If not, everybody would use radix-sort and nobody would even consider quicksort.

Worst case analysis assuming unbounded arbitrary input is only of theoretical interest, in the real world you care about the average cost over the dataset you actually run the algorithm on. Unless you write hard realtime systems (life-support, weapon systems, etc).

> You could say this about any restriction in the type system.
>
> (`@obsolete`? Did you mean `deprecated`?)

(sure, or "@forbid" or "@notimplemented" etc)

On Saturday, 28 December 2013 at 17:23:38 UTC, Ola Fosheim Grøstad wrote:
> What you want is a (mild) warning if you use a templated algorithm and that algorithm use a O(N) primitive where it is invisible to the library user. A warning you should be able to suppress (basically telling the compiler "trust me, this is deliberate").

How is that significantly different than the current situation?

If you use walkLength, then that's you telling the compiler "trust me, this is deliberate". The only difference is that the current behavior doesn't use a warning, it just errors out with "this thing doesn't define a length", which is reasonable behavior.

FYI, if your thing defines length, then walkLength calls it. So it's effectively as fast to use when your thing has length defined, otherwise it suggests that you understand that a relaxed constraint of O(N) is acceptable and will do that for you if length doesn't exist.

On Saturday, 28 December 2013 at 17:23:38 UTC, Ola Fosheim Grøstad wrote:
> STL is not great, has never been great, and probably will never be great. Cool idea, bad execution for the language it was implemented in. So they had to change C++ to support i better! :-P
>
> How much time does a committee need to agree on a hash-table implementation? Or should I say decades? STL is so designed-by-a-committee that it hurts. It is not a shining star! Not at all.
>
> STL is ok for early prototyping with C++11, but if you care about performance you roll your own.

Nice tirade, but I only referenced STL for its take on algorithmic complexity requirements. If it makes the concept more palatable, you could instead imagine it as the anti-thesis of Java's collection interfaces.

> Single linked lists is very useful for situations where you want lists that are mostly empty or short, but where you do not want to impose an upperbound. O(N) on length() does not matter much in many real-world scenarios.

In these cases you can use `walkLength` which is in itself the very warning you want.

> What you want is a (mild) warning if you use a templated algorithm and that algorithm use a O(N) primitive where it is invisible to the library user. A warning you should be able to suppress (basically telling the compiler "trust me, this is deliberate").

You could define a wrapper type to explicitly attach O(n) primitives onto ranges and/or containers, but generally the response is that you're using the wrong container, so this probably won't find its way to Phobos.

However, it should be noted that D supports flexible metaprogramming which has resulted in algorithms with looser requirements, such as Andrei's `std.algorithm.levenshteinDistance` which doesn't require random access, circumventing the problem entirely.

> Why is that?  If your non-associative array on average is of length 3-4 then it might outperform an associative array.

In terms of advantages, it is only a minor syntactical benefit over using std.algorithm.among/canFind/find.

But the disadvantages are serious, most notably generic code that uses `in` and assumes it has some complexity guarantee would experience a blow-up in complexity when an array is passed.

Further, adding syntax sugar to such an operation sends the wrong signal and is thus asking for trouble during code maintenance - initially the array might have been small and use of `in` judicious, but later down the line the array grows while the use of `in` is preserved because it *looks* low-cost (after all, it looks identical to AA lookup). Alternatively, it can be a teaching problem; by having the scalable AA lookup and the non-scalable array lookup use the same syntax, a beginner could produce really bad code as a result of the hidden but vital difference.

(Also, for many typical element types, a length of 3-4 is an extremely conservative measure. The number where an array starts to be slower can be much, much higher than that, but the idea is that scalability is initially more important than micro-optimization [unless it's a C program, in which case using anything but an array is often not even worth the effort])

On Saturday, 28 December 2013 at 17:53:31 UTC, Chris Cain wrote:
> How is that significantly different than the current situation?

It is different in the sense that if your lengths are short you either have to write your own container or your own algorithm because the algorithm designer assumed that walkLength would be too slow in all cases? In the case of phobos you probably could just change the algorithm to use walkLength yourself and include it with your source. In a more complex framework it might be more difficult?

> FYI, if your thing defines length, then walkLength calls it. So it's effectively as fast to use when your thing has length defined, otherwise it suggests that you understand that a relaxed constraint of O(N) is acceptable and will do that for you if length doesn't exist.

Yes, but I still think that all containers should have length() regardless of efficiency because that is more intuitive, and then you might either provide properties that can be used to assess performance or define a lengthFast() for those algorithms that require O(1).

On Saturday, 28 December 2013 at 18:38:55 UTC, Ola Fosheim Grøstad wrote:
> It is different in the sense that if your lengths are short you either have to write your own container or your own algorithm because the algorithm designer assumed that walkLength would be too slow in all cases? In the case of phobos you probably could just change the algorithm to use walkLength yourself and include it with your source. In a more complex framework it might be more difficult?

struct LengthWrapper(T) {
   T wrapped;
   size_t length() @property {
       return wrapped.walkLength();
   }
   alias wrapped this;
}

LengthWrapper!T assumeWalkLengthOK(T)(T thing) {
   return LengthWrapper!T(thing);
}

There you go. Use it like:

```
someGenericAlgorithm(assumeWalkLengthOK(myContainer));
```

Squelches the error message and documents the intent. Could be better, but it saves us writing a language feature for it.

On Saturday, 28 December 2013 at 18:47:52 UTC, Chris Cain wrote:
> ...snip...
>
> There you go. Use it like:
>
> ```
> someGenericAlgorithm(assumeWalkLengthOK(myContainer));
> ```
>
> Squelches the error message and documents the intent. Could be better, but it saves us writing a language feature for it.

I keep forgetting to use voldemort types, and in this case it really makes sense:

    import std.range;
    auto assumeWalkLengthOK(T)(T thing)
    if(isInputRange!T)
    {
        struct Result
        {
            T wrapped;
            size_t length()
            {
                return wrapped.walkLength();
            }
            alias wrapped this;
        }
        return Result(thing);
    }

Same usage, `someGenericAlgorithm(assumeWalkLengthOK(myContainer));` (I didn't actually run this through dmd, but it should work in theory)