Abstract
Proof Blocks is a software tool which enables students to write proofs by dragging and dropping prewritten proof lines into the correct order. These proofs can be graded completely automatically, enabling students to receive rapid feedback on how they are doing with their proofs. When constructing a problem, the instructor specifies the dependency graph of the lines of the proof, so that any correct arrangement of the lines can receive full credit. This innovation can improve assessment tools by increasing the types of questions we can ask students about proofs, and can give greater access to proof knowledge by increasing the amount that students can learn on their own with the help of a computer.
Introduction: Bridging the Gap in Proof Education
Mathematical proofs are the bedrock of computer science theory, yet they remain notoriously difficult to teach and learn. Students often struggle to make the leap from observing an instructor construct a proof to staring at a blank page themselves. This "blank page syndrome" is compounded by a significant feedback gap: unlike programming, where a compiler provides instant error messages, proofs are typically graded manually. In large courses, students may wait weeks to discover a logical error made on the first page of an assignment.
To address these challenges, researchers from the University of Illinois at Urbana-Champaign developed Proof Blocks. This software tool provides scaffolded practice by allowing students to assemble proofs from pre-written lines, offering the immediate, automated feedback necessary for effective learning.
The Proof Blocks Solution
Proof Blocks is inspired by "Parsons’s Problems," a well-established method in computer science education where students arrange shuffled lines of code into a functional program. In the context of proofs, students are presented with a set of blocks, each containing a mathematical statement or a step in an argument.
By providing the "blocks," the tool removes the initial cognitive load associated with syntax, notation, and linguistic clarity. This allows beginners to focus entirely on the logical flow and structure of the argument. It serves as a crucial "middle ground" assessment—more challenging than multiple-choice questions but less daunting than free-form proof writing.
The Grading Engine: Dependency Graphs
The core innovation of Proof Blocks lies in its flexible grading mechanism. Traditional autograders often require a single "correct" linear sequence, which is antithetical to the nature of mathematical writing where multiple valid paths often exist.
Instead, Proof Blocks utilizes Directed Acyclic Graphs (DAGs) to define logical dependencies. When an instructor creates a problem, they specify which lines must precede others. For example, if Line B relies on a variable defined in Line A, the DAG indicates a dependency from A to B.
The autograder accepts any topological sort of this graph as a correct solution. This allows for the natural flexibility of mathematical writing while maintaining rigorous logical standards. The system also supports subproofs—essential for proofs by induction or cases—ensuring that blocks belonging to a specific sub-argument remain contiguous.
Evaluation and Real-World Impact
The researchers evaluated Proof Blocks through a large-scale deployment in a discrete mathematics course at UIUC during the Fall 2020 semester, involving over 400 students. The tool was integrated into the PrairieLearn platform for both practice and exams.
The results were overwhelmingly positive:
- Student Reception: Out of 51 surveyed students, 46 found the interface easy to use, and over two-thirds felt the tool accurately reflected their understanding of proofs.
- Efficiency: The tool saved hundreds of hours of manual grading time, allowing course staff to focus on direct student support.
- Equity: Automated feedback provides "in-flow" guidance to students who may not be able to attend traditional office hours, democratizing access to proof-writing mastery.
Limitations and Future Work
While successful, the authors acknowledge current limitations. Students are currently restricted to provided lines rather than generating their own statements. Furthermore, the system's accuracy depends on the instructor's DAG; unnecessary "stylistic" dependencies can lead to unfair penalties.
Future developments include "Faded Parsons’s Problems," where students fill in blanks within blocks, and algorithms to automatically generate Proof Blocks from LaTeX source code, potentially scaling the tool's library across various mathematical disciplines.
Summary updated