Optimal Program Synthesis via Abstract Interpretation - POPL 2024

Explore a groundbreaking 20-minute video presentation from POPL 2024 on optimal program synthesis using abstract interpretation. Delve into a novel framework for synthesizing programs with numerical constants that optimize quantitative objectives like accuracy across input-output examples. Learn how the proposed approach employs A* search with an abstract interpretation-based heuristic to improve scalability and provide optimality guarantees. Discover a strategy for constructing abstract transformers for monotonic semantics in domain-specific languages (DSLs) for data classification. Examine the implementation of this approach in existing DSLs and its superior scalability compared to current optimal synthesizers. Access supplementary materials, including reusable artifacts, to further explore this innovative research in program synthesis and optimization.