October 07, 2020
On Wednesday, 7 October 2020 at 00:11:20 UTC, Paul Backus wrote:
> 
> I agree that allowing completely unrestricted tuple mutation would be problematic, but I think it's still worth asking how far we could potentially go in that direction.

I would be happy to discuss this over a coffee or beer sometime.
As a thought experiment it's exciting.

> For example, maybe you're only allowed to mutate tuples inside the scope that declares them. That would let you implement templates like Filter and staticMap iteratively, while still presenting an immutable "interface" to the rest of the program.

If you can prove:
 - It never escapes a 'mutable' version into a monophonic scope.
 - Inside a polymorphic scope (template) all transforms are derived from the shape defining parameters (template parameters) or are invariant.

That is necessary, but I am not sure it's sufficient.
October 07, 2020
On Wednesday, 7 October 2020 at 00:18:10 UTC, Ola Fosheim Grøstad wrote:
> On Wednesday, 7 October 2020 at 00:11:48 UTC, Stefan Koch wrote:
>> If you know a way to do that cleanly, that does not involve a redesign of the compiler,
>> I am very interested to hear about it.
>> As things stand type functions are what I can get away with, and still be reasonably confident I won't violate language invariants.
>> Also their syntax blends in fairly nicely with the rest of D.
>
> Allright, if the syntax is such that it can be made more general later then all is good.
>
> (Ive only modified the dmd lexer/parser, so I don't know where the limitations are bqeyond ast level...)

With more general you mean, not just apply to types but to anything?

Yes that can happen. Adam actually wants this functionality as well.
Tbh. the syntax is currently blocking me here.
What name do I give to the (pseudo) TOP type?
that can hold anything a variadic template parameter can hold?
October 07, 2020
On Tuesday, 6 October 2020 at 23:39:24 UTC, H. S. Teoh wrote:
> On Tue, Oct 06, 2020 at 11:16:47PM +0000, claptrap via Digitalmars-d wrote: [...]
>>
> I would write it like this:
>
> 	int[] vals = [4,7,28,23,585,73,12];
>
> 	int[] getMultiplesOf(int i)
> 	{
> 	    return vals.filter!(v => (v % i) == 0).array;
> 	}
>
> One line vs. 4, even more concise. ;-)

The point is to show language not library.


> Thing is, what someone finds intuitive or not, is a pretty subjective matter, and depends on what programming style he's familiar with and/or prefers.  What a C programmer finds readable and obvious may be needlessly arcane to a Java programmer, and what an APL programmer finds totally obvious may be completely impenetrable to anyone else. :-P

We're not looking for "is this intuitive to Java programmers", we're asking is this intuitive to D programmers, so if they already know D then *you have context* in which to judge whether it's intuitive or not. And "It's just like regular D code but with types" pretty much hits the nail on the head as fair as intuitive goes.




October 07, 2020
On Tuesday, 6 October 2020 at 23:27:10 UTC, Adam D. Ruppe wrote:
> On Tuesday, 6 October 2020 at 20:57:10 UTC, claptrap wrote:
>> Im less interested in performance than I am in being able to express what I want to do in clear concise code.
>
> Give me an example of what you'd like to use type functions for.
>
> I betcha I can adapt it to current D with very few changes.

I dont doubt it, but the question is could I do it? could a new D user do it?

IE. Whats the learning curve like?


> Take a look at this for example:
>
> ---
> import std.algorithm;
> template largestType(T...) {
>         auto get() {
>                 return reified!"a.sizeof".map!T
>                     .sort!((a, b) => a > b).front; // or maxElement of course
>         }
>         alias largestType = T[get.idx];
> }
>
> pragma(msg, largestType!(long, int, real, byte)); // real

See the point is even even though I understand that, it took me a while to grep it, and I couldn't just rattle that off the top of my head, it'd take me a fair while to figure out how to do that. (Maybe i wouldn't even be able to on my own)

But with Type Functions it'd be something like this...

// assuming type is synonym for alias or whatever.

type convTargets(type[] args)
{
    assert(args.length > 0);
    type result = void; // IIRC void.sizeof == 1?
    foreach(t; args)
        if (t.size > result.sizeof) result = t;
    return result;
}

The point is TF are obvious, if you know regular D code, you can use type functions. I've got the gist of it from a handful of forums posts. The cognitive load is so much lower.


October 07, 2020
On Wednesday, 7 October 2020 at 01:07:17 UTC, claptrap wrote:
> On Tuesday, 6 October 2020 at 23:39:24 UTC, H. S. Teoh wrote:
>> On Tue, Oct 06, 2020 at 11:16:47PM +0000, claptrap via Digitalmars-d wrote: [...]
>>>
>> I would write it like this:
>>
>> 	int[] vals = [4,7,28,23,585,73,12];
>>
>> 	int[] getMultiplesOf(int i)
>> 	{
>> 	    return vals.filter!(v => (v % i) == 0).array;
>> 	}
>>
>> One line vs. 4, even more concise. ;-)
>
> The point is to show language not library.
>
>
>> Thing is, what someone finds intuitive or not, is a pretty subjective matter, and depends on what programming style he's familiar with and/or prefers.  What a C programmer finds readable and obvious may be needlessly arcane to a Java programmer, and what an APL programmer finds totally obvious may be completely impenetrable to anyone else. :-P
>
> We're not looking for "is this intuitive to Java programmers", we're asking is this intuitive to D programmers, so if they already know D then *you have context* in which to judge whether it's intuitive or not. And "It's just like regular D code but with types" pretty much hits the nail on the head as fair as intuitive goes.

