Definition of Program Synthesis
Program synthesis involves the automated generation of computer programs that satisfy a defined operational specification. The objective is to transition from manual code authorship to deterministic synthesis from requirements.
Technical Methodologies
- Inductive Synthesis: Generating code based on provided input-output examples (e.g., programming by example).
- Deductive Synthesis: Utilizing formal logic to mathematically derive a program implementation from its specification.
- LLM-Guided Synthesis: Leveraging AI to generate program candidates, followed by verification via automated solvers and unit testing.
Legacy and Evolutionary Synthesis
- Genetic Programming (GP): An evolutionary methodology that "evolves" computer programs to solve specific tasks through mutation and selection.
- ADATE (Automatic Design of Algorithms Through Evolution): A system for the automatic generation of recursive functional programs.
- Early LISP Synthesizers: 1970s research into automatically generating recursive LISP functions from input-output pairs.
- Rosette (GitHub): A solver-aided language that turns a high-level model into a specialized program synthesizer.
Operational Objective
The research focus is the automated synthesis of correct-by-construction binaries from verified requirements. This approach aims to eliminate implementation errors by replacing manual coding with formal generation pipelines.
Projects & Links
- DreamCoder (GitHub): A project combining neural networks with symbolic search to learn program abstractions.
- Microsoft PROSE (GitHub): A framework for inductive program synthesis utilized in enterprise data processing.