Andrew Consortium
School of Computer Science
Carnegie Mellon

August, 1994

The 1994 Visual Languages Comparison


Moderator: Wilfred J. Hansen, Director, Andrew Consortium, School of Computer Science, Carnegie Mellon University, Pittsburgh, PA 15213-3891

Panelists: Brigham Bell, USWest; Greg A. McKaskle, National Instruments; Garth Smedley, Prograph; Dan Kimura, Washington University; Joerg Poswig, Universitaet Dortmund

(C) 1994 IEEE. Reprinted with permission, from Proceedings 1994 IEEE Symposium on Visual Languages, IEEE Computer Society Press, Los Alamitos, CA, October 4-7, 1994. St. Louis, Missouri, to appear.

Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the IEEE copyright notice and the title of the publication and its date appear, and notice is given that copying is by permission of the Institute of Electrical and Electronics Engineers. To copy otherwise, or to republish, requires a fee and specific permission.


Abstract


Diverse visual languages have been proposed, implemented, and published; but each is demonstrated on problems chosen by its authors. To make a fair comparison, the 1994 Visual Languages Comparison project proposed a set of three problems and solicited solutions to these problems in various visual languages. Submissions arrived for one graphic rewriting system--ChemTrains--and four data flow languages--LabVIEW, Prograph, Show and Tell, and VisaVis.




Visual programming has been a fruitful and provocative area of research with many diverse languages proposed and implemented. Since some of these are proposed for general programming, it is fair to ask how well they can be used for typical programming problems. To explore this issue a committee chose three problems and invited authors of visual languages to solve those problems in their languages.

Submissions were received from ChemTrains, which is a graphic rewriting system, and four data flow languages: LabVIEW, Prograph, Show and Tell, and VisaVis. All submissions included solutions to the first problem; the other problems were more complex and received fewer solutions.

1. Prime number generator

The first problem was intended to test computation and iteration over a set of data:

Write a program to compute the number of primes in the first k integers, where k is a value elicited from the user at run-time.

The canonical solution to this problem is the Sieve of Erastothenes, which starts with a list of integers and crosses out those which are multiples of primes. After crossing out multiples of the ith prime, the i+1th prime is the next larger undeleted entry. This scheme requires no division and is usually faster than algorithms with division, but only the ChemTrains and LabVIEW solutions used this approach.

1.1 ChemTrains - Brigham Bell

ChemTrains is a visual production system (or rule-based) language, in which both the rules and the arena on which they operate are defined using pictures. These pictures are composed from four kinds of objects--text, boxes, ovals, and freehand sketches--interconnected by unidirectional or bidirectional links. Each rule consists of a pattern picture and a result picture.

For execution, the pattern picture in each successive rules is checked against the arena. When the pattern picture matches a portion of the arena, that portion is modified as indicated by the differences between the pattern and the rule's result picture. The only attributes that are matched are objects, connections, and containment; no other geometric constraints--such as adjacency--are considered. For a further description of ChemTrains design and its rationale refer to [Bell, 1992a; Bell, 1993].

The ChemTrains prime number program requires eight rules: skip-non-prime, delete-non-prime, increment-multiple, increment-prime-finder, cleanup, condense, start-prime-filtering, make-integer-list. The first four filter out the non-prime numbers from an ordered list of integers. The next two remove extraneous image elements and condense the prime numbers into a sequence.

The final two rules start up the process by making a list of integers to a specified length and inserting three pointers to reach this initial diagram:

Pointer P ("Prime", ) points to a currently known prime number whose multiples are used to delete non-prime numbers.
Pointer M ("Marker", ) travels between the P pointer and the end of the list, deleting multiples of P's integer.
Pointer X ("indeX", ), marches upward from zero while M is advancing; when X reaches P, M has reached a multiple of P.

Increment-prime-finder moves M and X each to the right by one cell:

Eventually, pointer X, , will arrive at the same cell as P, . Then because of rule order, the second rule, delete-non-prime, will fire:

The italicized n is a ChemTrains "variable"; it will match any object, in this case an integer. Delete-non-prime moves X to zero and changes the integer over M to an "x". Subsequently, M and X will resume marching to the right under rule increment-prime-finder.

