WEBVTT

1
00:00:00.000 --> 00:00:08.167
This overview explains how an occurrence-based syntax-tree
evaluator can repeat the same logical computation.

2
00:00:08.167 --> 00:00:11.867
A deliberately raw evaluator exposes duplication,

3
00:00:11.867 --> 00:00:17.684
but it is not automatically a fair substitute
for a stronger memoized comparator.

4
00:00:17.684 --> 00:00:17.700
but it is not automatically a fair substitute
for a stronger memoized comparator.

5
00:00:18.000 --> 00:00:21.533
This expression contains A and B twice.

6
00:00:21.533 --> 00:00:25.567
Use A one, B one, and C zero.

7
00:00:25.567 --> 00:00:30.800
In a raw tree, the left occurrence and the nested occurrence can be separate nodes even

8
00:00:30.800 --> 00:00:34.000
though they print identically.

9
00:00:34.000 --> 00:00:36.500
Visit the left branch first.

10
00:00:36.500 --> 00:00:41.233
Read A and B and combine one with one, producing one.

11
00:00:41.233 --> 00:00:45.867
Keep that value visible while following a simple eager tree evaluator into the other

12
00:00:45.867 --> 00:00:52.933
branch; an evaluator that short-circuits or simplifies is a different declared model.

13
00:00:52.933 --> 00:00:58.533
The raw eager traversal computes A and B again, getting another one.

14
00:00:58.533 --> 00:01:03.667
It combines that one with C zero, giving zero, and then combines the two branches

15
00:01:03.667 --> 00:01:05.967
by or to obtain one.

16
00:01:05.967 --> 00:01:10.300
The duplicate calculation is visible in the trace, not inferred merely

17
00:01:10.300 --> 00:01:13.622
from the written formula.

18
00:01:13.622 --> 00:01:13.633
from the written formula.

19
00:01:13.633 --> 00:01:18.833
A raw occurrence-based evaluator follows written syntax.

20
00:01:18.833 --> 00:01:25.433
The left and right branches each contain
A AND B, the subexpression named S.

21
00:01:25.433 --> 00:01:30.700
There are two occurrences even if the subexpression has the same meaning.

22
00:01:30.700 --> 00:01:39.233
At 11011, an occurrence traversal computes
A AND B for the left branch and again for the right.

23
00:01:39.233 --> 00:01:44.700
The two visits are separate executions
before their branches feed the final OR.

24
00:01:44.700 --> 00:01:50.867
Our companion teaching evaluator deliberately omits memoization here.

25
00:01:50.867 --> 00:01:59.067
The contrast is with a memoized traversal over
the same rule, checked across all 32 assignments.

26
00:01:59.067 --> 00:02:03.567
This is an ablation that exposes duplication.

27
00:02:03.567 --> 00:02:09.867
The current direct BitSet implementation
already memoizes shared object identities,

28
00:02:09.867 --> 00:02:15.533
so it cannot automatically stand in for this raw occurrence evaluator.

29
00:02:15.533 --> 00:02:21.733
Use a deliberately declared raw control,
and do not call it the strongest comparator.

30
00:02:22.038 --> 00:02:29.483
Return to the opening three-input tree: F equals A and B, or the conjunction of A and B with C.

31
00:02:29.483 --> 00:02:33.329
This is separate from the intervening five-input tree.

32
00:02:33.329 --> 00:02:42.443
Set A to one, B to zero and C to one, and evaluate both copies under the same eager traversal.

33
00:02:43.193 --> 00:02:51.683
Under the declared eager raw traversal, the two occurrences of A and B are both evaluated and both return zero.

34
00:02:51.683 --> 00:02:57.213
The nested right branch then combines zero with C one, remaining zero.

35
00:02:57.213 --> 00:02:59.829
The root or returns zero.

36
00:02:59.829 --> 00:03:06.756
A different input has changed the values but not eliminated the duplicate subexpression from the tree.

37
00:03:07.506 --> 00:03:11.271
This case establishes a specific contrast.

38
00:03:11.271 --> 00:03:14.781
Eager trace evaluates both copies.

39
00:03:14.781 --> 00:03:19.057
Simplification or short-circuiting is a separate model.

40
00:03:19.057 --> 00:03:26.422
Keep the input, intermediate values, and conclusion together when comparing it with the previous case.

41
00:03:26.422 --> 00:03:33.226
The calculated answer belongs to this complete assignment under the stated rule.

42
00:03:33.518 --> 00:03:38.818
A memo keyed by a compatible subexpression and evaluation context can reuse the first

43
00:03:38.818 --> 00:03:41.318
result at the second occurrence.

44
00:03:41.318 --> 00:03:44.318
That changes the execution strategy.

45
00:03:44.318 --> 00:03:48.252
The same source formula can therefore have different costs under a raw

46
00:03:48.252 --> 00:03:52.318
traversal and a memoized evaluator.

47
00:03:52.318 --> 00:03:57.185
If a memo is keyed only by object identity, two separately allocated nodes

48
00:03:57.185 --> 00:03:59.385
may not share an entry.

49
00:03:59.385 --> 00:04:04.418
Equal printed text does not guarantee identical runtime objects.

50
00:04:04.418 --> 00:04:11.418
A structural sharing or canonicalization step may be needed to connect those identities.

51
00:04:11.418 --> 00:04:16.952
State these details before calling a comparator a raw evaluator.

52
00:04:16.952 --> 00:04:21.885
Otherwise a comparison can accidentally measure redundant work that another reasonable

53
00:04:21.885 --> 00:04:24.652
baseline already removes.

54
00:04:24.652 --> 00:04:31.618
The lesson is to inspect the execution mechanism, not just the formula's appearance.

55
00:04:31.618 --> 00:04:31.622
Distinguish written occurrences, stored objects, and executed work.

56
00:04:31.622 --> 00:04:37.452
Distinguish written occurrences, stored objects, and executed work.

57
00:04:37.452 --> 00:04:43.652
Declare the evaluator's reuse behavior before using it as a control.