Teaching Booleans About Versions: A Theory-Augmented BDD Library in OCaml
What if checking whether two formulas with a million nodes are logically equivalent took exactly one machine instruction? Binary Decision Diagrams (BDDs) make this possible. They give you a canonical representation of boolean functions (two logically equivalent formulas always produce the exact same structure), which turns equivalence checking into a pointer comparison. Theo is an OCaml library…