# Evaluated vs. unevaluated Association

This question might have a remote connection to my older question, it is also about sameness of expressions and subtle differences observable only in certain forms.

I encountered this strange behavior:

a = Hold[<|1 -> 2|>]
(* Hold[Association[1 -> 2]] *)

b = Hold[Evaluate[<|1 -> 2|>]]
(* Hold[<|1 -> 2|>] *)

a === b
(* False *)

FullForm[a]
(* Hold[Association[Rule[1, 2]]] *)

FullForm[b]
(* Hold[Association[Rule[1, 2]]] *)

a[[1, 0]]
(* Association *)

b[[1, 0]]
(* Association *)

Uncompress[Compress[b]] === b
(* False *)

Uncompress[Compress[b]] === a
(* True *)

Print[Grid[{TreeForm /@ {a, b}}, Dividers -> All]]


What is going on here? What's the actual difference between a and b?

After I already started to write this question, I came up with more tests that might be more revealing:

MapAt[Hold, a, {1, Key[1]}]
(* MapAt::partw: Part {1,Key[1]} of Hold[Association[1->2]] does not exist. *)
(* MapAt[Hold, Hold[Association[1 -> 2]], {1, Key[1]}] *)

MapAt[Hold, b, {1, Key[1]}]
(* Hold[<|1 -> Hold[2]|>] *)

Depth[a]
(* 4 *)

Depth[b]
(* 3 *)

AssociateTo[a[[1]], 3 -> 4]
(* AssociateTo::invak: The argument Association[1->2] is not a valid Association. *)
(* AssociateTo[a[[1]], 3 -> 4] *)


So, it looks that a does not hold a real Association, but rather some kind of "raw" expression that can turn into a real Association when evaluated. For some reason, FullForm (which is supposed to be the most verbose) hides these details.

As a practical matter, I would like to be able to construct a Hold with a real Association inside, but whose values might be unevaluated expressions (wrapping each value in its own Hold is a possibility, but it would complicate matters).

• related: (46850), (148095), (203201) Aug 25 '19 at 8:01
• An easy way to hold the contents of the Association is to use RuleDelayed. E.g. <|1:>Print[1], 2:>Print[2]|> Aug 25 '19 at 15:52

Summary

The confusion we observe here is largely due to ambiguous use of the symbol Association as an expression head. On the one hand, Association can be used as a constructor function to build an association object. On the other hand, it serves as the symbolic head of a constructed association object. The difference between these two uses is normally hard to spot since the FullForm of a constructor expression is visually indistinguishable from the synthetic full-form of a constructed association object. The two uses have different semantics, as observed in the question.

Many atomic types of Wolfram Language suffer from this same ambiguity.

Discussion (current as of V12)

Notwithstanding the ideal in Wolfram Language that everything is an expression, the basic head-with-elements composite expression is not always a good representation for some data types. There might be efficiency issues or the representation might include details that are too distracting for the user to see.

The way to deal with such issues is to introduce new optimized types of expression to represent the challenging data types. These optimized types are usually atomic, but some go so far as to fully simulate composite expressions (e.g. packed arrays). These custom objects might be built into the kernel (e.g. associations or images) or they may be implemented in high-level WL code (e.g. datasets). Either way, the internal subparts of these optimized types are generally not observable to the usual part access and pattern-matching facilities in the language. Not observable, that is, unless the developer of the feature provided purpose-built functions to simulate such access.

Associations use of this kind of optimization. The optimized object is a handle to a kernel-provided hash-trie implementation that offers both memory and speed advantages over an equivalent but unoptimized high-level expression. ByteArray and Image are just two of many other examples of similarly motivated optimizations.

The constructor expression for an association is composite, but the produced object is atomic:

AtomQ[Unevaluated@<| 1 -> 2 |>]
(* False *)

AtomQ[<| 1 -> 2 |>]
(* True *)


The implementation of association provides a synthetic FullForm for these atoms:

<| 1 -> 2 |> // FullForm
(* Associaton[Rule[1, 2]] *)


... but the synthetic Part implementation does not match that synthetic FullForm:

Part[<| 1 -> 2 |>, 1]
(* 2, but if the full form were true then it should be 1 -> 2 *)


There are good practical reasons for this mismatch, but they can lull one into thinking that an Association atom is just a normal composite expression.

Associations are not unique with respect to such anomalies. Almost all atomic optimizations of expressions involve mismatches of this kind. What is more, the language does not enforce consistency -- it is up to the developer of each optimization to decide how fully to simulate basic expression behaviour.

Here are some things to watch out for:

