Program Synthesis

Welcome to Program Synthesis Pub — a personal blog where I curate papers, review research, and collect resources around program synthesis and adjacent fields like machine learning, formal verification, mathematical logic, and other areas where synthesis ideas shine.

What is Program Synthesis?

At its core, Program Synthesis is about automatically generating programs that satisfy a given intent — without manually writing out the full implementation.

There are several ways to specify what we want a program to do:

1. Formal specifications — logical statements that describe the behavior precisely.
2. Input-output examples — showing what the correct outputs should be for given inputs.
3. Execution traces — recording the behavior we expect during program execution.
4. Machine learning models — using neural networks or other statistical models to guide or accelerate the search for programs.

In short: synthesis is a search problem, where the goal is to find a correct program that matches a desired behavior.

Program synthesis is not just machine learning (even though it sometimes uses ML). It is not only about code generation either — a “program” can mean any structured sequence of instructions, including mathematical procedures or strategies.

Get started now

Getting Started

Introduction

Program synthesis is not a brand-new idea — it has roots going back to the early days of computing — but it is still a young and rapidly evolving research field.

Some researchers even compare the current state of program synthesis to the state of deep learning research in the early 1990s: lots of excitement, important early breakthroughs, but much still to discover.

There are excellent early overviews like:

• Survey of Program Synthesis (Gulwani et al.)
• Program Synthesis Explained (James Bornholt)
• Program Synthesis 2017–2018 (Alex Polozov’s Blog)

However, many of these are now a few years old. This blog aims to update, expand, and curate a wider collection of research across various perspectives and adjacent topics.

Why Study Program Synthesis?

• Open research problems — There is still so much unexplored territory across theory, algorithms, and applications.
• Efficient computation — Many synthesis methods require much less compute than large-scale deep learning.
• Strong correctness guarantees — Instead of just approximating behavior, synthesis seeks programs that provably meet the desired intent.

A Simple Comparison

Here is a rough illustration of how program synthesis differs from traditional programming and machine learning:

# Traditional programming: you write the code manually
def magicNumber(parameter):
    result = parameter + 2
    return result

magicNumber(2)  # => 4

# Programming by Example (PBE): you give examples and the system infers the program
# Example: input 2 -> output 4, input 3 -> output 5
# The synthesizer figures out: "add 2"

# Machine Learning: you train a model to approximate a behavior
import some_deep_learning_library

def magicNumber(parameter):
    train, test = some_deep_learning_library.split_data(parameter)
    model = some_deep_learning_library.model.fit(train, test)
    return model.predict(parameter)

In program synthesis, we want the exact program, not just an approximate behavior. In machine learning, we approximate based on training data.

Thank you to the contributors of Program Synthesis Pub!

Code of Conduct

We are committed to fostering a respectful, welcoming community for everyone interested in program synthesis and related topics.

View our Code of Conduct.