Look into better a better representation for Associations such as a Python dict

[rocky]

See also https://github.com/Mathics3/mathics-core/pull/90

[mmatera]

For me, the idea would be to implement some kind of Atom, like ImageAtom to store it. However, I would like to wait to have finished the changes in the core to define the most suitable implementation.

[TiagoCavalcante]

In Wolfram Language Associations are NOT orderless. This is a very strange behavior because we can't access the index of a rule in an association, but the order of the Association's keys makes 2 Associations different (<| a->2, b->1 |> != <| b->1, a->2 |>). This is strange because the 2 Associations may be different, but if you don't have the source code of a module, you CAN'T know what is different between the 2 Associations.

I believe that this should be taken into account while creating the new Implementation of Association.

Also, the Association atom should have 2 dicts, one for the Rules and the other for the RuleDelayeds.

[rocky]

Python dictionaries in 3.x aren't orderless either.

[TiagoCavalcante]

@rocky so in this case, we should use HAMTs from the immutables module, or from CPython's internals as Axel recommended.

[mmatera]

Maybe the best would be to implement some kind of AssociationAtom using standard Python dictionaries, and then iterate over it looking for different internal representations.

[rocky]

Yes, I have been aware of both of these kind of ideas for a while and some others as well that I've not been exactly secret about but I haven't been that articulate about either.

For now is please be patient and let's defer discussing, designing and implementing it for a bit later when the time is right. I think we'll get there soon enough.

[mmatera]

For now is please be patient and let's defer discussing, designing and implementing it for a bit later when the time is right. I think we'll get there soon enough.

@rocky I think the idea is not to design or implement anything right now, but to think about how it should be done. This could be helpful to planify the reworking of the core.

[mmatera]

Also, the Association atom should have 2 dicts, one for the Rules and the other for the RuleDelayeds.

@TiagoCavalcante The distinction between Rule and RuleDelayed makes sense if you want to evaluate the elements of the association before applying it. I think it would be better to store in the dictionary mathics.core.Rule objects instead of Expressions the replace rule. For example:

Doing this, Association[{a->x*x, b:>x*x}] would be stored internally as a Python dictionary {"System`a": x^2,"System`b": x*x}

[rocky]

Ok. I guess I need to be more patient then.

Let me say though that largely for me this has been distraction because there has been little that I haven't been aware of except maybe that there is this immuables package out there if it turns out that an OrderedDict isn't sufficient. (But it is not clear to me whether this is a problem that needs solving).

[mmatera]

Ok. I guess I need to be more patient then.

Let me say though that largely for me this has been distraction because there has been little that I haven't been aware of except maybe that there is this immuables package out there if it turns out that an OrderedDict isn't sufficient. (But it is not clear to me whether this is a problem that needs solving).

@rocky, I think that this issue involves two problems, that need to be split off. One is about the internal representation of certain objects (maps / immutable maps / whatever someone clever invented) and the other is how we implement an interface between this internal representation and something that can be part of an expression.
The first one is more or less independent of how we restructure the core, while the second isn't. In particular, the question is how this interface is going to behave during further evaluations.

[rocky]

@mmatera Yes, I knew about this and understood this even before the first time you mentioned it in https://github.com/Mathics3/mathics-core/issues/162#issuecomment-1046396395

[TiagoCavalcante]

@TiagoCavalcante The distinction between Rule and RuleDelayed makes sense if you want to evaluate the elements of the association before applying it. I think it would be better to store in the dictionary mathics.core.Rule objects instead of Expressions the replace rule. For example:

Doing this, Association[{a->xx, b:>xx}] would be stored internally as a Python dictionary {"Systema": x^2,"Systemb": x*x}

Yes, great idea, this way all elements could be kept in the same table (a generalization of dictionaries, HAMTs, hash tables, binary trees, array, ...), we just need to evaluate the Rules and keep the RuleDelayed as is.

Let me say though that largely for me this has been distraction because there has been little that I haven't been aware of except maybe that there is this immuables package out there if it turns out that an OrderedDict isn't sufficient.

I have commented about these 2 other options because, as you said, Python dictionaries are indexed in some way. But in truth, the user won't see the difference between the implementations of Association, just the performance.

@rocky, I think that this issue involves two problems, that need to be split off. One is about the internal representation of certain objects (maps / immutable maps / whatever someone clever invented) and the other is how we implement an interface between this internal representation and something that can be part of an expression. The first one is more or less independent of how we restructure the core, while the second isn't. In particular, the question is how this interface is going to behave during further evaluations.

Here it is better to start with a simple implementation and improve it with HAMTs (or whatever be chosen) later. So I guess step 1 is done by now.

[mmatera]

Something similar can be done for Dispatch.