Strange Loop Conference | "Program Synthesis: A Dream Realized?" by Roopsha Samanta @StrangeLoopConf | Uploaded October 2021 | Updated October 2024, 1 week ago.
The dream of program synthesis seeks to automatically create programs that conform to a user’s intent. Classically, program synthesis has been framed as a problem of generation of correct-by-construction programs from complete, formal specifications of their expected behavior. An increasingly favored and more tractable paradigm of program synthesis, however, is inductive program synthesis. Broadly construed, inductive program synthesis can be framed as a problem of generalizing partial specifications of program behavior, such as a set of input-output examples, into programs that are potentially correct over the entire input domain.
Unfortunately, similar to other inductive reasoning engines such as AI-based systems, inductive synthesis engines encounter challenges like overfitting, ambiguity, and brittleness. Thus, while the synthesized program may indeed conform to its partial specification, it may not exhibit the intended behavior on unseen inputs. PL researchers have been trying to tackle these problems through syntactic inductive biases applied to the space of candidate programs. However, the dream of program synthesis is yet to be realized.
In this talk, I will present a gentle introduction to classical and inductive program synthesis, illustrate common problems faced by inductive reasoning engines and common inductive biases used to offset the problems, and describe my group’s semantics-guided approach to improve the generalizability and robustness of inductive synthesis engines.
Roopsha Samanta
@roopshasamanta
Recorded at Strange Loop 2021
thestrangeloop.com
The dream of program synthesis seeks to automatically create programs that conform to a user’s intent. Classically, program synthesis has been framed as a problem of generation of correct-by-construction programs from complete, formal specifications of their expected behavior. An increasingly favored and more tractable paradigm of program synthesis, however, is inductive program synthesis. Broadly construed, inductive program synthesis can be framed as a problem of generalizing partial specifications of program behavior, such as a set of input-output examples, into programs that are potentially correct over the entire input domain.
Unfortunately, similar to other inductive reasoning engines such as AI-based systems, inductive synthesis engines encounter challenges like overfitting, ambiguity, and brittleness. Thus, while the synthesized program may indeed conform to its partial specification, it may not exhibit the intended behavior on unseen inputs. PL researchers have been trying to tackle these problems through syntactic inductive biases applied to the space of candidate programs. However, the dream of program synthesis is yet to be realized.
In this talk, I will present a gentle introduction to classical and inductive program synthesis, illustrate common problems faced by inductive reasoning engines and common inductive biases used to offset the problems, and describe my group’s semantics-guided approach to improve the generalizability and robustness of inductive synthesis engines.
Roopsha Samanta
@roopshasamanta
Recorded at Strange Loop 2021
thestrangeloop.com
