ALGORITHM ANIMATION AND DEBUGGING
WITH THE WINSANAL SYSTEM
PRZEMYSLAW SZMAL
JAROSLAW FRANCIK
This paper has been published at the Proc. of 15th IASTED Conference APPLIED INFORMATICS, Innsbruck, 1997
Abstract: WinSanal is a data-driven system for algorithm visualization. It enables presentations of the contents of chosen data structures in an adequately chosen, suggestive graphical form. An extensive subsystem of data transformation is helpful in obtaining highly abstract visualizations. The system exhibits also features of a graphically driven debugger.
Keywords: algorithm animation, computer graphics, debugging, software visualization.
INTRODUCTION
Algorithm visualization depends on exhibiting characteristic properties of algorithms by use of adequate graphical means. If created pictures change, we say of algorithm animation. Execution of a program with simultaneous graphical presentation of data is called projection. For preparation of projections and for performing them algorithm visualization systems (AVS) are used. An extensive review of problems connected with algorithm animation the reader can find in [1, 2, 3].
The aim of works we do is to create an AVS that would allow to prepare high quality projections in a short time. The system is also intended to interactively aid program debugging, using graphical representation of data. We called the system WinSanal. We have its working, though not yet final version [4, 5]. In the paper we present some interesting features of the system and its architecture.
The means offered by a chosen AVS ensure that a standard quality visualization can be prepared relatively easily. To get a higher quality visualization one has to put more work into its preparation. We expect we shall be able to obtain in our system visualizations with as good standard as in other systems but at a less expense of work.
The quality (readability, comprehensibility, clearness) of a visualization counts much for the user who is to observe projections. It is mostly influenced by two factors. The first is the repertoire of graphical representations offered by the system. In WinSanal it is not as reach as in the best known AVSs such as Balsa [6, 7], Zeus [8] or in XTango [9]. However, in practice only a limited subset of representations has been used in visualizations [10]. WinSanal's repertoire is close to that subset. The second factor is the possibility of creating projections at a high level of abstraction [2, 11]. Such projections outstep isomorphic mapping data structures or code to graphics. In order to illustrate the semantics of an algorithm one has to show not only the elements that result from the state in which the algorithm currently is. Other elements, that maybe do not explicitly occur in the algorithm at all, have to be shown. In WinSanal an extensive subsystem of data transformations establishes a general tool for obtaining highly abstract visualizations. A good example is presentation of discrete changes of data in the form of smooth transitions. Balsa-I [6] did not own this feature. It appeared in Balsa-II [7] and later systems. Actually it became a part of a de facto standard.
The ease of adapting programs for projections under an AVS is affected by another two factors. The first of them is system assistance in the visualizer's activities. In WinSanal this category of programmer's aids is currently under construction, so attempts to compare them with existing solutions would be premature. The second factor is the character of text annotations and other elements that have to be inserted to the visualized program. They are necessary to notify the AVS that the state of the program changed and in what manner, and how the changes are to be illustrated. The number, form and layout of such insertions may be taken into consideration. In event-driven AVSs, as Balsa and XTango, the program had to notify the system both of the fact of a change of its state and of the data values. In data-driven AVSs - among others Animus [12] and WinSanal fall under this category - only the fact of change should be announced, and the AVS reads the appropriate data values by itself. In WinSanal we significantly reduced the diversity of indispensable calls to the AVS in comparison with other systems. It was possible thanks to a deep parameterization of the chain of transformations to which source data are subject before they are displayed in a graphical form.
GENERAL INFORMATION
WinSanal was created on a basis of experience from Sanal, our first AVS [13, 14]. Sanal had been developed in 1989-1996. It was an event-driven AVS. It worked under the DOS system, and was implemented in Borland's Turbo Pascal. It was used to visualize programs written in this language.
WinSanal, what we mentioned in the introduction, is a data-driven AVS. It works in Microsoft Windows 95/NT. It was implemented in C++ using object oriented technology. Programs to be visualized should be written in C++. WinSanal exhibits features of a graphically controlled debugging program. The user can interactively modify the contents of observed data structures either by direct manipulation with displayed graphical elements, or symbolically.
SYSTEM ARCHITECTURE
The architecture of the system - or, to be more precise, of its part liable for projection execution - reflects the chain of transformations through which data have to pass. There are four stages of the transformations. They are schematically shown in Fig. 1.
FIG. 1 SCHEMATIC FLOW OF DATA IN THE WINSANAL SYSTEM
The first stage is data acquisition. It is implemented using objects called shadows. They are responsible for reading data values from the observed program, and for triggering the process of further data transformations.
In the second stage translation of data takes place. Data values are transformed so that they can be used to control graphical aspects of the image being created. This step engages translator objects. Their transition functions are defined by the user while the visualization is prepared. When necessary, translators may be linked in cascades.
In the third stage, which we called generation of sequences, additional information is introduced to the main data stream. This information has no equivalent in the structures of the observed program but makes possible realization of successive steps of smooth motion of graphical elements. This operation is made by pacer objects, or sequence generators. Pacers may also initiate auxiliary data flow paths, used to determine the trajectories to be followed by the elements of the picture. Another liability of pacer objects is to control the pace of the whole projection.
The last, fourth stage is data rendering. The main objects used here are grels. They establish final representation for graphical elements visible on the screen.
In the case of user (observer) interaction, the described path performs backward data transformation: starting from user-generated information, through a sequence of reverse transformations up to relevant modification of data structures of the observed program. As was stated before, one of the forms of user interaction is direct manipulation graphical elements. The implementation of this feature does not give us full satisfaction yet; in fact it is temporarily disabled.
TYPICAL COURSE OF PROJECTION
Projection follows a fixed, three-phase scheme which is the same for all groups of data subject to visualization. Phases of projection for different data groups do not have to (and sometimes simply cannot) be synchronized, so in practice they are often observed to be interlaced.
In the initial phase the scene of projection is configured - windows to display the picture are created. In the second phase the actors contributing the projection are introduced. The system is informed which data values should be observed, and then paths for data flow and transformation for them are defined, with a shadow at the beginning, one or more translators followed by a sequence generator inside and with a grel at end. The user is free to assemble and reassemble objects in order to get effects he wants. In the last, read-and-play phase, the system cyclically reads current data values, transforms them step by step to a graphical form and displays them.
PREPARATION OF VISUALIZATION
To accomplish projection, calls to functions responsible for completion of consecutive phases have to be inserted into the text of visualized program. What's more, special configuration script has to be supplied which contains description of non-default attributes of shadows, translators, sequence generators and grels. The chaining schemes for these path elements are also given.
Our system is designed and constructed to get reduction of amount of work necessary to achieve the required form of a program that directly controls a projection. The insertion of calls to functions that initiate the cycle: read data - display image still has to be made manually. The automation of this operation, among the others, is what we just work on; we employ a method of analysis of data flow in the program - a technique used in compiler construction. Evidently, more sophisticated visualizations require finishing the texts of programs by hand, after they have been annotated automatically.
SAMPLE VISUALIZATION
Let's illustrate the main features of our system with a sample visualization of an algorithm of hash table access. We show three different approaches to the same problem: starting with a simple rendition of data structures that exist in the program, we increase the abstraction level in consecutive visualizations. Such highly abstract projections make analysis of behaviour of the program easier, especially when large input data sets are involved.
The first visualization shows the algorithm behaviour in detail (Fig 2). The size of the hash array is only 23. The input keywords (read from a file) appear in the left part of a window. A small circle shows the value of the hash function, and an arrow signs the actual position in which the word is inserted into an array, after all collisions (if any) are resolved. This detailed visualization may be useful while the program is debugged, as well as when it is a part of some didactic activity. Nevertheless, in real applications much larger arrays are usually used. It is impossible to visualize big arrays as a whole with such details. What's more, the algorithm by itself is quite trivial - a software engineer would rather want to engage in the analysis of behaviour of the algorithm working upon large input sets.
FIG. 2: VISUALIZATION OF HASH TABLE WITH A SMALL INPUT DATA SET
In the lower part of Fig. 3 another visualization of the same algorithm is shown. The size of hash array is now 501. We can no more use the detailed view, as the array items should be represented by bars only 1-2 pixel wide! Instead we show a histogram that tells how many accesses (reads and writes) to consecutive items of the array occurred during the program execution. Large values of histogram items represent these items of the array, which either were sought many times or took part in many collisions. In the scale used for this projection, groups of clustered items are clearly visible. Individual bars of the histogram are only 1 pixel wide; in the case of even larger data sets single bar may represent a group of neighbouring items. Note that a similar histogram may be created also for small sets of input data, as in the right part of a window shown in Fig. 2.
The last of our approaches to the hash table visualization is shown in the upper part of Fig. 3. It is a diagram of average number of accesses necessary for seeking up a single item, in function of the factor of filling of the array. One can easily note, that when the filling of array exceeds about 75%, the number of accesses increases dramatically - in case of input data sets of this size a larger hash table should be used.
FIG. 3: VISUALIZATION OF HASH TABLE WITH A LARGE INPUT DATA SET
It should be emphasized that all presented visualizations have been implemented using the same version of the annotated source files (except of the change of array size). To create all these different visualizations the projection configuration script was the only part we had to change.
CONCLUSIONS
We created a preliminary version of WinSanal, a system for algorithm animation with elements of a graphically driven debugger. It provides facilities for presentation of the way algorithms (or programs) work - they comprise a set of graphical representations for data, and mechanisms for data acquisition, translation and rendering. Tools for creating dynamic pictures at a high abstraction level are available.
The system is data driven. Thanks to that the process of adapting programs so as they could drive projections is simplified: the repertoire of text insertions is limited, and a great deal of instructions describing how data transformation should look like is shifted to a configuration script.
Preparing projections is not yet as straightforward as one could wish. At a moment, text annotations have to be made manually. However, standard projections will be available at a less effort after completion of a module for interactive configuring projection elements. Another future aid is a text preprocessor. It will annotate the source text so that automatic notification of changes of data values to the system could take place. Independently, the repertoire of available graphical representations should be developed, as well as specialized mechanisms for presentation of non-elementary data structures; actually we focus on dynamic data structures.
WinSanal may serve didactic purposes, among others in the fields of programming, algorithm analysis and construction. It may be used in professional programming as a supplementary tool for program design, analysis and debugging
REFERENCES
- B.A. Price, I.S. Small, R.M. Baecker, A taxonomy of software visualization. Proc. of 25th Hawaii International Conference on System Sciences, 1991, 597-606.
- G. C. Roman, K. C. Cox, Program visualization: the art of mapping programs to pictures, International Conference on Software Engineering, New York, 1992, 412-420.
- J. Stasko, C. Patterson, Understanding and characterising software visualization systems. Proc. of 1992 IEEE Workshop on Visual Languages.
- J. Francik, P. Szmal, M. Nowak, Systems for algorithm visualization aiding the research (in Polish), Proc. of 3rd National Conference on Computer Aided Research, Polanica Zdroj, 1996, 317-322.
- J. Francik, P. Szmal, WinSanal: A system for algorithm animation for use in education and software engineering (in Polish), Proc. of 2nd Conference Computer Science in Universities for National Economy, Gdansk, 1996, 49-54.
- M. H. Brown, R. Sedgewick, A system for algorithm animation, Computer Graphics: SIGGRAPH'84 Conference Proceedings, Minneapolis, Minn. 18(3) 1984, 177-186.
- M. H. Brown, Exploring algorithms using Balsa II, Computer, 21(5) 1988, 14-36.
- M. H. Brown, Zeus: a system for algorithm animation and multi-view editing, Research Report 75, Digital Equipment Corporation Systems Research Center, Palo Alto 1992.
- J. Stasko, Animating algorithms with XTANGO, SIGACT News, 23(2), 1992, 67-71.
- J. DeTreville, The GraphVBT interface for programming algorithm animations, Proc. of 1993 IEEE Symposium on Visual Languages, Los Alamitos, CA, 1993, 26-31.
- G. C. Roman, K. C. Cox. Abstraction in algorithm animation, Proceedings of 1992 IEEE Workshop on Visual Languages, Los Alamitos, CA, 1992, 18-24.
- R. A. Duisberg, Animated graphical interfaces using temporal constraints, Proc. ACM SIGCHI 86, 1986, 131-136.
- J. Francik, P. Szmal, Synchronous visualization of algorithms - a realization in the SANAL system (in Polish), Zeszyty Naukowe Politechniki Slaskiej, seria Informatyka, 27, 1994, 37-54.
- J. Francik, P. Szmal, Multi-station algorithm visualization in computer networks (in Polish), Proc. of 3rd Conference on Computer Networks, Zeszyty Naukowe Politechniki Slaskiej, seria Informatyka, 30, 1996, 293-310.
- Other related links at this site:
-
Algorithm Animation main page
More information on WinSANAL system (including sample animations)
List of other papers on algorithm animation