Seminar Program Synthesis

Seminar in Theoretical CS, Winter 2023/24

News

  • 17.05.2023: We are online!

Introduction and Assignment of Topics

  • Slides of introduction (TBA)

Dates & Deadlines

TBATopic preferences due
TBADetailed outline due
TBAFull report due
TBAPresentation slides due
TBASeminar talks

Note that the full versions of your report and your slides should be your final submissionand the camera-ready versions should differ only with regard to minor remarks, comments, and corrections by your supervisor. Please feel free, however, to talk to your supervisor about submitting preliminary versions before the due dates.

Overview

Program synthesis refers to the task of automatically finding a program in the underlying programming language that satisfies the user intent expressed in the form of some specification. This task is typically solved by performing some kind of search over the space of programs to generate a program that is consistent with the specification. The latter can be given in various forms, such as input/output examples, natural language, program templates, or logical assertions. A comprehensive overview to relevant approaches and techniques is provided in the survey report Program Synthesis by Sumit Gulwani, Oleksandr Polozov, and Rishabh Singh.

Prerequisites

Basic knowledge in Formal Languages and Automata Theory and Mathematical Logic is expected. For some of the topics, experience with Formal Semantics of Programming Languages and Probabilistic Programming is helpful.

Topics

No.TopicStudentSupervisor
Syntax-Guided Synthesis
1R. Alur, R. Bodik, G. Juniwal, M.M.K. Martin, M. Raghothaman, S.A. Seshia, R. Singh, A. Solar-Lezama, E. Torlak, A. Udupa: Syntax-guided synthesis. FMCAD 2013
2A. Solar-Lezama: Program Sketching. STTT 15, 2013
3A.V. Nori, S. Ozair, S.K. Rajamani, D. Vijaykeerthy: Efficient synthesis of probabilistic programs. ACM SIGPLAN Notices 50, 2015
Synthesis by Deductive Search
4S. Srivastava, S. Gulwani, J.S. Foster: From program verification to program synthesis. POPL 2010
5N. Polikarpova, I. Sergey: Structuring the Synthesis of Heap-Manipulating Programs. POPL 2019
Synthesis from Input/Output Examples
6J. Hamza, V. Kuncak: Minimal Synthesis of String To String Functions From Examples. VMCAI 2019
7S. Chasins, P.M. Phothilimthana: Data-Driven Synthesis of Full Probabilistic Programs. CAV 2017
8K. Shi, J. Steinhardt, P. Liang: FrAngel: component-based synthesis with control structures. POPL 2019
Synthesis by Equational Term Rewriting
9C. Smith, A. Albarghouthi: Program Synthesis with Equivalence Reduction. VMCAI 2019
Synthesis using Large Language Models
10J. Austin, A. Odena, M. Nye, M. Bosma, H. Michalewski, D. Dohan, E. Jiang, C. Cai, M. Terry, Q. Le, C. Sutton: Program Synthesis with Large Language Models. arXiv 2021
11E. Nijkamp, B. Pang, H. Hayashi, L. Tu, H. Wang, Y. Zhou, S. Savarese, C. Xiong: CodeGen: An Open Large Language Model for Code with Multi-Turn Program Synthesis. arXiv 2022

Registration

Registration to the seminar is handled via the SuPra system.

Grading Scheme

You can access the grading scheme here: https://moves.rwth-aachen.de/wp-content/uploads/seminar_grading_scheme.pdf

Additional Material

Contact

Thomas Noll