Technology

5 pages
7 views

An Experiment In Algorithm Animation using SMALLTALK on a Macintosh

Please download to get full document.

View again

of 5
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Share
Description
An Experiment In Algorithm Animation using SMALLTALK on a Macintosh
Transcript
  15 zy   zy An Experiment in Algorithm Animation using SMALLTALK on a Macintosh zyx Ramzan Mohamed A prototype system for algorithm animation, imple- mented on a Macintosh using smalltalk-80, is presented. zyxwvuts his paper shows that algorithm animation zyxwv an be incorporated as a graphical side effect of‘pro- cedures that access data structures. This strategy allows the programmer to concentrate on implementing an algorithm with little or no effort required for the animation of the algorithm. 1 Introduction Algorithm animation is a growing area for computer science research. Current work has been done using high-performance graphics based personal worksta- tion~.~.~,~ he results from these research efforts are impressive, though they still have some shortcomings. Brown University Algorithm Simulator and Animator, or BALSA,I.* suffers from the disadvantage that each piece of algorithm animation must be coded separately and then orchestrated. While INCENSE3 overcomes this problem by use of a library of display “artists”, each with a variety of “formats” for each inbuilt data type, the system is geared more to debugging than for use a teaching or research tool. This paper describes experience gained using an object oriented programming language4v5 (SMALLTALK-80) on a small computer (a Macintosh) to implement a system of algorithm animation that can be used by a programmer with little or no regard for the animation itself. The long term goal is to produce a system for use in teaching and research. 2. Design Smdtalk6>’ is one of the earliest in the category of Object Oriented Programming Languages. (For an excellent introduction to the rationale of object oriented programming, see the recent book by Brad Cox5 . The whole Smalltalk system is based solely on This zyxwvutsrqponml aper was presented at the EUROGR PHICS Department of Computing zyxwvutsr cience University of Glasgow Glasgow Scotland GI2 SQQ U.K. UK) onfermq NOIW~C~ pril 13-15 1987 message passing between objects of many differing classes. Objects consist of some private workspace and a set of operations or. methods). The nature of an object is determined by the types of operations it can perform. Objects representing numbers have arithmetic type operations. Objects representing data structures have operations for information storage and retrieval. A Class is a collection of objects which possess the same operations. In Smalltalk classes are themselves regarded as objects. Objects can communicate with other objects (of any class) by sending or receiving messages. Each valid message an object responds to has its own method which describes how to perform one of its operations. The result of a message may be an alteration of the internal state of an object or initiation of some process- ing which may result in a reply. One of the major advantages of Smalltalk is that classes of objects can inherit methods or operations defined in their parent (super) class. A subclass of a class can then modify any inherited method or add new ones of its own. Thus related classes of objects incre- mentally become more specialised the further down the inheritance tree they are. It is an easy matter to define a new subclass which has many similar properties to its parent (super) class but has new operations defined within it. Once a subclass has been defined, instances of that class (objects) can be created at any time. The use of Smalltalk-80 for algorithm animation is attractive for several reasons. It provides informa- tion hiding within objects from external users of those objects, and inheritance of class methods assists consid- erably in integration of new subclasses to existing classes. Additionally the system comes already sup- plied with high level classes, and their associated methods, thus providing a considerable help to the sys- tem implementation. The Macintosh implementation used for this investigation is supplied, free of charge, by Apple Computer Inc. to academic institutions. The work described concentrates on providing graphical representation for objects in the Smalltalk class ‘Array’. The main crux of the design is to provide a new subclass, ‘PictArray’, that inherits all the existing methods of its parent (super) class ‘Array’. The new class should also possess the necessary graphical attri- butes and their associated methods to perform animation of the basic data structure. North-Holland Computer Graphics Forum 6 1987) 151-156  152 zyxwvutsrqponml . Mohamed zyxwvut An Experiment zyxwv n AlKorithm Animation zyxw In general, there are only two primitive opera- tions that are essential for an array structure zyxwvut   zyxwvu eading and writing element contents. When considering sim- ple sorting algorithms two more higher level operations become apparent. These are, copying the contents of one element into another element in the same array and swapping the contents of two array elements “copy” and “exchange”). Both these operations zyxwvut an be syn- thesised from the two primitive operations. Copying and swapping of array elements are performed in any sorting implementation in any language and can replace one or more program statements. The animation of the may structure is encapsu- lated in these two high level operations and occurs as a side eKect. This approach allows the programmer to concentrate on the algorithm and not on the animation. Additionally, the graphical array representation mani- pulated by the ‘‘wpy“ and “exchange“ operators has Selection zyxwvutsr ort of n array Figure la. Selection Sort of an array +Index ......... ........ .. .:.:.:.:.:.:.:. 3 12 ......... Figure Ic. the ability to retain index names and values and all manipulations of pointers and elements automatically update the graphical representation. When a new ‘PictArray’ object is created it may be initialised before use Several levels of initialisation are allowed. These allow specification of title, position and size of clipping window and whether indices are to be displayed. The design allows for initialisation of a clipping window size from either the user or by the programmer. The other two parameters if not specifically initialised are assigned reasonable default values. Finally, two more methods allow the array representation to be made visible or invisible to the user by the programmer at any time within the life of the object. Again setting up the initial picture still involves little or no effort on the part of the program- mer. Selection Sort of an array clndex Fl pos Figure Ib. Selection Sort of an array +Index ......... +Minimum Figure Id. Figure 1. Basic array representation a), values moving out from array b) swapping over c) and moving back into the array d).  R. Mohamed /An Experiment in Algorithm Animation zyxw 53 zy The layout of the representation is quite simple. It is made up of a title box under which is a vertically arranged stack of individually boxed indices (optional) and their values. The area to the right, under the title bar is reserved for any named pointers into the array zyxwv see figure la). 3. zyxwvut mplementation Apple Computers Inc. supply their version of Smalltalk-80 with two levels of image. Level 0 is a stripped down image which zyxwvutsr ill run on the Macintosh 512K. It is missing many of the classes of the level 1 image but does retain full support for editing, compil- ing, debugging and browsing. The available memory is also low with only enough room for 3000 objects. The level 1 image is designed for machines with 1Mb or more of memory and appears to be a full image of the Xerox Licence 1 system. Initial experiments quickly showed that a 512K Macintosh running Apple Smalltalk-80 level 0 had insufficient memory for our purposes, zyxwvu o software development proceeded on a lMbyte Macintosh Plus running the level 1 Smalltalk image. No major prob- lems have been encountered with this setup so far. The PictArray class, as stated before, is imple- mented as a specialised subclass of the class Array. All standard methods belonging to ‘Array’ are inherited along with newer methods as described above. One private method ‘displayArray’ srcinally redrew the whole representation at every change. This proved to be inefficient and slow and this method was split into three. parts. Two of these allow selective updating of an array element and all the pointers into the array. These methods are then called recursively from a revised version of ‘displayArray’. This improvement significantly speeded up the update time and allowed the animation to proceed at a reasonable pace for teaching bepers. However, it is still a little too slow for more advanced students or debugging. Subscript names and positions are held in a Dic- tionary object (Associative store). The position, representing an array subscript, is referred to by sub- script name rather than value as subscript names pro- vide a more exclusive indexing key. Two or more occurrences of the same position will result in one being stored as a positive integer and the rest as nega- tive ones. This distinction is then used to offset the pointer name in the displayed raster by a fixed offset so making the two names visible. This simple arrange- ment is considered adequate as it is unlikely that three or more pointers will point to the same array element. The animation is quite simple and consists of the indexed value being pulled out, moved up or down the array and then being pushed back into the array. Swapping two elements causes them to be pulled out (see figure lb), moved (see figure lc) and then pushed back in simultaneously see figure Id). All the anima- tion occurs on the left side of the representation. 4 Results The speed of pointer updating and animation is a little disappointing but when compared to ease of prototyp- ing the new class this does not seem too bad a trade off. A Pascal implementation would not have the same system overheads present in the Smalltalk Virtual Machine but would be more complex to program. In a typical Pascal implementation the programmer would have to declare a data structure local to their procedure or globally, and call a host of external procedures to manipulate it. They could now write their own pro- cedures or functions to access the data structure ille- gally, as there is no compulsion on the part of the pro- grammer to use the existing routines. The results are encouraging, if one compares the first two example listings see figures 2 and 3) of a sim- ple selection sort implemented in Smalltalk.8 There is very little difference between them save for the mes- sages using pointer names and the swap elements mes- sage. If one ignores the swap message, as this is easy to I min temp 1 to:self size do: [ :i temp elf at:i. min ci i + 1 to: self size do: [ :j I ((self at:j) < self at:min) True: [ min ] 1 self swap:i with:min]. Figure 2. Selection sort of Array self) min temp I to:self size do: [ :i I temp elf at:i using:’Index’. min ci. i + 1 to: self size do: [ :j ((self at:j using:’Pos’) < (self at:min using:’Minimum’) iffrue: [ min ] 1 self swap:i with:min]. Figure 3. Selection sort of PictArray (self)  154 zyxwvutsrqponml . Mohamed zyxwvuts   zyxw n Experiment in lgorithm nimation zyxw   count temp pos atEnd 2 to:self size do: [ :count I temp self at:count. pos zyxwvuts   count. atEnd alse. [ atEnd ] whileFalse: [ (self at:(pos - 1)) > temp) iffrue: [ self at:pos put:(self at:(pos -1)). pos os -1 zyxwvuts   ifFalse:[ atEnd rue]. zyxwvutsr os = 1 ifTrue:[ atEnd rue].]. self at:pos put:temp]. Figure 4 Insertion sort of Array (self) temparray temp pos atEnd self at:2 using:’last sorted’. (isvisible = true) ifTrue:[ temparray ictArray new: 1. temparray initialise:Temp Store’ at:arrayView bottomLeft size:80@40 indexoff true. temparray show]. 2 to:self size do: :count temp elf at:count using’last sorted’. (isvisible = true) pos count. atEnd false. [ atEnd ] whileFalse: itTrue:[ temparray at: 1 put:temp using:”]. [ (self at:(pos 1) using:’Pos- 1 ’ > temp) iffrue: [ t elf at:pos using:’Pos’. self copyFrom:(pos 1 to:pos. pos os -1 ] ifFalse:[ atEnd true]. pos = 1 inrue:[ atEnd true].]. self at:pos put: temp using:’Pos’. (isvisible = true) itTrue:[ temparray hide]. Figure 5 Insertion sort of PictArray (self) add to the the class Array, then the differences betwen the two pieces of code are neghgible. Looking at the more complex case the two listings of an insertion sort (see figures and 5) appear to differ somewhat at first sight. The Array listing (see figure 4) is a straight for- ward insertion sort whereas the PictArray listing see figure 5) has been enhanced by use of a second PictAr- ray that is used to hold and display the value of ‘temp’. Most of the extra lines of code deal with initidsing, displaying and removing the visible ‘temp’ store. If these lines are ignored then again there is very little difference between the two pieces of code. Most of the differences lie with using an extended message form when accessing array elements. There is one apparently superfluous line t elf at:pos using:’Pos’ ”, which has been added just to update position of the pointer ‘Pos’. 5. Discussion Smalltalk-80 has proved to be a good choice with which to implement the ideas. Its central object oriented paradigm has made implementation and integration of the software within the Smalltalk environment easy. There is still plenty of scope for improvement and enhancement of the ideas within the system. However, a certain minimum requirement was found necessary for software development. A memory sue of lMByte has proved satisfactory. Some problems were expen- enced with the amount of available disc space and 2 800K byte disc drives must be considered a minimum requirement, though a hard disc would be adventa- geous. Paradoxicaily, compilation of the class source caused a stack overflow when using the smaller 512K Macintosh. This was overcome by running level 0 on the IMByte Macintosh and then copying the resultant image file produced. The completed class description has been ported across to a Whitechapel Mgl workstation, running an academic implementation of Smalltalk, without any problems. The Mgl code running at approximately the same speed as the Macintosh. One criticism of the current implementations of Smalltalk in use is the speed of the interpreter. On both the Mgl and Apple versions execution speed is just acceptable. This performance is unlikely to improve appreciably in the near future and the possibil- ity of using oiher more efficient object oriented pro- gramming anguages is currently being investigated. This simple design does demonstrate that it is possible to animate an algorithm with little or no effort on the part of the programmer. In its present form the design is flexible enough to be applied to other algo- rithms and data structures in a straightforward way. There are still a number of problems needing to addressed. The screen layout in its present form is fixed and rigid. A more flexible approach would allow for selection of one of several screen formats and sizes for display.3 This approach would require some form of intelligence on the part of the object so that it can pick the most appropriate representation for any given oc~a-  R. Mohamed zyxwvut   An Experiment in Algorithm Animation zyx 55 zy sion. When zyxwvutsrq ll the other basic data structures and abstract data types a language may possess are also Despite this, the experiments reported here give grounds for optimism that zyxwvut lgorithm animation will won become a widely available and convenient tool for both programmers and educators. References 1. considered the size of the problem is considerable. 4. zyxwv   6. Brown M H, and Sedgewick R, “A System of Algorithm Animation,” Computer Graphics 18 3), Brown M H and Sedgewick R, “Techniques for Algorithm Animation,” IEEE Sofmare Yl), 8. Myers B A, zyxwvutsr INCENSE:A System for displaying 7. pp. 177-186 1986). 2. pp. 28-39 985). 3. Data Structures,” Computer Graphics 17 3), BYTE 6 8), Smalltalk Issue 1981). Cox B J, zyx n Object Oriented Programming Addison-Wesley Publishing Company, Reading Massachusetts 1 986). Goldberg A, Robson D, n Smallralk-8O:The Language and its Inylernentation Addison-Wesley Publishing Company, Reading Massachusetts 1983). Krasner G, in Smalltalk-80:Bits of Histo~y ork of Advice Addison-Wesley Publishing Company, Reading Massachusetts 1 983). Sedgewick R, n Algorithms Addison-Wesley Publishing Company, Reading Massachusetts 1983). pp. 115-125 1983).
Related Documents
View more...
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks
SAVE OUR EARTH

We need your sign to support Project to invent "SMART AND CONTROLLABLE REFLECTIVE BALLOONS" to cover the Sun and Save Our Earth.

More details...

Sign Now!

We are very appreciated for your Prompt Action!

x