ARMVLS - Atomic Reaction Model Visual Language System
 
Kai Warendorf, Wen-Jing Hsu and Poh Yeen Seah
School of Applied Science, Nanyang Technological University, Singapore 639798
wdorf@acm.org
Abstract: Visual language (VL) is a programming language without textual codes and algorithm animation (AA) is about visualizing a computer algorithm. Visual programming (VP) and AA are traditionally separate factions in software visualization (SV). With the Atomic Reaction Model (ARM), we have bridged these two major branches in SV. ARM Visual Language System (ARMVLS) is a visual language algorithm animator, modeling the fundamental cause-and-effect of a simple atomic reaction. ARMVLS is a system that allows the end-user to animate algorithms - to visually demonstrate or to assist in the description of how a computer algorithm works by means of drawing and moving images on screen.   1      Introduction
 
Since the early 1980's when researchers began building systems to visualize computer programs and algorithms, there have been many terms defined and used in the literature, such as VP and AA that we used in the previous section, and other phrases like program visualization. Yet after more than a decade of advances in interface technology, researchers have not fully agreed on these definitions.

The Oxford English Dictionary suggests visualization as "the power or process of forming a mental picture or vision of something not actually present to the sight", so a visualization can result from input of any combination of the human senses. The general consensus of program visualization is the use of various techniques to enhance the human understanding of computer programs, while visual programming is the use of visual techniques to specify a program in the first place. Algorithm visualization or animation is understood to be the visualization of a high-level description of a piece of software which is in contrast to code or data visualization (which are collectively a kind of program visualization) where actual implemented code is visualized. Price et al [1993] used the term software visualization (SV) to include all these definitions.

Although there were various attempts to bridge these two visualization branches from 1994 to 1996, we consider only Opsis [Michail 1996] to have achieved this task to a certain degree, based on our definition of a VL. Since there are no other currently existing systems that can integrate AA and VP, we put ARMVLS among the ranks of pioneer VL algorithm animators.

The objective of ARMVLS is the following:

    1. Portability and extensibility. Portability concerns the amount of effort needed to deliver the new system across platforms; extensibility determines the extent of restructuring required when building new features on old ones.
    2. Object orientation deals with assigning properties to graphical objects created using the graphical editor. Graphical objects are the basis for Object-Oriented Visual Programming (OOVP) [Kimura 1995].
    3. Resource sharing, group-working and networking. Resource sharing pools graphical objects to share among users of the new system; group-working and networking distributes the responsibility of system development and maintenance between all participating members or users.
    4. Incorporation of multimedia. This addresses the issue of integrating multimedia into animation. We defined visualization to be the result of combined input from all the human senses. Incorporation of multimedia pertains to the ease of specifying images, as well as sound for visualization.
    5. Code-free programming. This is visual programming.
2     The Traditional BALSA Approach

BALSA stands for Brown University Algorithm Simulator and Animator [Brown 1991]. It is one of the earliest AA systems to make use of the graphics and windowing capabilities of personal workstations in the 1980's. It was designed for two purposes: as a teaching tool for undergraduates and as an aid to algorithm design and analysis. As a teaching tool, it allows the teacher to give a running commentary on the prepared graphical animation running on each student’s machine. This is the automated process of the traditional classroom teaching example that we gave in the previous chapter. Figure 1 shows BALSA with several view windows. A view is an animated picture portraying the events generated by an algorithm. Each view can exist as a separate window to show the various aspects of the algorithm being animated.

    Figure 1: BALSA showing the code view, input, status message, current view of the tree data structure, and a view of the tree history.
     
We see from the still in Figure 1 that BALSA supports multiple simultaneous views of the running algorithm. The contents of each view window depend on what the teacher has provided and cannot be changed by the student. A code view (the window at the lower left quarter of the BALSA screen) is usually provided to show the listing of the current procedure in Pascal with the current line highlighted. Views of data structures can range from dots or sticks to complex graphs, trees or computational geometry abstractions. BALSA is able to display multiple views of the same data structure, and is also the first system that can show algorithms racing with each other on the same display (e.g. to compare the speeds of various sorting algorithms). This pioneering work made it the benchmark against which all subsequent AA systems have been measured.