If recursive templates are not intuitive to you, perhaps you still have more D to learn, to become this mythical "D programmer".

My 16 lines of template essentially compiled in D for at least the past 10 years.
It literally is "regular D code".

If recursion and declarative programming isn't intuitive to you in general, then perhaps that's not D's problem at all.

/Daniel K
October 06, 2020
On 10/6/20 9:07 PM, claptrap wrote:
> On Tuesday, 6 October 2020 at 23:39:24 UTC, H. S. Teoh wrote:
>> On Tue, Oct 06, 2020 at 11:16:47PM +0000, claptrap via Digitalmars-d wrote: [...]
>>>
>> I would write it like this:
>>
>>     int[] vals = [4,7,28,23,585,73,12];
>>
>>     int[] getMultiplesOf(int i)
>>     {
>>         return vals.filter!(v => (v % i) == 0).array;
>>     }
>>
>> One line vs. 4, even more concise. ;-)
> 
> The point is to show language not library.

That's a made-up restriction, and it's odd that it is being discussed here as a virtue.

Beginners are attracted to large languages that have everything built in. A good language is focused on general primitives that allow writing a great deal in libraries.


October 07, 2020
On Wednesday, 7 October 2020 at 01:27:17 UTC, claptrap wrote:
> IE. Whats the learning curve like?

It is hard to say right now because this is a brand new technique. It has been possible in D ... basically forever, these language features are all quite aged, but to my knowledge, nobody has tried it this way before.

> See the point is even even though I understand that, it took me a while to grep it, and I couldn't just rattle that off the top of my head, it'd take me a fair while to figure out how to do that. (Maybe i wouldn't even be able to on my own)

That might just be because you've never seen a combination of patterns like that before... and that's OK, I made up that particular thing just a few hours ago. (Though it is based on some ideas Andrei and I have been bouncing back and forth.)

But with a little library refinement and some tutorials, maybe it would prove to be easy to learn and to use.

The usage of a string lambda reminded me of the early days of std.functional and std.algorithm. Back then, a function literal looked like `(args) { return thing; }`. They shortened to strings since they liked the shortness and that's what we had, but it wasn't great.

Right now, a template lambda doesn't exist. We don't even have a short form literal like delegates did. So I'm using a string there. Maybe we are walking down the same path.

> But with Type Functions it'd be something like this...
>
> // assuming type is synonym for alias or whatever.
>
> type convTargets(type[] args)
> {
>     assert(args.length > 0);
>     type result = void; // IIRC void.sizeof == 1?
>     foreach(t; args)
>         if (t.size > result.sizeof) result = t;
>     return result;
> }

You could have also written that:

// normal boilerplate
template biggest(args...) {
    int helper() {
      // this stuff is really similar between the two!
      assert(args.length > 0);
      size_t result;
      size_t bestSize; // just store the answer and the size separate
      foreach(idx, t; args)
         if(t.sizeof > bestSize) {
             result = idx;
             bestSize = t;
         }
      return result;
    }
    // then this part always follows the same pattern again
    alias biggest = args[helper];
}

That pattern btw is very useful to know regardless of if this technique works out - it is also the same idea I used for user-defined literals in D ages ago.

Anyway, that's where my young library constructs are coming from - trying to recognize and abstract this pattern a little. But the core of it IS just regular D code: just it returns indexes into the array instead of the item itself because compiler tuples are weird. (I've been telling Stefan in a separate chat if type functions become compiler tuple functions, able to work with that `args...` thing to its full potential, we'd have something compelling in new functionality, not just speed. That can replace some of the super-ugly string mixins in my jsvar and jni that transform runtime argument lists! But idk if that will prove possible yet. He's exploring it, though.)

The major problem with this pattern so far is it is slow. I was actually going to abandon it after Phobos' existing implementations and the typefunctions prototype both blew it out of the water in speed terms.

But some people say using regular std.algorithm stuff is more important to them than speed. So I'm still toying with it for that sake.
October 06, 2020
On 10/6/2020 11:09 AM, Adam D. Ruppe wrote:
> The Phobos implementation started life with a very simple implementation too. It became what it is because it *had to*, specifically for performance reasons.

Professional C Standard library implementations tend to be hideous code to perform objectively simple operations. The reason is speed is so desirable in foundational code that it drives out all other considerations. (memcpy() is a standout example.)

I remember back in the 80's when Borland came out with Turbo C. The compiler didn't generate very good code, but applications built with it were reasonably fast. How was this done?

