Programming and Computer Software, Vol. 27, No. 4, 2001, pp. 217–226. Original Russian Text Copyright © 2001 by Vazhenin, Mirenkov.
Visual Programming System VIM A. P. Vazhenin* and N. N. Mirenkov** * Institute of Computational Mathematics and Mathematical Geophysics, Siberian Division, Russian Academy of Sciences, Department of Mathematical Support for High-Performance Computational Systems, pr. Akademika Lavrent’eva 6, Novosibirsk, 630090 Russia e-mail:
[email protected] ** The University of Aizu, Laboratory for Parallel Distributed Computations, Tsuruga, Ikki–machi, Aizu–Wakamatsu City, Fukushima, 965-8580 Japan e-mail:
[email protected] Received April 10, 2000
Abstract—In this paper, aspects of creation of the visual programming system VIM based on “filmification” of application algorithms and methods are considered. Abstract self-explanatory films, which are series of frames/pictures with video, animation, audio, and other multimedia effects, are used for presentation of the method. Each frame of such a film corresponds to a certain stage, called computational step, of problem solution. A hierarchical organization of objects of such a system is suggested. The objects include both multimedia components, which demonstrate properties or an idea of the algorithm, and corresponding template programs serving for automated generation of the program created on the basis of the film specification and formulas defined by the user during the input dialog.
1. INTRODUCTION Modern multimedia systems and the Internet allow geographically distributed community of users to use various methods of information exchange and processing, as well as new and effective ways of knowledge representation, such as visualization, animation, audio, and the like. This results in the appearance of very interesting multimedia applications and, in particular, new technologies aimed at the improvement of traditional programming methods. Specifically, in spite of wide use of parallel computations for solving largescale problems, only relatively small group of experts can really use them. Therefore, the problems of portability and effective reusability of software components has been the subject of intensive studies up to now. It should be noted that pictograms, electronic tables, forms, and charts are widely used practically in all computer systems. This usage is supported by the development of the theory of visual languages, as well as their pictogram and symbolic representations [4, 8, 11]. Visual programming, which uses examples or templates, provides a good evidence of the implementation of friendly calculations [17]. Corel DRAW, Photoshop, Lotus 1-2-3, WordPerfect, and Scientific WorkPlace allow the user to manipulate visual objects of very high level of functionality [6]. An audio color teaching film based on animation of program data is known in the literature since 1981 [2]. A certain number of commercial systems (Khoros, AVS, etc.), which realize various methods of data visualization, are worth noting as well. Typical examples of commercial systems oriented to the end user are such systems as Alias, Wavefront, 3D studio MAX, Avid-composer. However, the systems
and approaches described above are either technologies of very special purpose or have not demonstrated all their advantages up to the present. Various publications concerning skeleton-based methods, support software for these methods, visual languages and systems, as well as approaches related to “human–computer” interface, may be viewed as an important step on the way of increasing the productivity of programmers and users. Cole [12], Scillicorn [26], Darlington [14], Geerling [15], and many other authors presently develop structural approach for description of architectures, computational schemes, and programs. New compilation facilities and their interactive visual environment are discussed in works of Bacci, Danelutto, and Pelagatti [1], Bode [4], Burkhart [7], Gilder, Krishnamoorthy, Punin [16], and others [8, 3, 10]. McIntosh-Smith, Brown, Hurly [21], Kessler [18], Decker, Dvorak, and Rehmann [13] created intellectual algorithms and systems for generation of parallel codes. Multimedia approach for interactive specifications of applied algorithms and data representations [23, 24], which is referred to as VIM technology, is based upon a collection of computational schemes represented in the “film” format. Each scheme by itself reflects some knowledge about a certain method of data processing. When applied to computational methods, a given scheme determines a set of nodes (structure) and/or objects moving in a space–time coordinate system, as well as partial order of scanning these nodes and objects. The user represents his/her algorithmic ideas in the form of a computational scheme and refines its particular contents during the program generation. The
0361-7688/01/2704-0217$25.00 © 2001 åÄIä “Nauka /Interperiodica”
218
VAZHENIN, MIRENKOV
purpose of such an approach is to increase efficiency of applied programmers, to support demonstrativeness of parallel programs, and to make parallel computers accessible to a large number of users. In this work, we discuss specific features of VIM technology, consider basic multimedia components of the VIM compiler, suggest a hierarchical organization of objects in such a system, describe basic constructs of a specification language for formulas, and demonstrate working environment of a VIM program, which includes means for checking and controlling the execution of the program and a subsystem for visualization of matrix data. 2. SPECIFIC FEATURES OF VIM PROGRAMMING 2.1. Multimedia Signs The main idea of VIM technology consists in the combined use of visualization, animation, and sonification when representing application methods. The name VIM stands for “VIsualization of Methods.” Note that the method is defined as a plan of actions/steps of problem solution. For specification of a method (task for a computer), the so-called abstract films are used, which are sets/series of pictures or images of various formats, types, and representations. Thus, a VIM film, just as an ordinary film, is a sequence of frames. The difference is that, in a VIM film, each frame is made to correspond to a certain stage of problem solution. For example, each frame of a film demonstrating solution of a system of linear algebraic equations may correspond to a step of elimination of one variable. Hence, a sequence of such frames demonstrates the dynamics of changes in time produced by the method. In other words, a film is a “dynamic shell” or an “idea” of computations. This type of abstraction relates to multimedia objects or special-purpose signs. These signs are self-explanatory, which means that no special training is required to understand and use them. This is achieved primarily through the use of images and sound instead of a text. Elements of a VIM film, when applied to computational methods, are a parametrized set of nodes in fourdimensional coordinate space–time. They specify also partial order of scanning (traversing) these nodes. A set of nodes forms a structure. Traditional examples of structures are linear and ring arrays, lattice, tree, pyramid, multistage network, and the like. Each structure may also be viewed as an index computation space or as a data collection. In order to organize computations, it is required to define operations on each node in addition to the scanning order. A particular set of these operations determines specific applications of the problem being solved. From this point on, we will use the term formula in reference to these objects of a film. The validity of such an approach is based on the fact that various methods often have similar schemes and differ only by
operations or formulas used when “visiting” the nodes of the structure. In particular, in spite of the existence of thousands of different algorithms, the number of basic strategies of implementation of these algorithms is relatively small. This point is well illustrated in the work [25], which shows the generality of the schemes for path problem and for the Gauss–Jordan algorithm. Consider a very efficient approach “divide and conquer.” A large number of best and widely used computer algorithms reduce to this model. Another example is the branch and bound method. This technology is applied to solving a wide range of problems in combinatorial optimization, operations research, and artificial intelligence. Both of these models are, in fact, special cases of computations on trees and can be represented by a limited number of algorithms for these structures. Similar situation takes place for algorithms of solving linear algebra problems. There are many iteration methods and schemes for these problems, which, as a rule, reduce to a rather limited number of execution schemes. These schemes are closely related to the character of scanning procedures on the nodes of a latticetype structure. For implicit methods, the execution scheme of these procedures is based on the propagation of the computation wave front along diagonals or sides of the structure fragments from one boundary to another and back. Wave fronts may be linear or twodimensional structures. As a rule, the computations in all nodes of such a front can be executed in parallel, while the computations related to various positions of the front itself are performed sequentially. In addition to wave schemes, the so-called multicolor (for example, black/white ordering) schemes are used. The computations in all nodes of one color may be executed in parallel, those on nodes of different colors, sequentially. Explicit schemes may use similar methods as well. 2.2. Films and Template Programs A VIM film is an architecturally independent multimedia scheme that defines a data structure and the computations on this structure. This scheme is user-oriented and serves as a base for man–machine dialog, which results in creation of a program for a computer. This explains the dualism of the properties of a VIM film, which, along with multimedia objects, contains also textual components or program fragments. As shown in Fig. 1, each film is associated with a set of templates. These templates are programs or special files (control data). This part of the system is invisible for the user. When the user manipulates the film, the system performs adequate transformations of the templates. In other words, whereas multimedia schemes form a special film language for the users, the templates are some intermediate language, which accumulates knowledge about the method. Figure 1 illustrates also the process of creation of an executable program based on the VIM
PROGRAMMING AND COMPUTER SOFTWARE
Vol. 27
No. 4
2001
VISUAL PROGRAMMING SYSTEM VIM
219
Fig. 2. The hierarchy of objects in a VIM system. Fig. 1. Basic VIM elements and operations.
film and on the information inputted by the user. All operations performed on a film (creation, insertion or removal of frames, input and editing of formulas) are registered in the so-called transformation file, which is used for the specification of template program parameters. These templates reflect the computation scheme of the film and, depending on the situation, may use the transformation file as “include” file via macro-substitutions or by way of inclusion of special libraries of program modules. The program template is used for the generation of a final executable code. This code may be sequential or parallel depending on the template type, architecture, and basic software. Since the templates are, in fact, specially developed architecture-oriented program fragments, the VIM technology supports the portability of parallel programs and opens new perspectives for supercompilers. 3. VIM OBJECTS AND THEIR HIERARCHY As was already noted, the dualism of VIM-film properties demands the availability of special objects operating with both visual and textual components. Figure 2 shows the hierarchy of VIM classes. The lowest level of this hierarchy is occupied by a VIM node. A set of VIM nodes forms VIM structure. Note that the way the nodes are grouped determines the type of the structure (line, lattice, hypercube, etc.). It is the structure that is the most important factor in the film specialization. For better perception and demonstrativeness, as well as for binding templates to the film, the structure may be supplemented by control lines or structures. One or several structures form a VIM frame, which corresponds to a computational step of the algorithm. When forming an executable code for the frame, formulas specifying calculations must be defined. The last object of the hierarchy is a VIM film, which specifies the order of the frames in time. It should be noted PROGRAMMING AND COMPUTER SOFTWARE
Vol. 27
Fig. 3. The VIM-node editor.
that such a structure organization is rather conditional and allows for recursion and superposition of objects. For example, it is possible to use a film inside a node if the operations performed by it are sufficiently complex. Let us examine VIM classes in more detail and give necessary definitions. 3.1. VIM node A VIM node is an elementary indivisible multimedia domain in 3D space. Multimedia characteristics of a VIM node include a node type, color, shape, the presence or absence of sound effects, and the like. Figure 3 demonstrates the dialog window of the VIM-node editor. As can be seen from the figure, there are many ways to efficiently represent properties of a VIM node, as well as specific features of calculations inside it. One can easily use graphical objects (circles, rectangles, etc.), colors, single and multiframe images, as well as sound patterns. Formulas can be attached to each node. Formulas are meant to be a certain program or simply a set of No. 4
2001
220
VAZHENIN, MIRENKOV - Active VIMnodes - Passive VIMnodes
Tuning area Setting parameters of a scanning loop
I=2
Scanning area
- SubStructure 1 J=2
- SubStructure 3
- SubStructure 2
I=2
- Control Lines
J=2
Fig. 4. VIM structure.
Coordinating area
operations to be executed by an active VIM node. Equivalent nodes are those that have identical visual representations and perform the same computations. 3.2. VIM structure The VIM structure is a set of VIM nodes located in space according to the structure type (1D, 2D, 3D, tree, pyramid, etc.). Control lines/structures are used to address nodes and establish relationships between them (Fig. 4). Substructure is a part of structure containing equivalent VIM nodes. Thus, the same formulas should be attached to the nodes of the substructure to ensure performing identical actions. The substructure configuration determines the order of scanning its nodes when executing the VIM program. As it was already noted, this is to be implemented in the template. Therefore, this object, along with multimedia properties, contains
Redefining location of control structures Fig. 5. Template structure.
a textual (program) component. Thus, each template consists of three parts: tuning area, scanning area, and coordinating area (Fig. 5). The tuning area of a template contains operators specifying parameters of the loop that determines the order of scanning the substructure nodes. The scanning area is a set of loops that scan VIM nodes in accordance with the structure type and the substructure configuration. For example, the sequential scanning of a submatrix may be implemented as follows:
/****************************************/ /* Scanning Loop for 2D-rectangle */ for(_sI=_StRow;_sI
