Program Synthesis

TA Anastasiia Izycheva, Raphaela Palenta
Time Tuesdays 14:00-15:30
Room 02.07.034
Module IN0014, IN2107, IN4922

Final Report


In the final report you should summarize everything you have learnt during the semester. More specifically, you should:

  • put key ideas of each paper in a general context of program synthesis,
  • relate papers to each other (inside one session's sub-topic and across them),
  • write down your thoughts and observations (the notes you made during discussion rounds should help you with that).

The report should be minimum 6, maximum 8 pages long. Please use the following template for Latex: template.tex. ACM Proceedings latex style is most likely already installed on your computer, but in case you're missing here is class file and bibstyle file.

We also provide you with the grading rubrics that express our expectations in a more structured way.


The submission deadline for the final report is August 11, 23:59 (Sunday). To submit send a pdf containing your report as an attachment to the email to both Anastasiia and Raphaela.


During the seminar we will touch the surface of the current research on program synthesis. We will see several applications and learn about techniques used to generate code automatically.

The seminar is intended for Master students, but advanced Bachelor students are welcome as well.

To get an access to papers in DL ACM and Springer you need to set up proxy.


Language: good written English

There are no formal prerequisites, but the words "formal methods", "verification", "search space" etc. should not scare you but rather inspire :)

Prior experience with program analysis, verification or automated reasoning is helpful.


All students are expected to be present during all sessions and read all papers.

Your final grade will be based on your activity during discussion sessions (20%), paper presentation (40%) and final report (40%). You have 20-25 minutes for the paper presentation.


30.04.2019 (Enumerative synthesis)

Lundholm: Scaling Enumerative Program Synthesis via Divide and Conquer
Kübrich: TRANSIT: Specifying Protocols with Concolic Snippets

moderators: Wilzbach, Nassif

14.05.2019 (Programming by example)
Backs: FrAngel: Component-Based Synthesis with Control Structures
Werner: Robust Relational Layout Synthesis from Examples for Android

moderators: Raya, Tellenbach

28.05.2019 (Machine-learned strategies)
Budanaz: Program Synthesis using Conflict-Driven Learning
Griebel: Accelerating Search-Based Program Synthesis using Learned Probabilistic Models

moderators: Yakymets, Kameter

18.06.2019 (Type-based synthesis)
Gottfriedsen:Program Synthesis from Polymorphic Refinement Types
Heinzelmann: Type-and-example-directed program synthesis

moderators: Backs, Werner

25.06.2019 (Counter-example guided synthesis)
Tellenbach: Counterexample Guided Inductive Synthesis Modulo Theories
Raya: Program sketching

moderators: Griebel, Budanaz

09.07.2019 (String-transformations)
Kameter: Minimal Synthesis of String To String Functions From Examples
Yakymets: Compositional Program Synthesis from Natural Language and Examples

moderators: Gottfriedsen, Heinzelmann

23.07.2019 (Database algorithms)
Wilzbach: SQLizer: Query Synthesis from Natural Language
Nassif: Synthesizing highly expressive SQL queries from input-output examples

moderator: Lundholm, Kübrich


Slides from the introductory meeting are here.

All presentations are available for download here. For accessing it use the credentials you received via email.

Interesting blog post explaining program synthesis on a high-level.