2.3.1 Parallelism and Communication for Clean Solutions

The world naturally works in parallel, and so parallelism is a helpful tool for modeling the real world. An effective way to demonstrate this is to introduce parallelism early and without any particular fanfare. In fact, the instructor may wish to consider not mentioning the word “parallelism” until after this exercise has been completed. In this exercise, a parallel solution arises as a natural consequence of the desire to model the real world, and thus students are more comfortable with it as just another part of programming.

In this first exercise, students are presented with a cartoon boy with four frames of animation (Figure 2.1), and the image of a basketball. The task is for the students to create an animation of the boy walking and dribbling the basketball across the screen. For simplicity, the instructor may wish to disregard whether or not the ball is actually “hitting” the boy’s hands. Rather, the instructor might consider requiring simply that the ball must move in a fairly natural-looking way as the boy continues to walk forward smoothly.

In Scratch, an object loaded into a script is called a sprite. So in this example there is a boy sprite, containing four related images, and a basketball sprite. Each sprite has a script-editing area. This is the only area in which commands may be given to that sprite, except indirectly through intersprite communication, as discussed below. Often, blocks of commands are triggered through some user action, such as pressing the space bar or the “flag” button in the Scratch interface.

In the code in Figure 2.2, both the boy script and the basketball script are activated by hitting the flag button. Even here, a simple form of parallelism is in use. The boy and the ball start at the same location. The boy moves forward a small distance at a time, changing to the next frame of animation at each step. In parallel, the ball moves down and then up, also spinning slightly and moving right slightly.

The problem with this code is the precise relationship required between several numbers. As shown, the boy moves seven “steps” at a time (not corresponding to an animated step), with a 0.2 s wait time between each move, and an unknown short time to execute the next costume command to go to the next frame of animation. The ball has far more moves to be executed in the same amount of time, as the ball’s vertical movement should be faster than the boy’s horizontal movement. But at the same time, the ball must move horizontally, at the same pace as the boy. Thus, there are complex relationships between the numbers controlling the movement of the sprites. Determining the perfect balance between these numbers is a frustrating exercise in trial and error with limited educational value. In fact, the numbers shown in Figure 2.2 are not precisely correct in order to obtain natural movement. Rather, the ball and the boy will become out of sync, with one increasingly distant from the other as they move across the screen. Even a small imperfection in the relationship between these numbers will be revealed when the sprites are allowed to move sufficiently far.

With more effective use of parallelism, a simple and flexible solution is easily obtainable with very little trial and error required. The solution involves parallelism not just in the boy and ball acting simultaneously, but also in two separate blocks of code for the ball running simultaneously.

Consider the solution in Figure 2.3. In this solution, the boy sprite uses the broadcast block to send a message to the ball sprite. The ball sprite listens for this message with the when I receive block. This will occur in parallel with the ball’s larger code block, which now handles only vertical movement. With the boy “telling” the ball exactly when to move, no more guessing or precise balancing of commands is required between the two sprites.

In contrast to the previous code, this code is quite easy to tweak for good visual performance, with a good balance obtainable in just a couple of trials. This is because there are fewer dependent numbers. In particular, note that the ball’s horizontal movement (change x by 7) can now perfectly and trivially match the boy’s horizontal movement (move 7 steps). The only numbers to tweak, then, are those controlling the vertical movement for the ball, through the relationship between repeat 13 and change y by ± 5.

Through some hints in the problem description, students can be guided to this more effective solution. This can be done without mentioning the word “parallelism” yet, so as to avoid the suggestion that this is something particularly difficult or different from what ordinary programming is. Only when the exercise has been completed and the solution is being discussed as a class is it necessary to explicitly introduce concepts of parallelism and intersprite communication, drawing an analogy to the coordination of processes through communication. Thus, the students’ first exposure to these concepts is in a fun context, in which the more sequential solutions are unnatural and unwieldy, while the parallel solution is very natural and helpful. And so students’ appreciation of parallelism begins.

2.3.2 A Challenge of Parallelism: Race Conditions

Of course, for all its benefits, parallelism does sometimes bring unique challenges to a problem, and to be literate in programming requires students to be aware of these challenges. One challenge of parallelism is that of race conditions. Since Scratch actually executes code concurrently, not truly in parallel (as discussed above), “race conditions” in Scratch actually give behavior that is consistent, though often unexpected. So in this context one might define these “race conditions” as unexpected program behavior occurring because of the arbitrary interleaving of concurrent code.

This issue arises very naturally in an exercise based on the simple video game Pong. An implementation of this game comes with the Scratch installation, and the code discussed here is a modified version of that provided code. In this game, a ball bounces off the top and sides of the screen, and the player controls a horizontally moving paddle at the bottom of the screen on which the ball can also bounce. The player’s goal is to prevent the ball from bypassing the paddle and thus hitting the bottom of the screen.

Figure 2.4 shows Scratch code for the ball sprite, while Figure 2.5 shows code for the paddle sprite. Note that the three loops (two repeat until loops and one forever if loop) each depend on the “Boolean” variable stop to determine when they should stop looping. When a new game is started by the player clicking on the flag, the clear intent of the programmer is for the initialization code to run first. Note, however, that all four blocks of code are triggered by the flag, and thus they are all running concurrently.

In Scratch, the interleaving of these concurrent commands is consistent, but arbitrary from the programmer’s perspective. In the code in Figures 2.4 and 2.5, once one game has been completed (when the ball touches the red color at the bottom of the screen), the stop variable remains set to 1. When a new game is begun, if the loop conditions are checked before the set stop to 0 initialization code is executed, then the repeat until loops will immediately terminate and the game will not run properly.