Borland carefully implemented the C library in hand-optimized assembler by some very good programmers. Even printf was coded this way. The speedups gained there sped up every Turbo C program. At the time, nobody else had done that.

Much as I hate to admit it, Borland made the smart move there.

October 06, 2020
On Tue, Oct 06, 2020 at 08:47:33PM -0700, Walter Bright via Digitalmars-d wrote:
> On 10/6/2020 11:09 AM, Adam D. Ruppe wrote:
> > The Phobos implementation started life with a very simple implementation too. It became what it is because it *had to*, specifically for performance reasons.
> 
> Professional C Standard library implementations tend to be hideous code to perform objectively simple operations. The reason is speed is so desirable in foundational code that it drives out all other considerations. (memcpy() is a standout example.)

A little tangential aside: one time as a little coffee break challenge, I decided to see how D compares to GNU wc in terms of the speed of counting lines in a text file.  The core of wc, of course, is in memchr -- because it's scanning for newline characters in a buffer.  In the course of ferreting out what made wc so fast, I studied how GNU libc implemented memchr.  Basically, in order to speed up scanning large buffers, it uses a series of fancy bit operations on 64-bit words in order to scan 8 bytes at a time, I suppose the goal being to achieve close to 8x speedup, and also to reduce the number of branches per iteration to capitalize on the CPU's pipeline.

In order to do this, however, some not-so-cheap setup was necessary at the beginning and end of the buffer, which generally are not 8-byte aligned.  When a particular call to memchr scanned many bytes, of course, the speed of scanning 8 bytes at a time outweighed this setup / teardown cost, and wc generally outperformed my D code.

However, when the lines being scanned were on the short side, the overhead of setting up the 8-byte-at-a-time scanning added up significantly -- the shorter lines meant less time was spend scanning 8 bytes at a time, and more time spent in the complicated code dealing with non-aligned start/end of the buffer. In this case, I discovered that a simplistic for-loop in D outperformed wc.

This led me to think, realistically speaking, how long do lines in a text file tend to be?  My wild guess is that they tend to be on the shortish side -- maybe about 60-70 characters on average? For code, a lot less, since code generally has more whitespace for readability reasons.  Files that have very long lines tend to be things like XML or compressed Javascript, which generally you don't really use wc on anyway, so in my mind, they seem to be more the exception than the norm when it comes to the applicability of wc.  Furthermore, I venture to propose that your average string length in C is probably closer to the 80-120 character ballpark, than to large buffers of 1K or 8K which is where the 8-byte-at-a-time scanning would perform much better. Sure, large text buffers do get handled in C code routinely; but how many of them realistically would you find being handed to strchr to scan for some given byte?  The kind of C strings you'd want to search for a particular byte in, IME, are usually the shorter kind.

What this means, is that yes memchr may be "optimized" to next week and back -- but that optimization came with some implicit assumptions about how long it takes to find a character in a string buffer. These assumptions unfortunately pessimized the common case with the overhead of a fancy 8-byte-at-a-time algorithm: one that does better in the *less* common case of looking for a particular byte in a very large buffer.

My point behind all this, is that what's considered optimal sometimes changes depending on what kind of use case you anticipate; and with different usage patterns, one man's optimal algorithm may be another man's suboptimal algorithm, and one man's slow, humble for-loop may be another man's speed demon.  Optimizing for the general case in a standard library is generally a very tough problem, because how do you make any assumptions about the general case?  Whichever way you choose to optimize a primitive like memchr, you're imposing additional assumptions that may make it worse for some people, even if you think that you're improving it for your chosen target metric.



> I remember back in the 80's when Borland came out with Turbo C. The compiler didn't generate very good code, but applications built with it were reasonably fast. How was this done?
> 
> Borland carefully implemented the C library in hand-optimized assembler by some very good programmers. Even printf was coded this way. The speedups gained there sped up every Turbo C program. At the time, nobody else had done that.
> 
> Much as I hate to admit it, Borland made the smart move there.

So what does this imply in terms of Phobos code in D? ;-)  Should we uglify Phobos for the sake of performance?  Keeping in mind, of course, what I said about the difficulty of optimizing for the general case without pessimizing some legitimate use cases -- or maybe even the *common* case, if we lose sight of the forest of common use cases while trying to optimize our chosen benchmark trees.


T

-- 
Life begins when you can spend your spare time programming instead of watching television. -- Cal Keegan
October 07, 2020
On Wednesday, 7 October 2020 at 01:07:17 UTC, claptrap wrote:
> On Tuesday, 6 October 2020 at 23:39:24 UTC, H. S. Teoh wrote:
>> On Tue, Oct 06, 2020 at 11:16:47PM +0000, claptrap via Digitalmars-d wrote: [...]
>>>
>> I would write it like this:
>>
>> 	int[] vals = [4,7,28,23,585,73,12];
>>
>> 	int[] getMultiplesOf(int i)
>> 	{
>> 	    return vals.filter!(v => (v % i) == 0).array;
>> 	}
>>
>> One line vs. 4, even more concise. ;-)
>
> The point is to show language not library.

Why?