December 15, 2023 ; Catergory: projects
If you’d like to see my final result, it can be found here!
Like many computer scientists my age, I started my programming journey in Scratch trying to make something close to the videogames I loved playing. Unfortunately, I didn’t quite make anything on the level of Pokémon or Mario (though I’d argue the shitty Pokémon platformer I made that barely functions was almost as good), but it did spark a lifelong interest in coding. In that light, Scratch succeeded in its mission statement - to get kids interested in and thinking about programming. After having used Scratch obsessively from around the ages of 9-12, I ended up graduating into ‘proper’ languages, such as Python, leaving Scratch behind.
And behind me is where Scratch stayed, until recently. I was in a lecture, and the lecturer asked the audience what imperative programming languages could be used to teach the course in. As a joke, someone mentioned using Scratch, and people laughed. The lecturer replied “Scratch might be a little limited as a language”, and then moved on. Everyone else moved on from the Scratch suggestion. I did not move on from the Scratch suggestion. The thought stuck with me, what if I did use Scratch in this course? And so I tried. The rest of this article will explain what happened. Not to spoil things, but my lecturer was right 😭💀.
Just as a caveat before we start, a lot of the content of this article is aimed at people with a passing familiarity of coding. If you’re a very experienced coder, feel free to skim to get a sense for the general challenges I faced. For everyone else, I hope you’ll learn something on the way!
To test what was possible in the Scratch engine, I decided to implement the Quicksort algorithm. As its namesake suggests, it is a very efficient list sorting algorithm. So much so that despite being developed in 1959 is still widely used today. Quicksort is a divide-and-conquer algorithm, meaning it solves the problem by dividing up the problem into smaller and smaller subproblems until they’re easy to deal with. Traditionally this is done using a recursive approach. First, I’ll explain what a recursive function is, then I’ll give an overview of how Quicksort works, just so we’re all up to speed.
At a basic level a recursive function is a function that calls itself within its definition, with a base case prevent it running infinitely. Intuitively it’s similar to a recursive function in maths, such as the definition of the Fibonacci numbers:
\[fibonacci(n) = \begin{cases} 1 &\text{if $n=0$ or $1$} \\ fibonacci(n-1) + fibonacci(n-2) &\text{ otherwise} \end{cases}\]We can also write a recursive definition of a factorial in the following way:
\[factorial(n) \begin{cases} 1 &\text{if $n=0$} \\ n \times factorial(n-1) &\text{ otherwise} \end{cases}\]In fact let’s create a recursive program in pseudocode for computing factorials:
Let’s consider what happens when we call factorial(5). Since 5 doesn’t equal 0, we ignore the base case and move to the recursive step. It says we should return 5 times the value of factorial(4), but we don’t know the value of factorial(4) yet! Therefore factorial(5) ‘pauses’ itself, so to speak, storing its information into memory to let factorial(4) compute so it can give its value back to factorial(5)1. The same thing happens to factorial(4) and so on and so on until we reach factorial(0). At this point we have 5 calls patiently waiting and they can finally see some relief as 0 does in fact equal 0 and simply returns a 1, and closes itself. factorial(1) receives this, and itself returns 1 and closes. We repeat this back up to factorial(5), wherein we finally return 120, which is indeed 5 factorial.
Why use recursion? Well, there are many reasons to, but in this specific instance it ends up working really well with divide and conquer strategies. By definition a divide and conquer algorithm breaks a problem down into subproblems, until they are easily solvable. The parallels to recursion are clear: when we want to ‘divide’ we call smaller versions of the problem, and when its small enough to handle we can invoke a base case. Structurally speaking then, a recursive algorithm gives us a great way to translate problems from a general approach to code. We’ll do just that in the next section!
The high level description of Quicksort is as follows:
Below is a visualisation of the process in action (sourced from Wikipedia):
As stated earlier, Quicksort’s divide-and-conquer nature makes it easy to adapt to a recursive problem. This time we won’t be returning specific values, but each call will modify the list by reordering around the pivot. In terms of passed in data we’ll pass in the left-most index and right-most index of the part of the list we are focusing on to define the specific subproblem we are tackling.
When the left-most index is equal to or larger than the right-most index we are in the base case, as in this case the sub-list is either a singleton or empty. There also exists a second base case. If the pivot ends up at the start of the list, then the left subcase does not exist. In our implementation, this results in a subroutine call with a negative index. We deal with this case the same as the last, just by doing nothing and returning.
In all other cases, we will call a function called partition that reorders the values within our specified range around the pivot (in this case, the rightmost value). After that we will make two recursive calls: one to the left half and another to the right half. Recounting from the section above, this means that the right half will not be called until the entire left half has been sorted (think about why this must be the case!), which explains the behaviour in the above gif.
In pseudocode we get the following (sourced from Wikipedia):
1 // Sorts a (portion of an) array, divides it into partitions, then sorts those 2 algorithm quicksort(A, lo, hi) is 3 // Ensure indices are in correct order 4 if lo >= hi || lo < 0 then 5 return 6 7 // Partition array and get the pivot index 8 p := partition(A, lo, hi) 9 10 // Sort the two partitions 11 quicksort(A, lo, p - 1) // Left side of pivot 12 quicksort(A, p + 1, hi) // Right side of pivot
The code for partition goes as follows (an exercise for the reader is to try and understand why code this achieves the desired result):
1 // Divides array into two partitions 2 algorithm partition(A, lo, hi) is 3 pivot := A[hi] // Choose the last element as the pivot 4 5 // Temporary pivot index 6 i := lo - 1 7 8 for j := lo to hi - 1 do 9 // If the current element is less than or equal to the pivot 10 if A[j] <= pivot then 11 // Move the temporary pivot index forward 12 i := i + 1 13 // Swap the current element with the element at the temporary pivot index 14 swap A[i] with A[j] 15 16 // Move the pivot element to the correct pivot position (between the smaller and larger elements) 17 i := i + 1 18 swap A[i] with A[hi] 19 return i // the pivot index
Now that we’ve gone through the specifics of how Quicksort works, we are finally ready to tackle implementing it in Scratch!
Now that we know what we’re dealing with, we can move onto the specifics of how I attempted to solve this problem in scratch.
Scratch has a lot of weird quirks that make it more difficult than expected to just straightforwardly implement the code shown above. In order they are the saving of variable/list contents between program instances, a lack of return, and a lack of local variables; the final of which causes serious issues in implementation!
Firstly, for whatever reason, variables and lists can keep their values between instances of a program. We therefore need to make sure we clear these out, lest we end up with data merging between instances, causing even more chaos.
Secondly, Scratch doesn’t have a return block. A return is used to exit from a subroutine and to potentially also return variables to the original place that called it. You’ll notice that returns are used twice in the Quicksort algorithm, once to exit out of the base case for Quicksort’s recursion and another to return the pivot’s location once partition has terminated. How are we meant to deal with this restriction?
Well in the former case, consider what the block of code that hosts the return is for. In a sense it’s guarding the rest of the program from accidentally recusing on the base case by exiting early, and importantly nothing more. Implicitly then, the code below it only runs if left is smaller than right. So we can rewrite the function to remove the return check, and place the rest of the code under the if left < right: conditional.
In the latter we can circumvent this issue using global variables. A global variable is a variable accessible by all code blocks all throughout the program. To ‘return’ the pivot from the partition subroutine, we can just create a variable called PIVOT_INDEX that is written to by partition and then used by the main loop as in the code example above.
Thirdly, scratch doesn’t have local variables for subroutines2! There technically are ‘local’ variables, but they are local to sprites, not code blocks. This may initially seem like a problem for partition, as it uses local variables in its calls, but we can replace them with global variables in this specific instance. This is because there isn’t a case where a specific instance of partition is interrupted, and hence would have its variables overwritten, by another instance of partition. Always, partition will run from start to end, and once it is finished will have no need to care for its local variables and can hence be discarded.
However the lack of local variables does cause an issue for our main Quicksort implementation. Specifically in regards to the value of the pivot that’s used to call further instances of the Quicksort algorithm. Previously, we ended up assigning this value to a global variable, which mirrors what we did for the local variables in partition, however this time doesn’t solve the issue. You may already have noticed why. The PIVOT_INDEX value is required for two further lines of code, the ones where we call new instances of Quicksort on the left and right sub lists. Since as stated above the code for the right-half waits patiently until the left half finishes, it needs PIVOT_INDEX to stay constant so it can use it when its ready. But PIVOT_INDEX doesn’t stay constant, it’s going to be changed by the left call (assuming we don’t call a base case). This is disastrous for us, as it means we no longer guarantee having the required information when we return to call any right side calls. How do we deal with this?
There are several ways you may want to remedy this issue. I want to focus on one: turning our recursive solution into a looping solution. It might not be obvious that this is possible, after all the recursive solution ‘branches out’, calling multiple instances per individual instance, whereas looping solutions run sequentially, completing a list of repetitive tasks. But one of the most important theorems in computability theory states that recursive functions are as powerful as looping functions, and vice-versa (that is to say, they can both be used to solve the same set of problems). Therefore there should exist a looping algorithm that does what we want.
To construct it, we are going to ‘unfold’ our recursive function. Each recursive call has a set of specific parameters associated with it, in this case the left and right index. That’s all that is needed to know what instance of a function to call. What we can do is save this information somewhere, to be accessed later when it is needed, bypassing the need to keep a recursive call open until its own calls resolve. It can just shelve the information for us and at that point its job is over. Lets call this memory storage the CALL STACK, as it saves call instances. It acts in accordance to the stack datatype, meaning the most recently added data is the first to leave. This behaviour is useful to us, as it allows us to mimic the behaviour of the recursive solution better (not needed in this case, but good practice in general). If we order it so the right side goes in first, then the left, then when we retrieve a call to process we will take the first left one, which will itself then put its own left call in front and so on. Just like the recursive solution we iterate down into the leftmost subproblem and move right from there.
Now that we have a CALL STACK, we can finally sketch out a looped solution. The pseudocode works as follows (I’ve not added the revisions needed for the Scratch solution in order to provide a general solution):
1 algorithm quicksort_loop(A, lo, high) is 2 CALL_STACK := empty 3 CALL_STACK push high // push adds data to the stack 4 CALL_STACK push lo 5 while CALL_STACK is not empty do 6 left = CALL_STACK pop // pop removes the most recent element and returns it 7 right = CALL_STACK pop 8 9 if left >= 0 && left < high then 10 p := partition(A, left, right) 11 12 CALL_STACK push right 13 CALL_STACK push (p + 1) 14 CALL_STACK push (p - 1) 15 CALL_STACK push (left)
I hope it’s clear how this solution mirrors the recursive one. Each loop executes a specific call by retrieving the data from the CALL STACK, and by the way that we have set up our stack, and how we push data to it, the loop will execute calls in the same order that the recursive solution will. Isn’t it really interesting that this is possible at all? Recall at the start we felt out the intuition behind Quicksort by understanding its relation to recursive problem solving - it felt like such a natural fit. However with just a few changes, we are able to remove its dependence from it by noticing the fundamental parallels between loops and recursive functions. Armed with this knowledge we can finally get to work implementing the Scratch solution!
I won’t go into the details of the specific implantation because, well, I sort of already have lol. All the scripting I did was putting everything we’ve discussed up until this point into practice. You can try out my code directly here (press the green flag):
And if you’d like to see the code, click here, and then click ‘See Inside’.
This article feels long enough to deserve a nice concluding paragraph, to really tie everything together. So then, what did I takeaway from this? Besides, of course, realising that Scratch was really not as good as I remember it being, and adapting to Python (I hated it at first!) was overall a good thing lol.
Well, forcing myself to program within the limitations of Scratch forced me to be creative about how I approached my implementation. In doing so, I’ve come to appreciate the links that tie two areas of coding together: loops and recursions, and gained an intution behind an important aspect of computability theory. Not bad Scratch, not bad. Anyway, I’ve taken up far too much of your time, I hope you enjoyed this coding escapade 🙏.