What's the difference between these 2 associations?

Question

I have 2 associations similar to these simplified ones:

asso1 = <|3 -> 5/7|>;
asso2 = BinaryDeserialize[BinarySerialize[asso1, PerformanceGoal -> "Size"]];

Evaluating them result in different looking output:

asso1
asso2
(* <|3 -> 5/7|> *)
(* <|3 -> Rational[5, 7]|> *)

And using them result in unequal behavior (even though asso1 === asso2 is True):

Map[g, asso1, {-1}]
Map[g, asso2, {-1}]
(* <|3 -> g[5/7]|> *)
(* <|3 -> Rational[g[5], g[7]]|> *)

At first I thought it was about whether the association was evaluated as an argument of Set, but

asso3 = Unevaluated[<|3 -> Rational[5, 7]|>]

results in the same as asso1.

What's the property/attribute/something I'm missing about asso2 that makes it different?

Answer 1

Preamble

The real problem here seems somewhat deeper than what the (mostly correct) observations in comments indicate. In Mathematica, a number of objects, which are so-called raw objects (including in particular Association, SparseArray, and Rational) require a non-trivial construction stage, which usually happens during evaluation.

Had Mathematica's objects been fully opaque (like in many other languages), and this wouldn't have been a problem. But in WL, as we know, everything is an expression. But in the case of a raw object, the FullForm or InputForm of expression don't fully define the state of the object that expression stands for - because it depends on whether or not it has been constructed / evaluated (inner representation of the object has been constructed).

For example:

ByteCount[Unevaluated[Rational[1, 2]]]
AtomQ[Unevaluated[Rational[1, 2]]]

(*
  88

  False
*)

while

ByteCount[Rational[1, 2]]
AtomQ[Rational[1, 2]]

(*
  56

  True 
*)

This situation is not specific to rationals only. Consider an example involving SparseArray, for example:

array = <|"data" -> SparseArray[{{1, 1} -> 1, {2, 2} -> -1}]|>;
arrayProcessed = BinaryDeserialize @ BinarySerialize @array;

Now

array[["data", 1, 1]]

(* 1 *)

but

arrayProcessed[["data", 1, 1]]

During evaluation of In[61]:= Part::partd: Part specification <|data->SparseArray[Automatic,{2,2},0,{1,{{0,1,2},{{1},{2}}},{1,-1}}]|>[[data,1,1]] is longer than depth of object.

(*
   <|"data" -> SparseArray[Automatic, {2, 2}, 0, {1, {{0, 1, 2}, {{1}, {2}}}, {1, -1}}]|>[["data", 1, 1]]
*)

What really happens

Now, here is the crux of the matter. Most such (raw) objects are turned into their InputForm before the WXF serialization. But since there is no way to tell from the InputForm, whether we deal with a fully formed (evaluated) expressions or not, this information, or distinction, is lost. As a result, such objects don't always round-trip. Instead, they are deserialized as their InputForm expression, which needs explicit evaluation to be converted back to the original object. And if they end up inside held (sub)expressions, as parts of a larger expression being deserialized, then such evaluation never happens naturally, and the user would have to perform some post-processing of the deserialized expression, to enable it.

Associations are some of the exceptions, since WXF format has a special token A to represent fully formed associations. Looking at the documentation, one can see some other types which have special tokens. The type Rational does not have a separate token, which is probably the technical reason behind the behavior in question. My familiarity with the WXF is not deep enough to tell whether this is an oversight, or there are good reasons to keep things this way.

So, the Rational[...] object gets transformed into an expression Rational[5, 7] during serialization. When it is deserialized, it remains a normal expression: WXF does not convert it back to the object, because it has no special token, and instead a generic InputForm was used to serialize it. And since it is inside association (which does get fully constructed by WXF - exactly because it is an exception with a special token), it is not re-evaluated by the main evaluator after the deserialization - since fully constructed association does not re-evaluate its parts (formally it is HoldAllComplete).

This is basically it, so those not interested in more details, can skip the next section and go straight to the summary.

The roots of the problem

There are two aspects of the overall design of WL's objects, which I'd like to mention here, and which have the consequences that I consider rather unfortunate. Whether or not those could've been avoided, I don't know.

Two-stage object construction process, and the lack of explicit constructors

One is that there is no notion of an object's constructor for objects, for which a number of core functions work not according to their structural form (e.g. Part, Length, Map etc. for SparseArray). Had there been separate heads fully integrated into the language (e.g. SparseArrayCreate for SparseArray), to represent not a fully formed object, and it would've been easier to solve such round-tripping problems, or perhaps the language would solve them automatically for us. It could've also been a single head like ObjectCreate, so that a constructor call would look like ObjectCreate[Association, rules].

