System`Private`*Entry* and *Valid*, or: How does Mathematica know which expression is which?

Question

Goal

The answers to this question are intended to be a place to describe the behavior and mechanism of the undocumented functions of the form System`Private`*Entry* and System`Private`*Valid* (and any related functions). This is in somewhat the same style as the Language`* documentation project, but much more tightly focused, and maybe without the need to document each function individually (as many seem closely related).

I'm looking for detailed insight into what's happening internally, as opposed to simply how I might use such functions in an "engineering" way.

Rough Overview

The *Entry* functions are used to change (and detect) the way Mathematica traverses an expression, but not an expression "in the abstract" as we're used to it—an actual, specific instance of an expression in memory(?). Not all a[1]'s are the same!

The Valid functions can be used to set an internal flag on the same (and read it).

Are there other functions which ought to be included in this which also modify specific instances of data, or perhaps set different flags other than Valid?

If anyone wants to just contribute bits and pieces of knowledge, that's also welcome! I'll try to compile any such contributions in a CW and include anything I find out personally.

---

Motivation

System`Private`SetNoEntry

SetNoEntry lets us declare a specific instance of a Mathematica expression as atomic (AtomQ), and so prevents Mathematica from "entering" the expression somehow (e.g. for part extraction). I was reading this answer by Leonid Shifrin, and this comprehensive answer by Mr. Wizard, and started wondering if there are any systematic rules that tell us when Mathematica considers an expression "the same" internally.

Consider

t1 = a[1]
t2 = t1
t3 = (# &)[t1]
Block[{a}, t4 = t1]
t5 = ReplacePart[t1, 1 -> 1]
t6 = MapAt[Identity, t1, 1]

System`Private`SetNoEntry[t1];

AtomQ /@ {t1, t2, t3, t4, t5, t6, a[1]}

(* Out: {True, True, True, True, True, False, False} *)

All of these successfully refer to "the" a[1] in t1's OwnValues, except for a different instance of a[1], and one that's been altered by an evaluation. A close look at the evaluation of ReplacePart shows us that it (apparently) determined that the first part of a[1] was already 1, and didn't re-evaluate a[1]; so, it "didn't change". (A chained, nontrivial ReplacePart[ReplacePart[t1, 1 -> 0], 1 -> 1] does indeed change the expression identity, so this isn't intrinsic to ReplacePart.)

So, any complete-enough documentation of the behavior of these functions should be able to at least suggest how to approach the following: how do we check if two expressions are strictly the same internally or not? (Note that SameQ[t1, a[1]] gives True.)

In the same spirit, it seems that t1's ownvalues refer to some specific expression in memory, as opposed to simply being a rule that reconstructs an expression. This forces us to expand the "everything is an expression" abstraction a little bit, and makes us ask: when is it detectable that we're making a reference to a specific data structure in memory? How and when does Mathematica pin down certain expressions in memory, and when are we acting "in place" as opposed to making a copy?

System`Private`SetValid

A partial solution for how to check if two expressions are "really" the same is given in this answer by b3m2a1: set a System`Private`SetValid flag, and see when it disappears.

Note that these flags seem impervious to Block, suggesting, at the very least, that this flag is not among the dynamic properties typically attachable to a symbol:

Block[{s}, System`Private`SetValid[s]]; System`Private`ValidQ[s] (* Out: True *)

One would need to manually extract the state of each of the two expressions under the ValidQ functions, clear them both, set the flag of one of them, see if the other has it too, then restore the original Valid states. This seems doable, if a little tedious—but is there a better way, which somehow accesses the "identity" of the expression, and provides some insight on what's going on where?

---

Function list

Here's a list of all such functions. Many might be essentially redundant (easily explained based on the behavior of another), but here they all are anyway.

Note: except for System`Private`ValidMeijerGQ, which seems unrelated.

System`Private`*Entry*

• System`Private`SetNoEntry
• System`Private`EntryQ
• System`Private`NoEntryQ
• System`Private`HoldSetNoEntry
• System`Private`HoldEntryQ
• System`Private`HoldNoEntryQ
• System`Private`ConstructNoEntry

System`Private`*Valid*

• System`Private`SetValid
• System`Private`ValidQ
• System`Private`NotValidQ
• System`Private`HoldSetValid
• System`Private`HoldValidQ
• System`Private`HoldNotValidQ

The functions here of the form System`Private`*Hold* might well be the same as the ones without Hold in the name, except for the HoldAllComplete attribute, and might just perform the relevant {action on/assignment of flags to} a held argument instead of a fully-evaluated argument. So, they might not need any special treatment or documentation.

Likewise, the *Q functions might be straightforward given other info, but it could be a good chance to document under what circumstances they will evaluate to True.