Synthesizing Formal Semantics from Executable Interpreters
<|reference_start|>Synthesizing Formal Semantics from Executable Interpreters: Program verification and synthesis frameworks that allow one to customize the language in which one is interested typically require the user to provide a formally defined semantics for the language. Because writing a formal semantics can be a daunting and error-prone task, this requirement stands in the way of such frameworks being adopted by non-expert users. We present an algorithm that can automatically synthesize inductively defined syntax-directed semantics when given (i) a grammar describing the syntax of a language and (ii) an executable (closed-box) interpreter for computing the semantics of programs in the language of the grammar. Our algorithm synthesizes the semantics in the form of Constrained-Horn Clauses (CHCs), a natural, extensible, and formal logical framework for specifying inductively defined relations that has recently received widespread adoption in program verification and synthesis. The key innovation of our synthesis algorithm is a Counterexample-Guided Synthesis (CEGIS) approach that breaks the hard problem of synthesizing a set of constrained Horn clauses into small, tractable expression-synthesis problems that can be dispatched to existing SyGuS synthesizers. Our tool Synantic synthesized inductively-defined formal semantics from 14 interpreters for languages used in program-synthesis applications. When synthesizing formal semantics for one of our benchmarks, Synantic unveiled an inconsistency in the semantics computed by the interpreter for a language of regular expressions; fixing the inconsistency resulted in a more efficient semantics and, for some cases, in a 1.2x speedup for a synthesizer solving synthesis problems over such a language.<|reference_end|>
@article{liu2024synthesizing,
    title={Synthesizing Formal Semantics from Executable Interpreters},
    author={Jiangyi Liu, Charlie Murphy, Anvay Grover, Keith J.C. Johnson, Thomas
  Reps, Loris D'Antoni},
    journal={arXiv preprint arXiv:2408.14668},
    year={2024},
    archivePrefix={arXiv},
    eprint={2408.14668},
    primaryClass={cs.PL}
}