Canonicalization Interning

This overview explains how normalization, structural keys, and interning let a compiler share one stored node between matching structures. This matters because sharing can avoid duplicate structure, but merging nodes without a valid identity rule can change the result. Imagine constructing the node and of A and B twice. An intern table maps a structural key to an existing node. The key must identify the operation and the compatible child identities, so equal-looking printed names do not accidentally merge different inputs. On the first request, no matching key is present, so a node is created and stored. On the second compatible request, the key finds that node. Both consumers can refer to N. This is an explanation of structural interning, not a claim that every implementation performs every possible canonical rewrite. And and its De Morgan expression compute the same Boolean function. Their written structures are different. A structural interning table does not automatically prove this equivalence or merge them unless an explicit canonicalization rule establishes a common form. Normalization first puts the children in the order required by the declared rule. A structural key describes the resulting operator and its children. Interning looks for a stored node with that key and reuses it when present. These are normalization, structural identity, and interning. Compare A AND B with B AND A. For this commutative operator, a stable child order can give the same normalized structure. Looking up its key then reuses one stored node. Compare A AND B with A OR B: the operator differs, so the keys must differ even when both happen to return one at A B equal 11. Canonical here means canonical under these rules, not a globally smallest representation of every equivalent Boolean function. Current compilation also has structural admission guards before building or cache lookup. An inadmissible expression is a refusal, not a failed Boolean identity. Work a second complete case with A 1, B 1. Keep this assignment fixed throughout the calculation. Each symbol retains the meaning already introduced; a new value does not create a new logical rule. At one one, both and and or return one. If a table merged their nodes solely because of this observed output, it would be wrong on other inputs. The input zero one is enough to separate them. A safe structural key identifies an operation and its children, not just a sampled result. This case establishes a specific contrast. Observed equality is not structural identity. Exact equivalence requires a stronger check. Keep the input, intermediate values, and conclusion together when comparing it with the previous case. The calculated answer belongs to this complete assignment under the stated rule. Agreement on one input does not justify merging two arbitrary expressions. And and or both return one at one one, but disagree at zero one. Structural identity, sampled agreement, and semantic equivalence must not be used interchangeably. A compiler may reject an input before evaluation because its shape or size is outside the accepted limits. That refusal is not the Boolean value false. No decision under the rule has been obtained; the requested computation was not admitted. A caller should distinguish accepted evaluations returning zero or one from refused inputs. Otherwise a resource-limit or unsupported-form error can masquerade as a logical decision. The correct fallback or error handling depends on that distinction. AND and OR can agree on one input and disagree on another, so one matching output does not justify merging their nodes. Safe sharing follows the declared normalization and structural-key rules, with a separate proof for any additional rewrite.