The third rule, increment-multiple, fires when pointer M has reached the end of the list:

It moves P to the right, moves M to join P and moves X from wherever it is back to the zero cell. Usually the result will leave P pointing at a cell with an "x" instead of an integer, so the next rule to fire will be skip-non-prime which moves P and M to the right together until they are at the next cell with an integer. By construction, this is the next prime.

At one point in the execution, the multiples of two have been deleted and the integer 9 is just about to be deleted as a multiple of three:

Eventually, this final state is reached:

with all the primes shoved to the left by the condense rule.

One advantage of this solution is that it produces a graphical--and potentially educational--simulation of the Sieve of Erastothenes. The solution illustrates the importance of rule order; for instance, "increment-prime-finder" must follow "delete-non-prime" or the program will not delete non-prime numbers.

1.2 LabVIEW - Greg A. McKaskle

LabVIEW is a data flow language with a large library of predefined functions and interaction images. Each data flow diagram has an associated front panel--a graphic representation which can accept input from the user and provide imagery as feedback. See [Daley, 1992], [Jagadeesh, 1993], [Kodosky, 1991].


Figure 1a. LabVIEW primes, front panel

The front panel shown for the primes problem, Figure 1a, shows SampleSize as a user set-able parameter and NumberOfPrimes as a computed value. These are displayed with standard widgets supplied with LabVIEW. The corresponding block diagram, Figure 1b, stretches from input of SampleSize on the left to output of Primes and NumberOfPrimes on the right. The left side of the diagram initializes a Boolean array to contain two false values (for 0 and 1) and SampleSize-minus-2 true values. Then a FOR loop is executed N times with SampleSize supplied as the value for N; if the ith element is false, the number isn't prime and the box with the dark grey border is not executed. If the ith element is true, it is prime; so all multiples of i, starting at twice i, are set to false by the computation within the innermost box.

Figure 1b. LabVIEW primes, block diagram

Arithmetic operations are shown in triangular blocks and array operations in rectangles with suggestive pictures. From left to right, these rectangles have the semantics of:

generate an array of like values (twice)
concatenate two arrays
select the ith element of an array
store a value at a location in an array

The rightmost operator rectangle invokes an operation defined with another data flow diagram. It selects from an array of integers those corresponding to the true values in the Boolean array. The associated front panel is the lower half of Figure 1a: it displays a sequence of white or black disks for the Boolean values and a sequence of integers giving the primes.

1.3 Prograph - Garth Smedley

Prograph is a visual object-oriented data-flow language. Classes, attributes, and methods are created and modified through direct manipulation of icons on the screen. Prograph has an integrated development environment with an editor, interpreter, debugger and compiler. The interpreter supports creating, editing and browsing code, even while it is executing. Prograph offers class libraries, one of which implements the Macintosh graphical user interface. [Cox, 1989]

The prime number computation takes advantage of Prograph's built-in list handling. In these first two panes,

"try candidate" has three inputs, the second of which is a list. The call on "try candidate" in the first pane shows that it is iterated, with the left output being supplied as the left input and the list recycling in the middle. The comparison of candidate+2 with K determines when to terminate the loop.

The call on "add it or not" determines whether to add the candidate to the list. This function is implemented with two panes, called "cases":

The first of these iterates through the list of known primes with predicate "prime?" calling it once for each element of the list as indicated by "...". When the list is exhausted, the case attaches the candidate to the list of known primes. If the predicate fails, the x in the square--called a "next case control"--terminates the first case and initiates the second, which discards the candidate. The "prime?" block

determines whether the candidate is divisible by a known prime. The check in the square terminates the graph--succeeding--if the current list element exceeds the upper bound. The octagon terminates with failure if the division produces a remainder of zero.

1.4 Show and Tell (STL) - Takayuki Dan Kimura

Show and Tell (STL) is a data flowgraph language with the distinction that arbitrary images can be utilized as function names; in Figure 2, these images are handwritten names. The upper left window shows the STL drawing panel and the lower right the list of objects used in this solution. The output (3 5 7 11) is in the middle bottom window.

The notation is this:

