Seminar Program Synthesis

Seminar in Theoretical CS, Winter 2023/24

News

17.05.2023: We are online!

Introduction

Slides of introduction

Dates & Deadlines

Oct 11, 2023; 16:30	Kick-off meeting (CS Department, building E1, 2nd floor, room 4201b)
Oct 16, 2023	Topic preferences due
Nov 20, 2023	Detailed outline due
Dec 18, 2023	Full report due
Jan 15, 2024	Presentation slides due
Jan 22, 2024 (afternoon)	Seminar 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.

Schedule of Talks

Time	Monday, January 22
14:00 – 15:30	Jakob van Sprang, Rico Stanosek, Krzysztof Kostrzewa
15:45 – 16:45	Yussur Mustafa Oraji, Andreas Holzinger
17:00 – 18:00	Dominik Geißler, Markus Rümenapp

Topics

No.	Topic	Student	Supervisor
Syntax-Guided Synthesis
1	R. 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	Yussur Mustafa Oraji	Lutz Klinkenberg
2	A. Solar-Lezama: Program Sketching. STTT 15, 2013	Dominik Geißler	Tobias Winkler
3	A.V. Nori, S. Ozair, S.K. Rajamani, D. Vijaykeerthy: Efficient synthesis of probabilistic programs. ACM SIGPLAN Notices 50, 2015	–	–
Synthesis by Deductive Search
4	S. Srivastava, S. Gulwani, J.S. Foster: From program verification to program synthesis. POPL 2010	–	–
5	N. Polikarpova, I. Sergey: Structuring the Synthesis of Heap-Manipulating Programs. POPL 2019	Jakob van Sprang	Thomas Noll
Synthesis from Input/Output Examples
6	J. Hamza, V. Kuncak: Minimal Synthesis of String To String Functions From Examples. VMCAI 2019	Markus Rümenapp	Tobias Winkler
7	S. Chasins, P.M. Phothilimthana: Data-Driven Synthesis of Full Probabilistic Programs. CAV 2017	–	–
8	K. Shi, J. Steinhardt, P. Liang: FrAngel: component-based synthesis with control structures. POPL 2019	Rico Stanosek	Thomas Noll
Synthesis using Large Language Models
9	J. 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	Andreas Holzinger	Lutz Klinkenberg
10	E. 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	–	–
Synthesis by Reinforcement Learning
11	D.J. Mankowitz et al.: Faster sorting algorithms discovered using deep reinforcement learning. Nature 618, 2023	Krzysztof Kostrzewa	Thomas Noll

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