If a stack triggered by a "when I receive" block contains a "wait" block and is re-triggered before it can complete, the first instance is never completed. This seems to me a reentrancy bug. Has anyone noticed the same problem?
In this example, there are no problems, as long as Delay < 1. As soon as Delay > 1, Counter is increased continuously (and never decreased) and the Pop sounds stops playing.
[blocks]
<when green flag clicked>
<set{ Counter }to( 0
<forever>
<broadcast[ Clock
<wait( 1 )secs>
<when I receive[ Clock
<change{ Counter }by( 1
<wait( Delay )secs>
<change{ Counter }by( -1
<play sound[ pop
<stop script>
[/blocks]
Offline
Hi Alebaba, you're right, there cannot be two instances of the same thread.
to prevent this and make sure the thread isn't called while it is still running you should use the [blocks]<broadcast[ clock ]and wait c>[/blocks] block.
You might also check your code, if you really need the clock thread at all, since it is timed anyway. Also, you don't need the [blocks]<stop script>[/block], because you're in no loop there.
Hope that helps
Offline
Jens, thanks for your comments.
Strictly speaking, you are right. I could do without broadcasting the Clock signal. However, this is the simplest way to approximate a time reference that gives a cadence to my simulation, regardless of how fast the other threads execute.
I think it's unwise on the Scratch implementation side to allow a new instance of the thread to override the one that's already running. It seems to me that there is no point in trying to start a new thread on time at all costs, if one can never be sure if it will be completed. This seriously limits the use of the broadcast command.
You are also correct on the "stop script" command. It's a just a cosmetic thing, so that there is no snap-on connector at the end of the thread. Completely unnecessary in this case, I agree.
Alex
Offline
alebada wrote:
It seems to me that there is no point in trying to start a new thread on time at all costs, if one can never be sure if it will be completed
You're right, I agree.
It can be quite hard to keep track on all your threads. I sometimes implement a kind of workaround to this by using a variable ("busy") to flag a possibly long thread as unfinished, and checking that before broadcasting the event associated with it....
Offline
I think the Scratch developers had to make a choice about the meaning of "when I receive" and "when key clicked" and the other "when" hats. The choice was whether every event started the thread or whether the thread was only started it if wasn't already running. Both choices lead to program bugs in some situations, but I think it may be easier to explain the "always start" semantics to a new programmer.
Scratch developers, what was the real reasoning behind this choice?
Offline
The great thing about computer is that they reliably do exactly as instructed. The frustrating thing is that sometimes, that isn't what you want.
To Kevin's point, avoiding "re-entrance" would require setting some option or adding another command ( a "When I Receive (message) but NOT if I'm Already Doing This" block) complicating Scratch.
Implementing Jens' suggestion of a local "busy" variable is pretty easy. One way:
When I Receive (signal)
If (busy flag) = 1
Stop Script
Set (busy flag) = 1
Do a Bunch of Stuff
Set (busy flag) = 0
Offline
Edwin, it's really not quite that simple as I had to find out. Actually, I have to check the 'busy' flas *before* trying to fork off to a possibly active thread.
Something like this:
(first thread)
if busy = 0
broadcast event
(end of thread)
(second thread)
when I receive event
set busy to 1
do something complex
set busy to 0
(end of thread)
Once my project tries to reenter the second thread while it is running, the projects gets stuck.
Offline
Because the broadcast is "lost"? Or is this a bug?
I don't think I've seen this (I'm only on my 2nd Scratch project), but I'm bug-hunting in my current project and will have to investigate this.
Perhaps adding "<Wait Until (busy = 0)>" in the receiving block would be possible?
Last edited by EdnaC (2007-09-13 11:59:08)
Offline
I believe Jens's solution with two threads is about a simple as it gets. You can't send the message that starts the second thread while the second thread is busy.
There are parallel programming languages that provide cleaner ways to enforce non-reentrant code, mutual exclusion, and atomic actions, but I have not yet seen one simple enough to be part of scratch.
Offline
There is a possibly perfect reason for Scratch to force an uncompleted thread to start anew: It's the only way (I'm aware of) to synchronize parallel threads. In fact, I use this feature often in harmonical musical projects that play several notes / melodies at once. sometimes If I waited for every note in several threads to fully complete, the different threads would shift depending on their complexity and the music would eventually get out of beat. Forcing the threads to start new in regular intervals keeps such musical projects synchronized.
In such a context, this is actually a critical feature of Scratch (music would not be possible without synchronization). Lots of projects use broadcasts to synchronize threads, a good example for such a 'public interface' is Kevin's 'synchronize to beat' event in his one sprite composer: http://scratch.mit.edu/projects/kevin_karplus/3185
Offline
Jens, Kevin, Edna:
Thanks for posting your comments to my question.
It seems to me that there is a third alternative to the two that Kevin suggests: "The choice was whether every event started the thread [overriding the context of the one that's already running --Alex] or whether the thread was only started it if wasn't already running."
IMHO, the correct behavior should be to start a new thread in a new context (i.e. with different stack and local variable space) without overriding the one that's already running. While this solution would possibly lead to the problem of scheduling many threads allocating many resources, i.e. a memory management system prone to memory leaks, I think this should be left to the programmer's choice.
Regarding Jens' latest comment (about music synchronization), the current implementation might be the sensible thing to do in case of musical programs as it exhibits graceful degradation, but it may not be the best choice in other cases. In fact, it may be useless even for musical synchronization, if you ever have to use in the program stack a wait() command to implement, say, a musical pause.
I would like to hear from the Scratch team, if this is really the intended behavior or an implementation bug.
--Alex
Offline
Jens wrote:
Edwin, it's really not quite that simple as I had to find out. Actually, I have to check the 'busy' flas *before* trying to fork off to a possibly active thread.
Something like this:
(first thread)
if busy = 0
broadcast event
(end of thread)
(second thread)
when I receive event
set busy to 1
do something complex
set busy to 0
(end of thread)
Once my project tries to reenter the second thread while it is running, the projects gets stuck.
In fact, this code has a problem as well, as it contains a race.
Suppose that the first thread executes and triggers the second thread. Before the second thread can set the busy variable to 1, the first thread executes again and triggers the second thread another time... Now the second instance of the second thread effectively kills the first instance.
You may never see any problem in one implementation of the Scratch interpreter, but the next implementation might cause the same code that always worked to start failing. If there will ever be multiprocessor implementations of Scratch, this code could fail quite often!
--Alex
Offline
Scratch is full of race conditions, as there are no atomic test-and-set operations. A truly parallel language would have more powerful (but also more complicated to explain) synchronization operators.
Forking a new thread at each broadcast, as alebeda suggests, is another possible semantics for when-I-receive, but it would add considerable extra complexity to both the interpreter (which currently has no dynamic allocation of scratch sprites or scripts) and to the user's concept of what is happening. It could be handy in a number of situations (like playing a musical round by broadcasting a start from the middle of the script), but debugging is already pretty complicated for a lot of scratch programmers, and adding re-entrant threads would not simplify debugging!
Offline
Kevin, I agree with your assessment. I think that the bottom line is that, when a Scratch programmer starts worrying about race condition and thread reentrancy, he/she has automatically graduated to a real programming language. In a sense, it's a nice problem to have, because Scratch would have achieved its purpose of teaching beginners how to program.
--Alex
Offline
I was surprised how quickly I encountered this issue. It is easy to reproduce with a simple example: http://scratch.mit.edu/projects/Bargonaut/51711
I hit the bug while trying to make a Shark eat a fish, but only eat it once while the fish was dying an elaborate death. (Isn't Scratch great?) Nevertheless, I found that sending an additional message from the first "receive" block to continue was a good solution.
<when I receive[ MSG ]>
<if <( OK <=> 0 )> >
<set{ OK }to( 1 )>
<broadcast[ MORE ]>
<when I receive[ MORE ]>
fancy animation, etc.
<set{ OK }to( 0 )>
In other words, don't do anything that takes a long time in a "receive" block. If you need to do something fancy, just send a "private" message to your sprite and complete the action in that receive block. Just make sure your initial block checks some state variable to avoid re-entering the second receive block.
That said, it would be nice to have a choice whether the "receive" is a new instance of the message. Or, having a clean-up block (destructor) would work, but that would be too much to ask in Scratch.
-Brad
Offline
Running into restart problems with scripts happens fairly soon, as Bargonaut observed.
The standard solutions are what he described:
use a secondary message to actually do the action.
use a variable to see whether the main message is allowd to send the secondary message or not.
Offline
I hit this same problem when trying to implement towers of hanoi in Scratch.
The typical implementation is a 5 line recusive algorithm:
hanoi(n,A,B,C)
if (n>=1) {
hanoi(n-1, A, C, B);
doMove(A, B);
hanoi(n-1, C, B, A);
}
The first problem I hit was that I would have to maintain my own call stack with lists for every argument. It would be nice if scratch allowed parameterized procedures (i.e. custom blocks). But even when I had done this, I hit the problem that my recursive calls never completed (the "backFromBroad" sound never plays). I do not want to make the effort to rewrite with tail recursion (if that is even possible) and convert to iteration, since I believe the recursive solution is more elegant. I do not see how the workaround (described above) of blocking the call until the message block completes is going to help here - because it will just lead to deadlock. Any other suggestions? Here is my recursive method (with simulated callstack using lists).
http://scratch.mit.edu/projects/beckerb4/260239
Last edited by beckerb4 (2008-09-08 19:52:02)
Offline