www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Associative arrays

reply Imperatorn <johan_forsberg_86 hotmail.com> writes:
Sooo, when are we implementing this? 😁

https://dlang.org/spec/hash-map.html#static_initialization
May 10
parent reply "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
On Mon, May 10, 2021 at 05:31:21PM +0000, Imperatorn via Digitalmars-d wrote:
 Sooo, when are we implementing this? 😁
 
 https://dlang.org/spec/hash-map.html#static_initialization
This has been on the list for many years, and I haven't seen any signs of it manifesting any time soon. In the meantime, you could simply do this: static immutable K[V] myAA; static this() { myAA = [ "abc": 123, ... // etc. ]; } T -- If you think you are too small to make a difference, try sleeping in a closed room with a mosquito. -- Jan van Steenbergen
May 10
parent reply Chris Piker <chris hoopjump.com> writes:
On Monday, 10 May 2021 at 18:31:20 UTC, H. S. Teoh wrote:
 This has been on the list for many years, and I haven't seen 
 any signs of it manifesting any time soon.
Hi H. S. I assume it's not been done because it's hard. Do you happen to know what makes it a difficult problem for compiler implementers? I don't need to know, but am curious. Thanks,
May 18
parent reply Ola Fosheim Grostad <ola.fosheim.grostad gmail.com> writes:
On Tuesday, 18 May 2021 at 07:40:53 UTC, Chris Piker wrote:
 On Monday, 10 May 2021 at 18:31:20 UTC, H. S. Teoh wrote:
 This has been on the list for many years, and I haven't seen 
 any signs of it manifesting any time soon.
Hi H. S. I assume it's not been done because it's hard. Do you happen to know what makes it a difficult problem for compiler implementers? I don't need to know, but am curious.
I hope it stays unimplemented. AAs should be replaced by a library solution and AA literals should work with custom AAs. The special casing is not good for metaprogramming.
May 18
parent reply Chris Piker <chris hoopjump.com> writes:
On Tuesday, 18 May 2021 at 07:50:06 UTC, Ola Fosheim Grostad 
wrote:
 I hope it stays unimplemented. AAs should be replaced by a 
 library solution and AA literals should work with custom AAs. 
 The special casing is not good for metaprogramming.
I'm new to D and don't come from a hard-core C++ background. On naive first take, the fact that D had a construct resembling python dictionaries made D more attractive. In fact, it was AAs that finally tipped me in favor of trying D. Can you tell me more about why AAs are an undesirable language feature?
May 18
next sibling parent reply Ola Fosheim Grostad <ola.fosheim.grostad gmail.com> writes:
On Tuesday, 18 May 2021 at 08:08:10 UTC, Chris Piker wrote:
 On Tuesday, 18 May 2021 at 07:50:06 UTC, Ola Fosheim Grostad 
 wrote:
 I hope it stays unimplemented. AAs should be replaced by a 
 library solution and AA literals should work with custom AAs. 
 The special casing is not good for metaprogramming.
I'm new to D and don't come from a hard-core C++ background. On naive first take, the fact that D had a construct resembling python dictionaries made D more attractive. In fact, it was AAs that finally tipped me in favor of trying D. Can you tell me more about why AAs are an undesirable language feature?
Hashing strategies needs contextual knowledge. But that is not the main reason. The main reason is that D needs better metaprogramming. A hashmap literal should bind to any hashtable. There is no reason to not make it a 100% library construct. Stuff it into your runtime and you would hardly notice any difference. Golden design rule: never add language features that can be done as library constructs, ever.
May 18
parent reply Chris Piker <chris hoopjump.com> writes:
On Tuesday, 18 May 2021 at 08:22:56 UTC, Ola Fosheim Grostad 
wrote:
 The main reason is that D needs better metaprogramming.
That's an interesting take. So far, with only a month's usage of D I'm seeing so much meta-programming capability that it actually worries me a bit. With string mixins and so many other meta programming features around I'm starting to think that reading other people's D code is going to be quite difficult, similar to perl.
 Golden design rule: never add language features that can be 
 done as library constructs, ever.
This sounds like a reasonable position. Imagine for a second that AAs were implemented as a library. What would the library equivalent of this: ```d long[string] aa = ["foo": 5, "bar": 10, "baz": 2000 ]; ``` look like?
May 18
next sibling parent reply Mathias LANG <geod24 gmail.com> writes:
On Tuesday, 18 May 2021 at 09:14:46 UTC, Chris Piker wrote:
 This sounds like a reasonable position.  Imagine for a second 
 that AAs were implemented as a library.  What would the library 
 equivalent of this:

 ```d
 long[string] aa = ["foo": 5, "bar": 10, "baz": 2000 ];
 ```

 look like?
