CMPT 489 / 980 Special Topics in Programming Languages: Program Synthesis - Fall 2024

Instructor	Yuepeng Wang
Time and Location	Wed 11:30 am - 12:20 pm @ BLU10011 Fri 10:30 am - 12:20 pm @ BLU10011
Instructor Email	yuepeng@sfu.ca
Instructor Office Hours	Wed 2:00 - 3:00 pm or by appointment
TA	Xiaoyu Liu
TA Email	xla411@sfu.ca
TA Office Hours	Mon 11:00 am - noon @ Zoom

Course Description

This is a seminar-style special topics course on recent advancements in program synthesis. Program synthesis aims to generate programs automatically from high-level specifications, such as input-output examples, logical formulas, natural language descriptions, reference implementations, etc. Many techniques have been developed recently for program synthesis to support various applications in real-world scenarios. We will learn the applications, specifications, and algorithms of program synthesis from research papers.

Grading

• Paper Reviews 25%
• Presentation 25%
• Projects 40%
• Class Participation 10%
All paper reviews and projects must be your own work.

Tentative Schedule

Week	Date	Topic	Assign
1	09/04	Introduction
	09/06	Synthesis, Grammar, and DSL
2	09/11	Abstract Syntax Tree
	09/13	Inductive Synthesis	P
3	09/18	Boolean Satisfiability
	09/20	Satisfiability Modulo Theories
4	09/25	Satisfiability Modulo Theories
	09/27	[1] Recursive Program Synthesis. CAV'13 [2] Scaling Enumerative Program Synthesis via Divide and Conquer. TACAS'17	R1
5	10/02	[3] Synthesis Through Unification. CAV'15
	10/04	[4] Synthesizing Highly Expressive SQL Queries from Input-Output Examples. PLDI'17 [5] Component-Based Synthesis of Table Consolidation and Transformation Tasks from Examples. PLDI'17	R2
6	10/09	[6] Data Migration using Datalog Program Synthesis. VLDB'20
	10/11	[7] Synthesizing Data Structure Transformations from Input-Output Examples. PLDI'15 [8] Type-Directed Program Synthesis for RESTful APIs. PLDI'22	R3
7	10/16	Discussion
	10/18	[9] Programming by Demonstration Using Version Space Algebra. ML'03 [10] FlashMeta: a Framework for Inductive Program Synthesis. OOPSLA'15	R4
8	10/23	OOPSLA 2024
	10/25	[11] Program Synthesis using Abstraction Refinement. POPL'18 [12] egg: Fast and Extensible Equality Saturation. POPL'21	R5
9	10/30	Discussion
	11/01	[13] Oracle-Guided Component-Based Program Synthesis. ICSE'10 [14] Program Synthesis using Conflict-Driven Learning. PLDI'18	R6
10	11/06	[15] Program Sketching. STTT'13
	11/08	[16] Stochastic Superoptimization. ASPLOS'13 [17] Program Synthesis Using Deduction-Guided Reinforcement Learning. CAV'20
11	11/13	Discussion
	11/15	[18] DeepCoder: Learning to Write Programs. ICLR'17 [19] Jigsaw: Large Language Models Meet Program Synthesis. ICSE'22
12	11/20	[20] Fiat: Deductive Synthesis of Abstract Data Types in a Proof Assistant. POPL'15
	11/22	[21] Multi-modal Synthesis of Regular Expressions. PLDI'20 [22] Visualization Question Answering using Introspective Program Synthesis. PLDI'22
13	11/27	Discussion
	11/29	Time for Final Project

Academic Honesty Statement

Academic honesty plays a key role in our efforts to maintain a high standard of academic excellence and integrity. Students are advised that ALL acts of intellectual dishonesty will be handled in accordance with the SFU Academic Honesty and Student Conduct Policies (https://www.sfu.ca/policies/gazette/student.html).