Scratch

Hi,
An implementation of a programming language ought to have its semantics defined at a high level without requiring the user to read the source code! I would appreciate it if one of the developers could answer me.
Moti

I suspect the developers are pretty busy trying to get version 1.3 out the door.  We'll just have to wait and see if they can find time to respond to these requests.

Hi, MotiB (and others curious about how Scratch works).

Scratch simulates concurrency (i.e. more than one stack running at the same time) by executing a few commands in each stack, then moving on to the next one. After running a few commands from every running stack, Scratch updates the screen so the the user can see what's happening, then the whole cycle starts over. Stacks are processed some order, of course, but the programmer should not rely on that order since it might change the next time the project is run or it might be different when the project is running in the Java player on in some other version of Scratch.

Each command block is executed complete ("atomically") except when that block waits for something. Blocks that wait include timed blocks, such as "wait," "glide", and "play note", and blocks that wait for something to finish, such as "play sound and wait" and "broadcast and wait." When Scratch encounters a waiting block it checks to see if it is still waiting; if so, Scratch continues on to run the next stack. If not, Scratch goes on to the next block after the wait block. (Fine point for computer scientists: The "wait" block always waits at least one cycle of the scheduler, even if the wait time is 0. Thus "wait 0" can be used the way "yield" is used in some other threading systems.)

How many blocks does Scratch run in each stack before it moves on to the next stack, assuming there are no wait blocks to interrupt the flow early? This is where Scratch is subtly clever. It runs as many commands as it can until it gets to the end of the innermost loop. If it doesn't hit a loop, Scratch simply runs the rest of the blocks in the stack. The reason this is clever is that if a stack does some test, say whether one sprite is touching another, then the commands that depend on that test are also run before Scratch moves on to the next stack. That keeps another stack from changing conditions -- for example, by moving the touched sprite. Although any computer scientist knows that this is not a foolproof strategy, it's a close match to how we think about program execution (it's easier to think about the sequential execution of a single stack in isolation, as if no other stacks were running). An expert programmer could actually use this guarantee to create a robust concurrency control mechanism, perhaps to illustrate that idea for a computer science class.

There is one more aspect of Scratch execution that may be relevant. When Scratch is running in the normal, development mode, it actually updates the screen even more often than indicated. In fact, Scratch tries to update the screen after the execution of every block that has some visual effect. Scratch runs faster than the video update rate, so some changes happen so fast that the user never sees them. But suppose someone tries to make their sprite dance writes a program like this:

  forever
    move 10 steps
    move -10 steps

Note that the two move blocks leave the sprite exactly where it was when it started, and there are no "wait" blocks. If Scratch only updated the screen once per loop, there would be no visible effect; it would look like the program wasn't running. But since, in development mode, Scratch updates the screen after each move command, the user will see an occasional flicker and realize that the program is doing something, even thought it is just going too fast, and needs a wait block to slow it down.

These extra displays slow Scratch down once you have finished your program. So, in presentation mode and when running in the Java applet, Scratch omits these extra display updates. On the other hand, if you are having trouble understanding what you program is doing, you might want to slow Scratch down even further by turning on "single stepping" using the "Extra" menu.

So that's the story. I hasten to add that you don't need to understand these details to use Scratch. Some people, especially computer scientists, like to know how things work *exactly*. But many Scratch users write sophisticated Scratch programs that include a great deal of concurrency (many stacks running at the same time) without knowing these details.

  -- John

Hello,

First let me say that my interest is more than "academic". We have taught relatively advanced concepts of concurrency to high school students. The concurrency and event handling in Scratch make it a sophisticated programming environment. In evaluating Scratch for use in junior high schools, I would like to use some examples of concurrency, and for this I need a precise knowledge of the semantics.

John, thank you for your explanation. I understand the motivation behind the "subtly clever" atomic operations, but it is unexpected!

Just one question: Why is the mechanism _not_ "foolproof" and "robust"? If I can _depend_ on the atomicity within a loop, I should be able to write a semaphore:
  loop
    if S > 0
       S <- S - 1
       exit loop
  end loop

True, this is a busy-wait semaphore, but at an elementary level that is sufficient.

Moti

I'm interested in writing the equivalent of P and V (Djikstra's semaphore operations) in Scratch after someone said it couldn't be done: I've create a sprite s, with a 'local' variable s, containing 3 scripts:

when I receive P
  wait until s > 0
  change s by -1

when I receive V
  change s by 1

when I receive Init
  set s to 1

Now to test it I've an elephant with a green flag script

when green flag clicked
  broadcast init and wait
  broadcast P and wait
  move 10 steps

but clicking the green flag doesn't move the elephant. Single stepping shows the broadcast of the init works and s gets set to 1, the P gets broadcasted (and the s gets changed to 0) but the move 10 steps never gets run. If I change the broadcast P and wait to just broadcast P it works.

From reading the description of Scratch/Squeak's concurrency above I think it should do, since single stepping again shows that the when I receive P works and terminates.

Any thoughts anyone?

John Stout

Well, isn't that strange? Your project works fine on 1.4 on my machine, but mine still doesn't work. I wondered if it was something to do with the green flag script running 'inside' the semaphore sprite, but I've moved it to another sprite and it still works.

If I move the green flag script to the stage and try to run it it fails with a red border.

I've just discovered BYOB which might help solve the issue, since I can declare the operations as atomic to remove any doubts of the atomicity.

Many thanks. I'll try and recreate it amd see if it's something to do with my version. Could it be because I called the sprite and the 'local' variable the same name?

John Stout

Last edited by jstout (2009-08-10 04:24:34)