Return to anim.ms CVS log

Up to [Research Unix] / researchv10dc / vol2 / anim

Annotation of researchv10dc/vol2/anim/anim.ms, revision 1.1

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.