On matter of scoping and tail call optimization.

[ghost]

As seen by this project, scratch 3.0 uses dynamic scoping as opposed to static scoping: https://scratch.mit.edu/projects/259998618/ This is an issue as it is (1) different from scratch 2.0, which may lead to incompatibility, and in addition, it makes it much harder for tail call optimization to be implemented. Also, I would like to request that tail call optimization be implemented, as as scratch is meant to be a tool for starting programming, it should be able to facilitate use of many styles of programming.

[towerofnix]

In my view, dynamic scoping is neat - but less important than tail-call optimization, because TCO probably enables more types of programming than dynamic scoping (which can partially be worked around via variables or lists), and dynamic scoping hypothetically causes incompatibilities. (But I'd be surprised if there exists a project which relies on the value of a custom block's nonexistent input that shares the name with one of a custom block calling that one to be 0.)

Edit: BTW, tied forum topic: https://scratch.mit.edu/discuss/topic/320438/

[joker314]

Regarding dynamic scoping only:

---

I would've thought dynamic scoping was removed in #1640, where an extra return null; is added to engine/threads.js

Old behaviour

Traverse the call stack until we find a custom hat which has a parameter with the correct name (dynamic scoping)

New behaviour

Traverse the call stack until we find any custom hat (static scoping)

---

Procedures invoking broadcast scripts (invoking more broadcast scripts...) allows the broadcast scripts to access the parameters of the procedure which invoked it. This is dynamic scoping. I don't know 2.0 behaviour regarding this.

---

The PR was merged 13 days ago. Maybe it hasn't been merged in by gui, hasn't reached production, and perhaps llk.github.io/scratch-vm isn't updated? Or that PR didn't solve the issue for some reason? Or I'm completely wrong?

[joker314]

Problem has been idenitified by imfh and towerofnix on the forums.

When a custom block has no parameters, its frame's params object is null.

Back when Scratch 3.0 had dynamic scoping, we would--for efficiency--continue traversing the stack frames if we got null, because null means the custom procedure has no arguments, and hence can't contain an argument we're referencing. (thanks to imfh for discovering that non-null params work okay; to towerofnix for identifying the relevant code to remove) https://github.com/LLK/scratch-vm/blob/3bd079781002d339c77850a74d44b0f1ee785081/src/engine/thread.js#L346-L348 However, now that we use static scoping, we want the opposite behaviour: if we didn't find what we were looking for, we should stop looking -- not peek into the caller scope. This is what scratch-flash does, it checks if .args is null and, if so, returns 0 immediately.

Let's do that (but return null instead). Here's what a fix might look like

diff --git a/src/engine/thread.js b/src/engine/thread.js
index 47777a97..c7998e72 100644
--- a/src/engine/thread.js
+++ b/src/engine/thread.js
@@ -344,7 +344,7 @@ class Thread {
         for (let i = this.stackFrames.length - 1; i >= 0; i--) {
             const frame = this.stackFrames[i];
             if (frame.params === null) {
-                continue;
+                return null;
             }
             if (frame.params.hasOwnProperty(paramName)) {
                 return frame.params[paramName];

Or, alternatively, one might want to change frame.params.hasOwnProperty to frame.params && frame.params.hasOwnProperty and remove the null check altogether.

Another option might be to always add a params object to custom procedures, but when there are no key-value pairs, use {} rather than null.

[towerofnix]

BTW, if we always return null after the topmost stack frame, shouldn't we get rid of the for loop and just do const frame = this.stackFrames[this.stackFrames.length - 1]?

[joker314]

Note: towerofnix's idea is what scratch-flash does, but scratch-flash doesn't even touch the stack frame. If you don't need to look through the call chain, you can just use the active thread's parameters rather than the last stack frame's parameters. (These two are the same set of parameters if you're in a custom procedure)

[joker314]

Regarding tail-call optimisation.

Normally, when we do tail-call optimisation in other programming languages, we say that if a recursive call is made at the end of a function, these two things are the same:

• returning to after the call was made and running the non-existent rest of the script ("do nothing")
• not returning at all ("do nothing")

And, so, to be memory efficient, we can do the second option: instead of pushing a stack frame, we replace the current stack frame.

In Scratch, it's not so simple. Consider this script:

Let's say the user -- while the script is running -- decides to add a feature: after looping, count down. She does this 6 seconds in. The first script has now called the second script, and the first stack frame has been destroyed.

The output of this will be

3
2
1

But the user might expect

3
2
1
0

So if we add this optimisation, we will have to sacrifice the ability to add blocks underneath former-tail calls and have that modify old stack frames (unless someone can see a clever way around this?).

I think this is a valid trade-off maybe. What are your thoughts? EDIT: tested and I'm right that dropping stack frames would prevent changing old stack frames while the script is running

[thisandagain]

/cc @kchadha @mzgoddard @ktbee

[mzgoddard]

@joker314 I opened a PR for a small change related to your Nov 6th comment. Though instead of returning null when we don't see params on the stack frame, the stack frame will have params initialized for each "procedure" stack frames. Stack frames are used for a few things other than procedures so we want to skip over stack frames that still have params set to null.