https://github.com/dlang/druntime/blob/bf21d1bad623c6988d644117c3c0aa4d4f08b771/src/object.d#L2657-L2660 The [playground](https://run.dlang.io/) will show the call to `_d_assocarrayliteralTX` if you select ASM.
May 18
parent Chris Piker <chris hoopjump.com> writes:
On Tuesday, 18 May 2021 at 09:24:02 UTC, Mathias LANG wrote:
 https://github.com/dlang/druntime/blob/bf21d1bad623c6988d644117c3c0aa4d4f08b771/src/object.d#L2657-L2660
Wait. Are the unittests from that link indicative of the current end-user syntax, or what AA usage would look like under a library scheme? (or both?) from line: 2892 ```d auto dict = ["k1": 1, "k2": 2]; int sum; foreach (v; dict.byValue) sum += v; ```
May 18
prev sibling next sibling parent reply Ola Fosheim Grostad <ola.fosheim.grostad gmail.com> writes:
On Tuesday, 18 May 2021 at 09:14:46 UTC, Chris Piker wrote:
 On Tuesday, 18 May 2021 at 08:22:56 UTC, Ola Fosheim Grostad 
 wrote:
 The main reason is that D needs better metaprogramming.
That's an interesting take. So far, with only a month's usage of D I'm seeing so much meta-programming capability that it actually worries me a bit. With string mixins and so many other meta programming features around I'm starting to think that reading other people's D code is going to be quite difficult, similar to perl.
 Golden design rule: never add language features that can be 
 done as library constructs, ever.
This sounds like a reasonable position. Imagine for a second that AAs were implemented as a library. What would the library equivalent of this: ```d long[string] aea = ["foo": 5, "bar": 10, "baz": 2000 ]; ``` look like?
It could look the same, but long[string] would now be a shorthand for std.xyz.Map!(long,string) or something like that instead of a special case.
May 18
next sibling parent reply Chris Piker <chris hoopjump.com> writes:
On Tuesday, 18 May 2021 at 09:41:06 UTC, Ola Fosheim Grostad 
wrote:
 It  could look the same, but long[string] would now be a 
 shorthand for std.xyz.Map!(long,string) or something like that 
 instead of a special case.
Hum, that's unfortunate. Though it's a separate issue, I think this means that the error messages generated by AA associated code would become neigh unreadable, just like many error messages involving templates. I'd probably avoid using a library implementation in that case, because the usability of a construct is tied to the debug-ability of a construct. Unless I'm mistaken*, the hash function used to generate the AA would become part of the data type and thus the decent into Type Hell(tm) would begin... Maybe in a few months I'll have a different opinion, but D template error messages really made last week more difficult at work, so any library function that encourages dmd to pump out more text-walls is something I'll try to avoid using. -- *always likely
May 18
parent Ola Fosheim Grostad <ola.fosheim.grostad gmail.com> writes:
On Tuesday, 18 May 2021 at 10:18:28 UTC, Chris Piker wrote:
 On Tuesday, 18 May 2021 at 09:41:06 UTC, Ola Fosheim Grostad 
 wrote:
 It  could look the same, but long[string] would now be a 
 shorthand for std.xyz.Map!(long,string) or something like that 
 instead of a special case.
Hum, that's unfortunate. Though it's a separate issue, I think this means that the error messages generated by AA associated code would become neigh unreadable, just like many error messages involving templates.
Error messages is not a language deficiency, that is an implementation priority. Completely unrelated. There is no reason for error messages to change.
May 18
prev sibling parent reply Adam D. Ruppe <destructionator gmail.com> writes:
On Tuesday, 18 May 2021 at 09:41:06 UTC, Ola Fosheim Grostad 
wrote:
 It  could look the same, but long[string] would now be a 
 shorthand for std.xyz.Map!(long,string) or something like that 
 instead of a special case.
It would actually be really cool if the AA literal was just rewritten into a constructor call of key, value, key, value, .... _d_aa_literal(T...)(T args) // pragma(discardable) too would be nice [4: "hello", 6: "bye"] _d_aa_literal(4, "hello", 6, "bye") Then you can construct it at ctfe and it retains the order and the capability of heterogeneous types. It'd be overpowered to an awesome extent... and would fix that annoying static initialization of AA things.
May 18
next sibling parent reply Ola Fosheim Grostad <ola.fosheim.grostad gmail.com> writes:
On Tuesday, 18 May 2021 at 11:54:45 UTC, Adam D. Ruppe wrote:
 It would actually be really cool if the AA literal was just 
 rewritten into a constructor call of key, value, key, value, 
 ....
