Intention-Based Diagnosis of Programming Errors

W. Lewis Johnson, Elliot SolowayAAAI 1984

In the early days of AI in education, researchers sought to move beyond simple syntax checking toward systems that could understand the logic of novice programmers. This 1984 paper introduces PROUST, a diagnostic system designed to "read the mind" of students by modeling their underlying intentions. By doing so, PROUST can diagnose deep logic errors and the specific misconceptions that cause them.

The Challenge of Novice Programming

Debugging novice code is notoriously difficult for automated systems. Beginners don't just make typos; they often have fundamental misconceptions about loop structures, data flow, and problem decomposition. Traditional debugging methods typically fail for two reasons:

  1. Symptom-based analysis is too shallow, as many different errors can manifest as the same failure.
  2. Causal behavior analysis (like symbolic execution) is often derailed by the bugs themselves; if the code is fundamentally broken, its execution path no longer reflects the student's actual goal.

The primary challenge is variability. Novices solve problems in highly idiosyncratic ways. To be effective, a debugger must understand the student's goal to determine if their implementation is a valid (but buggy) attempt or a total misunderstanding.

Methodology: Intention-Based Diagnosis

The core innovation of PROUST is Intention-Based Diagnosis. Instead of analyzing what the code does, the system analyzes what the code was meant to do through a process called Goal-Plan Analysis.

PROUST is provided with a description of a problem, which it breaks down into a set of Goals (e.g., "Input a sequence," "Sum the values"). It then utilizes a Knowledge Base of Plans—stereotypic ways to achieve these goals. For example, a student might choose a WHILE loop or a REPEAT loop for a sentinel-controlled input sequence.

Figure 1: PROUST maps high-level programming templates (plans) like 'PROCESS-READ WHILE' to actual code segments to understand student intent.

When PROUST attempts to match a student's code to a known plan and fails, it identifies a "plan difference." It then consults a Bug Catalog to see if that difference matches a known novice misconception, such as using an IF statement where a WHILE loop is required. For complex cases where multiple intentions might fit, PROUST performs a Differential Diagnosis, comparing hypothetical goal structures and selecting the one that best explains the student's code.

Evaluation and Results

The system was evaluated using the "Rainfall Problem," a classic benchmark in computer science education research. The evaluation involved hundreds of PASCAL programs written by students, with "ground truth" established by human graders.

Figure 4: Performance metrics for PROUST across different test sets, showing high accuracy in bug recognition for completely analyzed programs.

PROUST demonstrated impressive accuracy for an early AI system. In its initial large-scale test (Test 1), it provided a "Complete Analysis" for 75% of the programs. Within those programs, it correctly identified 95% of the bugs. Notably, the system frequently identified errors that human graders had missed during manual review. Even when programs were too confusing for a full analysis, PROUST could often provide a "Partial Analysis," identifying a significant portion of the bugs in specific code fragments.

Key Insights and Limitations

The success of PROUST highlights that bugs are often not random failures but the logical output of malformed mental models. By treating bugs as misconceptions, PROUST provides pedagogically useful feedback rather than just error locations.

However, the system has notable limitations:

  • Fragility: Between 5% and 17% of programs remained "unanalyzable" if the student's approach was too fragmented or unique.
  • Knowledge Engineering: PROUST relies on a pre-defined library of goals and plans. Scaling this to more complex or open-ended tasks would require significant effort.
  • Language Specificity: While the framework is theoretically language-agnostic, the implementation was tied to PASCAL.

Despite these hurdles, PROUST proved that understanding programmer intent is a powerful and necessary component of automated programming instruction, paving the way for future intelligent tutoring systems.

Summary updated

BibTeX
@inproceedings{johnson1984intention,
  author = {W. Lewis Johnson and Elliot Soloway},
  title = {{Intention-Based Diagnosis of Programming Errors}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1984},
}
Figure