To animate a computer algorithm in BALSA, the teacher starts with the standard Pascal implementation of the algorithm and annotates it with markers at points where the code changes interesting data structures or enters/exits a subroutine. These markers are called interesting events and they make calls to BALSA’s Interesting Event manager with parameters that typically identify program data [Brown 1991]. After annotating the source code, the teacher builds views. Each view controls some screen real estate and is notified by the Interesting Event manager when an interesting event is encountered in the algorithm. The notified view is then responsible for updating its graphical display appropriately based on the event. This is done by either modifying the existing view from the BALSA library or by building a completely new view using the built-in graphics primitives. With these overheads, the code can bloat to a considerate length. Animation code can even be longer than algorithm code, resulting in a situation where the student spends more effort on constructing the animation than on experimenting with the algorithm. Therefore, we re-state that BALSA systems are not particularly effective as tools for active learning, i.e. to let students animate algorithm themselves.

3     ARMVLS: Design Issues

3.1    Features of ARMVLS

The features are manifold and only a few can be described it this paper. ARMVLS …

    1. belongs to the ranks of pioneer VL algorithm animators,
    2. is the first VL algorithm animator to perform sorting, searching, tree and possibly graph algorithms using the same engine,
    3. enables very fast prototyping for both the novice and the expert animation programmer,
    4. allows VP in the most natural manner so that algorithms can be programmed exactly as how we would visualize them to be,
    5. is Internet ready and capable of cross-platform interface since it is a Java applet, and
    6. employs dynamic state transitions to reduce programming efforts and to increase the detail level and realism in animation.
ARM has an impact on the current SV technology as it injects fresh ideas into AA and VP. For AA, it is a break from the traditional textual coding of algorithms; for VP, it gives a new lease of life to GRSs to handle complex problems, and hence the ability to wrestle with the ever dominating dataflow VLs.

3.2    How to animate in ARMVLS

The snapshot in Figure 2 shows the Atomic Reaction Model Visual Language System (ARMVLS) after the completion of a three-level binary search tree (BST) construction. The BST was programmed from scratch and made ready to run in less than five minutes, demonstrating the rapid prototyping capability of our Atomic Reaction Model (ARM). There are no functions or modes which specially cater for tree construction. All features and constructs of ARM are generic and can apply to all algorithms that it can animate, where deemed fit. Creating animation in ARMVLS also does not require an expert user. In fact, the BST was animated by a programming illiterate who was only briefed on the aspects of ARM pertaining to BST, and taught the BST insertion algorithm itself just minutes before she created the animation.

ARM is designed as a general programming heterogeneous visual language (GPHVL) with the ultimate aim of animating all algorithms achievable by textual coding. This is not to be confused with BALSA systems [Price et al 1993]. Algorithm animation (AA) using BALSA’s approach are basically coded in text and therefore restricted only by the machine power, compiler capability and human creativity. ARMVLS is a visual programming (VP) system to animate algorithms that are themselves programmed in ARM.

Of course, our goal is extremely ambitious and will take many more years of research to achieve, considering the level of VL technology today. Nevertheless, we felt that our contribution to the VL research community is our approach adopted in ARM.

ARM introduces many new terms that may be unfamiliar in Computer Science. These terms are either Physics or Chemistry jargon since ARM, as the name implies, is modeled after a simple atomic reaction.

3.3    The Atomic Reaction

In our simple atomic reaction, we assume only two types of atoms: the active and the inactive. Active atoms have kinetic energy. They are unstable particles and they move around. They are called reactors. Inactive atoms, or reactants, are stable and do not move. Because reactors move, they initiate interactions with reactants. In an interaction, there can be two possible outcomes: either nothing happens, or there can be excitation. We say the interaction is sparked when there is excitation. If the excitation involves only one reactor and one reactant, it is a reaction; if many reactants are involved, it is a compound reaction. ARM does not define the many-reactor-to-one-reactant and the many-reactor-to-many-reactant cases. In subsequent discussions, we use the term ‘reaction’ to include compound reaction as well, unless we explicitly specify that compound reaction is excluded.
 

Figure 2 ARMVLS constructing a binary search tree

In a reaction, there can be three resulting scenarios:

a. the reactor remains excited and the reactant remains stable,

b. the reactor remains excited and the reactant becomes excited, or

c. the reactor stabilizes and the reactant becomes excited.

When the reactor stabilizes, it becomes a reactant; the opposite is also true — when the reactant is excited, it becomes a reactor and fires an excitation response (potential energy to kinetic energy) that throws it into motion. The reactor also fires an excitation response in order to keep itself in motion if it is to remain excited. We use active responses to refer to the set of excitation responses that an atom fires as a reactor; and for those excitation responses that the atom fires as a reactant, we call them passive responses. Dual responses is the intersection set of these two response types, i.e. a dual response is both an active and a passive response. We say that an atom is triggered when it either becomes or remains active after a reaction.
 
Figure 3 Atomic objects defined with two responses for building binary search trees in ARM