That is an interesting thought. I was thinking more in the direction of a compile time type for literals that could be passed around and comsumed by some destination type. But I have not given this a lot of thought, so maybe your suggestion is sufficient? The only way to gind out is to map out all the usage scenarios and find something that the type system can resolve.
May 18
parent Ola Fosheim Grostad <ola.fosheim.grostad gmail.com> writes:
On Tuesday, 18 May 2021 at 12:01:39 UTC, Ola Fosheim Grostad 
wrote:
 On Tuesday, 18 May 2021 at 11:54:45 UTC, Adam D. Ruppe wrote:
 It would actually be really cool if the AA literal was just 
 rewritten into a constructor call of key, value, key, value, 
 ....
That is an interesting thought. I was thinking more in the direction of a compile time type for literals that could be passed around and comsumed by some destination type. But I have not given this a lot of thought, so maybe your suggestion is sufficient? The only way to gind out is to map out all the usage scenarios and find something that the type system can resolve.
Here is another idea: a compile time forward range that produces key,value pairs...
May 18
prev sibling next sibling parent Imperatorn <johan_forsberg_86 hotmail.com> writes:
On Tuesday, 18 May 2021 at 11:54:45 UTC, Adam D. Ruppe wrote:
 On Tuesday, 18 May 2021 at 09:41:06 UTC, Ola Fosheim Grostad 
 wrote:
 It  could look the same, but long[string] would now be a 
 shorthand for std.xyz.Map!(long,string) or something like that 
 instead of a special case.
It would actually be really cool if the AA literal was just rewritten into a constructor call of key, value, key, value, .... _d_aa_literal(T...)(T args) // pragma(discardable) too would be nice [4: "hello", 6: "bye"] _d_aa_literal(4, "hello", 6, "bye") Then you can construct it at ctfe and it retains the order and the capability of heterogeneous types. It'd be overpowered to an awesome extent... and would fix that annoying static initialization of AA things.
Yes
May 18
prev sibling parent reply Steven Schveighoffer <schveiguy gmail.com> writes:
On 5/18/21 7:54 AM, Adam D. Ruppe wrote:
 On Tuesday, 18 May 2021 at 09:41:06 UTC, Ola Fosheim Grostad wrote:
 It  could look the same, but long[string] would now be a shorthand for 
 std.xyz.Map!(long,string) or something like that instead of a special 
 case.
It would actually be really cool if the AA literal was just rewritten into a constructor call of key, value, key, value, .... _d_aa_literal(T...)(T args) // pragma(discardable) too would be nice [4: "hello", 6: "bye"] _d_aa_literal(4, "hello", 6, "bye") Then you can construct it at ctfe and it retains the order and the capability of heterogeneous types. It'd be overpowered to an awesome extent... and would fix that annoying static initialization of AA things.
Let's make that 2 arrays (static or stack-allocated dynamic) to avoid the vararg template cost. -Steve
May 18
parent reply Adam D. Ruppe <destructionator gmail.com> writes:
On Tuesday, 18 May 2021 at 12:57:01 UTC, Steven Schveighoffer
 Let's make that 2 arrays (static or stack-allocated dynamic) to 
 avoid the vararg template cost.
That's good for current AAs, but it can't do the heterogeneous types. Of course that's illegal in D right now anyway I'm just holding out hope for an expansion for json literals w/o explicit constructors on each element too. :) but yeah that'd work just fine too.
May 18
parent Steven Schveighoffer <schveiguy gmail.com> writes:
On 5/18/21 9:04 AM, Adam D. Ruppe wrote:
 On Tuesday, 18 May 2021 at 12:57:01 UTC, Steven Schveighoffer
 Let's make that 2 arrays (static or stack-allocated dynamic) to avoid 
 the vararg template cost.