• It is not possible to tell if an expression is atomic just by looking at its input form or even its full form.
• It is not possible to tell if an expression is optimized just by looking at its head. Even though some constructor functions return an object with a different head (e.g. Interpolation -> InterpolationFunction), most do not (e.g. Association -> Association). The design choice of using the same head for distinct expression types is an interesting one but will not be taken up in detail here.
• A strong clue that an expression has been optimized is that part access or pattern-matching gives surprising results. For associations, the initial implementation did not support pattern-matching at all. A simulation was added in later releases, but a scan of pattern-matching vs. association questions on this site will show that the simulation is not perfect. Graph objects provide subelement access through purpose-built property functions and do not support the regular part and matching mechanisms.
• The input syntax and display forms of an optimized type may not be symmetric. As examples, try examining the input forms of Dataset[{1}] or Image[{{1}}] or ByteArray[{1}].
• The display forms of optimized expressions sometimes leave out critical information required to reconstitute the object's state (e.g. association examples from the question or copy-paste-evaluating a packed array's input form).
• The display forms of the unoptimized version of an optimized expression will generally not use short input syntax. For example, HoldForm[Complex[1, 2] // InputForm] or similar expressions using Rational or Association.
• Atomic expressions can be written in high-level WL code using SetNoEntry. Such expressions are opaque to most forms of pattern-matching (but not all). Some built-in functionality use this (e.g. Dataset).
• When investigating the transition from unoptimized to optimized expression forms, beware that any evaluation will disturb the observations. We must write expressions like AtomQ[Unevaluated@...]. TreeForm in particular is known to have evaluation leaks that require doubling up constructions such as Unevaluated to see the actual structure (e.g. TreeForm[Unevaluated@Unevaluated@<|1 -> 2|>]).
• This is an extremely insightful answer which clearly shows that the WL behaves in many respects like a natural language. Its grammer and syntax is not well defined, you have to learn it by trial and error and listening to expert speakers. Aug 25 '19 at 18:27
• A very nice summary, +1. Just want to note that we have a number of subtle issues due to the (bad in my view) design choice of having the constructor use the same symbol as the actual built structure. For example, it creates problems for WXF deserialization (assocs that we get back need additional evaluation to internal structs), and some subtle scoping bugs, such as this With[{assoc = <|"x" -> a|>}, Function @@ {a, assoc}][y] returning <|"x" -> a|> instead of <|"x" -> y|>. Internal folks are well aware of these issues, but they seem to not be easily solvable in automatic way. Aug 25 '19 at 19:06
• The insight that the constructor of a data structure and the head of the constructed data structure might have been different symbols — but just happened in this case to be the same due to a (maybe questionable) design decision — is very helpful to my understanding of this issue. Thanks! Aug 25 '19 at 22:18
• @VladimirReshetnikov Happy to help. To my mind, this single aspect of this story is really the crux of the matter, and is what is causing the biggest trouble (which prompted me to add this comment to an excellent answer above, which does contain this information but does not stress its importance to the degree I would do). Should constructor for such structures use a different head, and there would be no confusion - of course, with the understanding that the unevaluated constructor expression would not be AssociationQ any more (which I also think would've been correct). Aug 26 '19 at 16:08
• @LeonidShifrin I introduced an initial summary block, copying some text from one of my other posts on this subject to punch up the significance of the constructor/constructed ambiguity. Thanks for the feedback. Aug 26 '19 at 16:23

Associations are atomic (AtomQ).

Except for the most fundamental atomic types (such as Integer, String, Symbol, Real, etc.), most atoms have a representation as a compound expression1, which will normally immediately evaluate to a true atom. This is the difference between a and b: b contains a real association, while a contains its compound representation which is not actually an association, but would evaluate to one as soon as the Hold is removed. I wrote about this in more detail in two answers to this question, and showed how to obtain the compound representation of an atom.

The reason why most atoms have a compound representation is so that they can be serialized (e.g. saved to an .m file, Compressed, sent through MathLink, stored in a notebook, etc.) without each serialization method having to support each atomic type individually.

For most such atoms, there is a function to test their type. For associations, this is AssociationQ. The patterns _Association and _?AssociationQ are not equivalent. The first one will match any compound expression with the head Association. The second one will only match true associations. There is also GraphQ, ImageQ, MeshRegionQ, etc.

1 Here I use the term "compound expression" to refer to an expression that has a head and multiple arguments in the form head[arg1, arg2, ...] accessible in the standard way, i.e. it is not an atom. Not to be confused with ;.

• I find your wording "compound expression" unfortunate: Complex[1,2] looks like a (standard) expression, but evaluates to an atom. (Compound expressions are expressions concatenated by ;) Aug 25 '19 at 11:30
• @MichaelWeyrauch That's a good point. What would be a better term for "non-atoms"? Are you aware of a standard term? I can't find one in the documentation. Aug 25 '19 at 11:53

Not a full answer, but too long for a comment.

Please keep in mind that an Association is quite a complex data structure. Associations are atomic, thus they behave quite differently from purely tree-based Mathematica expression. This is why the constituents of an Association cannot be accessed as we are used to do it with Part. (This has also to do with the fact that Part is overloaded for objects with head Association.)

The true data structure lives more on the "C-side" of Mathematica; it is not implemented in the top-level language (as far as I know). A "true" Association consists of a trie along with various routines for accessing and modifying it. Think of it as a C++ class whose routines have been linked to Mathematica symbols. All that we can see of a true Association on the Mathematica side is basically what the developers want us to see. They tried their best to keep it as intuitive as possible. But of course it is impossible to completely hide the fact that Associations are no common Mathematica expressions.

Hold prevents building up this structure, so Hold[<|1 -> 2|>] will evaluate only to a real Asssociation when Hold is removed. So Hold[<|1 -> 2|>] is a merely tree-based expression and is displayed as such by FullForm[Hold[<|1 -> 2|>]]. In contrast, the Evaluate in Hold[Evaluate[<|1 -> 2|>]] causes the Association to be generated. And from that time on, <|1 -> 2|> is going to be atomic.

• Constituents of associations can be accessed by Part, e.g. asoc[["key"]] gives the value associated with that key. Aug 25 '19 at 5:21
• What I meant was that this causes an error: Association[1 -> 2][[1, 2]]. Aug 25 '19 at 5:27