![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to anim.ms CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [Research Unix] / researchv10dc / vol2 / anim|
Return to anim.ms CVS log | Up to [Research Unix] / researchv10dc / vol2 / anim |
1.1 root 1: .so ../ADM/mac
2: .XX anim 451 "A System for Algorithm Animation"
3: .EQ
4: delim @@
5: .EN
6: .nr dP 1
7: .nr dV 1
8: .nr dT 8 \" tab stops this far apart in .P1/.P2
9: .nr NH .5v \" adds extra space before NH or SH heading
10: .nr ds .5i \" default indent for programs
11: .hy 14 \" set hyphenation: 2=not last lines; 4= no -xx; 8=no xx-
12: .\"
13: .de IN \" assumes called as .INCLUDE filename
14: .sy compile \\$2.t
15: .so \\$2.o
16: ..
17: .de ge \" assumes .ge called as .get
18: .sy trget \\n(.$ \\$2 '\\$3' '\\$4' '\\$5' >junk.\\n($$
19: .so junk.\\n($$
20: .sy rm junk.\\n($$
21: ..
22: .de ru \" assumes .ru called as .run
23: .sy \\$2 \\$3 \\$4 \\$5 \\$6 \\$7 \\$8 \\$9 >junk1.\\n($$
24: .get junk1.\\n($$
25: .sy rm junk1.\\n($$
26: ..
27: .TL
28: A System for Algorithm Animation
29: .br
30: Tutorial and User Manual
31: .AU
32: Jon L. Bentley
33: Brian W. Kernighan
34: .AI
35: .MH
36: .AB
37: A program or an algorithm can be animated by a movie
38: that graphically represents its dynamic execution.
39: For instance, a memory allocator might be animated by lines that
40: appear when memory is allocated and disappear when it is freed;
41: a sort might be animated by a randomly scrambled
42: sequence of lines being permuted into order.
43: Such animations are useful for debugging programs, for developing
44: new programs, and for communicating information about how programs work.
45: This paper describes a basic system for algorithm animation:
46: the output is crude, but the system is easy to use;
47: novice users can animate a program in a couple of hours.
48: The system currently produces movies on Teletype 5620 terminals
49: and workstations that support the X window system, and also renders movies into
50: ``stills'' that can be included in
51: .I troff
52: documents.
53: This paper is a user manual and a tutorial introduction
54: to algorithm animation using the system.
55: .AE
56: .NH
57: Introduction
58: .PP
59: Dynamic displays are better than static displays for
60: giving insight into the behavior of dynamic systems.
61: The pictures in Figure 1, for instance, illustrate four
62: equal-mass bodies moving in the plane
63: under Newtonian attraction.
64: .KF
65: .INCLUDE stars
66: .sp
67: .ce
68: \f3Figure 1:\fP Bodies moving under Newtonian attraction
69: .KE
70: Time marches across the pictures left to right,
71: at roughly equal intervals.
72: Each column, called a
73: .I snapshot ,
74: depicts three
75: .I views
76: of the bodies.
77: The top view gives the current position as a dot; the tail formed
78: by the last few positions hints at the velocity and the acceleration.
79: The middle view renders the path of each body as a line.
80: The bottom view depicts the history of velocities by dots
81: recorded at equal time intervals:
82: low velocities give close dots and
83: high velocities leave the dots far apart.
84: .PP
85: The first snapshot shows the bodies starting slowly, far apart.
86: In the second snapshot they have recently experienced a
87: high-velocity encounter near the center.
88: In the third snapshot the bodies are again far apart,
89: moving slowly toward another encounter in the fourth snapshot.
90: In the fifth snapshot the large time-step of our simulation program
91: violates conservation of energy and sends the bodies racing away
92: from each other.
93: .PP
94: This paper describes the animation system that produced those pictures.
95: A sixty-line C simulation program was augmented with eight
96: .I printf
97: statements to generate a
98: .I script
99: file describing the paths of the four bodies in the three views.
100: That file was processed by a program named
101: .I stills
102: to produce the pictures above, using
103: .I pic
104: and
105: .I troff ;
106: we were able to control what frames were displayed, in what size and form.
107: A program named
108: .I movie
109: displays the same data on a Teletype 5620 terminal or an X workstation;
110: the viewer can control the speed of display,
111: proceed forward or backward through time,
112: and change the screen layout to emphasize certain views.
113: Those components can be depicted as:
114: .PS
115: boxht = .25; boxwid = .6
116: ellipseht = .25; ellipsewid = .6
117: lineht = .1; linewid = .4
118: down
119: box "generator"
120: line down
121: A: ellipse "script"
122: line from A.se right down
123: box "stills"
124: line down
125: box invis "pic | troff | ..."
126: line from A.sw left down
127: box "movie"
128: line down
129: box invis "5620, X, ..."
130: .PE
131: .PP
132: Several systems have been developed for algorithm animation
133: |reference(sedgewick brown ieee).
134: Most of those systems produce animations of very high quality;
135: unfortunately, they are expensive in both programmer time and CPU time.
136: Our system is at the opposite end of the spectrum:
137: its output is primitive, but the system is easy to use;
138: a new user can animate a simple program
139: in an hour or two by adding a few lines of code.
140: Although our system was designed primarily with program animation
141: in mind, the gravitational example shows that it can be useful
142: in other domains as well.
143: .PP
144: Section 2 introduces the system by animating a sorting algorithm.
145: Sections 3 through 5 describe the three primary components of
146: the system:
147: script
148: files,
149: .I movie ,
150: and
151: .I stills .
152: Section 6 describes the animation of several larger programs,
153: and Section 7 discusses a few everyday matters about using the system.
154: .NH
155: A Simple Example \(em Sorting
156: .PP
157: Insertion sort is the method most card players use.
158: As each card is dealt, it is inserted into
159: its proper place among the existing cards.
160: To sort the array @X[1..N]@, insertion sort maintains the
161: sorted subset in @X[1..I]@ and increases @I@ from 2 to @N@.
162: The subarray @X[1..1]@ is sorted by definition.
163: The first phase of the algorithm sifts @X[2]@ down
164: so that @X[1..2]@ is sorted, the second phase sifts
165: @X[3]@ down so that @X[1..3]@ is sorted, and so on.
166: .PP
167: Here is an implementation of insertion sort in
168: .I awk |reference(awk book):
169: .P1
170: .get is.awk
171: .P2
172: The first
173: .CW for
174: statement sprinkles
175: .CW x[1..n]
176: with random integers in the range @1..25@, and the second and third
177: .CW for
178: statements perform the insertion sort.
179: The function
180: .CW swap
181: exchanges array elements;
182: .CW show
183: prints the current state of the array.
184: .PP
185: If we run this program with
186: .CW n
187: set to 7, we get this static display
188: of sorting a 7-element array of random integers:
189: .P1
190: .run sh is.awk 7
191: .P2
192: .PP
193: The animation system provides an alternative:
194: by adding a few more
195: .CW print
196: statements to the program, we can produce input for the animation system,
197: thus providing a dynamic display
198: of the sorting process.
199: Furthermore, we can use graphics as well as text,
200: to give a more visual presentation of the algorithm.
201: .PP
202: For this example, we decided to present two
203: views.
204: The top view simply shows the numbers in the array as they are sorted;
205: it is essentially the same as the textual output above,
206: except that we have added a vertical bar:
207: elements to the left of the bar are in order.
208: The bottom view is graphical: the value of each element is represented
209: by the length of the corresponding vertical line.
210: .PP
211: These six snapshots
212: show the state after each phase of the sorting algorithm:
213: .sy make.sorts
214: .INCLUDE is3
215: .PP
216: Although the two views represent the same information,
217: they are useful for different tasks.
218: The textual nature of the top view is easier for novices to follow,
219: and the complete information is handy for debugging small examples.
220: The more visual bottom view is better for displaying large sorts.
221: .sp 1
222: .LP
223: .I "The Program."
224: .PP
225: Here is the complete
226: .I awk
227: program
228: .CW is.gen
229: that generated the animation depicted above.
230: .P1
231: .get is.gen
232: .P2
233: It is very similar to the first version,
234: but we have added the functions
235: .CW less
236: to make comparisons and
237: .CW draw
238: to display elements,
239: as well as several
240: .CW print
241: statements.
242: In addition to performing their sorting functions,
243: .CW less
244: and
245: .CW swap
246: record their actions by printing output
247: into a script file that will serve as input to
248: .I movie
249: and
250: .I stills .
251: This animation uses four commands:
252: .CW line ,
253: .CW text ,
254: .CW view
255: and
256: .CW click .
257: .PP
258: A line from @( x sub 1 , y sub 1 )@ to @( x sub 2 , y sub 2 )@ is
259: drawn by a command of the form
260: .P1
261: @optional_label:@ line @x sub 1@ @y sub 1@ @x sub 2@ @y sub 2@
262: .P2
263: (Throughout this paper, literals are shown in
264: .CW typewriter
265: font and categories are in @italics@.)
266: The coordinates of the line can lie in any range;
267: later programs will scale them appropriately.
268: The label on a line is optional.
269: When a labeled object is drawn
270: the object that previously had that label is erased.
271: Thus for all lines that have the same label,
272: the act of drawing one line erases its predecessor.
273: (There is also an explicit
274: .CW erase
275: command.)
276: .PP
277: Text is produced at @( x , y )@ by a command of the form
278: .P1
279: @optional_label:@ text @x@ @y@ @anything@ @at@ @all@
280: .P2
281: As with lines, labels are permitted;
282: re-use of a label erases whatever object previously had that label.
283: For example, the vertical bar is always printed with the label
284: .CW bar ,
285: so each bar erases the previous one.
286: .PP
287: The
288: .CW view
289: command is used to place output in a particular view.
290: There are two views here,
291: .CW text
292: and
293: .CW geom :
294: .P1
295: view text
296: view geom
297: .P2
298: The
299: .CW draw
300: function draws text in the
301: .CW text
302: view
303: and lines in the
304: .CW geom
305: view, relying on implicit erasure to remove the previous object
306: before creating a new one.
307: Different views are independent, so a label like
308: .CW a1
309: can be used in several views without interference.
310: .PP
311: Interesting events are marked by the
312: .CW click
313: command:
314: .P1
315: click swap
316: click comp
317: click phase
318: .P2
319: .I Stills
320: and
321: .I movie
322: can refer to each click with this mechanism,
323: as we will see in more detail shortly.
324: .PP
325: Labels, view names and click names are arbitrary
326: and unrelated to one another.
327: .sp 1
328: .LP
329: .I "The Script File."
330: .PP
331: Executing the command
332: .P1
333: is.gen 3 >is1.s
334: .P2
335: produces the script file
336: .CW is1.s
337: containing a sort of three elements.
338: The basename
339: .CW is1
340: is for ``insertion sort 1''; the suffix
341: .CW .s
342: identifies it as a script file and is required by the animation system.
343: Here is
344: .CW is1.s ,
345: printed in two columns to save space:
346: .P1
347: .ps 8
348: .vs 8
349: .ta 3i
350: .run 2col is1.s
351: .P2
352: .sp
353: .PP
354: Here is a picture of all clicks in the script file
355: .CW is1.s ,
356: produced by
357: .I stills .
358: .INCLUDE is1
359: As before, time goes from left to right.
360: Both views of the current state are depicted in a snapshot at each
361: .CW click ;
362: the label below each frame tells the name and number of the click.
363: This detailed picture illustrates the animation system;
364: here is a sparser picture that illustrates insertion sort
365: on a 14-element array:
366: .INCLUDE is2
367: .sp 1
368: .LP
369: .I "Making Stills."
370: .PP
371: The last picture was included in this document by this
372: .I stills
373: description:
374: .P1
375: .get is2.t
376: .P2
377: The description is delimited by the lines
378: .CW "\&.begin stills"
379: and
380: .CW \&.end
381: (which correspond, for instance, to
382: .CW \&.EQ
383: and
384: .CW \&.EN
385: in
386: .CW eqn
387: or
388: .CW \&.TS
389: and
390: .CW \&.TE
391: in
392: .CW tbl ).
393: Text following the sharp character
394: .CW #
395: is a comment to be ignored.
396: The
397: .CW view
398: statements specify the empty string as the title for both
399: views of the data.
400: The
401: .CW print
402: statement displays snapshots at the requested
403: .CW click s
404: of
405: .CW phase .
406: .PP
407: The last four statements are parameter assignments of the form
408: .P1
409: @parameter_name@ @value@
410: .P2
411: Assignment to the
412: .CW file
413: parameter names the script file to be displayed.
414: The next two assignments set the height and width of frames,
415: and the final statement causes
416: .CW medium
417: text (the default text size) to be set
418: five points smaller than the current
419: .I troff
420: point size.
421: .sp 1
422: .LP
423: .I "Viewing A Movie."
424: .PP
425: To watch a movie on the 5620,
426: make a window of suitable size and shape
427: and in it type the command
428: .P1
429: is.gen 20 | movie
430: .P2
431: If you want to access the script later, type instead
432: .P1
433: is.gen 20 >is.s
434: movie is.s
435: .P2
436: After a pause to run
437: .CW is.gen
438: (about 15 seconds on a VAX\(tm-750 in this case), the 5620 down-loading procedure
439: will begin;
440: after that (another 30 seconds), the data for the movie itself will
441: begin to appear.
442: When this is finished (also about 30 seconds),
443: a message about the number of bytes
444: sent (about 9500) appears in the upper left corner.
445: .PP
446: At this point, the mouse buttons can be used to
447: redisplay the movie.
448: Button 3 is the main control.
449: It has 9 menu items:
450: .P1
451: again
452: faster 1
453: slower 1
454: 1 step
455: backward
456: fatter 1
457: thinner 1
458: or mode
459: new file
460: Quit?
461: .P2
462: To play the movie again,
463: select
464: .CW again .
465: (This movie takes about 6 seconds at full speed.)
466: You can stop it at any point by pushing any button;
467: a further push of button 1 continues it.
468: To slow the display, select
469: .CW slower ;
470: each selection halves the speed by increasing
471: a wait interval by a factor of two.
472: After three selections the menu reads
473: .P1
474: again
475: faster 8
476: slower 8
477: \&...
478: .P2
479: Try selecting
480: .CW again
481: to see the sort once at this speed, then select
482: .CW faster
483: three times to get back to full speed.
484: .PP
485: The items labeled
486: .CW fatter
487: and
488: .CW thinner
489: control the thickness of lines in an analogous manner.
490: Selecting
491: .CW fatter
492: several times results in obese lines;
493: you may return things to normal with
494: .CW thinner .
495: .PP
496: Three menu items control binary mode settings:
497: .CW 1
498: .CW step
499: or
500: .CW run ;
501: .CW backward
502: or
503: .CW forward ;
504: and
505: .CW or
506: .CW mode
507: or
508: .CW xor
509: .CW mode .
510: For each, the label indicates the next state,
511: not the current state.
512: .PP
513: Normally the movie is played from beginning to end without pause.
514: The menu item labeled
515: .CW 1
516: .CW step
517: puts it into a mode where it displays only one ``step''
518: each time button 1 is pushed.
519: This allows you to inspect the sort a frame at a time.
520: This item changes to
521: .CW run
522: when
523: .CW 1
524: .CW step
525: has been selected
526: so you can revert to continuous action.
527: .PP
528: The
529: .CW backward
530: item causes the steps to be taken in reverse order (time runs backwards);
531: the menu item changes to
532: .CW forward
533: when selected.
534: After the sort ends, select
535: .CW backward
536: and
537: .CW again
538: and watch the array scramble itself before your very eyes.
539: Judicious use of
540: .CW 1
541: .CW step
542: and
543: .CW backward
544: and
545: .CW forward
546: make it easy to examine a few snapshots in detail.
547: .PP
548: Normally items are displayed in ``exclusive OR'' mode,
549: which means that a bit drawn over a previous one erases it.
550: If you are drawing numerous objects in a crowded area,
551: this can lead to unintended erasures.
552: The
553: .CW or
554: .CW mode
555: item switches to ``inclusive OR'' for drawing objects,
556: and erases objects by clearing.
557: Some movies are far better in one mode than the other.
558: .PP
559: The
560: .CW new
561: .CW file
562: item allows one to view a new movie without having to reload the
563: .I movie
564: program into the 5620.
565: We'll see how it works in Section 4.
566: .PP
567: The
568: .CW Quit?
569: menu item is the way to exit.
570: If selected, it displays a skull and crossbones
571: to warn that its effect is irreversible.
572: Pushing button 3 again exits;
573: a different button avoids quitting.
574: .PP
575: Button 2 contains menu items to control the size and shape
576: of the views on the screen and to control the meaning of a
577: ``step'' in 1-step mode.
578: For this sorting movie, button 2 looks like:
579: .P1
580: view text
581: view geom
582: click comp
583: click swap
584: click phase
585: .P2
586: When a view is selected, you can sweep a rectangle
587: in which that view is to be displayed;
588: the use is exactly like the
589: .CW New
590: menu item in
591: .I mux .
592: You can arrange the views any way you like;
593: try deleting the textual view by sweeping its rectangle out of the window.
594: .PP
595: When a
596: .CW click
597: is selected, 1-stepping proceeds to the next
598: occurrence of that click.
599: So, for example, to see swaps one at a time,
600: select
601: .CW click
602: .CW swap
603: on button 2 then select
604: .CW 1
605: .CW step
606: on button 3.
607: Each hit of button 1 will pause at the next
608: .CW click
609: .CW swap
610: statement in the script file, in either
611: .CW forward
612: and
613: .CW backward
614: mode.
615: .PP
616: Multiple clicks may be selected.
617: Selecting both
618: .CW click
619: .CW comp
620: and
621: .CW click
622: .CW swap
623: will cause a pause after every comparison and every swap.
624: Selected clicks are marked with an asterisk in the menu;
625: selecting a click that already has an asterisk
626: removes the asterisk and turns off the click.
627: .PP
628: In
629: .CW run
630: mode, the movie runs at full speed until it encounters a selected click,
631: then pauses for a time proportional to the selected speed.
632: Selecting no clicks is equivalent to having selected an implicit
633: click that occurs after each geometric object
634: (text, line, circle, rectangle)
635: is drawn or erased,
636: so animations run faster when some clicks are turned on (with
637: .CW click
638: .CW phase
639: selected, for instance, the sorting movie runs nearly twice as fast).
640: .sp 1
641: .LP
642: .I "Summary."
643: .PP
644: This exercise illustrates the capabilities
645: and limitations of our animation system.
646: The output of
647: .I movie
648: is a crude but useful animation.
649: The output of
650: .I stills
651: is handy for more detailed study and for presentation in documents
652: (we would like to include a movie in this document, for instance,
653: but paper is easier to distribute than videotape).
654: A sophisticated animation system might require 500 lines of
655: code to produce beautiful animations of insertion sort.
656: Our output is unpolished by comparison, but it is adequate
657: for many purposes and requires just a few dozen lines.
658: .PP
659: If our system is so crude, why bother using it?
660: Why not animate an algorithm simply by drawing geometric objects
661: on the output device you happen to be using?
662: Some of the answer lies in extra services like these:
663: .IP
664: .I "Device Independence."
665: A script file can be rendered as a movie on a 5620 or an X11 workstation;
666: the system is designed to make it easy to port to additional
667: output devices.
668: The same script file can be incorporated into a document by
669: .I stills .
670: .IP
671: .I "Names."
672: Labels allow geometric objects to be erased;
673: implicit erasure by re-using a label avoids
674: much of the tedium of bookkeeping.
675: Click names mark key events;
676: they can be used to group related events.
677: .IP
678: .I "Independent Views."
679: Different simultaneous views of a process
680: are crucial for animating algorithms.
681: In our system, a single statement moves from one view to another.
682: Within a view, the user need not be
683: concerned about the range of coordinates;
684: the system scales automatically.
685: Labels in different views are independent.
686: .IP
687: .I "Viewer Control."
688: Both
689: .I movie
690: and
691: .I stills
692: allow the viewer to select which views will be displayed
693: and which clicks will be recognized.
694: Additionally,
695: .I movie
696: allows the viewer to go forward or backward, in single
697: steps or running at a selected speed.
698: .IP
699: .I "An Interface To The World."
700: Although writing to files takes more computer time than using the
701: geometric primitives provided by a specific output device,
702: we will soon see how those files allow complicated tasks
703: to be easily composed out of simple software tools.
704: .LP
705: Our system does not support interactive animations, however:
706: once the script has been generated,
707: there's no way to change it
708: except to generate it again.
709: .NH
710: The Script Language
711: .PP
712: This section is a more complete description of the
713: script language in which animations are described.
714: A script file is processed by the heretofore unmentioned program
715: .I develop ;
716: errors in script files are reported by that program.
717: The output of
718: .I develop
719: feeds
720: .I stills
721: and
722: .I movie :
723: .PS
724: boxht = .25; boxwid = .6
725: ellipseht = .25; ellipsewid = .6
726: lineht = .1; linewid = .4
727: down
728: box "generator"
729: line down
730: ellipse "fname.s"
731: line down
732: box "develop"
733: line down
734: A: ellipse "fname.i"
735: B: box "stills" with .w at A.e + (.2, -.4)
736: line down
737: box invis "pic | troff | ..."
738: C: box "movie" with .e at A.w - (.2, .4)
739: line down
740: box invis "5620, X, ..."
741: line from A.se to B.nw
742: line from A.sw to C.ne
743: up
744: line up from B.n
745: ellipse "docfile"
746: .PE
747: The command
748: .CW develop
749: .CW fname.s
750: produces the
751: .I intermediate
752: file
753: .CW fname.i
754: from the script file
755: .CW fname.s ,
756: unless
757: .CW fname.i
758: already exists and is newer than
759: the corresponding script file.
760: Fortunately, most users need not be concerned with intermediate files and the
761: .I develop
762: program; both
763: .I movie
764: and
765: .I stills
766: call
767: .I develop
768: implicitly.
769: Appendix I defines the format of an intermediate file.
770: .PP
771: The script language provides
772: commands to draw geometric objects
773: and commands that control the pictures.
774: A line whose first non-blank character is
775: .CW #
776: is a comment;
777: comments may not appear on the line after other commands.
778: Blank lines are ignored.
779: .sp 1
780: .LP
781: .I "Geometric Commands" :
782: .CW text ,
783: .CW line ,
784: .CW box ,
785: .CW circle .
786: .PP
787: Geometric commands describe text, lines, rectangles, or circles.
788: They share the common form
789: .P1
790: @optional_label:@ @command@ @options@ @x@ @y@ @additional@ @parts@
791: .P2
792: If a label is present, it names the object and will implicitly
793: erase any existing object with the same name in the same view.
794: The options are a (possibly null) list of names,
795: terminated by the next numeric field.
796: .PP
797: Text is placed at a position by the command
798: .P1
799: @optional_label:@ text @options@ @x@ @y@ @string@
800: .P2
801: The available options are
802: .P1
803: [center] ljust rjust above below
804: small [medium] big bigbig
805: .P2
806: At most one option may be selected from each line;
807: if none is selected, the option in brackets is used.
808: The first line describes text position, and
809: the second line describes text size.
810: The text string may be quoted.
811: If there is no leading quote, then the string starts at the first
812: non-blank character and continues until the end of the line.
813: If there is a leading quote, subsequent leading white space is kept
814: and any trailing quote at the end of the line is removed;
815: intermediate quotes are kept.
816: Some strings, including
817: (but not necessarily limited to)
818: .CW bullet ,
819: .CW dot ,
820: .CW circle ,
821: and
822: .CW times ,
823: are recognized by later processors.
824: .PP
825: A line is drawn by
826: .P1
827: @optional_label:@ line @options@ @x sub 1@ @y sub 1@ @x sub 2@ @y sub 2@
828: .P2
829: The available options are
830: .P1
831: [-] -> <- <->
832: [solid] fat fatfat dotted dashed
833: .P2
834: The first line of options describe whether the line should
835: be drawn with arrowheads; the default is without arrowheads.
836: The option
837: .CW <-
838: puts an arrowhead at the @( x sub 1 , y sub 1 )@ end of the line,
839: .CW ->
840: puts an arrowhead at the other end,
841: and
842: .CW <->
843: puts them at both ends.
844: The second line of options describes the body of the line.
845: .PP
846: A rectangle is drawn by
847: .P1
848: @optional_label:@ box @options@ @xmin@ @ymin@ @xmax@ @ymax@
849: .P2
850: The only options are
851: .P1
852: [nofill] fill
853: .P2
854: Under the default
855: .CW nofill
856: only the border of the box is drawn;
857: a
858: .CW fill ed
859: box has a solid interior as well.
860: .PP
861: A circle is drawn by
862: .P1
863: @optional_label:@ circle @options@ @x@ @y@ @radius@
864: .P2
865: The radius is measured in the @x@ dimension.
866: Circles will look right only if @x@ and @y@ are in about the same range.
867: As with rectangles, the options are
868: .P1
869: [nofill] fill
870: .P2
871: .sp 1
872: .LP
873: .I "Control Commands" :
874: .CW view ,
875: .CW click ,
876: .CW erase ,
877: .CW clear .
878: .PP
879: The current view is set by the statement
880: .P1
881: view @name@
882: .P2
883: If there are no view statements in the script file,
884: .I develop
885: generates a single implicit view named
886: .CW def.view .
887: If geometric objects appear before the first view statement,
888: they go in that view and a warning message is generated.
889: .PP
890: A click is named by
891: .P1
892: click @optional_name@
893: .P2
894: If no name is present, then the name
895: .CW def.click
896: is implicitly supplied.
897: .PP
898: A labeled geometric object can be explicitly erased by the command
899: .P1
900: erase @label@
901: .P2
902: .I develop
903: prints a warning
904: if the object was never defined or has already been erased.
905: The various views have distinct name spaces;
906: the same label may be applied to two unrelated objects in two different views.
907: All objects in the current view can be erased by the statement
908: .P1
909: clear
910: .P2
911: .PP
912: None of these commands may have labels.
913: .sp 1
914: .LP
915: .I "Summary."
916: .PP
917: The script language contains the following commands;
918: options are indented on a subsequent line, with defaults in brackets:
919: .P1
920: # comment
921: @optional_label:@ line @options@ @x sub 1@ @y sub 1@ @x sub 2@ @y sub 2@
922: [-] -> <- <->
923: [solid] fat fatfat dotted dashed
924: @optional_label:@ text @options@ @x@ @y@ @string@
925: [center] ljust rjust above below
926: small [medium] big bigbig
927: @optional_label:@ box @options@ @xmin@ @ymin@ @xmax@ @ymax@
928: [nofill] fill
929: @optional_label:@ circle @options@ @x@ @y@ @radius@
930: [nofill] fill
931: view @name@
932: click @optional_name@
933: erase @label@
934: clear
935: .P2
936: .PP
937: The shell command
938: .CW develop
939: .CW fname.s
940: makes the intermediate file
941: .CW fname.i
942: from the script file
943: .CW fname.s ,
944: if
945: .CW fname.i
946: is out of date.
947: The purpose of the intermediate file is to trade
948: increased space (for storing the intermediate file) for
949: reduced run time (a script file is developed just once, not
950: each time it is used).
951: The
952: .I movie
953: and
954: .I stills
955: shell scripts could be rewritten to pipe their inputs through
956: .I fdevelop ,
957: a filter form of
958: .I develop .
959: The
960: .I fdevelop
961: program can handle script files with at most 20,000 lines;
962: the argument
963: .CW -l\f2n\fP
964: changes the upper bound to
965: .I n
966: instead.
967: It can similarly handle at most 10,000 pieces of geometry
968: active at any time;
969: the argument
970: .CW -s\f2n\fP
971: (for ``slots'') changes that upper bound.
972: Error messages tell when these bounds need to be increased.
973: After any
974: .CW -l
975: and
976: .CW -s
977: arguments,
978: .I fdevelop
979: can have an optional file name.
980: If there is a name, that is the input file; otherwise,
981: the standard input is used.
982: The output is written on
983: the standard output.
984: .NH
985: The Movie Program
986: .PP
987: Movie production, as with most 5620 programs,
988: uses a host process and a terminal process.
989: The host sends the intermediate file produced by
990: .I develop
991: in a compact form to the terminal,
992: which stores it in a form suited
993: for forward or backward display.
994: As the file is shipped, the line number in
995: the intermediate file is displayed in the
996: upper-left corner of the window every 100 lines.
997: Afterwards, the total number of bytes
998: stored is displayed in that location.
999: The terminal process allocates 80,000 bytes
1000: (typically 5-10,000 objects)
1001: for the picture;
1002: the argument
1003: .CW -m\f2n\fP
1004: sets the allocation to
1005: .I n
1006: instead.
1007: .PP
1008: The button 3 menu was sketched in Section 2.
1009: In general, drawing can be interrupted at any point by
1010: pushing any button, then resumed by pushing button 1.
1011: .PP
1012: Four menu items control two variables:
1013: .P1
1014: faster [speed]
1015: slower [speed]
1016: .P2
1017: decrease (halve) and increase (double) the pause at selected clicks, and
1018: .P1
1019: thinner [line width]
1020: fatter [line width]
1021: .P2
1022: alter the width of lines.
1023: (If the line thickness is @n@, then
1024: .CW solid
1025: lines are @2n - 1@ bits wide;
1026: .CW fat
1027: and
1028: .CW fatfat
1029: lines are larger.)
1030: Three menu items control binary attributes:
1031: .P1
1032: backward forward
1033: or mode xor mode
1034: 1 step run
1035: .P2
1036: The mode displayed on the menu is the next state, not the current one.
1037: If the program is currently in
1038: .CW or
1039: .CW mode ,
1040: for instance, then
1041: .CW xor
1042: .CW mode
1043: is displayed.
1044: .PP
1045: The
1046: .CW new
1047: .CW file
1048: item allows one to view a new movie without downloading the
1049: .I movie
1050: program again.
1051: After selecting that item,
1052: text in the upper left of the window asks for the name of the intermediate
1053: file to be processed.
1054: The
1055: .I movie
1056: program does not call
1057: .I develop
1058: to make the intermediate
1059: .CW .i ) (
1060: file from the script
1061: .CW .s ) (
1062: file;
1063: that is the responsibility of the user,
1064: typically in a separate window.
1065: .PP
1066: Button 2 lists views and clicks.
1067: Selecting a view results in an icon for sweeping a rectangle,
1068: as in
1069: .I mux .
1070: Views may be positioned anywhere;
1071: portions positioned outside the window will not be shown.
1072: Initially, views have a 5 percent margin at each edge;
1073: this margin is zero for views that have been reshaped.
1074: If the window itself is reshaped, all views revert to
1075: the default position and margin.
1076: .PP
1077: Normally, in 1-step mode, the display pauses after each
1078: primitive object (line, text, etc.) has been drawn or erased.
1079: If any clicks are defined and turned on by button 2, however,
1080: then the display pauses only at those points.
1081: Any number of clicks may be turned on.
1082: Clicks that are turned on are marked with an asterisk;
1083: they may be turned off by selecting them again.
1084: .PP
1085: As it is for the 5620, so it is for X workstations,
1086: although the exigencies of the X window system
1087: have forced us to curtail some features.
1088: To keep the code relatively portable,
1089: there are again two processes, so
1090: the window in which one starts the animation clones another
1091: window of uncontrolled size, shape and position
1092: where the animation itself occurs.
1093: .PP
1094: The current terminal programs support
1095: many, but not all, text size and line mode options.
1096: .PP
1097: If
1098: .I movie
1099: has a single argument, it must be either a
1100: .CW .s
1101: or
1102: .CW .i
1103: file;
1104: .I movie
1105: .I develop s
1106: a
1107: .CW .s
1108: file.
1109: If it has no arguments, then it will pipe
1110: the standard input
1111: through
1112: .I fdevelop ;
1113: no intermediate file is created.
1114: For more exotic situations, use
1115: .I fmovie :
1116: with no arguments, it projects the intermediate file
1117: from the standard input;
1118: with a single argument, it projects that intermediate file.
1119: .NH
1120: The Stills Language
1121: .PP
1122: The
1123: .I stills
1124: program is a typical
1125: .I troff
1126: preprocessor.
1127: Portions of its input bracketed by
1128: .CW .begin
1129: .CW stills
1130: and
1131: .CW .end
1132: are translated into
1133: .I pic
1134: commands, and the rest of the input is passed through untouched.
1135: A paper containing
1136: .I stills
1137: input is typically compiled by a command like
1138: .P1
1139: stills paper | pic | troff >paper.out
1140: .P2
1141: .PP
1142: There are three classes of statements in a
1143: .I stills
1144: description:
1145: .CW print ,
1146: .CW view ,
1147: and parameter assignments.
1148: Only two statements are mandatory in a particular description:
1149: an assignment to the
1150: .CW file
1151: parameter and a
1152: .CW print
1153: statement.
1154: Text following the sharp symbol
1155: .CW #
1156: is discarded as a comment; blank lines are ignored.
1157: .PP
1158: There may be any number of
1159: .CW print
1160: statements of any combination of the following forms:
1161: .P1
1162: print all
1163: print final
1164: print @clickname@ all
1165: print @clickname@ @number@ @number@ @number@ ...
1166: .P2
1167: The first statement causes a snapshot to be drawn at each
1168: .CW click
1169: statement in the script file; the second draws one at the end of the file.
1170: The third form prints all
1171: .CW click s
1172: of the designated name, and the fourth prints only the clicks enumerated
1173: in the list of numbers.
1174: .PP
1175: View statements select which views are to be printed in snapshots
1176: and assign titles to views.
1177: .P1
1178: view @name@ @optional@ @title@
1179: .P2
1180: The views appear in the order they are named,
1181: either top-to-bottom if time goes
1182: .CW across
1183: the page or left-to-right if time goes
1184: .CW down
1185: the page.
1186: If there are no
1187: .CW view
1188: statements, each snapshot depicts all views in the script.
1189: If the title is enclosed in quote marks, they are stripped and
1190: leading space is kept.
1191: If no title is given for a particular view, the view name
1192: itself is used as a title;
1193: thus an empty title is needed to turn off printing.
1194: .PP
1195: Parameters can be set by assignment statements of the form
1196: .P1
1197: @parameter_name@ @value@
1198: .P2
1199: All parameters are reset to their default values at each
1200: .CW .begin
1201: .I stills
1202: statement.
1203: Numeric values may be of the form
1204: .CW n ,
1205: .CW +n ,
1206: .CW -n ,
1207: or absent (zero default).
1208: .IP
1209: .I Filename
1210: parameter:
1211: .CW file .
1212: The script file is named by assigning to the
1213: .CW file
1214: parameter with a statement of the form
1215: .CW file
1216: .CW basename.s .
1217: The
1218: .I stills
1219: program
1220: .I develop s
1221: that script file and then reads
1222: .CW basename.i .
1223: .IP
1224: .I "Text sizes" :
1225: .CW "small medium big bigbig" .
1226: The assignment
1227: .CW small
1228: .CW -2
1229: causes text with the
1230: .CW small
1231: option to be printed two point sizes smaller than the current
1232: .I troff
1233: point size.
1234: Assigning
1235: .CW "+5"
1236: or
1237: .CW "5"
1238: to
1239: .CW "bigbig"
1240: increases the point size by 5 for
1241: .CW bigbig
1242: text.
1243: All changes are relative; there is no way to set
1244: absolute point size.
1245: .IP
1246: .I "Line widths" :
1247: .CW "solid fat fatfat" .
1248: Relative size changes for line widths, exactly as for text sizes.
1249: .IP
1250: .I "Direction" :
1251: .CW "across down" .
1252: By default, snapshots proceed across the page in time.
1253: The assignment
1254: .CW down
1255: .CW 5
1256: causes time to proceed down the page for 5 snapshots before
1257: starting a new column;
1258: .CW down
1259: .CW 0
1260: or
1261: .CW "down"
1262: yields as many snapshots as will fit on an 8-inch page.
1263: The assignment
1264: .CW across
1265: .CW 7
1266: gives 7 snapshots in a row before starting a new row;
1267: .CW across
1268: .CW 0
1269: or
1270: .CW across
1271: adapts to a 6-inch width.
1272: .IP
1273: .I "Frame parameters" :
1274: .CW "frameht framewid margin" .
1275: The height and width of frames are given in inches; defaults are 1.5.
1276: The margin of a frame is the white space surrounding the data;
1277: the default is 0.05, or a five percent border.
1278: .IP
1279: .I "Optional parts" :
1280: .CW "frames times" .
1281: Frames are the solid borders around pictures;
1282: times are the click name and number that triggered a snapshot.
1283: Both have the default value
1284: .CW vis
1285: and are shown; they may be suppressed by assigning them the value
1286: .CW invis .
1287: .PP
1288: In summary,
1289: .I stills
1290: input consists of these commands:
1291: .P1
1292: print all
1293: print final
1294: print @clickname@ all
1295: print @clickname@ @number@ @number@ @number@ ...
1296: view @name@ @optional@ @title@
1297: @parameter_name@ @value@
1298: .P2
1299: .LP
1300: At least one
1301: .CW print
1302: statement and a
1303: .CW file
1304: assignment are mandatory;
1305: other statements are optional.
1306: The parameter names in the right column may appear on the left side of a
1307: name/value assignment:
1308: .P1
1309: .ta 1.1i
1310: \f2Filename\fP file
1311: \f2Text sizes\fP small medium big bigbig
1312: \f2Line widths\fP solid fat fatfat
1313: \f2Direction\fP across down
1314: \f2Frame parameters\fP frameht framewid margin
1315: \f2Optional parts\fP frames times
1316: .P2
1317: .........
1318: .NH
1319: Larger Animations
1320: .PP
1321: The examples in this section illustrate algorithms on several
1322: classes of data structures, including arrays, trees and graphs.
1323: The graphical style is simple; this is easy for the animator and
1324: effective for the viewer.
1325: The programs in this section are not presented as paradigms of
1326: good programming style; rather, they show how succinct programs
1327: can yield useful animations.
1328: .PP
1329: In the paper cited earlier, Brown and Sedgewick employ
1330: several conceptual levels in animating an algorithm.
1331: .IP
1332: .I Execution.
1333: At one extreme is the program to be animated,
1334: executing on the data of interest.
1335: .IP
1336: .I "History of ``Interesting Events.''
1337: What events in a computation should be depicted in the animation?
1338: The simple animation of insertion sort in Section 2 used augmented
1339: .CW less
1340: and
1341: .CW swap
1342: routines to capture two primitives of most sorting programs:
1343: comparisons and data movements.
1344: It also explicitly recorded information associated with the
1345: interesting event of finishing a phase.
1346: .IP
1347: .I "Geometric interpretation of events.
1348: One must next decide how to represent
1349: the interesting events pictorially.
1350: An array of integers, for instance, might be represented by
1351: a sequence of numbers, a scatterplot of bullets, or a sequence
1352: of vertical bars.
1353: .IP
1354: .I "Rendering on a device.
1355: In our system, this is the job of
1356: .I movie
1357: and
1358: .I stills .
1359: .LP
1360: The sample program
1361: .CW is.gen
1362: identified interesting events and gave them
1363: a geometric interpretation in separate procedures
1364: within a single program.
1365: Alternatively, it may be more convenient
1366: to implement the various tasks as a pipeline of two programs:
1367: a generator program writes interesting events that
1368: are given a geometric interpretation by a program that writes
1369: a script file.
1370: .PP
1371: One usually prints a
1372: .CW click
1373: statement immediately after the event it marks.
1374: Sometimes, though, one draws additional objects to
1375: highlight the event, which are erased immediately after the
1376: .CW click .
1377: In that case, one uses a sequence like
1378: .P1
1379: @draw@ @event@ @E@
1380: @highlight@ @E@
1381: click E
1382: @remove@ @highlights@
1383: .P2
1384: .sp 1
1385: .LP
1386: .I "Sorting, Again."
1387: .PP
1388: We will return to the subject of
1389: sorting with a more interesting animation:
1390: a race of insertion sort versus quicksort.
1391: We will use the same insertion sort we saw earlier,
1392: and a quicksort described in Section 10.2 of |reference(programming pearls).
1393: The two sorting routines and their supporting functions
1394: are contained in this
1395: .I awk
1396: program:
1397: .P1
1398: .get race.gen
1399: .P2
1400: Quicksort is called as
1401: .CW "qsort(l,u)"
1402: to sort the subarray
1403: .CW x[l..u] .
1404: The function
1405: .CW draw
1406: represents the numbers to be sorted as vertical lines.
1407: The
1408: .CW BEGIN
1409: block sets
1410: .CW n ,
1411: initializes the array,
1412: draws the initial representation,
1413: and then calls a sort routine.
1414: As it stands, the code depicts a 50-element quicksort.
1415: .PP
1416: Some algorithm animation systems present races of programs
1417: by implementing a simple form of time slicing.
1418: To create a race in our system, we first ran the program into the file
1419: .CW qs.s .
1420: We then changed the final line in the
1421: .CW BEGIN
1422: section to call
1423: .CW isort ,
1424: and ran that into the file
1425: .CW is.s .
1426: Finally, we merged the two scripts into one with this
1427: .I awk
1428: program:
1429: .P1
1430: .get race.splice
1431: .P2
1432: The loop copies the script of insertion sort until it encounters a
1433: .CW click
1434: .CW comp
1435: statement; it then copies quicksort until it encounters the corresponding
1436: .CW click ,
1437: at which points it prints the
1438: .CW click
1439: statement.
1440: The variables
1441: .CW s1
1442: and
1443: .CW s2
1444: store the status of the most recent
1445: .CW getline s
1446: of the two files; the status is one if a record was found and
1447: zero if an end-of-file was encountered.
1448: When one file is exhausted, the remainder of the other is copied.
1449: (A production splicer should
1450: have a more graceful interface for naming the files and views.)
1451: .PP
1452: The resulting script file is an execution of the
1453: sorts in two parallel views, synchronized by comparisons:
1454: .INCLUDE race
1455: As before, insertion sort sifts each element into place in turn.
1456: This picture only hints at the operation of quicksort;
1457: insight into that algorithm requires the identification
1458: of interesting events beyond comparisons and swaps.
1459: Quicksort finishes after 240 comparisons, while insertion
1460: sort takes almost three times as long.
1461: For completeness, here is the
1462: .I stills
1463: input that produced the picture:
1464: .P1
1465: .get race.t
1466: .P2
1467: .sp 1
1468: .LP
1469: .I "Trees."
1470: .PP
1471: Here are pictures of a (nonbalanced) binary search tree after inserting
1472: 5, 10, 15 and 20 random integers in the range 0..999:
1473: .INCLUDE bst
1474: In the last two frames, the labels for node 3
1475: and 13 are squeezed too close together.
1476: The script was generated by this
1477: .I awk
1478: program:
1479: .P1
1480: .get bst.gen
1481: .P2
1482: The animation code consists of just three lines in the
1483: .CW insert
1484: procedure.
1485: .PP
1486: The pictures give insight into random binary search trees
1487: in spite of being rather ugly.
1488: The trees have two distinct failings: the depiction of
1489: individual nodes, and the layout of the entire tree.
1490: .PP
1491: A node is represented by its numeric value;
1492: each node is connected to its parent.
1493: If the shape of the tree is more important than
1494: the values it contains, one can delete the values entirely.
1495: We will shortly see a tree with more graceful edges.
1496: .PP
1497: The other aesthetic issue is the layout of the tree.
1498: The @y@-value is the depth of the node in the tree,
1499: which is a very robust choice
1500: (one could also use the time at which the node was inserted).
1501: The @x@-value in this example is simply the randomly generated value itself;
1502: there are many alternative choices.
1503: One could instead use the number of the node in an inorder traversal,
1504: which involves a multiple-pass algorithm:
1505: the tree is first built, then traversed and numbered, and the
1506: insertions are then reported with knowledge of the numbers.
1507: For this representation, it is crucial to separate the
1508: interesting events from their geometric representation;
1509: it is convenient to calculate these in two filters in a pipeline.
1510: .PP
1511: This animation of heapsort uses an alternative representation of trees.
1512: It was generated by a 50-line
1513: .I awk
1514: program.
1515: .INCLUDE heap
1516: Each snapshot shows the result of a
1517: .CW sift
1518: operation.
1519: The first four
1520: .CW sift s
1521: build the heap; subsequent
1522: .CW sift s
1523: maintain the unsorted elements as a heap.
1524: Arrows point from lesser elements to greater elements.
1525: .PP
1526: A node in the heap is represented by its value;
1527: lines between nodes have a single arrowhead and
1528: are chopped by twenty percent at each end.
1529: The root of the heap is at @(1/2,~-1)@,
1530: its two children are at @(1/4,~-2)@ and @(3/4, ~-2)@, their four
1531: children are at @(1/8,~-3)@, @(3/8,~-3)@, @(5/8,~-3)@, @(7/8,~-3)@, etc.
1532: .PP
1533: Other tree layouts proved useful in animating
1534: two algorithms dealing with parse trees.
1535: In both cases, a node's @x@-value was the minimum of the
1536: @x@-values among the node's descendants (equivalently,
1537: the @x@-value of its leftmost child); all edges were therefore
1538: either vertical or slanting down to the right.
1539: A random sentence generator built the tree left-to-right and top-down;
1540: just as in the binary search tree,
1541: the height of a node was one less than its parent.
1542: A parser built the tree in postorder and bottom-up:
1543: the height of a node was one greater than the
1544: maximum of the heights of its children.
1545: .sp 1
1546: .LP
1547: .I "A Graph Algorithm."
1548: .PP
1549: Prim's algorithm for computing the minimum spanning tree (MST)
1550: of a graph starts with a fragment consisting of a single vertex.
1551: It increases the fragment by adding the nearest vertex until all
1552: vertices are in the fragment, at which point it is the MST
1553: of the entire graph.
1554: This picture shows Prim's algorithm on the complete
1555: graph induced by a set of 50 planar points;
1556: the weight of an edge between two points is
1557: defined to be their Euclidean distance.
1558: .INCLUDE mst2
1559: The snapshots are taken every ten stages.
1560: .PP
1561: The obvious implementation of Prim's algorithm on an @N@-point
1562: set requires time proportional to @N sup 3@.
1563: Dijkstra discovered an elegant implementation of the algorithm
1564: with running time proportional to @N sup 2@:
1565: every point not in the fragment keeps a pointer
1566: to its nearest neighbor in the fragment.
1567: Here is Dijkstra's implementation on a ten-node planar graph:
1568: .INCLUDE mst1
1569: In this animation, nodes in the fragment are bullets, nodes
1570: not in the fragment are crosses, edges in the MST are
1571: .CW fat
1572: lines, and the nearest neighbors are pointed to by arrows.
1573: .PP
1574: These two sequences illustrate two
1575: styles of drawing graphs with our system.
1576: Dots and lines are sufficient for simple algorithms,
1577: while various symbols and line options can depict subtle processes.
1578: .PP
1579: The geometric nature of the above graphs made them easy to lay out.
1580: Laying out a general graph is very hard.
1581: If the graphs in your applications are specialized (such as trees),
1582: you might exploit that structure to compute an effective layout.
1583: A graph of @N@ vertices can be easily represented
1584: by an @N times N@ matrix in which the @i,j@-th element
1585: represents the edge from vertex @i@ to vertex @j@;
1586: that is useful for insight into some graph algorithms.
1587: If you have access to a program that produces good layouts of general graphs,
1588: you might use that program to compute positions of vertices,
1589: and then feed those into our system.
1590: .sp 1
1591: .LP
1592: .I "A Memory Allocator."
1593: .PP
1594: The
1595: .I develop
1596: program uses the
1597: .I malloc
1598: memory allocator for several of its data structures.
1599: We augmented
1600: .I develop 's
1601: calls to the allocator with data gathering
1602: routines to produce an animation;
1603: here is the final snapshot.
1604: .KF
1605: .INCLUDE malloc
1606: .KE
1607: The left frame is the arena of storage from which memory is allocated.
1608: Memory blocks are represented by lines,
1609: low addresses are at the bottom of the picture, and
1610: the picture is 1024 bytes wide.
1611: The right frame is a histogram of the sizes of memory currently
1612: allocated; there is a dot for each element, a vertical bar every ten
1613: positions to help counting, and the maximum value is in the lower right corner.
1614: .PP
1615: This snapshot was taken at the end of execution of
1616: .I fdevelop .
1617: The histogram shows two large blocks
1618: of 20,000 and 40,000 bytes, 96 blocks of size 16, and 96
1619: slightly larger blocks (the blocks of size 16 are symbol table records;
1620: each points to an allocated string).
1621: The arena shows the two huge pieces (the larger is higher)
1622: and a gap above the smaller (memory allocated by
1623: procedures that didn't call our augmented
1624: .I malloc ).
1625: The remainder of the arena is allocated efficiently.
1626: .PP
1627: A movie like this helped us find a bug in
1628: .I fdevelop :
1629: an early version allocated the symbol table nodes but did not
1630: .I free
1631: them.
1632: This problem manifested itself in an overloaded arena and a huge
1633: spike in the histogram at size 16.
1634: .PP
1635: The
1636: .I fdevelop
1637: program interacts with the storage allocator only through
1638: the two routines
1639: .I emalloc
1640: and
1641: .I efree .
1642: We animated the storage allocator by modifying those routines:
1643: .P1
1644: .get malloc.c
1645: .P2
1646: They write on the named file output lines of two types:
1647: .P1
1648: m @address@ @length@
1649: f @address@
1650: .P2
1651: The first line denotes that a
1652: .I malloc
1653: of the given length returned the given address;
1654: the second marks a
1655: .I free .
1656: .PP
1657: The resulting history file contains the interesting events;
1658: they are given a geometric interpretation by a subsequent program.
1659: Here is a simple program that generates only the arena view
1660: from the script file:
1661: .P1
1662: .get malloc.awk
1663: .P2
1664: The
1665: .CW BEGIN
1666: block initializes variables,
1667: the actions for
1668: .CW m
1669: lines draw memory, and those for
1670: .CW f
1671: lines erase memory.
1672: The variable
1673: .CW s
1674: is the starting byte of a block;
1675: .CW e
1676: is the ending block.
1677: The variables
1678: .CW sx
1679: and
1680: .CW sy
1681: are the @x@ and @y@ positions of the starting byte, and
1682: similarly for
1683: .CW ex
1684: and
1685: .CW ey .
1686: If the block fits on one line, then only a single line fragment
1687: need be drawn; otherwise, fragments of three types are needed.
1688: .PP
1689: The complete program for generating scripts
1690: from history files is 56 lines of
1691: .I awk .
1692: To ease tracing the action in the arena, it marks a
1693: .I malloc
1694: with an
1695: .CW x
1696: and a
1697: .I free
1698: with an
1699: .CW o .
1700: The histogram view is embellished with bars and the maximum value.
1701: There is room for further elaborations;
1702: one might, for instance, want to put either or both of
1703: the axes of the histogram on logarithmic scales.
1704: .sp 1
1705: .LP
1706: .I "Dynamic Statistical Displays."
1707: .PP
1708: Rick Becker constructed this display of air pollution
1709: in the Northeast United States:
1710: .INCLUDE ozone
1711: The data was gathered hourly on
1712: a single summer day in the early 1970's.
1713: The radius of each circle is proportional to the ozone
1714: reading (a common measurement of air pollution)
1715: at one of 32 stations in New Jersey,
1716: New York, Connecticut, and Massachusetts.
1717: The radius of the clock denotes the maximum ozone level prescribed
1718: by the Environmental Protection Agency;
1719: its hour hand goes from 7:00 AM to midnight.
1720: .PP
1721: This display shows how New York City's
1722: air pollution is blown to the northeast.
1723: Becker and his colleagues prepared a similar movie in the
1724: early 1970's using the technology of the day;
1725: it required several weeks of programming time, then
1726: a weekend with a movie camera to make the final film.
1727: He built this display from the same data in a couple of hours,
1728: then prepared a video tape of the
1729: resulting movie in under thirty minutes.
1730: The original movie was a bit nicer (it drew the background
1731: map and the circles in two different colors),
1732: but the new movie is just as useful, and provides stills for free.
1733: ......
1734: .NH
1735: Living With The System
1736: .PP
1737: The system that we have described is the
1738: bare bones of an animation environment.
1739: We have found that the most fruitful way of enhancing the
1740: environment is not by modifying the primary programs,
1741: but rather by using small filters that interact with the
1742: various files in the system.
1743: .PP
1744: We showed earlier, for instance, a race of two sorting algorithms.
1745: While other animation systems implement races with
1746: a general mechanism for time sharing,
1747: we did the job with a small
1748: .I awk
1749: program that merges two files.
1750: Our system does not have a facility for counting clicks;
1751: rather, we use filters such as
1752: .P1
1753: grep 'click comps' | wc
1754: .P2
1755: to see how many comparisons were made.
1756: We will even admit to using text editors to make minor changes
1757: to both script and intermediate files.
1758: .PP
1759: We have built several useful filters in addition to
1760: .I merge .
1761: The program
1762: .I view.clicks
1763: prints a summary of the views and clicks used in a script file;
1764: it is helpful as one is preparing a
1765: .I stills
1766: file.
1767: Its implementation uses the intermediate file described
1768: in Appendix I:
1769: .P1
1770: .get view.clicks
1771: .P2
1772: The first step of the shell script is to develop the script file;
1773: the subsequent
1774: .I awk
1775: program then reads the resulting intermediate file.
1776: The first pattern/action pair prints for each view its
1777: name and the @x@ and @y@ ranges in the script file.
1778: The second pair builds a string of all clicks from the
1779: define click statements, and the third pair prints that
1780: string and exits at the first non-define statement.
1781: .PP
1782: The program
1783: .I show.clicks
1784: takes a script file as input;
1785: its output is a new script file containing all information in
1786: the input and, in addition, a new view named
1787: .CW click.count
1788: in which the various clicks are counted.
1789: This is useful for preparing
1790: .I stills
1791: files and for debugging.
1792: Its input is a script file,
1793: either named explicitly or as the standard input.
1794: Here is the code:
1795: .P1
1796: .get show.clicks
1797: .P2
1798: The second pattern/action pair stores the name of the current view,
1799: and the fourth action copies each line onto the output file.
1800: The first pattern/action pair supplies a default view name, if needed.
1801: .PP
1802: The work is done when the third pattern recognizes a
1803: .CW click
1804: statement.
1805: The
1806: .CW if
1807: statement puts the click name in
1808: .CW cname ,
1809: and the
1810: .CW print
1811: statement switches to the new view.
1812: The second
1813: .CW if
1814: statement is executed when a new
1815: .CW click
1816: statement is seen; it assigns it a number and prints out the
1817: click name, once and for all.
1818: The two following statements rewrite the appropriate count
1819: and place a bullet next to it.
1820: The final statement returns to the current view.
1821: .PP
1822: One can use the ideas in
1823: .I show.clicks
1824: to process lines in the script file of the form
1825: .P1
1826: @name@ = @value@
1827: .P2
1828: The output script file has a new view named
1829: .CW variables ;
1830: it contains the name of each variable mentioned and its current value.
1831: .PP
1832: Larger filters have also proven useful.
1833: For instance, we built a set of tools to render animations
1834: of three-dimensional lines and text
1835: (circles and rectangles were not supported).
1836: The primary program translated a three-dimensional script into a
1837: standard script that contained two two-dimensional views for
1838: each three-dimensional view; the resulting
1839: .I movie
1840: and
1841: .I stills
1842: were suitable for viewing with standard stereo viewers.
1843: Support programs included a filter for rotating a view
1844: around a given line.
1845: .PP
1846: The
1847: .I movie
1848: and
1849: .I develop
1850: programs are in fact simple shell scripts that call filter
1851: versions named
1852: .I fmovie
1853: and
1854: .I fdevelop .
1855: You may find it convenient to rewrite those shell scripts for
1856: your environment.
1857: .SH
1858: Acknowledgements
1859: .PP
1860: We are deeply indebted to Howard Trickey;
1861: he gave us invaluable advice for getting a minimal
1862: animation facility working in the Sun environment,
1863: then finished the job properly.
1864: He subsequently made it all work under the X window system.
1865: Andrew Hume and Jane Elliott made possible
1866: our first experiments with animation.
1867: Our early users, Rick Becker and Chris Van Wyk,
1868: gave us bug reports and suggestions for improvements.
1869: Eric Grosse, John Linderman, Doug McIlroy,
1870: Steve Mahaney, Howard Trickey, and Chris Van Wyk
1871: made helpful comments on this paper.
1872: .SH
1873: References
1874: .LP
1875: |reference_placement
1876: .sp 100
1877: .BP
1878: .SH
1879: Appendix I \(em Intermediate Files
1880: .PP
1881: This appendix defines the intermediate files produced by
1882: .I develop .
1883: The files are easier to process than the corresponding script files.
1884: For instance,
1885: names are converted to small integers,
1886: floating point numbers are scaled to integers in 0..9999,
1887: and commands are abbreviated to single letters.
1888: .PP
1889: A line whose first non-blank character is
1890: .CW #
1891: is a comment.
1892: .PP
1893: An intermediate file begins with define statements
1894: that give the names of the views and the clicks:
1895: .P1
1896: d v @vnum@ @viewname@ @minx@ @miny@ @maxx@ @maxy@
1897: d c @cnum@ @clickname@
1898: d p @any@ @text@
1899: d p e
1900: .P2
1901: Fields are separated by tab characters.
1902: Both views and clicks are numbered 0, 1, 2, ....
1903: The four final numbers on a view line tell the
1904: range of the coordinates in the original script file.
1905: A line that begins with
1906: .CW "d p"
1907: is a ``pragma''; both
1908: .I movie
1909: and
1910: .I stills
1911: currently ignore all such lines.
1912: The defines appear at the front of the file in
1913: the order views, clicks, pragmas, then
1914: the ``end of defines'' pragma
1915: .CW "d p e" .
1916: .PP
1917: The geometric commands for lines, boxes, circles and text
1918: are mapped to the following:
1919: .P1
1920: g @slotnum@ l @vnum@ @opts@ @x sub 1@ @y sub 1@ @x sub 2@ @y sub 2@
1921: g @slotnum@ b @vnum@ @opts@ @x sub 1@ @y sub 1@ @x sub 2@ @y sub 2@
1922: g @slotnum@ c @vnum@ @opts@ @x@ @y@ @rad@
1923: g @slotnum@ t @vnum@ @opts@ @x@ @y@ @text@ @string@
1924: .P2
1925: Objects that are never erased have slot number 0;
1926: other objects are placed in ``slots'' that can hold at most one object.
1927: The third field is the type of geometric object;
1928: the fourth field is the view number.
1929: All @x@ and @y@ values are normalized to integers in the range 0..9999.
1930: There is a single separating tab before the (unquoted) text string.
1931: Options are given as a string of characters,
1932: whose length and interpretation are summarized as:
1933: .P1
1934: .ps -2
1935: .vs -3
1936: OBJECT POS NAME ABBREV
1937: text 1 center c
1938: ljust l
1939: rjust r
1940: above a
1941: below b
1942: 2 medium m
1943: small s
1944: big b
1945: bigbig B
1946: line 1 solid s
1947: fat f
1948: fatfat F
1949: dotted o
1950: dashed a
1951: 2 - -
1952: -> >
1953: <- <
1954: <-> x
1955: box 1 nofill n
1956: fill f
1957: circle 1 nofill n
1958: fill f
1959: .vs +3
1960: .ps +2
1961: .P2
1962: For instance, the options for a text string are described
1963: by two characters giving its position and its size;
1964: .CW small
1965: .CW center
1966: text has the option string
1967: .CW cs .
1968: Further options may be added at the right end of the string;
1969: subsequent programs should ignore letters they don't expect.
1970: .PP
1971: A click statement is represented as
1972: .P1
1973: c @cnum@
1974: .P2
1975: .PP
1976: An erase statement is translated into
1977: .P1
1978: e @line@ @repeated@ @here@, @except@ e @italic "for"@ @leading@ g
1979: .P2
1980: A processor may choose to implement this statement using
1981: either the geometric description or the slot number.
1982: .PP
1983: A
1984: .CW clear
1985: statement (which erases all objects in a view)
1986: is translated into a pair of starting and ending ``blank''
1987: commands that bracket a sequence of erase statements:
1988: .P1
1989: b s @vnum@
1990: b e @vnum@
1991: .P2
1992: The erase statements together clear the view.
1993: A processor may choose to implement the
1994: .CW clear
1995: either by ignoring the
1996: .CW b
1997: commands and letting the erase statements
1998: take their course or by explicitly processing the start
1999: command and then ignoring
2000: .CW e
2001: commands until encountering the
2002: .CW "b e"
2003: line.
2004: .PP
2005: As an example, running
2006: .CW develop
2007: on this trivial script file
2008: .P1
2009: line 1 2 3 4
2010: text small above 5 6 "Hello, world."
2011: click stage
2012: clear
2013: .P2
2014: produces this intermediate file:
2015: .P1
2016: d v 0 def.view 1 2 5 6
2017: d c 0 stage
2018: d p e
2019: g 1 l 0 s- 0 0 4999 4999
2020: g 2 t 0 as 9999 9999 Hello, world.
2021: c 0
2022: b s 0
2023: e 1 l 0 s- 0 0 4999 4999
2024: e 2 t 0 as 9999 9999 Hello, world.
2025: b e 0
2026: .P2
2027: .PP
2028: Here is a summary of the commands in the intermediate language:
2029: .P1
2030: # @comment@
2031: b s @vnum@
2032: b e @vnum@
2033: c @cnum@
2034: d v @vnum@ @viewname@ @minx@ @miny@ @maxx@ @maxy@
2035: d c @cnum@ @clickname@
2036: d p @any@ @text@
2037: d p e
2038: e @line@ @repeated@ @here@, @except@ e @italic "for"@ @leading@ g
2039: g @slotnum@ l @vnum@ @opts@ @x sub 1@ @y sub 1@ @x sub 2@ @y sub 2@
2040: g @slotnum@ b @vnum@ @opts@ @x sub 1@ @y sub 1@ @x sub 2@ @y sub 2@
2041: g @slotnum@ c @vnum@ @opts@ @x@ @y@ @rad@
2042: g @slotnum@ t @vnum@ @opts@ @x@ @y@ @text@ @string@
2043: .P2
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.