Proceedings of 11th IEEE International Symposium on Visual Languages, pp. 91-98, IEEE/CS, 1995.
Visualization of program execution is generally beneficial for programmers to understand the program. However, there exist only a limited number of visualization systems which can be used for practical applications. The main focus of the traditional visualization systems is on how to make concrete pictures, and they are customized for specific application domains. Therefore, the existing visualization systems cannot be easily used for a wide range of applications. In this paper, we propose an alternative framework for program visualization based on a bottom-up approach. A conventional top-down manner for designing a concrete final picture is not used here. Instead, our system draws an abstract picture as a set of local pictures by applying local drawing rules. We also introduced a scaling mechanism that prevents overflowing or overdrawing. The proposed framework also enables us to see a conceptual structure of the program naturally. A prototype system is developed by using the Scheme interpreter. Examples of visualization by the system are shown in this paper.
Programming is a time-consuming and difficult task. As Lieberman and Fry indicated, what makes programming so difficult is that a programmer must imagine the dynamic behavior of a program while he/she is writing its static description[7]. Moreover, such cognitively traced behavior is often different from its actual behavior.
Program visualization is obviously a promising approach for the problem. In fact, many systems that visualize dynamic change of data (e.g. Incense[10], algorithm animation systems[2,3,14], etc.) have been developed to date. On the other hand, there are few systems that visualizes control flows of programs. In the case of Lisp programming, for example, programmers still rely on trace and stepper to investigate program execution. However, the output obtained by trace or stepper is usually microscopic. Therefore, it is difficult to get macroscopic information of the program execution.
We also noticed that there are few visualization systems that can be used for practical programming applications. For example, consider algorithm animation systems. There is no doubt that algorithm animation is the most attractive and successful program visualization method with effective use of computer graphics. However, the algorithm animation is most effective only for novice programmers who are trying to learn the algorithm.
That is due to a trade-off between expressiveness and generality of the visualization. If more specific and concrete pictures are given programmers to represent the problem, the visual representation tends to be less general. For instance, an algorithm animation system which is highly customized for quicksort cannot be applied to other algorithms (e.g. graph algorithms) without changing its visual design. It also cannot be used to visualize a program which does not use explicit algorithms.
We believe that a visualization system which can be used for practical programming applications should be as general as possible. In other words, the system has to be able to visualize any programs written by programmers. (Such programs do not necessarily use explicit algorithms.) Therefore, we conclude that the traditional visualization framework which designs final pictures in a top-down manner cannot satisfy the generality.
This paper describes an alternative framework for program visualization based on a bottom-up approach. To accomplish the generality of the system, we did not take a traditional top-down approach for designing a concrete final picture. Instead, an abstract picture is drawn in a bottom-up manner. As the program runs, the visualization system draws local pictures by using the {\em local drawing rules}. The final picture is given as a set of the local pictures. We have to be very careful to adopt such a bottom-up approach because it can easily generate messy pictures. To solve the problem, we introduce a {\em scaling mechanism}. Visualization modules are embedded in the Scheme interpreter. As a result, programmers do not need to insert/delete any additional procedures into/from their programs for visualization.
The paper is organized as follows. Section 2 describes the proposed system in details. An example of visualization by the system is given in Section 3. Section 4 discusses applications of the proposed system. Related works are described in Section 5. Concluding remarks are presented in Section 6.
We chose the interpreter-based language Scheme[1] as development language and target language, because of its rapid prototyping capability. Our system is implemented as a meta-interpreter in Scheme. Our system is currently running on a SGI IRIS Indigo/XS using MIT Scheme 6.0.4 with GL interface. The Scheme interpreter checks the type of a given S-expression and sends it to a corresponding evaluation procedure. If the S-expression is not an atom, elements of the S-expression are evaluated recursively. In Figure 1, black arrows indicate the flow of S-expressions and black boxes indicate the procedures that are also found in a normal meta-interpreter.
Figure 1: An overview of the system. Black arrows indicate the flow of S-expressions, and black boxes indicate the procedures that are also found in a normal meta-interpreter. Gray boxes, gray ovals, and gray arrows indicate the visualization procedures, the local drawing rules, and the flow of a scale respectively.
The system is implemented by embedding visualization procedures into the normal meta-interpreter. In Figure 1, gray boxes, gray ovals, and gray arrows indicate the visualization procedures, the local drawing rules, and the flow of a scale, respectively. In the following sections, three keywords that characterize our system are described.
It is painful to insert visualization procedures into a program when we want to visualize the program. It reminds us of inserting many ``printf'' sentences when debugging C programs. Those additional procedures have to be deleted after the program is debugged. We believe that practical visualization systems should not force programmers to insert visualization procedures manually as stated above. Our system solves this problem by embedding visualization procedures into the system. As a result, programmers do not need to change their programs for visualization.
Similar approaches are found in other systems. For example, ParVis[8], which is a visualization system for parallel Lisp, has its own visualization modules in the interpreter. The algorithm animation system Pavane[3] also prevents programmers changing an original program by using a declarative approach.
One of the techniques newly introduced in our system is local drawing rules. The local drawing rules are defined at specific points that typically represent a control flow, such as conditional branch, iteration, function call, and so on. When execution of the program reaches to the point, the system refers to the local drawing rule and draws a picture. All pictures are drawn locally. Therefore, we do not know the final picture until the program is executed.
In our system, the local drawing rules are exchangeable. Users can define their own drawing rules as they need. For example, when they want to see just a trace of user-defined functions, they should define the rules only for the user-defined functions.
In the followings, we briefly describe examples of such local drawing rules. The rules will be used for visualizations later in Section 3.
First of all, a drawing rule for primitive functions is given as follows.
It is important to understand when user-defined functions are called. For that purpose, we define the following drawing rule for user defined functions.
For example, consider the following function definition.
Whenever the function (test) is evaluated, the picture shown in Figure 2 is drawn.
Figure 2: An example sub-picture that is drawn when the user-defined function (test) is called.
A conditional branch is one of the most important control structures in any programming languages. Scheme has if, cond, and case as conditional statements.
As the word branch shows, we often have an image of a branch for the conditional branch. The following drawing rule is defined to represent such ``branching image.''
For instance, consider the following function.
If the function is called as (if-test 1), the picture shown in Figure 3 is generated.
Figure 3: An example sub-picture that is drawn when the system evaluates an if-statement.
A cond-statement is translated to a set of if-statements, and then evaluated. Therefore, programmers can see which conditional statement is true by counting the number of blue spheres.
Iteration is another important control structure. Scheme has do to represent iteration.
When visualizing the iteration, it is important to know how many times the iteration is repeated. Keeping the fact in mind, we define the following rule.
For example, consider the following function.
A picture for (do-test) will be drawn as in Figure 4.
Figure 4: An example sub-picture that is drawn when (do-test) is called.
The proposed bottom-up approach based on the local drawing rules accomplishes the generality of our system. However, the approach itself has some potential problems.
First of all, if a picture is drawn only by local drawing rules, visualization can easily overflow a computer screen or overwrite existing pictures. For example, the recursive factorial program that is described later in Section 3.1 will overwrite the existing pictures. Secondly, if local pictures are drawn in the same scale, programmers cannot easily understand the nested depth of the program.
We introduce a scaling mechanism for that problem. As we described previously, Scheme interpreter evaluates an S-expression recursively. Our system reduces a scaling factor for drawing whenever such recursive evaluation occurs. The mechanism is illustrated in Figure 1. By applying the scaling mechanism, most pictures do not overflow the computer screen, and the overwrite problem can be minimized.
What is more important, the scaling mechanism enables us to represent program execution levels naturally. Especially, a picture tends to be strictly self-similar in the case of recursive calls.
In this section, we will show a visualization example to demonstrate how the final picture is drawn. That will also demonstrate the generality of our system.
The example is a recursive factorial program. The recursive factorial program is defined as follows.
We obtain the visualization result illustrated in Figure 5 when (fact 5) is evaluated.
After an initialization process, the system draws a yellow sphere and waits for user's input (Fig. 5 (1)). When the (fact 5) is given to the system, the system draws a pyramid for fact (Fig. 5 (2)) because the function is a user-defined function (see the use-defined function rule described in section 2.2.1.). The system looks up the definition of fact and evaluates (if (= n 1) 1 (* (fact (- n 1)) n)). A cube is drawn for the statement (Fig. 5 (3)) because that is a if-statement (see the if rule in section 2.2.2.). After that, a conditional expression (= n 1) is evaluated. A blue sphere is drawn for the expression (Fig. 5 (4)). Since n equals to 5, the result of evaluation is false. Therefore, the drawing direction is changed by 30 degree (Fig. 5 (5)). Then, the system evaluates (* (fact (- n 1)) n). Since the system cannot complete the evaluation before (fact (- n 1)) is evaluated, it draws nothing at this time. Then, a white sphere for (- n 1) is drawn (Fig. 5 (6)). Subsequently, (fact 4) is evaluated (Fig. 5 (7)). After each recursive call to fact is completed, the system draws white spheres corresponding to the evaluation of primitive function * (Fig. 5 (8)).
It is important to see that the recursive algorithm is represented naturally in its self-similar form.
Figure 5: A visualization obtained by evaluating (fact 5). (1) After an initialization process, the system draws a yellow sphere and waits for user's input. (2) When the (fact 5) is given to the system, the system draws a pyramid. (3) The system evaluates (if (= n 1) 1 (* (fact (- n 1)) n)), and draws a cube. (4) A conditional expression (= n 1) is evaluated by the system and a blue sphere is drawn. (5) Since n equals to 5, the result of evaluation is false. Therefore, the drawing direction is changed by 30 degree. (6) The system evaluates (* (fact (- n 1)) n). Since the system cannot complete the evaluation before (fact (- n 1) is evaluated, it draws nothing at this time. Then, a white sphere for (- n 1) is drawn. (7) In this way, the system evaluates fact recursively. This figure is just after (fact 1) is evaluated. (8) The final image. Each recursive call to fact was completed. The system draws white spheres corresponding to the evaluation of primitive function *.
Our system can normally be used as a visual tracer. Lisp has a debugging tool called trace. By specifying a function, programmers can investigate function calls.
Consider, for example, a program to calculate Fibonacci sequence.
The output obtained by tracing (fib 5) is shown in Figure 6. It is possible to know that fib is a kind of recursive program since (fib 5) calls (fib 4). However, it is hard to recognize that fib is a double recursive program, because (fib 3) called from (fib 5), which is at the 20th line, appears far from the first line.
Figure 6: Output obtained by tracing (fib 5).
On the other hand, Figure 7 is a resulting picture when (fib 5) is evaluated. Only the picture is enough for us to understand that this program is written using double recursions. We can also find that the left branch contains exactly the same figure as the right branch. That indicates the fact that the program executes the same calculation twice. Therefore, it will be beneficial for programmers to use our system in addition to the trace.
Figure 7: A visualization obtained by evaluating (fib 5). (1) Initial state. (2) The system is going to evaluate (fib 4). (3) The evaluation of (fib 2) which is called in (fib 3) is finished. (4) The evaluation of (fib 3) is finished. (5) The evaluation of (fib 4) is finished. (6) (fib 5) is completed. We can understand that this program is written using double recursion. We can also notice that the left branch contains exactly the same figure as the right branch. It indicates that this program is doing the same calculation twice.
We are currently extending our system to combine textual information such as function names and environmental variables. We are also implementing stepper capability in our system. Showing visual information and textual information together can be more useful for programmers.
The system can also be used as a performance tuning tool. By using the local drawing rules described in section 2.2, each primitive function is displayed as a white sphere. Therefore, a function written in a inefficient way will produce unnecessarily many white spheres. For testing this feature of the system, we visualized several list operational functions coded by different programmers. From the results, it was obvious for us to see which program was written in a efficient way.
Our system can also be used to understand program execution in a macroscopic level. Each figure generated by our system is an abstraction of the program execution. When we visualize a program which works correctly, we get a good image of the program execution. Even if we make a minor change which does not affect the program control flow, the entire figure remains almost the same. For example, a single recursive program such as a factorial program will always generate the spiral as shown in Figure 5. A double recursive program such as a Fibonacci program will generate a binary tree as shown in Figure 7. If the resulting figure is changed considerably, a programmer can notice that he might have made fundamental mistakes.
In addition, our system can be used as a fractal generator. In that case, inputs to our system do not necessarily follow any semantics. Our system can generate visualization results as long as the program is syntactically correct.
In principle, our system can visualize any Scheme programs. For instance, one program was randomly selected from a programming textbook, and the program was visualized by using our system. Figure 8 shows the visualization result. Even without seeing the program code, we can understand a rough structure of the program just from the picture.
Figure 8: An visualization of a program selected randomly from a programming textbook. Just by seeing the visualization result, we can have a rough image for the program structure. In principle, our system can visualize any Scheme programs.
We used Scheme because of its rapid prototyping capability. However, our framework can also be applied to compiler-based languages. We can obtain runtime information from an executable file compiled with debug flags. By using that information, it is possible to draw pictures in a similar bottom-up manner.
Algorithm animation systems[2,3,14] visualize various algorithms by using animation effectively. In general, the system expects two kinds of users, designers and end-users. Designers design visualization as it directly represents the algorithm, and implement the customized system by using algorithm animation toolkits. End-users insert software probes into their programs and see how algorithms work. Therefore, the end-users can use an algorithm animation system only when the system is customized by designers.
Lieberman[15] is a visualization tool for parallel logic programs. It tries to generate abstract visualization in a similar way as our system. VISTA's visualization is static, and it is based on a trace data. It maps a reduction tree generated by parallel Prolog into a concentric circle. As a result, every result tends to be similar, and each branch radiates in all directions.
According to Myers [11], program visualization systems are classified as static or dynamic, and as code-visualization or data-visualization. Our system should be categorized as dynamic code-visualization. However, as we described before, there are few systems that visualizes program control flow dynamically.
Our system has been influenced by the L-system[13] more than other program visualization systems. Starting from an axiom, the L-system produces a string using production rules. The system takes the obtained string as input and produces a new string. This process is repeated. When the string is translated into a visual representation, a fractal image is generated.
Similarly, our system takes an S-expression, instead of an axiom, as input. The S-expression is evaluated by an evaluator instead of a production system. If the S-expression is not an atom, its elements are evaluated recursively. During the evaluation process, the system draws a picture by using drawing rules.
A bottom-up approach for program visualization is proposed in this paper. Two new concepts, local drawing rules and a scaling mechanism, were introduced as key components of the proposed approach.
We have shown the proposed approach has advantages over conventional approaches in the following points:
There are following phrases in Mandelbrot's book [9, p. 293].
"This plate can be credited in part to faulty computer programming. The 'bug' was promptly identified and corrected. ..... The change that had been wrought by a single tiny bug in a critical place had gone well beyond anything we had expected."
Feedback systems have an ability to enlarge small errors significantly by iteration[12]. Our goal is to develop a visualization tool that amplifies even small bugs.