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