Program Reduction 101
From Delta Debugging to Perses and Syntax-Guided Reducers
Welcome
Program Reduction 101
Turn a 3,000-line failing program into a 26-line bug report. A practical and research-oriented guide to program reduction, from Delta Debugging to Perses and syntax-guided reducers.
What Is Program Reduction?
The missing step between finding a bug and understanding it.
A compiler fuzzer hands you a program with thousands of lines. The program crashes the compiler, but almost all of it is irrelevant. Before a developer can understand the bug, file a useful report, or add a regression test, someone has to shrink that program — without losing the failure.
That is program reduction. It turns “this generated program breaks the compiler” into “this small program explains the bug.”
The same problem appears everywhere structured inputs can fail: interpreters, static analyzers, theorem provers, database engines, build systems. In each case, the goal is not only to reproduce the failure, but to find a small artifact that still explains it.
What You Will Learn
Practice, theory, and research — all connected through Perses.
Run your first Perses reduction in Chapter 4. Write interestingness tests, inspect results, and build real debugging workflows.
Understand Delta Debugging, Hierarchical Delta Debugging, and how Perses uses grammar structure to search more efficiently.
Navigate the Perses research family: minimality, pairwise reduction, caching, LLM-guided reduction, and transformation power.
Reduce C, Rust, Java, Python, SMT-LIB, SQL, and more. Understand how grammar support extends Perses to new languages.
Who Should Read This
Choose a path based on what you need first.
Learning compilers, software testing, fuzzing, or debugging. Start at Chapter 1 and read sequentially.
Need to shrink large failure-inducing inputs into useful bug reports. Jump straight to Chapter 4.
Entering the program-reduction literature. Read the Perses Family chapter and the open problems chapter.
What You Will Be Able to Do
Concrete skills by the end of the book.
- Reduce a large failure-inducing input while preserving the target behavior
- Write an interestingness test that defines what Perses should keep
- Judge whether a reduced result is useful as a bug report, regression test, or research artifact
- Explain how Perses connects Delta Debugging, syntax-guided reduction, and the broader research family
- Navigate the open problems in program reduction and where research is heading
Why Perses
Perses is the center of this book because it captures a central insight of modern program reduction: programs are not just text, but structured artifacts with syntax. By using grammar information, Perses can search for smaller candidates while avoiding reductions that break the input before it reaches the target failure.
The original Perses paper introduced syntax-guided program reduction at ICSE 2018, led by Prof. Chengnian Sun and collaborators. Later Perses-family work at the University of Waterloo, with Prof. Sun’s students and collaborators including Yongqiang Tian, Zhenyang Xu, Mengxiao Zhang, Xueyan Zhang, Yiwen Dong, Jia Le Tian, Xintong Zhou, and Yiran Wang, extended the idea through minimality, pairwise reduction, caching, LLM-aided reduction, lexical guidance, and syntax-guided transformations. For details, see The Perses Family and Citing This Book and Perses.
About This Book Project
This book project was initiated by Dr. Yongqiang Tian, one of Prof. Chengnian Sun’s first students at Waterloo and now a Lecturer (Assistant Professor equivalent) at Monash University. Yongqiang has benefited deeply from Prof. Sun’s supervision and mentorship, and this book reflects that intellectual lineage.