Introduction
While declarative languages like Prolog are designed to allow programmers to focus on problem specification rather than procedural implementation, the reality of execution often forces a confrontation with the underlying inference engine. Misunderstandings of this engine—particularly regarding backtracking—lead to "procedural interference," where users struggle to distinguish between logic errors in their code and misconceptions about how that code is executed. This paper presents a prototype "consultant system" designed to debug the user's mental model by identifying specific deviations from standard Prolog logic.
The Prolog Execution Model
Central to the challenge of learning Prolog is mastering its procedural flow. The execution process is typically conceptualized through a "box model" involving four primary ports: CALL, EXIT, FAIL, and REDO. Transitions between these states define the search for solutions and the subsequent backtracking when a path fails. Understanding these transitions is critical for accurate mental execution of a program.
When a user's mental model of these transitions is flawed, they cannot accurately predict or trace program behavior. The consultant system addresses this by treating debugging as a search for a "hypothetical interpreter" that mirrors the user's incorrect expectations.
Methodology: Mal-Interpreters and Mal-Rules
The core of the diagnostic system is the "mal-interpreter." Unlike a standard interpreter, this modular engine allows for the substitution of correct procedural rules with "mal-rules"—intentional implementations of common human misconceptions. By swapping these modules, the system can simulate various flawed mental models and compare them against user-provided traces.
The diagnostic process involves several key steps:
- Trace Provision: The user provides a symbolic execution trace representing how they believe a specific program should run.
- Trace Comparison: The system compares the user's trace against its own internal trace generated by the mal-interpreter.
- Iterative Diagnosis: Upon finding a discrepancy, the system attempts to match the error to a known mal-rule, such as "redo-body-from-left."
- Tutoring: Once a misconception is identified, a tutoring module intervenes to correct the user's understanding before proceeding to check for deeper, nested errors.
Key Insights and Results
The research identified six primitive misconceptions that frequently plague Prolog users. One prominent example is the "redo-body-from-left" error, where a user incorrectly believes backtracking should restart from the leftmost subgoal of a clause. Another common bug is the "try-once-&-pass" misconception, where a user assumes a rule fails permanently after a single failed instantiation, ignoring subsequent backtracking opportunities.
Interestingly, the authors observed that these procedural errors are not exclusive to novices; experts also fall prey to them, albeit less frequently. This suggests that the lack of explicit syntactic markers for backtracking in Prolog makes mental execution inherently difficult for all users. The system's modular success in "plugging in" specific errors demonstrates a robust way to simulate and diagnose a wide variety of flawed mental models.
Conclusion and Future Work
The prototype demonstrates that debugging the human is a viable and necessary complement to debugging code. By modularizing the interpreter and formalizing misconceptions as mal-rules, the system can provide targeted pedagogical interventions. Future work aims to address the "consistency assumption"—the idea that users are consistently wrong in the same way—and to scale the system to handle the more complex "OR trees" (goal stacks) utilized by expert programmers as they move beyond simple AND-tree representations.
Summary updated