In other words, object construction in WL is a two-stage process. First, when some string representing an expression, is parsed (or an expression is otherwise constructed in WL's memory in some way), we end up with an expression on which we can operate with standard WL's set of built-in functions that work structurally (i.e. traverse an expression, act on its parts, etc.). At this stage, we get a fully functional expression, which can be traversed etc. just like any other WL expression. But for some object types, it just doesn't (yet) behave like the object it stands for should, for a number of core WL functions.

The second stage makes sense for raw objects, for which all or some of those structural functions should work differently than it would follow from the object's FullForm representation. This second stage requires evaluation of that object-defining expression by the kernel, and the resulting returned object is a fully constructed one.

The problem occurs every time when, for some such object, the first stage takes place, but the second stage gets delayed (for example due to non-standard evaluation), and then the result of the first stage is attempted to be used in the context, where the result of the second stage should actually be used.

---

As a simple example here, first consider functions Part and Map applied to an association expression, which has been formed but not yet evaluated - so it does not yet represent a fully constructed association:

Part[Unevaluated @ Association[{"a" -> 1, "b" -> 2}], 1] 
Map[f, Unevaluated @ Association[{"a" -> 1, "b" -> 2}]]

(*
  {"a" -> 1, "b" -> 2}

  Association[f[{"a" -> 1, "b" -> 2}]]
*)

We see that Part and Map work here purely structurally, as they would on any other inert head in place of Association. This is of course not what we are used to, for associations (since we normally work with evaluated and fully formed associations), and probably not the behavior we want from them - which is why associations need special behavior.

Also, one can explicitly verify that such an association expression does not represent a valid association:

AssociationQ @ Unevaluated @ Association[{"a" -> 1, "b" -> 2}]

(* False *)

which is, in fact, the main reason why AssociationQ predicate exists as a separate function, and why the pattern _Association does not really cut it. The same would hold for other raw objects, many of which have special predicates.

Now we repeat the same calls, but with the evaluated (and thus fully formed) association:

Part[Association[{"a" -> 1, "b" -> 2}], 1]
Map[f, Association[{"a" -> 1, "b" -> 2}]]
AssociationQ @ Association[{"a" -> 1, "b" -> 2}]

(*
   1

   <|"a" -> f[1], "b" -> f[2]|>

   True
*)

where obviously the actions of Map and Part do not follow the purely structural semantics based on the FullForm of the underlying expression, as it was the case with the first example.

We can also see the difference in the ByteCount:

ByteCount @ Unevaluated @ Association[{"a" -> 1, "b" -> 2}]
ByteCount @ Association[{"a" -> 1, "b" -> 2}]

(* 312 *)

(* 392 *)

where in the first line, we measure the memory used to store the normal expression, while in the second, the memory used to store a fully formed Association object.

Evaluation

The second aspect is evaluation. Since WL's expressions can represent both data and (possibly unevaluated) code, it is easy to mix the two together in such a way, that deserialization of a serialized expression would require a complex evaluation strategy to evaluate selectively some inner parts of an expression but not others - given that there are objects which are only fully constructed when evaluated, and which WXF does not by itself fully construct.

It is important to realize that WXF deserializer can not and should not, by itself, implement any non-trivial evaluation semantics. Its role is only to reconstruct WL expressions based on its spec and the binary serialized form of an expression. It does not call the main evaluator at any stage, and it creates WL expressions based purely on the information it finds in the serialized form.

For certain specific types of objects, WXF format has special tokens to indicate objects that can be constructed directly in memory. For all the others, they will be constructed as normal WL expressions. If those actually represent raw objects, then they will end up in a not fully constructed form of object-defining expressions, rather than fully formed objects - just as it was the case for Rational in the original example. And if they happen to be inside some held (sub)expressions, then the main evaluation procedure won't reach them either, during the normal evaluation of expression after it has been deserialized. So, they will remain expressions. In such cases, some special postprocessing will then be needed to evaluate those in-place and convert them to fully formed objects, already after the expression has been deserialized.

---

I'd like to stress that this has nothing to do specifically with Association. Here is an example involving just Hold instead:

held = Hold @ Evaluate [5/7]
heldProcessed = BinaryDeserialize @ BinarySerialize @held
held === heldProcessed
ByteCount /@ {held, heldProcessed}
Map[f, {held, heldProcessed}, {3}]

(*

  Hold[5/7]

  Hold[Rational[5, 7]]

  True

  {104, 136}

  {Hold[5/7], Hold[Rational[f[5], f[7]]]}

*)

where we observe the same behavior - the round-tripped object became an expression, which shows in how Map and ByteCount produce different results. That despite the fact that SameQ returns True - which can be explained by recalling that SameQ is based on structural comparison. You could also use Complex in place of Rational, and observe the same thing.

OTOH, this shows once again, that there are two semantically inequivalent forms of expressions for many types of objects, which however are treated as syntactically equivalent by Mathematica. Which is at best confusing, and at worst inconsistent, but this structural / semantic impedance mismatch can't be totally removed, since one can't hope to have all objects in the language to behave according to their purely structural form, and be able to do anything useful at the same time. So it must show up somewhere, and this is one of such places.

In a sense, this to a degree destroys the consistency of the "everything is an expression" principle. Here is where the previous discussion about the lack of the explicit constructors comes into play. Had there been explicit constructors for such objects, and there would've been a structural difference between fully formed and not fully formed objects, in which case everything would remain fully consistent with the principle. That said, things are unlikely to change. From the pragmatic viewpoint, one should simply be aware of this, because in the vast majority of cases (unlike the one under discussion) this issue doesn't show up.

---

Returning back to WXF, there seems to be no other way to operate, that would make sense for it, given that it aims at being language-agnostic and independent of any details of the WL kernel. But even if somehow WXF would be able to call the main evaluator, it would likely be very hard to deserialize arbitrary expressions correctly and efficiently, but also respect all the evaluation semantics of all held (sub)expressions involved in all cases, and avoid all kinds of evaluation leaks - since some parts of the serialized expressions could be held on purpose, and not at all intended for evaluation by the deserializer.

Turning back to the original example, the problem happens because Association is HoldAllComplete (but again, this general rule works for a fully formed association, and not for association constructor. But then the constructor has the same head, so we can't distinguish the two by their FullForm. The lack of the structural distinction between the constructor and fully evaluated expression hides the problem, but this is hardly a good thing here, since this is exactly what makes this much more confusing). WXF considers the assoc as a fully constructed one (which it certainly is in this case), that doesn't need further evaluation from the kernel, once deserialized. This can be seen as follows:

ByteArrayToString[BinarySerialize[<|3 -> 5/7|>], "ISO8859-1"]

(* "8:A-C\.03f\.02s\.08RationalC\.05C\.07" *)

As opposed to

ByteArrayToString[BinarySerialize[Unevaluated@<|3 -> Rational[5, 7]|>], "ISO8859-1"]

(* "8:fs\.0bAssociationf\.02s\.04RuleC\.03f\.02s\.08RationalC\.05C\.07" *)

(note the token A which stands for fully formed association, at the start of the first output, vs. Association in the second output).

So what is reconstructed back, is an expression representing a fully formed association, not a constructor for one - which is why in this case Rational has not been evaluated (since fully constructed association is inert and does not evaluate its elements). So the Rational inside remains a normal expression, not a formed Rational object. As was suggested in comments, in this particular case a relatively simple evaluation fixes the problem.

In general, the structure of the deserialized expression can be quite complex, and we may end up with a bunch of raw objects being held unevaluated as some deeply nested parts. What this means is that in general, at present, expressions involving raw objects can't be expected to round-trip properly. The best one can do is to perform certain particular post-processing, like the evaluation that was suggested to fix the original example.

Another possible method would've been to delay raw object's construction until "run-time". In the case in question, this would look e.g. like:

assoc1 = Association[3 -> 5/7]
assoc2 = BinaryDeserialize @ BinarySerialize @ Unevaluated @ Association[3 -> 5/7]

(* <|3 -> 5/7|> *)

(* <|3 -> 5/7|> *)

where in this case we serialize the constructor of an association, rather than a fully formed one - which enables it to evaluate upon deserialization.

Summary

The example in question shows an instance of a general problem of round-tripping WL expressions during WXF serialization / deserialization. A few observations can be made here:

• In general, WL expressions can not be expected to fully round-trip. In particular, when parts of expressions are so-called raw objects.

• The roots of the problem are the "everything is an expression" principle and the evaluation semantics of WL, and their implications. In particular:

  • For certain built-in objects (such as Association, SparseArray, etc.) structural functions such as Part, Map, etc. can't work based on their FullForm representation alone.
  • Therefore, such objects necessarily must have an object construction phase, and two non-identical forms, one representing an expression not yet formed, and the other representing a fully formed one. But their FullForm and InputForm are identical, which is unfortunate.
  • This is not so much a problem, so long as the entire work happens in the kernel, since it is rare to have to do work with an unevaluated expression representing some raw object. But it becomes a problem, when we try to round-trip such objects in a language-agnostic manner (i.e. WXF spec explicitly does not include any WL kernel - specific details).

• The second important ingredient of the problem is the evaluation semantics in WL, and in particular the non-standard evaluation and held expressions. In particular, these are what prevent WL evaluator from automatically reconstructing all raw objects from a deserialized expression.

• The lack of a structural distinction between a fully constructed expression, and an expression which is actually a constructor to be evaluated by the kernel, seems unfortunate.

• There are a number of methods (and their combinations) one can use, to deal with the round-tripping problem in each particular case. The two I will mention are

  • Expression post-processing with selective parts evaluation, after deserialization
  • Delaying raw object construction until run-time (serializing not fully formed objects, but effectively the code that would construct them)

  Which one to use when, depends on the case.