Data Structure Visualization:Existing Research and Systems
The idea of creating a system that would visualize data structures in computer programs is an old one, dating back even to the 1960’s [8]. During this long history, a number of systems for data structure visualization have been developed. Most, however, have only been research prototypes and have never been used by anyone outside the system’s creator(s). This relative lack of adoption is surprising in light of the potential benefits of data structure display identified above. A quick survey of widely-used current IDEs notes that none provide anything beyond the most limited abilities to persistently display data values, or more importantly, visualize data structures.
For a good overview of the aesthetic considerations and the general challenges in drawing data structures, see the article by Ding and Mateti [9].
The authors provide a rigorous survey of the different styles of drawings used in data structure diagrams. They enumerate a set of characteristics that influence people’s perceptions of data structure illustrations, including visual complexity, regularity, symmetry, consistency, modularity, size, separation, shape, and traditional ways of drawing. Further, they develop a set of guidelines for drawing aesthetically appealing diagrams. The guidelines are based on rules, factors, and objectives, and include the ability to quantitatively assess the aesthetics of different diagrams. Ding and Mateti note that the automatic drawing of data structure representations is difficult because a diagram should be determined not only by a structure’s declaration, but also by its intended usage.
Stasko and Patterson echo that thought by identifying the notion of intention content in program visualizations [10]. They note that a programmer’s intent in creating and using a data structure can significantly influence how the structure should best be visualized. For instance, a simple array of integers may be shown as a row of rectangles with the values inside; a row of rectangles whose height is scaled to the value of each element; a round pie chart with a wedge whose percentage size of the circle corresponds to the value of that array element; or a stack with the array elements sitting on top of each other. To generate the latter two representations, some knowledge of the purpose and goal of the surrounding program code is necessary.
In the remainder of this section, we present brief summaries of a few of the most note- worthy data structure visualization systems that have been developed. Each of these grew from research projects, and the final one, DDD, has been used significantly by outside users. In reviewing each system, we highlight its unique aspects, and we evaluate it with respect to the issues raised in the previous section.
Incense
The Incense system [11] developed by Myers was one of the earliest attempts to build a relatively full-featured data structure display system. Myers stated that Incense allowed a “programmer to interactively investigate data structures in actual programs.”
The system operated on a Xerox Alto personal computer and displayed data structures for the Mesa strongly typed programming language. In the system, data structures could be displayed at debug time by supplying a variable’s name; Incense examined the symbol table to determine the variable’s type. Once a variable was chosen, the user specified via the mouse a rectangular viewing area inside the active window to display the data. Incense automatically chose the appropriate view abstraction given the space requirements. Data with insufficient screen space were displayed as grey boxes.
The system included a large number of sophisticated default views for the language’s data types and structures, and it utilized a spline-based method for displaying pointers. Examples of views of different types of data structures are shown in Figure 44.1. Additionally, users could define their own data views using a predefined graphics library in Mesa. The difficulty of that process is unclear.
In order to implement Incense, Myers created the concept of an artist, a collection of procedures and data that handled display, erasure, and modification of the data being displayed. An artist had to be associated with a piece of data in the system in order to display it. To display pointers as arrows, Incense utilized layouts, special types of artists designed to locate and manage the various pointer and referent components of data.
The system was designed to allow users to also edit variables’ values at run-time in the graphical presentation, but it does not appear that this feature was ever implemented. Unfortunately, the host hardware’s space and processing limitations made Incense’s perfor- mance relatively poor which likely restricted it to being a research prototype. The system
did, however, illustrate a multitude of valuable capabilities that a data structure visualization system could offer.
VIPS
The VIPS [13] visual debugger by Shimomura and Isoda focused on providing a flexible set of views of lists in programs. The system ran on top of the DBX debugger, with VIPS and DBX communicating through pipes. For instance, when a user would issue a request to display a list, the VIPS system would send necessary messages to DBX to extract information needed for the display. In addition to views of list data structures, VIPS provided views (windows) of program text, I/O, variable displays, as well as control windows for debugger interactions. VIPS provided two main views of program lists, the whole list view and the partial list view. In the whole view, shown on the left side of Figure 44.2, list nodes were represented as small black rectangles thus allowing more than 100 nodes to be shown at once. The basic layout style used by the system was a classic binary tree node-link layout with the root at the left and the tree growing horizontally to the right. The whole list view assisted users in understanding structure. The partial list view, shown on the right-hand side of Figure 44.2, presented each node in a more magnified manner, allowing the user to see the values of individual fields within the node. By dragging a rectangle around a set of nodes in the whole list view, a user could issue a command to generate a new partial list view.
VIPS also allowed users to select particular pointer fields in list structures and only have the nodes connected by those pointers to be displayed.
To assist debugging, VIPS also provided a highlight feature in which list structures with values that had recently changed were highlighted in order to draw the viewer’s attention.
An earlier version of the system [12] provided multiple run-time views of executing Ada programs. Default data views in the system included scalars, linked lists, one-dimensional arrays and records. VIPS also allowed users to design their own data displays or “figures” by writing programs in the Figure Description Language FDL, a subset of Ada. FDL programs
FIGURE 44.3: GELO view of a list. Picture provided courtesy of Steve Reiss. contained parameters that could be associated with a variable or variables, promoting view
control via data values. Data displays were rendered automatically by the system. When space was tight, smaller representations were utilized.
The VIPS debugger provided one of the most extensive graphically-aided debugging systems onto a particular language. By adding views of the call stack, data flow, and program structure to program data visualizations, the system explored the boundary of visual de- bugging efforts at that time.
GELO
The GELO system [14] was designed to ease the production and display of complex pictures of programs and data structures. In the system, strongly typed data structures were displayed as picture objects of types data, tile, layout, arc, and empty. GELO differed from many other data structure display systems in that diagrams were not described in a world coordinate space, but by giving a set of topological constraints for their views.
The system was organized as three components: GELO managed the specification and display of classical program and data structures; APPLE allowed a user to design and customize the way that a particular data structure would appear by providing mechanisms for defining the mapping between the data structure and the GELO structures (more than one mapping was allowed); PEAR used these mappings to allow the user to edit the structures’ display, thereby modifying the underlying data structures.
GELO allowed users to specify both the data instances to be displayed and the drawing attributes of the display through fairly complex dialog box selections. It provided default displays for common structures such as lists and trees, as well as various heuristics for graph layout. A sample list view is shown in Figure 44.3 and a tree view is shown in Figure 44.4. GELO included view panning and zooming, abstractions on small objects, and scrollable windows.
Reiss noted that the system’s topological layout scheme was sometimes overly restric-
tive; users may have wanted to have a picture “look just so” but GELO did not provide this capability. The sheer amount of dialog and menu choices for designing a display also appeared to be daunting, but the sophistication of automatic layout GELO provided was quite impressive.
DDD
The DDD System [15, 16], developed by Zeller, provides some of the most sophisticated graphical layout capabilities ever found in a data structure display system. DDD is tech- nically a front-end to command-line debuggers such as GDB and DBX, and it provides all the capabilities of those debuggers. Additionally, program variables can be visualized in displays, rectangular windows that can be placed on a user’s canvas.
DDD’s sophistication comes in its techniques for visualizing pointer dereferencing. It draws a directed edge from one display to another to indicate the reference. DDD contains simple placement rules with edges pointing right and downward, or if desired, sophisticated graph layout algorithms can be invoked. Figure 44.5 shows an example data structure view from DDD.
In the default display mode, only one edge can point to any display. Thus, it is possible to have a visualization in which a display (variable or specific piece of memory) appears multiple times. DDD also provides alias detection, however, so that all program data residing at the same location are consolidated to the same display object. Thus, lists with cycles will be shown as the circular representation that one would expect.
DDD is particularly noteworthy in that the system is available as free software and it has been widely downloaded and utilized. It is perhaps the data structure visualization that has been most used by people other than the system creators.
In addition to the systems mentioned above, a number of other data structure display tools have been developed over the years. Some of the more noteworthy ones include
• GDBX [17] - A graphical extension to the UNIX debugger DBX.
• PROVIDE [18] - An ambitious process visualization and debugging environment for programs written in a subset/variant of the C programming language.
• Amethyst [19] - A system intended to simplify data structure visualization for novice programmers.
• DS-Viewer [20] - A system that focused on the display of structures in a weakly typed language such as an assembler language.
• Lens [22] - A layer on top of the DBX debugger that provided, via programmer annotations, both data structure display capabilities as well as simple algorithm animation operations.
• SWAN [21] - A system that allowed instructors and students to easily annotate programs to produce data structure views.
Comments
Post a Comment