TweetFollow Us on Twitter

Towers
Volume Number:2
Issue Number:1
Column Tag:Threaded Code

Animated Hanoi Towers in NEON

By Jörg Langowski, EMBL, c/o I.L.L., Grenoble Cedex, France, MacTutor Editorial Board

Lately, we have had a number of requests for a column on NEON. Since no neon articles have been forth coming, I have been asked to temporarily switch from my usual Forth ramblings to NEON. Since NEON is so close to Forth, we have decided to show a NEON example this month for a change. In light of this, we will re-name this column "Threaded Code" to cover all the Forth like object oriented languages that are Forth derivatives on the Mac.

The principles of object oriented programming have already been explained in several earlier columns (see LISP V1#6, NEON V1#8), so I am not going to dwell on that here. Rather, we are going to look at the famous Towers of Hanoi algorithm from an object-oriented point of view, gaining some on-hands experience with an example that - I feel - is particularly appropriate for this approach.

Let's recall: The 'towers' are three stacks of disks (Fig. 1). The leftmost one is filled with n disks stacked on top of one another in order of decreasing size, the other two are initially empty. The objective is to move the disks from the leftmost to the rightmost position, one by one, in such a way that a larger disk is never put on top of a smaller one. This works if one uses the middle position as a 'scratchpad' (try it out with pieces of paper), even though this is a rather tiresome procedure, if performed manually.

Fig. 1: Initial and final positions of Towers of Hanoi.

This is, of course, where Mac comes in; and the algorithm to solve the puzzle is very short if written recursively. In pseudo-Pascal it would look like this (see also John Bogan's Modula-2 column in V1#6):

procedure hanoi (n, start, inter, finish:integer);
    begin
     if n<>0 then 
 begin
 hanoi (n-1, start, finish, inter);
 move (n, start, finish);
 hanoi (n-1, inter, start, finish)
 end
    end;

where n is the number of disks, and start, inter and finish denote the starting, scratch and final positions for the disks. move is a procedure that (somehow) moves the disk from one stack to another.

OK, so if we set up a stack of disks, provide three towers to put them on to, and execute this procedure, we should be able to watch how Macintosh solves the Towers problem.

There are two things to notice: First, the definition is obviously recursive, second, we have to be careful how to represent our data.

Recursive definitions - NEON and MacForth

A very simple recursive procedure is the definition of the factorial of an integer number, which is given at the very beginning of the program example (listing 1). This definition works in NEON; you may refer to a word within the definition of the word itself (By the way, even if you weren't allowed to do it that way, you could resort to the forward declaration).

MacForth, however, sets the smudge bit in the vocabulary while compiling a new definition; therefore the word being defined is not known to the system at compile time and cannot be referred to by itself. You have probably seen the effect of the smudge bit already; when the compiler exits a declaration due to an error, words will show the first letter of the latest definition changed (in fact, it has the 8th bit set). One can easily circumvent this restriction by writing

: factorial   [ smudge ] 
   dup if dup 1- factorial * else drop 1 then ;
smudge

i.e., executing smudge during the compilation of factorial and resetting it afterwards. This will give a working definition, within the limit that is given by the 32-bit maximum integer size of the Macintosh.

Representation of disks and towers as NEON objects

Since we are, in fact, simulating material objects, moving them around and also displaying the result of our simulation on the screen, the Towers of Hanoi problem seems to be idealy suited for an object oriented language like NEON. We could define 'disks' as objects that can be drawn, put on top of other objects, called 'towers' and moved between them. The towers will automatically keep track of how many disks are on them, the disks will 'know' what tower they are on and how to 'draw themselves'.

The Three Towers

There is one predefined class in NEON, ordered-col, that represents a list of variable size. Elements of that list are 4-byte entities. A tower in our example will be an ordered-col of specified maximum size. In addition, it will have a certain position on the screen, which can be accessed by the methods getX: and getY: and a draw: method that draws the tower at its position in the current grafPort. That's all we need as a 'stacking device' for the disks. Everything else is taken care of by the disks themselves, as you will see soon.

The instance variables needed for every object of class tower are: rects that correspond to the base and the post, and ints that contain the x and y position of the center of the base.

Now we could start our simulation by creating three tower objects, e.g.

 tower babylon
 tower london
 tower pisa

Except for the fact that this looks cute, there is really no advantage in having named objects here. Just to make the point, and as an example how objects can be made to refer to other objects, we set up the three towers as a 3-element 4-byte array towers. This gives the additional advantage that we can refer to them by index. The array is initialized by the word make.towers, which shows how one can create 'nameless' objects on the heap with the heap> prefix (in my review copy of NEON, this information is hidden somewhere in the pages of Part III Chapter 1; I am confident that a revised manual will have this in the glossary).

xcenter ycenter ndisks heap> tower will leave on the stack the address of a new object of class tower created on the heap. The tower contains ndisks disks, and its base is centered at (xcenter,ycenter).

ndisks make.towers creates three of these gizmos equally spaced near the bottom of the screen, each of them having space for disks, but no disks on them yet. Their addresses are put into the array towers.

draw.towers will draw the towers, but not the disks. In this definition you see how one makes use of late binding; we want to send a draw: message to an object which is exactly known only at execution time (since towers could contain any kind of address). Therefore, if we want to draw the i-th tower, we have to write draw: [ i at: towers ] . (The same is true in immediate execution mode: draw: addr will abort with an error message, while draw: [ addr ] will do the correct thing, if addr is the address of a 'drawable' object. )

After you're finished with the example, you might want to dispose of them by calling dispose.towers. The same should be done to the disks; try writing a definition that will do the job.

Moving around the disks

The disk objects are more complicated than the towers. They have to be initialized and drawn; they will come in different sizes; and they will move around, sitting on one of the three stacks at any given time.

Since the disks won't shrink or grow, their size is known at initialization time and will be passed as a parameter to classinit:. This method also needs to know which tower the disk is on at the beginning (we pass the address of the tower object and put it into the instance variable which). The newly created disk it then put on top of the tower which it is associated with.

The draw: method is not quite general for disks, but very specialized for Hanoi disks: it makes use of the fact that a disk is only drawn right after it has been put on top of a stack. Since the size of that stack is known (by executing size: [ get: which ] ), the position of the topmost disk is exactly determined. Therefore, draw: calculates first the coordinates of the center of the disk and saves them in instance variables for later use, then does the necessary Quickdraw calls. If one wanted to do other things with the disks, e.g. drawing them at different places, one might want to factor out the code that calculates the coordinates.

undraw: removes the disk from its position (but not from the list which is being kept in the tower), and redraws the little black rectangle, the part of the post that had been overwritten previously. Here again, you see that a special assumption about the behavior of the disk is made: namely, that it does not cover anything but a certain part of the tower post.

dest move: finally will move a disk from wherever it was to the tower dest, undrawing and redrawing as necessary.

Object Interdependence

You see the line that we draw between general and specialized behavior of objects. The fact that a disk is displayed as a pattern-filled rectangle that takes up a certain amount of space on the screen is a behavior that would be general to any 'disk-like' object (unless we choose to rotate it as well). Association to another object, the tower, would also be something that could be implemented into an idealized 'general' disk. But the fact that this other object has a certain shape and that the disk can only be put onto it in a certain manner is extra information which the disk 'knows' about and which is used within the code that defines some of its methods.

To make the objects even more independent, 'MacDraw-like', would require a much more sophisticated interface between towers and disks than given here. One would then rather start by defining a subclass of window which has e.g. an ordered-col of objects associated to it, and which would be updated each time one of the objects is moved. I felt this would have created too much overhead to the program example. But you can see that MacDraw is not very far away, just go ahead and create that window, a set of objects and their appropriate behavior, and there you go... send us the code when you're done, we'll publish it.

Main routine

The main routine simply creates a Hanoi puzzle of ndisks disks and draws the initial position. ndisks i j k hanoi will move those disks ( or less, if you set ndisks differently) according to the rules of the game from tower i via j to k. Try

10 main
10 0 1 2 hanoi

or, to create a 'forbidden' pattern

10 main
5 0 1 2 hanoi
5 0 2 1 hanoi
5 1 0 2 hanoi

Have fun! Determined FORTH programmers might try to rewrite this example into MacForth or some other Forth. The Hanoi routine itself is simple. Doing the data representation in the same way should look rather more complicated...

Change of address

We have moved in the meantime. Please address all questions, remarks, suggestions, etc. regarding this column to:

Jörg Langowski

EMBL, c/o I.L.L., 156X

F-38042 Grenoble Cedex

France

Listing 1: Towers of Hanoi code
( © 110285 MacTutor by JL )
: factorial   dup if dup 1- factorial * else drop 1 then ;

:class tower <super ordered-col
        rect base
        rect column
        int xcenter
        int ycenter

    :M classinit: ( xcenter ycenter -- )
            put: ycenter put: xcenter 
            get: xcenter 70 -  get: ycenter 16 - 
            get: xcenter 70 +  get: ycenter   put: base
            get: xcenter 4 -   get: ycenter 
 limit: self 10 * 50 +  -
            get: xcenter 4 +   get: ycenter 16 - 
 put: column 
    ;M

    :M draw:  0 syspat dup fill: base fill: column ;M
    :M getX:   get: xcenter ;M
    :M getY:   get: ycenter ;M

;class

:class disk  <super object
        int size
        var which
        rect image
        int xc  int yc
    :M classinit: ( which size -- )   
                    put: size  put: which 
                    addr: self  add: [ get: which ] ;M
    :M draw: 
            getX: [ get: which ] put: xc 
            getY: [ get: which ] 
                 12 - size: [ get: which ] 10 * - put: yc
            get: xc get: size -  get: yc 4-   
            get: xc get: size +  get: yc 4+  put: image
            3 syspat fill: image  draw: image 
    ;M

    :M undraw: 19 syspat fill: image
            get: xc 4- get: yc 4- 
            get: xc 4+ get: yc 4+  put: image
            0 syspat fill: image
    ;M

    :M move: { dest -- }
            undraw: self
            addr: self add: [ dest ]
            size: [ get: which ] 1-  
            remove: [ get: which ]
            dest put: which   draw: self
    ;M
;class
3 array towers
: make.towers { ndisks -- }
   3 0 do 
      i 150 * 100 +  280 ndisks  heap> tower  
      i to: towers  loop ;

: draw.towers
   3 0 do draw: [ i at: towers ] loop ;

: dispose.towers   3 0 do  i dispose: towers loop ;

: hanoi { n start inter finish -- }
   n if   n 1-  start finish inter hanoi
          finish at: towers  
               move: [ last: [ start at: towers ] ]   
          n 1-   inter start finish hanoi
     then
;
: main  { ndisks -- }
    ndisks make.towers  cls draw.towers
    ndisks 0 do 
       0 at: towers 6 ndisks i - 4* + heap> disk drop 
                       draw: [ last: [ 0 at: towers ] ] loop
;
 

Community Search:
MacTech Search:

Software Updates via MacUpdate

RapidWeaver 6.0.8 - Create template-base...
RapidWeaver is a next-generation Web design application to help you easily create professional-looking Web sites in minutes. No knowledge of complex code is required, RapidWeaver will take care of... Read more
Artlantis Studio 5.1.2.7 - 3D rendering...
Artlantis Studio is a unique and ideal tool for performing very high resolution rendering easily and in real time. The new FastRadiosity engine now lets you compute images in radiosity-even in... Read more
MacUpdate Desktop 6.0.5 - Search and ins...
MacUpdate Desktop 6 brings seamless 1-click installs and version updates to your Mac. With a free MacUpdate account and MacUpdate Desktop 6, Mac users can now install almost any Mac app on macupdate.... Read more
BitTorrent Sync 2.0.82 - Sync files secu...
BitTorrent Sync allows you to sync unlimited files between your own devices, or share a folder with friends and family to automatically sync anything. File transfers are encrypted. Your information... Read more
Google Drive 1.20 - File backup and shar...
Google Drive is a place where you can create, share, collaborate, and keep all of your stuff. Whether you're working with a friend on a joint research project, planning a wedding with your fiancé, or... Read more
Simon 4.0.3 - Monitor changes and crashe...
Simon monitors websites and alerts you of crashes and changes. Select pages to monitor, choose your alert options, and customize your settings. Simon does the rest. Keep a watchful eye on your... Read more
Vitamin-R 2.23 - Personal productivity t...
Vitamin-R creates the optimal conditions for your brain to work at its best by structuring your work into short bursts of distraction-free, highly focused activity alternating with opportunities for... Read more
iDefrag 5.0.0 - Disk defragmentation and...
iDefrag helps defragment and optimize your disk for improved performance. Features include: Supports HFS and HFS+ (Mac OS Extended). Supports case sensitive and journaled filesystems. Supports... Read more
PCalc 4.2 - Full-featured scientific cal...
PCalc is a full-featured, scriptable scientific calculator with support for hexadecimal, octal, and binary calculations, as well as an RPN mode, programmable functions, and an extensive set of unit... Read more
FileZilla 3.10.2 - Fast and reliable FTP...
FileZilla (ported from Windows) is a fast and reliable FTP client and server with lots of useful features and an intuitive interface. Version 3.10.2: Note: Now requires a 64-bit Intel processor.... Read more

Warner Bros. Interactive Entertainment A...
Warner Bros. has some exciting games coming down the pipe! | Read more »
GDC 2015 – Star Trek Timelines will Prob...
GDC 2015 – Star Trek Timelines will Probably Make Your Inner Trekkie Squeal With Glee Posted by Rob Rich on March 4th, 2015 [ permalink ] Any popular fictional universe has its fair share of fan fiction – where belo | Read more »
Protect Yourself from an Onslaught of Ca...
Surprise Attack Games has announced a Cat-astrophic new physics puzzler called Fort Meow! In the game, a young girl named Nia finds her grandfather’s journal which triggers an all mighty feline attack! Why do the cats want the journal? Who knows,... | Read more »
GDC 2015 – Jelly Reef will be Game Oven’...
GDC 2015 – Jelly Reef will be Game Oven’s Last Hurrah, and it Seems like a Good Note to Go Out on Posted by Rob Rich on March 4th, 2015 [ permalink ] It’s sad knowing that Game Oven ( | Read more »
daWindci Deluxe Review
daWindci Deluxe Review By Campbell Bird on March 4th, 2015 Our Rating: :: BLUSTERY PUZZLESUniversal App - Designed for iPhone and iPad This updated puzzle game offers some creative gameplay and new mechanics, but still suffers from... | Read more »
Dungeon Hunter 5 Coming on March 12
Gameloft has excitedly announced that Dungeon Hunter 5 is on its way! Once again, you will adventure across the land of Valenthia exploring dungeons and fighting monsters. The game will have a new asynchronous multiplayer mode called Strongholds... | Read more »
GDC 2015 – The Sandbox 2 is Coming, and...
GDC 2015 – The Sandbox 2 is Coming, and Now it has Textures! | Read more »
Warner Bros. Interactive Announces Mort...
Mortal Kombat X, by Warner Bros. and NetherRealm Studios, will be a a free-to-play fighting/card-battle Mortal Kombat game. The game promises card collecting, multiplayer team combat, classic characters such as Scorpion, Sub-Zero and Raiden, and the... | Read more »
GDC 2015 – Piloteer is Whitaker Trebella...
GDC 2015 – Piloteer is Whitaker Trebella’s Latest Project, and it’s Definitely Something DIfferent Posted by Rob Rich on March 3rd, 2015 [ permalink ] You know | Read more »
PangoLand Review
PangoLand Review By Amy Solomon on March 3rd, 2015 Our Rating: :: COME VISIT PANGO AND FRIENDSUniversal App - Designed for iPhone and iPad PangoLand is an open-ended world full of familiar characters, bright colors and interactive... | Read more »

Price Scanner via MacPrices.net

iPad: A More Positive Outlook – The ‘Book Mys...
It’s good to hear someone saying positive things about the iPad. I’ve been trying to bend my mind around how Apple’s tablet could have gone from zero to bestselling personal computing device on the... Read more
Mac Pros on sale for up to $279 off MSRP
Amazon has Mac Pros in stock and on sale for up to $279 off MSRP. Shipping is free: - 4-Core Mac Pro: $2725.87, $273 off MSRP (9%) - 6-Core Mac Pro: $3719.99, $279 off MSRP (7%) Read more
Sale! 13-inch Retina MacBook Pros for up to $...
B&H Photo has 13″ Retina MacBook Pros on sale for up to $205 off MSRP. Shipping is free, and B&H charges NY sales tax only: - 13″ 2.6GHz/128GB Retina MacBook Pro: $1219.99 save $80 - 13″ 2.... Read more
Another Tranche Of IBM MobileFirst For iOS Ap...
IBM has announced the next expansion phase for  its IBM MobileFirst for iOS portfolio, with a troika of new apps to address key priorities for the Banking and Financial Services, Airline and Retail... Read more
Sale! 15-inch Retina MacBook Pros for up to $...
B&H Photo has the new 2014 15″ Retina MacBook Pros on sale for up to $250 off MSRP for a limited time. Shipping is free, and B&H charges NY sales tax only: - 15″ 2.2GHz Retina MacBook Pro: $... Read more
WaterField Designs Introduces the Minimalist...
With Apple Pay gaining popularity, Android Pay coming in May 2015, and loyalty cards and receipts that can be accessed from smartphones, San Francisco’s WaterField Designs observes that it may be... Read more
Sale! 15-inch 2.2GHz Retina MacBook Pro for $...
 Best Buy has the 15″ 2.2GHz Retina MacBook Pro on sale for $1774.99 $1799.99, or $225 off MSRP. Choose free home shipping or free local store pickup (if available). Price valid for online orders... Read more
13-inch 2.5GHz MacBook Pro (refurbished) avai...
The Apple Store has Apple Certified Refurbished 13″ 2.5GHz MacBook Pros available for $170 off the cost of new models. Apple’s one-year warranty is standard, and shipping is free: - 13″ 2.5GHz... Read more
13-inch 2.5GHz MacBook Pro on sale for $100 o...
B&H Photo has the 13″ 2.5GHz MacBook Pro on sale for $999.99 including free shipping plus NY sales tax only. Their price is $100 off MSRP. Read more
27-inch 3.5GHz 5K iMac in stock today and on...
 B&H Photo has the 27″ 3.5GHz 5K iMac in stock today and on sale for $2299 including free shipping plus NY sales tax only. Their price is $200 off MSRP, and it’s the lowest price available for... Read more

Jobs Board

*Apple* Retail - Multiple Positions (US) - A...
Sales Specialist - Retail Customer Service and Sales Transform Apple Store visitors into loyal Apple customers. When customers enter the store, you're also the Read more
*Apple* Solutions Consultant - Retail Sales...
**Job Summary** As an Apple Solutions Consultant (ASC) you are the link between our customers and our products. Your role is to drive the Apple business in a retail Read more
Position Opening at *Apple* - Apple (United...
…Summary** As a Specialist, you help create the energy and excitement around Apple products, providing the right solutions and getting products into customers' hands. You Read more
Position Opening at *Apple* - Apple (United...
**Job Summary** The Apple Store is a retail environment like no other - uniquely focused on delivering amazing customer experiences. As an Expert, you introduce people Read more
*Apple* Solutions Consultant - Retail Sales...
**Job Summary** As an Apple Solutions Consultant (ASC) you are the link between our customers and our products. Your role is to drive the Apple business in a retail Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.