Hi.

So, I was typing up a reply but it didn't fit in the comment field anyway. So I'm just going to paste it here.

But maybe this will help: whether associations are atomic or not is entirely up to us. It's not dictated by any implementation detail, just by whether we think it makes obeys the definition (hint: it doesn't).

But I think what you're really saying is that Associations are "NormalQ", i.e. they aren't equivalent to their FullForm in a literal sense. That means that they require special support in almost all kernel-level traversal (e.g. Part, Map) and mutation (e.g. Append) functions. One place they don't yet have this support is the pattern matcher, which is because the pattern matcher is very delicate code and it is quite a big job to add an entirely new class of expression to it.

So, in conclusion, there are two concepts that many people (including us), confuse: AtomQ and NormalQ.

AtomQ means: can I traverse this, or is it atomic?

clearly, Associations are not atomic

But historically, people have used AtomQ to mean something else: is this an ordinary expression, or does it have special traversal semantics?

e.g. SparseArrays

obviously, associations DO have special semantics

so they are not NormalQ

Currently, NormalQ does not actually exist. We've somewhat abused AtomQ to mean, in some cases, NormalQ.

Or rather, AtomQ =~= !NormalQ

(Let me know when you're finished. And thank you.)

anyway, here's my take, and I'm going to push hard on this because I think I'm right and everyone else is just a bit confused: Association isn't AtomQ, but neither is it NormalQ.

It clearly can be traversed, but it has special traversal semantics that are not 'ordinary FullForm'.