TL;DR
This paper introduces METALIFT, a novel framework that uses program synthesis to automatically build code transpilers for domain-specific languages (DSLs). By defining DSL semantics and search spaces, developers can leverage METALIFT to generate semantically equivalent code transformations, significantly reducing the effort and error-proneness associated with traditional transpiler development.
What Problem Does This Paper Address?
Developing compilers that translate general-purpose code into domain-specific languages (DSLs) is crucial for leveraging the performance and expressiveness of DSLs. Traditionally, this involves creating complex, pattern-matching rules, a process that is notoriously tedious, error-prone, and difficult to maintain as DSLs evolve. This paper addresses the challenge of building these transpilers more efficiently and reliably by employing program synthesis. The goal is to abstract away the complexities of transpiler development, making it accessible to developers without deep expertise in program synthesis.
Methods
METALIFT is a framework that automates the creation of code transpilers using program synthesis. The core idea is to replace manual rule-writing with an automated process that finds semantically equivalent code transformations. The process involves:
- DSL Semantics Definition: Developers define the semantics of their target DSL operators using METALIFT's specification language, MTL. This language is designed to be high-level and expressive, allowing for the definition of recursive and higher-order functions.
- Search Space Specification: Developers define the space of possible program transformations (summaries) that the synthesizer can explore. This is done using a context-free grammar (CFG) dialect of MTL, allowing for programmatic control over the search.
- Program Synthesis: METALIFT leverages external program synthesizers (like Rosette) to automatically find program summaries that are semantically equivalent to the input code, guided by the defined DSL semantics and search space.
- Verification: The synthesized summaries are formally verified for semantic equivalence to the source code using automated theorem provers (like Z3 and CVC5). This ensures the correctness of the generated transformations.
- Code Generation: Simple syntax-driven rules are used to translate the verified summaries into the concrete syntax of the target DSL.
A key innovation is the use of LLVM IR as an intermediate representation, allowing METALIFT to support multiple source languages. The framework also incorporates transformations for loop constructs to generate verification conditions.
Datasets
The paper evaluates METALIFT on benchmarks from prior work, specifically:
- Casper benchmarks: 44 out of 49 benchmarks from the Casper toolchain, which translates Java code to MapReduce operations.
- Domino benchmarks: All 10 benchmarks from the Domino DSL, which translates data-plane algorithms for programmable switches.
- Vector operation benchmarks: 5 array processing benchmarks, including stencil kernels and C++ code scraped from the web.
No new benchmarks were introduced.
Key Insights and Ideas
- Program Synthesis as a Transpiler Building Block: The paper demonstrates that program synthesis, when abstracted through a framework like METALIFT, can be a powerful and practical approach for building DSL transpilers, significantly reducing development effort.
- MTL as a Unified Specification Language: The MTL language serves as a crucial abstraction layer, allowing developers to define DSL semantics, search spaces, and verification conditions in a unified and accessible way.
- Separation of Concerns: METALIFT effectively separates the concerns of DSL semantics definition, search space exploration, synthesis, and code generation, making the overall process more manageable.
- Formal Verification for Trust: The integration of formal verification ensures that the generated transpiler transformations are semantically equivalent to the source code, providing a high degree of confidence in the output.
- Reduced Development Effort: The most striking insight is the dramatic reduction in lines of code required to build transpilers compared to traditional methods, highlighting the efficiency gains offered by METALIFT.
Key Results
- METALIFT successfully built three DSL transpilers targeting different application domains (Spark, Domino, and Vector Operations).
- The transpilers built using METALIFT required orders-of-magnitude fewer lines of code compared to prior specialized implementations. For instance, the Casper implementation required less than 1000 lines of code, compared to 25578 lines for Casper.
- The generated code had the same structure as that produced by prior tools, suggesting comparable performance.
- METALIFT successfully synthesized all 10 Domino benchmarks, requiring 74% fewer lines of code than the original Domino compiler.
- The framework translated all 5 vector operation benchmarks with an average running time of ~2 minutes, requiring less than 500 lines of code for the transpiler.
Limitations and Future Work
- Synthesizer Timeout: The synthesizer timed out on a few benchmarks, particularly for the Casper case study. This is attributed to METALIFT's reliance on LLVM for VC generation, which may be less optimized than specialized VC generators for specific languages.
- Bounded Synthesis: To manage complexity, METALIFT employs bounded synthesis, which only guarantees correctness for a finite set of program states. Full verification is performed afterwards.
- Future Work: The authors suggest several promising directions:
- Leveraging dynamic execution traces to automatically infer loop invariants.
- Improving synthesis with neuro-symbolic methods to learn effective search strategies.
- Integrating oracle-guided synthesis methods to extend the expressive power of synthesis queries.
- Making METALIFT modular to easily incorporate these optimizations.
Summary updated