Empty box = variable
Thick box = formal parameters
Dotted box = predicate
Double box = iteration control
Pair of open triangles = iterate value
Meshed rectangle = element by element

Figure 2. Show and Tell primes

The "Prime" panel is the main program, which finds the primes in the first five odd integers. On the left "3,5,7.." is invoked to create the list 3, 5, 7, 9, 11. This list serves as the initial value through the paired open triangles on the upper-line through the iteration box; the entire list, as modified by "Sieve" is the value on this line and serves as input to the next iteration. At each cycle, the first element of the current upper-line list is extracted with "top". When there are no more elements, "top" will fail and the iteration in "Prime" terminates. Otherwise, the first element is a prime and is appended to the output list in the lower left. That same first element and the current upper-line list are passed as parameters to "Sieve" which produces a new list omitting the first element and its multiples.

In the other cases of paired open triangles--in "3,5,7..." and "mod"--a single value is passed in, modified, and passed on to the next iteration. The list output from "3,5,7..." is via the meshed rectangle port at the bottom, which assembles the values from successive iterations in which the predicate (>0) succeeds. "Mod" repeatedly subtracts its second (rightmost) parameter from the iterating first parameter; the output is the last value before the predicate (<=0) fails.

The upper line through "Sieve" is through meshed rectangles, so each element of the list value is processed in a separate iteration. If the predicate (>0) succeeds, the current iteration value is appended to the output list under construction. "Top" is an inefficient version of what should be a primitive to find the first element of a sequence. Its first iteration succeeds because the first element from the list is greater than zero; subsequent iterations fail because the input element is not equal to the element from the previous iteration.

1.5 VisaVis - Joerg Poswig

VisaVis is a data-flow language with second order functions as a special focus. Such a function takes a function and a collection of data as arguments and applies the function to the data in some manner. Users can define their own second order functions in the language.

The algorithm for primes is in four parts, one in each quadrant [of a larger diagram omitted for space considerations]. In the upper left, VisaVis's "interval" operator generates a list of the integers from 2 to k and this list is processed through the "primes" operator. The latter--in the upper right quadrant (and sketched in Figure 3)--is a recursive function which terminates when the list is empty. Otherwise the first element is taken to be the next prime number and is merged with the results of the subsequent computations. The rest of the sequence and the first element become the two parameters of "sift", the output of which serves as input for the next recursive call (in the circle labeled "primes"). The final step is "Merge", another VisaVis operator, which attaches the prime from the current iteration to the list from the recursive call.

Figure 3. VisaVis "primes" function. Sketch of recursive "primes" function which extracts primes from a list of integers.

The "sift" process is in the lower left quadrant where the built-in second order function "FilterWithArg" applies the function "ModEqualNot" to the list and the current prime. "ModEqualNot" in the lower right returns True if the current list element is not divisible by the current prime.

The relation of the parts of the program are not clear in Figure 3, but can be made clear with the VisaVis "hierarchy tool", a simulated three dimensional image which depicts the nesting of program parts and the data values in transit. For an illustration of the animation of execution, see [Poswig, 1993].

In addition to the solution in Figure 3, which uses division, a solution was constructed with the hierarchy tool that employed a true sieve using addition instead of division. This solution proved slower, however, possibly due to simulation overheads.

2. Checkbook

The second problem aimed at traditional business computing requirements and especially the need for long term storage of information in files:

Write a simple program for checkbook accounting. It should accept user input for deposits and withdrawals to the account. Withdrawal information should include check number, date, payable to, reason, and amount. Deposit information should include date, reason/origin, and amount. Design a GUI with user interaction in a suitable layout that allows entry of the data and selection of the actions in any reasonable sequence. The program should maintain a list of all transactions and allow it to be reviewed.

The two commercial vendors--LabVIEW and Prograph--presented solutions to this problem, but space limitations prevent displaying them here. Both vendors took advantage of their special strengths.

LabVIEW's solution features realistic and colorful forms for check register, withdrawal, and deposit. These are front panels to data flow diagrams implementing the algorithms. When idle, the algorithm polls for input every quarter second.

