"""Price the associativity bug: how much of an expression space notices it. Every number printed here is a pure function of (source, assoc). There is no clock, no RNG and no floating point in the toy, so two runs of this file produce byte-identical output. python3 demo.py # everything below python3 demo.py --pipeline # just section 1 """ import itertools import sys from interp import ( ADD_FLIPPED, CORRECT, FLIPPED, LEVELS, Bin, Neg, Num, parse, run, tokenize, ) OPERANDS = ("2", "3", "4") OPS = ("+", "-", "*", "/") def rule(title): print() print("=" * 68) print(f" {title}") print("=" * 68) def draw(node, prefix="", tail=True, root=True): """The AST as an indented tree. The shape is the point of the whole toy, so it gets drawn rather than described. """ if isinstance(node, Num): label = str(node.value) elif isinstance(node, Neg): label = "neg" else: label = node.op print(prefix + ("" if root else ("`-- " if tail else "|-- ")) + label) kids = [] if isinstance(node, Bin): kids = [node.left, node.right] elif isinstance(node, Neg): kids = [node.operand] child_prefix = prefix if root else prefix + (" " if tail else "| ") for i, kid in enumerate(kids): draw(kid, child_prefix, i == len(kids) - 1, root=False) def flat(n): """Every flat n-operand expression over OPERANDS and OPS. No parentheses, no prefix minus: this is the space the headline percentages are over. """ for nums in itertools.product(OPERANDS, repeat=n): for ops in itertools.product(OPS, repeat=n - 1): source = nums[0] for op, operand in zip(ops, nums[1:]): source += op + operand yield source, ops def survey(n, assoc, ops=OPS): """(total, agree, differ, Counter-ish list of differing operator pairs).""" total = agree = 0 culprits = {} examples = [] for source, opseq in flat(n) if ops == OPS else _flat_over(n, ops): total += 1 good, bad = run(source, CORRECT), run(source, assoc) if good == bad: agree += 1 else: culprits["".join(opseq)] = culprits.get("".join(opseq), 0) + 1 examples.append((source, good, bad)) return total, agree, total - agree, culprits, examples def _flat_over(n, ops): for nums in itertools.product(OPERANDS, repeat=n): for opseq in itertools.product(ops, repeat=n - 1): source = nums[0] for op, operand in zip(opseq, nums[1:]): source += op + operand yield source, opseq def pct(part, whole): return f"{100.0 * part / whole:6.2f}%" # --- 1. the pipeline ------------------------------------------------------ def section_pipeline(): rule("1. ONE INPUT, TWO PARSERS, TWO ANSWERS") source = "2-3-4" print(f"\n source {source!r}") print(" tokens " + " ".join( f"{k}:{v}" if k == "num" else k for k, v in tokenize(source))) for label, assoc in (("CORRECT (left, left, right)", CORRECT), ("FLIPPED (right, right, right)", FLIPPED)): tree = parse(source, assoc) print(f"\n assoc = {label}") print(f" tree {tree!r}") print(f" value {run(source, assoc)}") print(" shape") draw(tree, prefix=" ") print("\n The tokens are identical. The evaluator is identical.") print(" One line in Parser.binary chose -5 or 3.") # --- 2/3. the sweep ------------------------------------------------------- def section_sweep(): rule("2. HOW MUCH OF THE SPACE NOTICES") print(f"\n space: a op b op c, a,b,c in {{2,3,4}}, op in {{+,-,*,/}}") print(" no parentheses, no prefix minus") print(f" 3^3 * 4^2 = {len(list(flat(3)))} expressions\n") for label, assoc in (("FLIPPED both arithmetic levels", FLIPPED), ("ADD_FLIPPED the additive level only", ADD_FLIPPED)): total, agree, differ, _, _ = survey(3, assoc) print(f" {label} agree {agree:>4} / {total} ({pct(agree, total)})" f" differ {differ:>4}") rule("3. WHERE THE 108 LIVE") total, agree, differ, culprits, examples = survey(3, FLIPPED) print("\n operator pairs that can tell the two parsers apart:\n") for pair in sorted(culprits): print(f" {pair} {culprits[pair]:>3} of 27 operand triples") print(f"\n total {sum(culprits.values())} " f"and every other pair of the 16 differs in 0 of 27") print("\n the first six witnesses, in enumeration order:\n") for source, good, bad in examples[:6]: print(f" {source:<8} correct {str(good):>8} flipped {str(bad):>8}") # --- 4. decay ------------------------------------------------------------- def section_decay(): rule("4. THE BUG GETS LOUDER WITH LENGTH") print("\n operands expressions FLIPPED agree ADD_FLIPPED agree") for n in (3, 4, 5): t1, a1, _, _, _ = survey(n, FLIPPED) _, a2, _, _, _ = survey(n, ADD_FLIPPED) print(f" {n} {t1:>7} {a1:>7} {pct(a1, t1)}" f" {a2:>7} {pct(a2, t1)}") # --- 5. a hand-written test suite ----------------------------------------- SUITE = ("1+2", "2*3", "10-4", "8/2", "1+2*3", "(1+2)*3", "2*3+4", "4+2*3", "10-2-3", "100/10/2", "2*(3+4)", "1+2+3+4", "-5+3", "6/3*2", "(2+3)*(4-1)", "7", "2*3*4", "1+2-3+4") def section_suite(): rule("5. WOULD YOUR TEST SUITE HAVE CAUGHT IT") print("\n 18 tests of the kind a person writes for a calculator:\n") caught = 0 for source in SUITE: good, bad = run(source, CORRECT), run(source, FLIPPED) verdict = "CAUGHT" if good != bad else "passes" caught += good != bad print(f" {source:<13} correct {str(good):>6} flipped {str(bad):>6}" f" {verdict}") print(f"\n {caught} of {len(SUITE)} fail under the flipped parser;" f" {len(SUITE) - caught} are blind to it.") # --- 6. boundary ---------------------------------------------------------- def section_boundary(): rule("6. WHERE THE BUG CANNOT EXIST") print("\n restrict the operators, re-run the same sweep:\n") print(" operators operands expressions agree") for ops, ns in ((("+",), (3, 6)), (("*",), (3, 6)), (("+", "*"), (3, 6)), (("-",), (3, 6)), (("/",), (3, 6)), (("-", "/"), (3, 4))): for n in ns: total, agree, _, _, _ = survey(n, FLIPPED, ops=ops) print(f" {{{','.join(ops):<3}}} {n} {total:>8}" f" {agree:>8} {pct(agree, total)}") print("\n and one pair of parentheses ends the argument:\n") for source in ("2-3-4", "(2-3)-4", "2-(3-4)"): good, bad = run(source, CORRECT), run(source, FLIPPED) verdict = "DIFFER" if good != bad else "same" print(f" {source:<10} correct {str(good):>4} flipped {str(bad):>4}" f" {verdict}") print("\n prefix minus rides along; it starts nothing:\n") for source in ("-2-3", "-2*3/4", "2*-3*-4", "-2-3-4", "-2/3/4", "2-3--4"): good, bad = run(source, CORRECT), run(source, FLIPPED) verdict = "DIFFER" if good != bad else "same" print(f" {source:<10} correct {str(good):>5} flipped {str(bad):>5}" f" {verdict:<6} {parse(source, CORRECT)!r}") # --- 7. the same edit, as a fix ------------------------------------------- def section_power(): rule("7. THE SAME EDIT IS THE FIX FOR '^'") print(f"\n LEVELS = {LEVELS}") print(" a right fold on level 2 is not a bug; it is what '^' means.\n") all_left = ("left", "left", "left") print(" expression fold-left fold-right python") for source in ("2^3^2", "2^2^3", "4^3^2"): py = eval(source.replace("^", "**")) # noqa: S307 - literal ints only print(f" {source:<12} {str(run(source, all_left)):>9}" f" {str(run(source, CORRECT)):>10} {py:>10}") print("\n Python agrees with the right fold. Same line, opposite verdict:") print(" associativity is a per-operator fact, and the parser is where") print(" that fact is written down.") def main(): if "--pipeline" in sys.argv: section_pipeline() return section_pipeline() section_sweep() section_decay() section_suite() section_boundary() section_power() print() if __name__ == "__main__": main()