×

Sign In

Sign in with your username and password to access your account.
×

Turning Scratch into a CPU emulator

Yes, I’m fully aware that I’m entering cursed lands. But still, I wanted to share this experience with the world, that is the result of a grumpy rant on garbage collected languages.

How did we even end up here? 🐈

The Scratch programming language is designed for beginners of young age that want to get into coding. It is based on a drag and drop system of functional blocks that control the program flow, interact with the screen and input devices, or do mathematical expressions. When one of my high school teachers talked to me about his idea to maybe use it as an introductory device for new students at my school, I mostly belittled Scratch as I thought it was for children.

A few days ago I went on a little rant as I had to vent some negative feelings about Java. Don’t get me wrong I like Java, but at this very moment, I was very annoyed with it. I tried to run a certain Minecraft modpack which kept crashing as it ran out of memory while it worked completely fine on my friends' machines. At some point, I stated that I could probably implement my Uni assignment equally as well with Scratch instead of Java.

Well, as it wasn’t that late yet, I actually gave it a go and found out some interesting things about Scratch and how to deal with it. Although it is kind of odd in some places and the UI can be cumbersome in a hand full of situations, I found the experience somehow enjoyable. I can definitely say now that my view was false and unfounded, as I had never tried it back then. For absolute beginners Scratch seems like a great way to get started with procedural thinking, breaking down problems, and very basic data structures like lists/arrays.

Recreating my assignment

As the last topic covered by the lecture was recursion calls of methods, the homework had multiple tasks just about that. The very last task required us to draw a pattern made up of alternatingly colored crosses that get smaller and smaller. Implementing the algorithm was luckily quite straight forward.


private static void drawPatternRecursive(int x, int y, int l, boolean c) {
    // Recur if length is greater than 16 pixels
    if( l > 16 ) {
        final int fl= l/4;
        drawPatternRecursive( x- fl, y+ fl, l/2, !c );
        drawPatternRecursive( x- fl, y- fl, l/2, !c );
        drawPatternRecursive( x+ fl, y+ fl, l/2, !c );
        drawPatternRecursive( x+ fl, y- fl, l/2, !c );
    }

    // Set draw color
    StdDraw.setPenColor( c ? StdDraw.ORANGE : StdDraw.BLUE );

    // Draw cross
    final double w= l*0.05;
    StdDraw.filledRectangle( x, y, w/2, l/2 );
    StdDraw.filledRectangle( x, y, l/2, w/2 );
}

Writing or rather building the same program with Scratch turned out to have its own kind of obstacles to overcome. Firstly figuring out how to draw stuff took me more google searches than I would like to admit. But after finding out that the “pencil” feature is an extension and can only be used by moving sprites it was pretty simple to use. Secondly, I was surprised that defined code blocks cannot have local variables.

If you wonder why this surprised me, you have to take a look at the functionality that defined blocks provide. Their main purpose is to reduce code duplication by naming a group of statement blocks that can be stepped into from another code section. At first, I expected that they would mostly act like a goto at the end of another block. However, I could not have been more wrong. In reality, they behave like a C-style function that can be called and returned from back to the caller. Even recursion works, suggesting that Scratch has a stack-like structure in the background to keep track of the call sights. Defined blocks can even have call parameters, allowing for inputs.

These parameters are read-only, so if you need to store some temporary value in your block global variables are your only choice. Furthermore, blocks cannot return any values to their caller due to the lack of a return statement, which also makes short-circuiting out of block impossible.

One way to work around these limitations is to not use any temporary values and copy-paste expressions, whenever a result is needed twice. But keeping track of states like counters in a global variable is still very limiting especially regarding recursion.

The solution I came up with is to make my own stack and only use a handful of global variables shared by everyone like registers on a CPU. When a block is entered, which wants to use one or more of these registers for its own purposes it first needs to save them on the stack. Before returning to its caller the block then needs to restore the registers old values from the stack. This makes Scratch an arguably weird CPU emulator like construct. However, if you ever wrote any assembler code you would be surprised how natural it feels.

I decided to use four registers called A to D which are like the stack pointer just global variables. The stack itself is a Scratch list. Interacting with the stack is done via the blocks called push and pop .

I think the drawing process looked interesting, so I recorded it.

Call convention

One thing to consider when dealing with the stack is to specify who is responsible for saving registers. Either the caller has to free up the registers or the callee has to save them. I went with the latter approach to prevent pushing and popping unnecessarily. Parameters are usually handed over the way Scratch intended it. Only in the case of variable size arguments or array, the stack should be used. Return values are supposed to be returned in the registers, as long as not more than two are needed.

Download

You can download the Scratch file here if you want to run the program yourself (you have to change the file extension to .sb3 ). In case you feel enticed to write your own thing on the CatPU (patent pending) please @ me on Twitter. :^)

last edited 9 days ago