That's good for current AAs, but it can't do the heterogeneous types. Of course that's illegal in D right now anyway I'm just holding out hope for an expansion for json literals w/o explicit constructors on each element too. :) but yeah that'd work just fine too.
Hm... that does kind of make sense. I was thinking maybe you could specify the type of key to be something that accepts multiple constructor values (like translate to Json(val)) but then the expression isn't self-contained, it has to look at what it's being assigned to (which also is a possibility, after all, AA literal assignment can get type hints from the thing it's being assigned to). I hope there's some way to avoid paying the variadic template penalty tax, which would be pretty heavy if you had a large literal (not uncommon). -Steve
May 18
prev sibling parent reply Paul Backus <snarwin gmail.com> writes:
On Tuesday, 18 May 2021 at 09:14:46 UTC, Chris Piker wrote:
 This sounds like a reasonable position.  Imagine for a second 
 that AAs were implemented as a library.  What would the library 
 equivalent of this:

 ```d
 long[string] aa = ["foo": 5, "bar": 10, "baz": 2000 ];
 ```

 look like?
Something like this, most likely: ```d auto aa = makeAA!(string, long)("foo", 5, "bar", 10, "baz", 2000); ```
May 18
next sibling parent Imperatorn <johan_forsberg_86 hotmail.com> writes:
On Tuesday, 18 May 2021 at 13:25:32 UTC, Paul Backus wrote:
 On Tuesday, 18 May 2021 at 09:14:46 UTC, Chris Piker wrote:
 This sounds like a reasonable position.  Imagine for a second 
 that AAs were implemented as a library.  What would the 
 library equivalent of this:

 ```d
 long[string] aa = ["foo": 5, "bar": 10, "baz": 2000 ];
 ```

 look like?
Something like this, most likely: ```d auto aa = makeAA!(string, long)("foo", 5, "bar", 10, "baz", 2000); ```
How hard would it be to "overload/override" the AA syntax to allow different implementations? 🤔 Like a default would require nothing (as it is today) but if you somehow told the rt that "hey, I want to use this for AAs plz". Then if you want better performance you could over time just plug a new implementation in. Why? So that existing code wouldn't have to be changed, but with some added configuration could get the benefits.
May 18
prev sibling parent reply Chris Piker <chris hoopjump.com> writes:
On Tuesday, 18 May 2021 at 13:25:32 UTC, Paul Backus wrote:
 On Tuesday, 18 May 2021 at 09:14:46 UTC, Chris Piker wrote:
 What would the library equivalent of this:

 ```d
 long[string] aa = ["foo": 5, "bar": 10, "baz": 2000 ];
 ```

 look like?
Something like this, most likely: ```d auto aa = makeAA!(string, long)("foo", 5, "bar", 10, "baz", 2000); ```
So if I understand correctly, the idea is to get rid of AAs and replace them with moral equivalent of a Java HashMap. I'm guessing this means array index and assignment would become something like: ```d value = aa(key); aa(key, value); ``` and AAs as a language construct would disappear. Or would the current syntax remain via CTFE?
May 18
next sibling parent reply Imperatorn <johan_forsberg_86 hotmail.com> writes:
On Tuesday, 18 May 2021 at 19:34:45 UTC, Chris Piker wrote:
 On Tuesday, 18 May 2021 at 13:25:32 UTC, Paul Backus wrote:
 On Tuesday, 18 May 2021 at 09:14:46 UTC, Chris Piker wrote:
 What would the library equivalent of this:

 ```d
 long[string] aa = ["foo": 5, "bar": 10, "baz": 2000 ];
 ```

 look like?
Something like this, most likely: ```d auto aa = makeAA!(string, long)("foo", 5, "bar", 10, "baz", 2000); ```
So if I understand correctly, the idea is to get rid of AAs and replace them with moral equivalent of a Java HashMap. I'm guessing this means array index and assignment would become something like: ```d value = aa(key); aa(key, value); ``` and AAs as a language construct would disappear. Or would the current syntax remain via CTFE?
We would keep the existing syntax, but lower it to something else
May 18
parent Chris Piker <chris hoopjump.com> writes:
On Tuesday, 18 May 2021 at 20:33:24 UTC, Imperatorn wrote:
 We would keep the existing syntax, but lower it to something 
 else
Even the constructor syntax? If so that would be welcome news.
May 18
prev sibling parent Paul Backus <snarwin gmail.com> writes:
On Tuesday, 18 May 2021 at 19:34:45 UTC, Chris Piker wrote:
 So if I understand correctly, the idea is to get rid of AAs and 
 replace them with moral equivalent of a Java HashMap. I'm 
 guessing this means array index and assignment would become 
 something like:

 ```d
    value = aa(key);
    aa(key, value);
 ```
 and AAs as a language construct would disappear. Or would the 
 current syntax remain via CTFE?
D allows overloading the index operator, so you would still be able to write value = aa[key]; aa[key] = value; As far as I know the only thing D's operator overloading doesn't support that the built-in AA syntax does is insertion of values into nested AAs with a single assignment: bool[string][string] aa; // NB: empty AA of AAs aa["foo"]["bar"] = true; // assigns both aa["foo"] and aa["foo"]["bar"] With a library type, you would instead have to write: Map!(string, Map!(string, bool)) aa; aa["foo"] = new Map!(string, bool); aa["foo"]["bar"] = true;
May 18
prev sibling parent reply Mathias LANG <geod24 gmail.com> writes:
On Tuesday, 18 May 2021 at 08:08:10 UTC, Chris Piker wrote:
 On Tuesday, 18 May 2021 at 07:50:06 UTC, Ola Fosheim Grostad 
 wrote:
 I hope it stays unimplemented. AAs should be replaced by a 
 library solution and AA literals should work with custom AAs. 
 The special casing is not good for metaprogramming.
I'm new to D and don't come from a hard-core C++ background. On naive first take, the fact that D had a construct resembling python dictionaries made D more attractive. In fact, it was AAs that finally tipped me in favor of trying D. Can you tell me more about why AAs are an undesirable language feature?
AA are definitely a great D feature IMO. But unlike other D features, they are not as composable as we'd like. Take slices for example. They compose fairly well. You can get an `int[]` from the GC, a static array, `malloc`, or even some other library-provided buffer. While extending them is tied to the GC (`a ~= b` will always call the GC), sub-slicing them, batch operations (`a[] = b` or `a[] = b[]`) will work just the same no matter what underlying memory you have. Associative arrays have none of that. They are tied to the way they've been implemented in the runtime, and predate a lot of features. They only work with qualifiers because of the C interfacing. You can't control the underlying memory, which means you can't reuse it or bind it to a buffer if you know the AA size in advance. They don't work well with qualifiers, because the compiler will error on `myAA[key] = value;` if `is(typeof(myAA[key]) : const)` because it can't know if it's an update or an insertion. We have require and update in druntime but those are not recognized by the compiler so they don't solve the problem. The following doesn't even compile: ``` void main () nothrow { int[int] aa; foreach (k, v; aa) {} } ``` Because:
 onlineapp.d(4): Error: `_aaApply2` is not `nothrow`
 onlineapp.d(1): Error: `nothrow` function `D main` may throw
Now as to why AA don't work at CT: They still use the "old" druntime approach, namely hiding all runtime magic behind `extern(C)` functions which are declared in the compiler frontend and defined in druntime (the linker doing the magic). This approach has the "upside" of bypassing all attributes checks (you can say that a function is ` safe pure nothrow nogc` in the compiler frontend but not mark it as such in the `extern(C)` function and things will link), but it has many downsides: First, it's not CTFEable, meaning many things depending on the runtime had to be duplicated in the frontend; second, it can hurt performances, as it can't be inlined (although LTO might do a good job here); lastly, well, it bypass all attributes checks so when you actually have a mismatch all hell breaks loose. There's been a few discussions about this over the year. For example, [this PR from a few years ago wanted to at least allow builtin types](https://github.com/dlang/dmd/pull/4571). IgorStepanov did some work, e.g. [here](https://github.com/dlang/dmd/pull/3904) and [here](https://github.com/dlang/dmd/pull/4175) (and more). Martin Nowak IIRC also did quite some work on it.
May 18
parent reply Chris Piker <chris hoopjump.com> writes:
On Tuesday, 18 May 2021 at 08:54:00 UTC, Mathias LANG wrote:

Thanks for the description, that was informative :)

 The following doesn't even compile:
 ```
 void main () nothrow
 {
     int[int] aa;
     foreach (k, v; aa) {}
 }
 ```
So basically I can use AAs, so long as I don't put them in critical software since they are always going to throw. No trouble, I can live with that, it's good to know that up front.
May 18
parent Steven Schveighoffer <schveiguy gmail.com> writes:
On 5/18/21 5:34 AM, Chris Piker wrote:
 On Tuesday, 18 May 2021 at 08:54:00 UTC, Mathias LANG wrote:
 
 Thanks for the description, that was informative :)
 
 The following doesn't even compile:
 ```
 void main () nothrow
 {
     int[int] aa;
     foreach (k, v; aa) {}
 }
 ```
So basically I can use AAs, so long as I don't put them in critical software since they are always going to throw.  No trouble, I can live with that, it's good to know that up front.
No, that's the wrong way to look at it. `foreach(k, v; aa)` isn't nothrow, because it accepts an opApply-style delegate. This is a language limitation, not a promise that they will throw in some cases. `foreach(kv; aa.byKeyValue)` is nothrow, (where kv.key and kv.value are used to access the data), because it uses the range interface to foreach. -Steve
May 18