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

Instructor	Yuepeng Wang
Time and Location	Tue 10:30 am - 12:20 pm @ WMC2503 Fri 10:30 am - 11:20 am @ AQ4140
Instructor Email	yuepeng@sfu.ca
Instructor Office Hours	Fri 11:30 am - 12:30 pm or by appointment
TA	Yang He
TA Email	yha244@sfu.ca
TA Office Hours	Tue 2:00 - 3:00 pm @ 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 20%
• Presentation 20%
• Projects 40%
• Class Participation 20%
All paper reviews and projects must be your own work.

Tentative Schedule

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

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).