Search papers, labs, and topics across Lattice.
This paper introduces SPECTRA, a novel approach for determining behavioral equivalence in Scratch programs by leveraging lens-parametric observation relations that account for various causal divergence phenomena. The method compiles Scratch projects into a causal intermediate representation, enabling the identification of equivalence and differences through a rigorous framework that includes SMT obligations and VM-backed counterexample-guided refinement. Key results show that SPECTRA successfully evaluates all 444 validated pairs without false-equivalence claims, outperforming structural, dynamic-only, and LLM baselines in identifying nuanced behavioral discrepancies.
SPECTRA reveals that Scratch programs can be behaviorally equivalent despite significant syntactic differences, challenging traditional notions of program comparison.
Two Scratch programs can be syntactically far apart-renamed variables, split scripts, extracted custom blocks, or reordered initialization-and still behave identically; a one-block edit, such as replacing a blocking broadcast with an asynchronous one, can create divergences visible only under specific schedules. Deciding behavioral equivalence is central to automated feedback, grading support, and repair validation, yet tree differencing is too strict and single-run dynamic comparison is unsound for concurrent, random, and timing-dependent behavior. We observe that equivalence for block-based programs is lens-parametric: final state, frame traces, monitors, event causality, and debug traces induce different observation relations. SPECTRA makes this explicit through a taxonomy of causal divergence phenomena and observation lenses. It compiles Scratch projects into a causal IR of typed resources and semantic transactions, canonicalizes renamings, guards, and procedure bodies, quotients same-trigger concurrency with Mazurkiewicz trace normal forms, separates program order from races, and handles residual frontiers through SMT obligations and VM-backed counterexample-guided refinement. Conclusive verdicts carry evidence: equivalence by bijection and trace quotient, difference by a typed witness, and unresolved cases remain unknown. On a VM-witnessed mutation corpus from real Scratch projects, SPECTRA decides all 444 validated pairs and makes 0/158 false-equivalence claims on witnessed-different pairs under strict scoring. Structural, dynamic-only, and LLM baselines fail on the classes predicted by the taxonomy; ablations quantify the contribution of partial-order reduction and lens parametricity; and targeted scenarios expose ambiguous-mutant divergences missed by random testing.
