Tags

Leo and I were studying the Fibonacci primes and we decided to build a sieve of Eratosthenes in HopScotch. (He actually wanted to write a program to find Fibonacci primes, but I figured that starting with the simpler program would be plenty of effort for this morning!)

You’d think that a sieve program would be trivial, but because HopScotch’s object model is a tad limited, we had to do a little bit of mind yoga to get there. Here’s our sieve (which you can open on the ipad hopscotch platform if you have it.)

Results first, of course:

The purple number on the bottom right is the multiple being filtered — this goes from 2 to 10 — this could skip all even numbers after two, but I didn’t bother. (You only have to go to the square root of the top value — exercise for the reader: Why?) The orange number is the value it is actually filtering out. It gets beyond 100 (which is the actual top number) for reasons that will be explained later on. Note that 71 and 73 are almost on top of one another making it look like the number 7713 snuck in somehow!

The weirdness with HopScotch’s object model is that there are no local variables, and no arrays nor object ids (that you can get your hands on), so you also can’t fake locals by building your own symbol table. There is a CLONE operation, but because there are no locals, the clones can’t really have a persistent personal identity. As a result, if you want to make, say, 100 objects representing the values 1-100, you either have to manually create 100 separate objects, or you have to do something slightly mind-bending.

The only way that we could figure out to uniquely identify objects in a way that allows you to actually compute with those identities — put another way, the only way to distinguish cloned objects from one another — is by their position; the position of an object is obviously a local (in two senses!) property of the object, and you can get it from the object.

So, the sieve we built creates 100 clones and puts them in sequential X positions on the screen (and random Y positions). The clone’s X position thus indicates its value (times a constant spacing factor). Here’s the setup code attached to the master object:

Note that these are attached to an object called “1”, which clones itself to create every. On the left is that initialization method for 1. The central loop clones the object 100 times. The interesting work is done on the right which is the clone initialization method. This names the object with the current counter (incremented in the master loop, on the left), and place is in the correct XY position on the screen. The X becomes the object’s identity, and the Y is random. This is what creates the layout in the first figure, above.  Note the wait in the inner loop on the left. Because this is all happening asynchronously, we have to give the new clone time to initialize before incrementing the counter, otherwise we’ll miss numbers. This could more complexly, and more correctly, done with semaphores through global flags, but that’s a lot more complex, and remember that a 6 year old is the one who’s programming all this. I had enough trouble explaining even this level of complexity. Anyway, here’s what it looks like near the beginning:

Before (almost)

I say near the beginning because I happened to capture this screenshot after it had started filtering multiples of 2 (purple), and had got up to 42 (orange), so the even numbers are already missing up to 42. Note, for example, that odd multiples of 3 are still there even on the left, such as 9 and 15. These will get filtered on the next (3) round.

Okay, so how does the filtering step work? Obviously you want to loop through the values up to 10 (sqrt of 100), removing all multiples of any of those numbers, well, except for the number itself (otherwise you’d also delete 2,3,5, and 7). This code is attached to a different (hexagon) object, and so has to have a bit of a delay so that the number field exists when it starts filtering. (Although it occurs to me that it could just as well have been added to the “1” object after the initialization was done, and that would have saved us the ugly 5000 wait. OTOH, the fact that this start filtering numbers before they are all placed makes the dynamics of the program slightly more interesting because you get to watch numbers on the right appearing even as numbers on the left start vanishing.)

K (incremented in the outer loop) is the factor we’re filtering on (2-10), and N (incremented by K in the inner loop) tells us what number to actually filter out).

(Note also that we repeat up to 110/k instead of the more obvious 100/k. This is to avoid an off-by-one error that could bite us at the top of the number spectrum when counting by large k; I didn’t want it to stop at, say 90 when counting by 9s or 10s. For some reason that I haven’t bothered to debug, this ends up sending us way through 100, like up to 126 in the first screenshot above.)

Finally, the core filtering logic is a simple method attached to each of the 100 clones of the master 1 object:

All that it does is to make the object vanish. What’s interesting, and what makes this actually work (!) is that the method trigger asks when N (which is incremented in the inner loop, above) is equal to the X position of the given clone (that is, when the clone’s X position = N * D, where D is the distribution factor, initialized at the very beginning). One of HopScotch’s cool features is that you can put somewhat complex conditions in the method triggers of objects, and this is what allows all this to work at all!