Predicate Optimizations (when targeting Wizard)

[ejrgilbert]

Overview

When targeting Wizard, predication will have to be done more strategically. Predicate expressions contain both static and dynamic data. Wizard supports evaluating static predicates at match time, so the whamm compiler will need to split out the static and dynamic portions of the predicate.

In the simplest case, if there is a dynamic portion of the predicate, the entire predicate is treated as dynamic. However, there can be some optimizations to this as follows.

Basis

Color guide:

• ${{\color{Aquamarine}{static part}}}$
• ${{\color{Red}{dynamic part}}}$

Expression	Static Part	Dynamic Part
${{\color{Aquamarine}{A}}}$ || ${{\color{Red}{B}}}$	${{\color{Aquamarine}{/\$A(..)/}}}$	${{\color{Red}{\{\}}}}$
second for ^^	${{\color{Aquamarine}{/!\$A(..)/}}}$	${{\color{Red}{\{B\}}}}$
${{\color{Aquamarine}{A}}}$ && ${{\color{Red}{B}}}$	${{\color{Aquamarine}{/\$A(..)/}}}$	${{\color{Red}{\{B\}}}}$
${{\color{Aquamarine}{A}}}$ == ${{\color{Red}{B}}}$	${{\color{Aquamarine}{/\$A(..)/}}}$	${{\color{Red}{\{B\}}}}$
second for ^^	${{\color{Aquamarine}{/!\$A(..)/}}}$	${{\color{Red}{\{!B\}}}}$
${{\color{Aquamarine}{A}}}$ != ${{\color{Red}{B}}}$	${{\color{Aquamarine}{/\$A(..)/}}}$	${{\color{Red}{\{!B\}}}}$
second for ^^	${{\color{Aquamarine}{/!\$A(..)/}}}$	${{\color{Red}{\{B\}}}}$

Given this basis, a pattern arises.

If we categorize parts of the predicate as either static or dynamic, we can use constant propagation to find each case to generate.

1. Categorize each lowest-level expression as static or dynamic (default to dynamic is something is mixed)
2. For the static and dynamic sets, generate truth table cases
3. Constant propagate each truth table case
4. Collect results and simplify

Example

( ${{\color{Aquamarine}{X}}}$ || ${{\color{Red}{Y}}}$ ) || ${{\color{Red}{B}}}$

2a) Dynamic Truth Table

${{\color{Aquamarine}{X}}}$
true
false

2b) Static Truth Table

${{\color{Red}{Y}}}$	${{\color{Red}{B}}}$
true	true
true	false
false	true
false	false

3a) Dynamic constant propagation

${{\color{Aquamarine}{X}}}$ = true

(true || ${{\color{Red}{Y}}}$ ) || ${{\color{Red}{B}}}$
true || ${{\color{Red}{B}}}$
true

${{\color{Aquamarine}{X}}}$ = false

(false || ${{\color{Red}{Y}}}$ ) || ${{\color{Red}{B}}}$
${{\color{Red}{Y}}}$ || ${{\color{Red}{B}}}$

3b) Static constant propagation

(${{\color{Aquamarine}{X}}}$ || true ) || true => true
(${{\color{Aquamarine}{X}}}$ || true ) || false => true
(${{\color{Aquamarine}{X}}}$ || false ) || true => true
(${{\color{Aquamarine}{X}}}$ || false ) || false => ${{\color{Aquamarine}{X}}}$

4) Collect and Simplify

| ${{\color{Aquamarine}{/\$X(..)/}}}$ | ${{\color{Red}{\{\}}}}$ |
| ${{\color{Aquamarine}{/!\$X(..)/}}}$ | ${{\color{Red}{\{Y||B\}}}}$ |

[ejrgilbert]

(Can also do some optimizations when I'm just emitting expressions, see crafting interpreters)