Parameters to a procedure (custom block) in Scratch are local and preserved over recursive calls to that procedure, but variables used within a procedure are not. (In programming language terms they are statics or owns)

You can make a variable behave as if it were a local variable by pushing any previous contents onto an explicit stack at the entry to the procedure, and restoring them on exit.

Here's an example: http://scratch.mit.edu/projects/28493818/

Although conceptually it's cleaner to push the contents before and after the point of call when recursing, doing so makes for messy and cluttered code, whereas pushing only at the entry and exit sequences may push one uninitialised copy on the first call, but it makes for neater and more maintainable source code.

This technique may not be needed a lot in most Scratch code, but it will come in useful when translating code from regular languages like C into Scratch.

Graham

It's worth noting that this breaks if you have custom blocks which run over more than one frame:

when gf clicked
custom
set [a v] to (return)

when gf clicked
custom
set [b v] to (return)

define custom
add [thing] to [local v]
repeat (10)
replace item (last v) of [local v] with ((1) + (item (last v) of [local v]))
end
set [return v] to (item (last v) of [local v])
delete (last v) of [local v]

This will give a = 19, b = 1 (or the opposite, depending on thread order) instead of the expected result a = b = 10. Enabling run without screen refresh gives the expected result.

nXIII wrote:

It's worth noting that this breaks if you have custom blocks which run over more than one frame:

when gf clicked
custom
set [a v] to (return)

when gf clicked
custom
set [b v] to (return)

This will give a = 19, b = 1 (or the opposite, depending on thread order) instead of the expected result a = b = 10. Enabling run without screen refresh gives the expected result.

Good catch - my assumption was that this would be used in translating some C function and used in a similar way to how it would be used in C, ie almost always single threaded code. But you're exactly right, in Scratch the default paradigm is multiple threads and that needs to be taken into account, and made thread-safe.

I have used stacks for recursion multiple times and never encountered any issues with multi-threading (though this may have been influenced by me using run without screen refresh)

Where it gets really messy is when you want to have local lists in recursion

Wait - how is a thread that hasn't had any activity for 2 years at the top of the ATs?

chooper100 wrote:

I have used stacks for recursion multiple times and never encountered any issues with multi-threading (though this may have been influenced by me using run without screen refresh)

Where it gets really messy is when you want to have local lists in recursion

You could use a pointer to an element in a “heap” or “RAM” list that is shared by all scripts.

chooper100 wrote:

Wait - how is a thread that hasn't had any activity for 2 years at the top of the ATs?

You necroposted!!!! Jk, someone else necroposted, and the Scratch Team must have deleted the post without closing the topic.

Chibi-Matoran wrote:

You necroposted!!!! -snip-

Nuuuu! lol

There was a bunch of spam caused by one initial spam posting and a bunch of followups which I asked them ST to delete but not to close the thread because I'm still interested in discussing the topic. Please no more meta-comments, just on topic.

To that end: the trick of pushing all registers on entry to a procedure and popping them on exit is stolen from compilers - I suspect there are other compiler techniques that could be mirrored in Scratch terms to support not only recursion but multithreading etc. The business of lists/heaps etc for example ought to fall out in the wash if you use an extensible list as a stack frame… instead of referring to “item x of list” you refer to “item base+x of list” where base is the end of the list at the point when the procedure was entered.

The only problem with these solutions is that you effectively end up coding in a stack-based language paradigm, eg with parameters and results on a stack, so that all your blocks end up being parameterless. This is somewhat alien to Scratch's programming style, whereas my initial suggestion was intended to make it easier to work alongside Scratch's normal idiom, but just adding recursion when it was easy to do so.

Whenever there are parallel threads, you can't use a shared stack. You either need to reserve an amount of stack space (eg adding a fixed offset to ‘base’ as above) or have multiple stacks for different parts of your program.

If you don't need to assign to the variables, another way is to make a helper custom block:

define foo (bar)
foo (bar) with baz: (123)

define foo (bar) with baz: (baz)
...

Jonathan50 wrote:

If you don't need to assign to the variables, another way is to make a helper custom block:

define foo (bar)
foo (bar) with baz: (123)

define foo (bar) with baz: (baz)
...

This *ought* to be the way that recursion in quicksort is handled - when you have partitioned and need to call twice recursively - once from lower..partition and once from partition+1..upper, *every* version of quicksort I've seen on scratch fails to save the value of partition around the first recursive call. However it turns out that by accident, the value of partition turns out to be correct because all the recursions and sub-recursions are in left to right order and the rightmost value of the last call happens to be in the right place anyway. And explicitly saving that value on a stack and restoring it turns out to be more expensive than just executing the wrong code and getting the right answer! However if you have a helper procedure whose only purpose is to call quicksort twice, and you pass it all three values (lower, partition, upper) then it works correctly without a significant overhead…