To make clear the concept presented so far, we apply it to build a Binary Search Tree. Suppose we have the numbers 20, 12, 35, 28 and 43. We let these numbers be represented by an atom each. Each atom is specified with two active responses: ‘move left down’ and ‘move right down’. The trigger conditions for these two responses are vo < vc and vo ³ vc respectively, where vo is the value of the atom, and vc is the value of the complement.

The complement refers to the other atom in an interaction, e.g. reactor A and reactant B interact, A is the complement of B and B is the complement of A. vo and vc are known as weights. Weights are like variables in textual languages; we do not call them variables because they are not memory cells that store only values — they are active structures. Yhe meaning of the trigger conditions is that active response ‘move left down’ will only be fired if the atom’s value is less than its complement’s (vo < vc); otherwise ‘move right down’ will be fired (vo ³ vc) instead as illustrated in Figure 3.

In figure 3, circles represent atoms, and the arrows are the active responses. Observe that all the atoms are identical except for their values. This means that we only create one atom, then we duplicate them to the required number (in this case, five) and assign them their individual values.

Atom 20, i.e. atom with value = 20, enters the interaction arena (represented by the enclosing box) as a reactor. There are no reactants that it can interact with, so it stabilizes to become a reactant. Atom 12 (vo = 12) enters as a reactor and interacts with atom 20 (vc = 20). As it is atom 12 that initiates the reaction, and. Since vo < vc the active response ‘move left down’ is triggered.
After the reaction, atom 12 stabilizes at its final position. Atom 35 now enters and interacts with atom 20. The trigger condition for active response ‘move right down’ is met as vo ³ vc. Similarly, atom 35 then stabilizes. Atom 28 joins the interaction arena, reacts with atom 20 and fires ‘move right down’.
Unlike previously for atoms 12 and 35, atom 28 does not settle this time; instead it starts another interaction with atom 35. vo < vc, so atom 28 remains excited and consequently executes the action for active response ‘move left down’. Atom 28 finally stabilizes after two consecutive reactions. It then allows atom 43 to enter. This frame now repeats the occurrences of frame 4.
Reaching atom 35, atom 43 fires active response ‘move right down’, since vo ³ vc. Atom 43 settles and the chain reaction initiated by atom 20 stops.

Figure 4 Chain reaction sequence for binary search tree construction example

Before we animate, we have to introduce another term — interaction arena. This is the place where atoms interact. In implementation, we call this place the animation window or the animator board, which is actually the window that displays the atoms. Figure 2 shows an animator board with grid lines. Initially, this interaction arena is empty. Each atom will join the arena one after another and cause a series of reactions. This series of reactions is called a chain reaction as illustrated in Figure 4.

4    Conclusion

We have tried to achieve the following objectives with this new approach of Algorithm Animation:

    1. Portability and extensibility. As ARMVLS is entirely written in Java the system can either be accessed via the Internet or as a standalone application on all platforms supporting JDK 1.1.
    2. Object orientation. All animations are programmed using objects and interact by Atomic Reactions.
    3. Incorporation of multimedia. This was not further explored in detail but all objects can be associated with images, and each reaction with sound.
    4. Code-free programming. The BST was programmed without any line of code in comparison to the BALSA approach where the original PASCAL program hat to be modified with animation sequences.
ARMVLS can be used as a supplement for Data Structure teaching since it allows students to understand the principles of an algorithm while using it. We think, that programming of algorithms is much easier when we can build a mental image of the algorithm execution sequence in our mind. Complicated procedures and recursive algorithms are more easily understood and therefore aid in the process of programming it in "real" programming code.

5    References

[Brown 1991]. Brown, M.H (1991). Zeus - A System for Algorithm Animation and Multi-View Editing. Proceedings of Visual Languages, 10-17.

[Kimura 1995]. Kimura, T.D (1995). Object-Oriented Dataflow, 1995 IEEE Symposium on Visual Languages, http://www.computer.org/conferen/vl95/talks/T21.html.

[Lawrence et al 1994]. Lawrence, A.W., Badre, A.M. and Stasko, J.T. (1994). Empirically Evaluating the Use of Animation to Teach Algorithms, 1994 IEEE Symposium on Visual Languages, IEEE Computer Society Press, 48-54.

[Michail 1996]. Michail, A. (1996). Opsis: A Java Applet for Teaching Binary Tree Algorithms, http://www.cs.washington.edu/homes/amir/Opsis.html, University of Washington.

[Price et al 1993]. Price, B.A., Baecker, R.M., and Small, I.S. (1993).A Principled Taxonomy of Software Visualisation, Journal of Visual Languages and Computing (4) 3.