In Prograph the interface editor was used to create screen interfaces for checks, deposits, and the transaction list shown in Figure 4. The algorithm is implemented with the aid of a simple class hierarchy: The Transaction class is an abstract class with two subclasses, Check and Deposit. The Account class has attributes for the current balance and a list of Transactions. Methods in the Account class add transactions to the list and update the balance. Each window in the application is a subclass of Prograph's Window class, while the transaction list is an instance of class Grid, from Prograph's class library.

Figure 4. Prograph check register


3. Rolling wagon wheel

Since visual languages are inherently graphical, it seemed appropriate to determine if they could perform a computation whose primary purpose was animation of a graphical image:

Write a program to display a simulation of a spoked wagon wheel rolling down a ramp whose slope can be varied by the user.

The trivial ChemTrains program for the rolling wheel has only two rules: an initial diagram with the wheel at the top and a final diagram with it at the bottom. ChemTrains automatically animates motion between two states. In fact, however, a more elaborate solution was created which divides the ramp into a series of sections and has a rule that moves the wheel from one section to the next.

LabVIEW programs draw pictures by appending drawing codes together and providing a control that can render them on the front panel. The codes are 2D primitives--circles, lines, bitmaps, and so on--and are appended by wiring together icons with appropriate parameters for diameter, color, etc. The draw wheel program encapsulates these drawing commands into a module that appends the drawing commands for a parameterized wheel. Similarly, other icons draw the ramp, calculate the effect that gravity has on the wheel position, and update the wheel rotation for a given wheel position. See the front panel illustration in Figure 5. The associated data flow diagram does the kinematics to accelerate the wheel due to gravity.
Figure 5. LabVIEW wagon wheel, front panel

In Prograph the wheel was programmed by creating classes for the ramp window and the wheel. Attributes in these classes include the height of the ramp, the position of the wheel, and the orientation of the spokes (diagonal or orthogonal). Methods of the ramp class provide for drawing or dragging the ramp and for animating the wheel, while the wheel class has methods for drawing the wheel and for drawing its spokes. Movement down the slope is at constant speed.

4. Observations

Various statistics were elicited from the submitters and are summarized in Tables 1 and 2.
ChemTrains LabVIEW Prograph Show and Tell VisaVis
Components 8 2 5 5 4
Pixels/100,000 6.0 2.9 2.3 4.9 1.5
Operators n.a. 14 8 10 13
Creation time, expert 2 hrs 1 hr 10 min 2 hrs 15 min
Creation time, tyro 2-3 hrs 15-20 min 25 min
Storage space 4K 124K 20K 12K 19 K
Time (primes<1000) 0.034 * 0.23 # 80 &
Table 1. Data for Primes problem. Component - a connected graph or a rule. For the primes program, ChemTrains and LabVIEWs reuse a single window to show successive components, Prograph utilizes one window per component, and both Show and Tell and VisaVis manage to display all components simultaneously. Operator - an icon in the graph, not counting loop control. Times for tyros are crude estimates by the panelists. Empty cells are values not reported.

* seconds on a Mac IIfx. An improved algorithm takes .019 seconds.
# seconds on a Quadra 700 ( 25 MHz, 68040).
& seconds estimated for PC 486/33MH. Observed time was 3 sec for primes in 1...100. Another solution in VisaVis using addition instead of division took 9 sec for primes up to 100.
Checkbook Wagon Wheel
LabVIEW Prograph ChemTrains LabVIEW Prograph
Components 3 24 * 2 8 5 *
Pixels/100,000 3.4 30.3 12.2 19.4
Creation time, expert 2.5 hrs 4 hrs 0.5 hrs 15 hrs 2 hrs
Creation time, tyro 3-4 hrs 6-8 hrs ~ 40 hrs 4-6 hrs
Storage space 111K 39K 3K 400K 36K
Table 2. Data for Checkbook and Wagon wheel problems.

*The checkbook program has 8 classes with a total of 24 methods. The wagon wheel program has 2 classes with a total of 5 methods. Each method has one or more graphs.

For comparison the sieve was coded in C in under half an hour. Execution on a DECstation 5000/20 required 3.6 milliseconds to find the 168 primes among the first thousand integers. The complete program required 53 operators, but only 13 of them would be required in a visual version. (In the statistics, loops and conditionals are not counted as operators.) Thus the C version is comparable in number of operators to the visual versions. The heart of the routine is

