Andrew Consortium
School of Computer Science
Carnegie Mellon
August, 1994
(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.
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.
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 i^{th} prime, the i+1^{th} 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.
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.
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 i^{th} element is false,
the number isn't prime and the box with the dark grey border is not
executed. If the i^{th} 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:
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.
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.
The notation is this:
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.
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.
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
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.
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 & |
* 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 |
*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
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 ax^{2}+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,
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.
[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.