Abstract: We describe a visual interactive framework that supports the computation of syntactic unifiers of expressions with variables. Unification is specified via built-in transformation rules. A user derives a solution to a unification problem by stepwise application of these rules. The software tool provides both a debugger-style presentation of a derivation and its history, and a graphical view of the expressions generated during the unification process. A backtracking facility allows the user to revert to an earlier step in a derivation and proceed with a different strategy.
Introduction
Unification is a fundamental operation in logic programming, automated theorem proving, and type inference. It involves finding a substitution—a set of variable assignments—that makes two symbolic expressions identical. Despite its mathematical precision, learning unification is often a dry and error-prone exercise in manual string manipulation. Most existing software tools lack the transparency needed for students to understand how a solution is reached, often presenting only the final result.
To address this gap, we introduce Kimberly, an educational software tool that transforms the abstract process of formal derivation into a visual, interactive experience. By combining a debugger-style interface with graph visualizations, it allows students to step through derivations, backtrack to explore different strategies, and see underlying data structures evolve in real-time.
Interactive Computation and Rule Application
Kimberly treats unification as a sequence of discrete, rule-based transformations, such as decomposition, orientation, and substitution. The tool employs a Model-View-Controller (MVC) architecture to maintain multiple synchronized "perspectives" (textual, tabular, and graphical).
The "Computation" panel serves as a debugger-style interface. It tracks the entire history of a derivation, allowing users to explore the state space non-deterministically. If a user reaches a dead end—such as an "occur-check" failure—they can backtrack to any previous step and attempt a different strategy.
Graphical Visualization of Terms
To move beyond the "wall of text" typical of symbolic expressions, Kimberly includes a "Visualization" panel. Internally, terms are represented as Directed Acyclic Graphs (DAGs). This representation is efficient for substitutions; instead of copying strings, the system simply redirects pointers in the graph.
The tool implements a novel layout engine to handle complex equations. Nodes are sorted topologically and mapped onto parallel circles, while edges are routed using a force-directed algorithm that treats them as elastic strings. This approach minimizes edge intersections and curvature, enhancing the readability of the resulting graph. While the tool supports 3D layouts to eliminate intersections, it uses highly structured, axially symmetric arrangements to maintain user orientation.
Key Insights and Results
Kimberly successfully demonstrates that unification can be taught as a state-space search. By visualizing the derivation history, students gain a deeper understanding of the strategies involved in choosing specific rules. Key results of this work include:
- A Functional Educational Tool: A single-document application capable of parsing, solving, and visualizing complex unification problems.
- Interactive Derivation: A suite of transformation rules that guarantee termination in either a solved form (the Most General Unifier) or an explicit failure state.
- Novel Layout Algorithms: An iterative edge-routing algorithm that produces structured, readable graph layouts for symbolic terms.
Limitations and Future Work
While Kimberly provides a robust framework, the authors acknowledge that the cognitive load of 3D visualizations requires further investigation. Future work will focus on adding automated node labeling and smooth animations for transitions between derivation steps. Additionally, the framework is designed to be extensible to other derivation-based methods, such as formal grammars and broader theorem-proving contexts.
Summary updated