For example, it is possible that the ordinary ball movement code block ceases while the paddle does respond to mouse movement. Thus, it is an interesting exercise for the students to devise arbitrary interleavings consistent with the evidence. One such interleaving for the example stated here is as follows:

1. Ordinary ball movement (first command)

2. If ball touches paddle, bounce (first command)

3. Initialization (first command)

4. Paddle script (first command)

The most important exercise, of course, is to devise program modifications to address this race condition and allow the code to execute correctly every time. There are many possibilities. For example, the initialization block of code could be extended, with wait 0.5 secs and set stop to 0 blocks added to the end. Alternatively, all blocks of code except the initialization block could have a wait 0.2 secs block added to the beginning. These modifications use a common trick of inserting a small wait in order to ensure an appropriate interleaving.

It is important to emphasize that this exercise depends on Scratch’s arbitrary interleaving of concurrent code. As such, seemingly inconsequential modifications to the code can alter this interleaving in a way that may change, or even eliminate, the negative effects of the race condition. While this might take the instructor by surprise and result in a perceived loss of an educational opportunity, it need not be so. Rather, the instructor could take “correct” code, in which the arbitrary interleaving does not lead to any negative effects, and introduce a seemingly inconsequential change. For example, in the initialization code, swapping the first two statements, and/or adding a very short wait at the start, could produce the negative effect of a race condition. These kinds of changes can lead to striking surprises and learning opportunities for students.

2.3.3 Blocking and Nonblocking Commands

Scratch also provides an excellent context in which to explore the use and behavior of blocking versus nonblocking commands. Table 2.1 provides these commands. It is important to remind students that every time they use one of these commands, they must make a conscious decision of whether they want blocking or nonblocking behavior.

For the most part, the commands behave as one would expect. The blocking say and think commands will block for the specified number of seconds, while the nonblocking versions cause the text to be said or thought indefinitely while the rest of the code executes. (The text disappears only when another say or think command is executed to replace it.) The blocking play sound command waits until the sound has finished before proceeding to the next command, while the nonblocking version moves on to the next command immediately. Finally, in the blocking broadcast, the sending sprite waits for the receiving sprite’s when I receive block of code to complete execution before continuing, while the nonblocking version continues immediately.

The broadcast commands are the primary mechanism for intersprite communication, and are an effective introduction to the PDC concept of interprocess communication. One interesting classroom exercise is to consider the code in Figure 2.6. Sprite 2 is waiting for the message “go.” Once the message has been received, sprite 2 enters a forever if loop. By way of explanation, consider how this code would look in pseudocode:

while True do

 if a > 5 then

 print “Boogety”

 end if

end while

So the a > 5 question is asked repeatedly, forever, once the “go” message is received the first time. Even though the answer will always be False, the question is continually asked.

When we examine the code for sprite 1, it is apparent that it will never say “All done!” The first broadcast go and wait will never unblock, because sprite 2 will never stop asking if a > 5. The reminder, “forever never ends,” is helpful, and yet it is easy to forget in certain contexts.

Of course, a simple modification to sprite 1’s code can have a large effect. If the original code and the modified code are not shown side by side, some students may not notice the difference between the original code in Figure 2.6, and the modified code in Figure 2.7. In this modified code, the nonblocking broadcast command is used. Thus, even though “forever never ends,” sprite 1 does not wait for sprite 2 to finish, and so sprite 1 does indeed say “All done!” here.

Another interesting modification is to change sprite 1’s code such that a is set to 6. While some students may be fooled initially, this is of no consequence for whether or not “All done!” is said. The only difference is that with a set to 6, sprite 2 would say “Boogety!” repeatedly, forever.

2.3.4 Shared and Private Variables

Scratch allows students to wrestle with the use of shared versus private variables as well. Shared variables are specified as available “for all sprites” at variable creation time, while private variables are “for this sprite only.”

One fun exercise in which both types of variables must be used effectively is in the creation of a “whack-a-mole” game. In the traditional carnival version of this game, a player uses a foam hammer to hit “moles” as they pop up from various holes and pop down those holes randomly and quickly. In this Scratch version, students add eight identical mole sprites arranged in two rows of four, with each assigned a key on the keyboard as shown in Figure 2.8.

The moles execute their code concurrently, each appearing and disappearing randomly and independently. Pressing a key while the corresponding mole is visible makes it immediately disappear and earns the player one point. Pressing a key while the corresponding mole is not visible results in a one-point penalty.

Scratch does not have a built-in mechanism for querying whether or not a sprite is visible. This means that each sprite must keep track of a Boolean variable indicating its visibility status. Since each mole’s visibility status is independent of the visibility status of the other moles, this status must be maintained in a private variable. In contrast, variables such as the score counter and parameters controlling game difficulty should be shared by all moles. So these variables must be created as “for all sprites.”

While the game difficulty value does not change within a single game, it is worthwhile pointing out to students that the shared score counter variable demonstrates a form of interprocess communication. Each sprite has access to this variable and can inform the other sprites that another “hit” has been registered by incrementing the variable. To push this interprocess communication even further, one could imagine an adaptive game in which sprites inform each other of player success via a score variable increase, which leads to increases in the shared difficulty parameter.

As in the blocking/nonblocking issue, it is important to instill in the students the fact that every time they create a new variable, they need to make an explicit decision about whether the variable should be shared or private. In short, if every sprite needs its own copy of some information, and that information need not be accessed by other sprites, then the variable should be private. Similarly, a shared variable can be used to enable all sprites to read, and perhaps write, some aspect of the current state.