Shape analysis for algorithm animation : strengths and weaknesses

Abstract

We present a non-traditional approach to algorithm visualization that is based on shape analysis, a static programm analysis, that so far has benn mostly used to verify program properties. Our approach differs from traditional visualizations: Instead of simulating a concrete program execution, we use the invariants produced by shape analysis to look at all possible program executions at the same time. This allows us to show meta level properties like correctness very easily, but at the price of a higher level of abstraction than most traditional visualizations. For example when sorting we do not model individual data values, but instead maintain a relation that tells us if a data value is smaller than another. Shape analysis is not a new technique, but its application to algorithm visualization is: The analysis output can quite naturally be interpreted as a set of graphs, however, suitable presentation of the shape analysis output requires preparation of the data. This includes methods to reduce the size of the analysis output and methods to make it easier to understand. The inherent abstraction also raises new problems. We discuss these problems and how they influence the layout of our visualization. We also give guidelines for creating analyses specifically with visualization in mind and provide a detailed description of an example analysis, that was created according to these guidelines. Lastly we implemented a visualization tool that was used as a testbed for many of the methods mentioned in the thesis and we will present a short overview of its features.

Wir präsentieren eine unübliche Herangehensweise an Algorithmenvisualisierung, die auf Shape Analyse basiert, eine statische Programmanalyse, die bisher hauptsächlich zum Verifizieren von Programmeigenschaften verwendet wurde. Unsere Herangehensweise unterscheidet sich von traditionellen Visualisierungen: Statt eine konkrete Programmausführung zu betrachten, verwenden wir Invarianten, die von Shape Analyse produziert wurden, um alle möglichen Programmausführungen gleichzeitig zu betrachten. Dies erlaubt es uns Meta-Eigenschaften wie Korrektheit sehr einfach zu zeigen, aber zum Preis einer höheren Abstraktionsebene als in vielen herkömmlichen Visualisierungen. Zum Beispiel beim Sortieren modellieren wir keine individuellen Datenwerte, sondern benutzen eine Relation, die uns sagt, ob ein Datenwert kleiner ist als ein anderer. Shape Analyse ist kein neues Verfahren, aber ihre Anwendung zur Algorithmenvisualisierung ist es: Die Ausgabe der Analyse kann relativ natürlich als Menge von Graphen interpretiert werden, aber, für eine sinnvolle Darstellung der Ausgabe müssen die Daten erst aufbereitet werden. Dies beinhaltet Methoden die Größe der Ausgabe zu reduzieren und Methoden die Verständlichkeit zu erhöhen. Die inhärente Abstraktion wirft auch wieder neue Probleme auf. Wir erörtern diese Probleme und die Art und Weise wie sie nusere Visualisierung beeinflussen. Wir geben außerdem Richtlinien, wie man Analysen ganz spezifisch zum Zwecke der Visualisierung erstellt und geben eine Beschreibung einer Beispielanalyse. Wir haben auch ein Visualisierungwerkzeug programmiert, mit dem viele der Methoden in dieser Arbeit getestet wurden und das wir kurz erläutern.