WEBVTT

1
00:00:00.000 --> 00:00:02.733
This overview explains how normalization,

2
00:00:02.733 --> 00:00:09.767
structural keys, and interning let a compiler share
one stored node between matching structures.

3
00:00:09.767 --> 00:00:17.967
This matters because sharing can avoid duplicate structure, but
merging nodes without a valid identity rule can change the result.

4
00:00:18.267 --> 00:00:23.100
Imagine constructing the node and of A and B twice.

5
00:00:23.100 --> 00:00:27.933
An intern table maps a structural key to an existing node.

6
00:00:27.933 --> 00:00:33.600
The key must identify the operation and the compatible child identities, so equal-looking

7
00:00:33.600 --> 00:00:38.433
printed names do not accidentally merge different inputs.

8
00:00:38.433 --> 00:00:44.967
On the first request, no matching key is present, so a node is created and stored.

9
00:00:44.967 --> 00:00:49.400
On the second compatible request, the key finds that node.

10
00:00:49.400 --> 00:00:52.333
Both consumers can refer to N.

11
00:00:52.333 --> 00:00:57.267
This is an explanation of structural interning, not a claim that every implementation

12
00:00:57.267 --> 00:01:01.733
performs every possible canonical rewrite.

13
00:01:01.733 --> 00:01:06.700
And and its De Morgan expression compute the same Boolean function.

14
00:01:06.700 --> 00:01:09.200
Their written structures are different.

15
00:01:09.200 --> 00:01:14.533
A structural interning table does not automatically prove this equivalence or merge them

16
00:01:14.533 --> 00:01:21.133
unless an explicit canonicalization rule establishes a common form.

17
00:01:21.167 --> 00:01:27.033
Normalization first puts the children in
the order required by the declared rule.

18
00:01:27.033 --> 00:01:32.300
A structural key describes the resulting operator and its children.

19
00:01:32.300 --> 00:01:38.233
Interning looks for a stored node with that key and reuses it when present.

20
00:01:38.233 --> 00:01:43.067
These are normalization, structural identity, and interning.

21
00:01:43.067 --> 00:01:46.433
Compare A AND B with B AND A.

22
00:01:46.433 --> 00:01:52.800
For this commutative operator, a stable child
order can give the same normalized structure.

23
00:01:52.800 --> 00:01:57.200
Looking up its key then reuses one stored node.

24
00:01:57.200 --> 00:02:00.500
Compare A AND B with A OR B:

25
00:02:00.500 --> 00:02:08.167
the operator differs, so the keys must differ even
when both happen to return one at A B equal 11.

26
00:02:08.167 --> 00:02:17.000
Canonical here means canonical under these rules, not a globally
smallest representation of every equivalent Boolean function.

27
00:02:17.000 --> 00:02:23.200
Current compilation also has structural admission
guards before building or cache lookup.

28
00:02:23.200 --> 00:02:28.965
An inadmissible expression is a refusal, not a failed Boolean identity.

29
00:02:28.965 --> 00:02:28.967
An inadmissible expression is a refusal, not a failed Boolean identity.

30
00:02:29.267 --> 00:02:33.400
Work a second complete case with A 1, B 1.

31
00:02:33.400 --> 00:02:36.833
Keep this assignment fixed throughout the calculation.

32
00:02:36.833 --> 00:02:41.100
Each symbol retains the meaning already introduced; a new value does not

33
00:02:41.100 --> 00:02:44.200
create a new logical rule.

34
00:02:44.200 --> 00:02:47.967
At one one, both and and or return one.

35
00:02:47.967 --> 00:02:51.767
If a table merged their nodes solely because of this observed output, it would

36
00:02:51.767 --> 00:02:53.933
be wrong on other inputs.

37
00:02:53.933 --> 00:02:57.200
The input zero one is enough to separate them.

38
00:02:57.200 --> 00:03:03.833
A safe structural key identifies an operation and its children, not just a sampled result.

39
00:03:03.833 --> 00:03:07.433
This case establishes a specific contrast.

40
00:03:07.433 --> 00:03:10.800
Observed equality is not structural identity.

41
00:03:10.800 --> 00:03:14.100
Exact equivalence requires a stronger check.

42
00:03:14.100 --> 00:03:18.067
Keep the input, intermediate values, and conclusion together when comparing

43
00:03:18.067 --> 00:03:20.067
it with the previous case.

44
00:03:20.067 --> 00:03:25.899
The calculated answer belongs to this complete assignment under the stated rule.

45
00:03:25.899 --> 00:03:25.900
The calculated answer belongs to this complete assignment under the stated rule.

46
00:03:26.200 --> 00:03:31.867
Agreement on one input does not justify merging two arbitrary expressions.

47
00:03:31.867 --> 00:03:37.267
And and or both return one at one one, but disagree at zero one.

48
00:03:37.267 --> 00:03:41.233
Structural identity, sampled agreement, and semantic equivalence must

49
00:03:41.233 --> 00:03:44.300
not be used interchangeably.

50
00:03:44.300 --> 00:03:49.133
A compiler may reject an input before evaluation because its shape or size

51
00:03:49.133 --> 00:03:51.600
is outside the accepted limits.

52
00:03:51.600 --> 00:03:55.133
That refusal is not the Boolean value false.

53
00:03:55.133 --> 00:04:01.267
No decision under the rule has been obtained; the requested computation was not admitted.

54
00:04:01.267 --> 00:04:05.700
A caller should distinguish accepted evaluations returning zero or

55
00:04:05.700 --> 00:04:07.967
one from refused inputs.

56
00:04:07.967 --> 00:04:13.933
Otherwise a resource-limit or unsupported-form error can masquerade as a logical decision.

57
00:04:13.933 --> 00:04:19.033
The correct fallback or error handling depends on that distinction.

58
00:04:19.033 --> 00:04:19.050
AND and OR can agree on one input and disagree on another,
so one matching output does not justify merging their nodes.

59
00:04:19.050 --> 00:04:27.200
AND and OR can agree on one input and disagree on another,
so one matching output does not justify merging their nodes.

60
00:04:27.200 --> 00:04:36.233
Safe sharing follows the declared normalization and structural-key
rules, with a separate proof for any additional rewrite.