/* find primes in 2...k
s is an array of booleans, initially TRUE

*/
p = 2; lim = sqrt(k);
while (p < lim) {
for (i = p+p; i <= k; i += p)
/* delete multiples of p */
s[i] = FALSE;

/* assert: for j in 2 <= j <= p**2
s[j] is true iff j is prime */

while ( ! s[++p])
{} /* find next prime */

}

Since arrays are such a vital component of the sieve approach, it is interesting that C is better suited to dealing with arrays than many visual languages. The latter tend instead to deal with higher-level (and more generally useful) constructs such as sets and lists.

More than one observer has noted that the various visual programs are not easy to read, despite the alleged advantages of visual expression. This is a problem with visual languages; there is not yet enough shared learning about what computational icons mean. After all, most of us went through high school algebra which taught the meaning of expressions like ax2+c and C programmers have learned to understand compound operations like while ( ! s[p++]) {}.

The most interesting aspect of the various flow diagram solutions are the conventions for iteration. Most have some notion that a line going in one side is connected from the output from the previous iteration at the opposite side of the box. In three of the systems a predicate determines whether the iteration continues. VisaVis utilizes recursion and second order functions instead of iteration. ChemTrains has only one loop, the one in the central execution driver; it is conceivable that an extension to ChemTrains would have multiple rule sets through which looping would be independent; this might reduce the importance of rule order.

Most of the solutions exploited one or more built-in facilities of the particular programming system. For instance,

LabVIEW and Prograph's solutions used existing graphical elements to create visually attractive interfaces.
LabVIEW's prime program utilizes built-in array access and display operators.
Prograph's prime solution utilizes built-in list handling.
In all the prime programs, storage management was simpler than in the C version.
Prograph's check book is based on its Grid class.
VisaVis' Primes utilized the FilterWithArg 2nd order function.
ChemTrains could have solved the wheel problem trivially because ChemTrains automatically animates motion between states.

It may be that built-in facilities are a major advantage of visual programming systems; since programs these days need to have graphical components, visual systems can integrate these in a program more readily than can a textual-only language system. It is interesting to speculate that the advantages of visual systems may not be in the programming itself, but rather in more convenient integration of programming, testing, and using the result.

Acknowledgements: The moderator is grateful for the aid of the committee for the 1994 Visual Languages Comparison: Kris Blom, NASA, JPL; Ron Dolin, Univ. Calif., Santa Barbara; Joe Pfeiffer, New Mexico State Univ.; Catalin Roman, Washington Univ.; Ephraim Glinert, RPI. Brigham Bell's early enthusiasm was crucial.


References

[Bell, 1992a] Bell, B., Using Programming Walkthroughs to Design a Visual Language, Ph.D. Dissertation, Technical Report CU-CS-581-92, University of Colorado, January 1992.

[Bell, 1993] Bell, B. & Lewis, C., "ChemTrains: A Language for Creating Behaving Pictures," Proceedings of the IEEE Symposium on Visual Languages, August 1993.

[Cox, 1989] Cox, P.T.; Giles, F.R.; Pietrzykowski, T., "Prograph: a step towards liberating programming from textual conditioning", Proc. 1989 IEEE Workshop on Visual Programming, Rome (Oct, 1989), 150-156.

[Daley, 1992] P. Daley, "Automated Monitoring of a Soil Vapor Remediation System," Scientific Computing & Automation, May 1992.

[Jagadeesh, 1993] J. Jagadeesh & Y. Wang, "LabVIEW" Product Review, Computer, February 1993.

[Kodosky, 1991] J. Kodosky, J. MacCrisken, & G. Rymar, "Visual Programming Using Structured Data Flow," Proceedings of the IEEE Workshop on Visual Languages, October 1991.

[Poswig, 1993] J. Poswig, G. Vrankar & C. Moraga, "Interactive animation of visual program execution," IEEE Symposium on Visual Languages, 1993, 180-187.

[Poswig, 1994] J. Poswig, G. Vrankar & C. Moraga, "VisaVis - A higher order functional visual programming language", Journal on Visual Languages and Computing 5, (1994), 83-111.