BALSA - Marc H. Brown
Smalltalk - Ralph L. London & Robert A. Duisberg
In addition to execution, a user can manipulate the view windows, set up additional views as well as zooming and syncronizing. The zooming feature of BALSA is a sophisticated feature which shows more or less information depending on the zoom scale. For example, in a "tree" view, all children may be visible when zoomed into a specific sub-region while they may be drawn together as a box in a "full" view of the tree. Synchronizing between windows is also supported by BALSA. This is extremely important when comparing multiple algorithms. The user can also input data to the algorithm at run-time. BALSA supports the input of data from user dialog boxes while the algorithm is executing. This can be done through keying in actual values or by selecting an input generator and providing input parameters. This can be useful in viewing several input generators simultaneously in order to see how an algorithm preforms under different kinds of data.
Performance testing is a more advanced user feature supported by BALSA. This is specifically pointed out because it is not obvious that running two animations side by side is not a good performance test. Through a side by side comparison of two animations, the performance of one may be impeded by the actual workings of BALSA. For example, one may call a command with more frequency. This command runs slowly in BALSA and therefore slows down the animation's performance. BALSA gets around this by counting analogous "interesting events" within the algorithms and supports a virtual time counter.
The first step, breaking the algorithm up, is the bulk of the preparation for the animation system. Toward this end, the programmer must separate the algortihm into three sections. They must distill the actual algorithm from the rest of the program as well as separate the input generators and the various views which make up the algorithm. Although this may seem a trivial task, it is important that it be done well so that the rest of animating process is possible. Once this process is complete, the "interresting events" in the actual algorithm must be annotated. These annotations take on the form of indicators that notify the BALSA system when something should be changed or updated in the animation display. Once the algorithm has been annotated, the program is put into the BALSA framework.
The views of the animation must be created by using the annotated cues from the algorithm in an intuitive and stylistic manner. This is where algorithm animation becomes a very subjective and personalized process. Here the paper skirts the issue of how to create good views and introduces the specifics of the viewing process in BALSA. This viewing process has three basic components: an adapter; a modeler; a render. The adapter reads in the annotated cues from the algorithm and transforms the information into parameters that allow the modeler to update the scenes. Finally, the renderer takes snapshots and sends them to the individual viewer.
Although the features of BALSA are discussed in detail in this paper. I felt that the paper still lacked content. I wanted a broader perspective on the system's usefulness and usability. More examples could have provided a stronger sense of the BALSA system without specifically expressing each feature in detail. However, this paper gave a strong understanding of what types of features an animated algorthim system should include.
In this Smalltalk system, the generation and viewing of algorithms is performed on the graphical end using the generic Smalltalk interface of a Model-view-controller (MVC). The MVC was modified minimally to accomodate the animation system. Specifically, a display routine was added to create views similar to the BALSA adapter. Although there are limitations with using a prepackaged tool, the hierarchy and manipulation that MVC supports can be helpful in generating views easily while supporting Smalltalk homogenity. This is as detailed as the paper gets in the structure of the animation system. The rest of the paper is reserved for the usage and implementation of several examples of the system.
Creating individual animations in the Smalltalk system is somewhat different than in the BALSA system. This is primarily due to the organization of the system with respect to the algorithm of interest. In the Smalltalk system, the algorithm is kept independent of the animation system. The authors promote that changing the algorithm should be as easy as slipping "a new slide under a microscope". This is a bit different from the BALSA system which embeds the algorithm. Otherwise, the systems both require annotation of interesting events and setting up views to display the animation.
Although the annotation process is not presented in detail, the authors make a few interesting comments about annotating from the experience of implementing multiple algorithms. They suggest that the annotations and interesting events in algorithms are in repeatable and predictable places. They are located at the initialization and completion of processes and loops as well as within each loop. This alludes to the automation of this process although they add subsequently, that program development may affect this simple placement. The authors also note that the process of creating views from the annotated information is and will remain a personalized and stylistic issue. They add that this process is recursive where views suggest modifications for subsequent views.
A number of examples of the system in work follow. A particularly interesting example is one called the Dutch national flag problem. This algorithm is a limited memory implementation of sorting a small number of type of elements. So, three colors are to be separated with a limitation on memory and swapping. The interesting part of this example is that the animation exposed a limitation in the algorithm. The algorithm was actually improved after creating an animation for it.
This paper was written at a higher level than the BALSA paper and acted as a good complement to it. An object-oriented animation system, such as the one persented in the Smalltalk paper, takes advantage of the modularity in OOP to facilitate animations. This system is a benchmark for the work in animating algorithms due to its leap into an object oriented framework.