Algorithm visualization using concrete and abstract shape graphs
Sascha A. Parduhn, Raimund Seidel, Reinhard Wilhelm · 2008
Traditional algorithm animation attempts to provide visualizations of the of a program on concrete In recent years a different approach has been proposed which attempts to visualize an execution on data. This is based on Cousots' notion of abstract interpretations, in particular in the case of programs manipulating pointer structures this is based on so-called analysis. Shape analysis maps all possible heap configurations that can arise during a program's executions (a potentially unbounded set) to a finite number of shape and it maps steps of the program to transitions between graphs. Every concrete of the program then corresponds to a sequence of transitions among graphs, the execution. Visualizing such an abstract is desirable since sets of graphs in a very strong sense encode invariants of the program and understanding the effect of a program usually benefits more from grasping what stays invariant than from seeing what changes. In this paper we combine the two approaches and argue for simultaneously visualizing a concrete and the corresponding abstract of a program. We have built a Visualizer for programs manipulating pointer structures that realizes this combined abstract/concrete visualization. It uses TVLA to automatically perform the analysis of a program. It allows to present abstract and concrete views in an extremely customizable way. This paper however does not present our Visualizer, but focuses on the technique to combine concrete and abstract visualizations.