Recursive custom blocks don't automatically yield

[towerofnix]

Super simple demo project: Recursive diamond animation!

Up to five "stack layers" deep, Scratch considers the possibility of a recursive procedure call, — that is, a custom block that's been behaviorally nested inside of its own definition, directly or indirectly! — and if so, it performs a yield, which may for example wait for a screen refresh.

The sneaky thing is in the definition of "stack layer". In Scratch, a stack layer is any level of evaluation nesting. It's sort of like the JavaScript call stack, but because everything in Scratch is a block, even basic control structures push a new stack layer.

Imagine something like this:

*myCoolScript() {
  this.callStack.push({why: 'myCoolScript'});
  if ('foo' !== 'bar') {
    this.callStack.push({why: 'if'});
    yield* this.sayAndWait('That makes sense!', 2);
    yield* this.doSomethingElse();
    this.callStack.pop();
  } else {
    this.callStack.push({why: 'if-else'});
    yield* this.thinkAndWait('Oh dear, oh dear', 3);
    while (this.fruits.length > 0) {
      this.callStack.push({why: 'while'});
      yield* this.eatFruit(this.fruits[Math.floor(Math.random() * this.fruits.length)]);
      this.callStack.pop();
    }
    this.callStack.pop();
  }
  this.callStack.pop();
}

*doSomethingElse() {
  this.callStack.push({why: 'doSomethingElse'});
  yield* this.myCoolScript();
  this.callStack.pop();
}

*eatFruit(fruit) {
  this.callStack.push({why: 'eatFruit'});
  if (Math.random() > 0.25) {
    this.callStack.push({why: 'if'});
    if (Math.random() > 0.25 /* no really */) {
      this.callStack.push({why: 'if'});
      yield* this.myCoolScript();
      this.callStack.pop();
    }
    this.callStack.pop();
  }
  this.callStack.pop();
}

Now this is terrible to read, but don't let that scare you away just yet! It's just to explain what Scratch is seeing. We're not Scratch, so we can make a slightly nicer abstraction out of this, but first we have to understand what Scratch is doing.

Let's imagine we follow the path into this.doSomethingElse() because 'foo' does in fact !== 'bar'. The actual execution order, which the JavaScript or Scratch runtime would take, looks like this:

1. this.callStack.push({why: 'myCoolScript'}); » Stack: [myCoolScript]
2. this.callStack.push({why: 'if'}); » Stack: [myCoolScript, if]
3. yield* this.sayAndWait('That makes sense!', 2); » output
4. yield* this.doSomethingElse(); » enter custom block!
5. this.callStack.push({why: 'doSomethingElse'}); » Stack: [myCoolScript, if, doSomethingElse]
6. yield* this.myCoolScript(); » enter custom block!
7. this.callStack.push({why: 'myCoolScript'}); » Stack: [myCoolScript, if, doSomethingElse, myCoolScript]
8. ...and on and on, infinitely, since this will just recurse forever.

So, right before Scratch begins executing the contents of any custom block (steps 4 and 6 above), it checks out the top five layers of the stack list. If any of those layers the custom block which it's in the process of starting, Scratch inserts a yield (possibly waiting for a screen refresh, etc).

At step 4, it's entering doSomethingElse. The stack is [myCoolScript, if]. The top five layers of that stack are also just [myCoolScript, if]. That doesn't include doSomethingElse, so Scratch doesn't insert a yield here. (It just begins executing the script's contents immediately.)

At step 6, it's entering myCoolScript. The stack is [myCoolScript, if, doSomethingElse]. The top five layers of that stack are also just [myCoolScript, if, doSomethingElse], and of course, that includes myCoolScript... so it inserts a yield, here.

OK, let's say the sky is falling!! Now 'foo' === 'bar'! What happens this time!?

1. this.callStack.push({why: 'myCoolScript'}); » Stack: [myCoolScript]
2. this.callStack.push({why: 'if-else'}); » Stack: [myCoolScript, if-else]
3. yield* this.thinkAndWait('Oh dear, oh dear', 3); » output
4. this.callStack.push({why: 'while'}); » Stack: [myCoolScript, if-else, while] (assuming we have any fruit, of course ✨)
5. yield* this.eatFruit(this.fruits[...]); » enter custom block!
6. this.callStack.push({why: 'eatFruit'}); » Stack: [myCoolScript, if-else, while, eatFruit]
7. this.callStack.push({why: 'if'}); » Stack: [myCoolScript, if-else, while, eatFruit, if] (assuming we're lucky)
8. this.callStack.push({why: 'if'}); » Stack: [myCoolScript, if-else, while, eatFruit, if, if] (assuming we're lucky again)
9. yield* this.myCoolScript(); » enter custom block!
10. this.callStack.push({why: 'myCoolScript'}); » Stack: [myCoolScript, if-else, while, eatFruit, if, if, myCoolScript]
11. ...and on and on, infinitely, since this will just recurse forever. Or until we're out of fruit!

The same recursion rule applies, of course, during steps 5 and 9 here.

Step 5 is just like before - no eatFruit on the stack, so no yield.

But step 9 is more interesting. The stack is [myCoolScript, if-else, while, eatFruit, if, if]. The top five layers of this, though, are only [if-else, while, eatFruit, if, if]! Even though we're recursing into myCoolScript, which is on the stack, it's too far away from the top, and Scratch never sees it. So... it doesn't insert a yield here!

See how that only happens because of how far we were nested inside ifs and if-elses and other custom blocks? Those simple control strucures really made a difference—one that could have a real impact, depending how badly a project turns out to depend on Scratch's behavior.

---

OK, we'll reply to this with a couple syntactical options we've considered, but here's just the summary of Scratch's behavior, to start!

[towerofnix]

Okay, so two bits of important implementation context:

1. Leopard, like Scratch, only ever evaluates one thread (trigger) at a time. See Project.step. Leopard always knows which thread is running, and as a result, can internally access this thread within methods on SpriteBase if we manually provide the "current trigger" on a this._currentTrigger property, or similar. This is crucial for being able to do anything related to a "stack", because stacks are unique to each thread/trigger, and actual behavior/evaluation is all handled inside the sprite's code. (There can be multiple threads alive at once, per target, of course.)
2. Code can throw errors. We can't willy-nilly push to a stack unless we are absolutely sure we're going to pop from it (or else discard the stack completely). If a function four layers deep throws an error, and a function one layer deep is what catches that error (e.g. with a try..catch), then we need to make sure that the stack trace is properly restored, and all three sub-layers are popped, before control returns to the error-handling function. JavaScript fortunately provides try..finally to make this "easy"... but it doesn't make for very nice syntax, as you'll see.

[towerofnix]

The first "totally effective approach" was as bog terrible as it could be. Here's the short example we wrote.

try {
  this.callStack.push(null);
  while (${condition}) {
    ${substack}
    ${warp ? "" : "yield;"}
  }
} finally {
  this.callStack.pop();
}

The big example code, in this style.

*myCoolScript() {
  try {
    this.callStack.push(null);
    if ('foo' !== 'bar') {
      yield* this.sayAndWait('That makes sense!', 2);
      if (this.callStack.recursive(this.doSomethingElse)) {
        yield;
      }
      try {
        this.callStack.push(this.doSomethingElse);
        yield* this.doSomethingElse();
      } finally {
        this.callStack.pop();
      }
    } else {
      yield* this.thinkAndWait('Oh dear, oh dear', 3);
      try {
        this.callStack.push(null);
        while (this.fruits.length > 0) {
          if (this.callStack.recursive(this.eatFruit)) {
            yield;
          }
          try {
            this.callStack.push(this.eatFruit);
            yield* this.eatFruit(this.fruits[Math.floor(Math.random() * this.fruits.length)]);
          } finally {
            this.callStack.pop();
          }
        }
      } finally {
        this.callStack.pop();
      }
    }
  } finally {
    this.callStack.pop();
  }
}

*doSomethingElse() {
  if (this.callStack.recursive(this.myCoolScript)) {
    yield;
  }
  try {
    this.callStack.push(this.myCoolScript);
    yield* this.myCoolScript();
  } finally {
    this.callStack.pop();
  }
}

*eatFruit(fruit) {
  try {
    this.callStack.push(null);
    if (Math.random() > 0.25) {
      try {
        this.callStack.push(null);
        if (Math.random() > 0.25 /* no really */) {
          if (this.callStack.recursive(this.myCoolScript)) {
            yield;
          }
          try {
            this.callStack.push(this.myCoolScript);
            yield* this.myCoolScript();
          } finally {
            this.callStack.pop();
          }
        }
      } finally {
        this.callStack.pop();
      }
    }
  } finally {
    this.callStack.pop();
  }
}

This is the worst thing ever, but there are some useful things to note.

• We don't need to push specific details onto the call stack in normal control structures, the only meaningful values are the ones which might match the custom block we're entering. So we just use null as padding.
• The try..finally must not contain the call to this.callStack.recursive() and subsequent yield, 'coz if an error is thrown during that yield, we'd end up popping something that hadn't been pushed yet. Yikes! (Another approach would be to make this.callStack.recursive() check the top 6 items except for the very top item, ala .slice(-6, -1).)

[towerofnix]

This approach is actually the first one we came up with at all. It's pretty simple, but it doesn't quite work, because we didn't realize normal control structures count as stack layers at this point.

yield* this.enter(this.${procName}, ${procArgs});

// wherein
*enter(fn, ...args) {
  if (this.callStack.recursive(fn)) {
    yield;
  }

  this.callStack.push(fn);
  try {
    yield* fn(...args);
  } finally {
    this.callStack.pop();
  }
}

Full example, which doesn't account for normal control structures

*myCoolScript() {
  if ('foo' !== 'bar') {
    yield* this.sayAndWait('That makes sense!', 2);
    yield* this.enter(this.doSomethingElse);
  } else {
    yield* this.thinkAndWait('Oh dear, oh dear', 3);
    while (this.fruits.length > 0) {
      yield* this.enter(this.eatFruit, this.fruits[Math.floor(Math.random() * this.fruits.length)]);
    }
  }
}

*doSomethingElse() {
  yield* this.enter(this.myCoolScript);
}

*eatFruit(fruit) {
  if (Math.random() > 0.25) {
    if (Math.random() > 0.25 /* no really */) {
      yield* this.enter(this.myCoolScript);
    }
  }
}

That isn't so bad, is it? Too bad it won't get much better from here...

• The basic idea is to offload stack behavior into a this.enter function, sort of modelling this.warp. It works pretty well, but it's still an awkward syntax.
• Obviously this doesn't handle normal control structures, which is its downfall...

[towerofnix]

This approach uses decorators! Wow! Well, we can't use decorators yet, and we probably won't be able to until 2029, or unless the Leopard editor starts embedding TypeScript or Babel. (Sure that's possible, but let's just call this imaginary for now.)

class Sprite1 extends Sprite {
  @recursionYields
  *myCustomScript() {
    ...;
    yield* this.myCustomScript();
  }
}

Full example. Would you believe this still doesn't handle normal control structures?

@recursionYields
*myCoolScript() {
  if ('foo' !== 'bar') {
    yield* this.sayAndWait('That makes sense!', 2);
    yield* this.doSomethingElse();
  } else {
    yield* this.thinkAndWait('Oh dear, oh dear', 3);
    while (this.fruits.length > 0) {
      yield* this.eatFruit(this.fruits[Math.floor(Math.random() * this.fruits.length)]);
    }
  }
}

@recursionYields
*doSomethingElse() {
  yield* this.myCoolScript();
}

@recursionYields
*eatFruit(fruit) {
  if (Math.random() > 0.25) {
    if (Math.random() > 0.25 /* no really */) {
      yield* this.myCoolScript();
    }
  }
}

This is way too sexy, and we'd love it if it dealt with normal control structures. In fact, if we don't care about being overeager with automatic recursive yields (and had Babel access LOL), then this is a totally workable approach!

But it doesn't deal with control structures, so it just won't work for perfect compatibility. Boo hoo.

[towerofnix]

This is exactly the same approach as above, but with setup in the constructor instead. Boring, but technically perfectly fine.

class Sprite1 extends Sprite {
  constructor(...) {
    ...

    this.myCustomScript = this.yieldWhenRecursive(this.myCustomScript);
    // or a syntax sugar form
    this.yieldWhenRecursive('myCustomScript');
    // or more likely, but begrudgingly
    this.prepareCustomScript('myCustomScript');
  }
}

Full example, still no normal control structure handling.

constructor(...) {
  ...

  // option #1
  this.myCoolScript = this.yieldWhenRecursive(this.myCoolScript);
  this.doSomethingElse = this.yieldWhenRecursive(this.doSomethingElse);
  this.eatFruit = this.yieldWhenRecursive(this.eatFruit);

  // option #2
  this.yieldWhenRecursive('myCoolScript');
  this.yieldWhenRecursive('doSomethingElse');
  this.yieldWhenRecursive('eatFruit');

  // option #3
  this.prepareCustomScript('myCoolScript');
  this.prepareCustomScript('doSomethingElse');
  this.prepareCustomScript('eatFruit');
}

*myCoolScript() {
  if ('foo' !== 'bar') {
    yield* this.sayAndWait('That makes sense!', 2);
    yield* this.doSomethingElse();
  } else {
    yield* this.thinkAndWait('Oh dear, oh dear', 3);
    while (this.fruits.length > 0) {
      yield* this.eatFruit(this.fruits[Math.floor(Math.random() * this.fruits.length)]);
    }
  }
}

*doSomethingElse() {
  yield* this.myCoolScript();
}

*eatFruit(fruit) {
  if (Math.random() > 0.25) {
    if (Math.random() > 0.25 /* no really */) {
      yield* this.myCoolScript();
    }
  }
}

It has the same problems as above, i.e. it's OK if we don't care about being overeager, but not workable for perfect compatibility.

[towerofnix]

Here's approximately the final syntax we came up with. This handles normal control structures. (Finally!)

*doSomethingRecursive(x, n) {
  if (n > 0) {
    if (x > 20) {
      yield* this.recurse(+2, this.whatever)(x);
    } else {
      yield* this.recurse(+2, this.whateverElse)(x);
    }
    yield* this.recurse(+1, this.doSomethingRecursive)(n - 1);
  }
}

// wherein
recurse(depth, procedure) {  /* note: not a generator */
  const bound = procedure.bind(this);
  const callStack = this.callStack;
  return function*(...args) => {  /* note: this is a generator */
    for (let i = 0; i < depth; i++) {
      callStack.push(null);
    }

    if (callStack.recursive(procedure)) {
      try {
        yield;
      } catch (error) {
        // An error during the initial yield means we should not continue
        // to evaluate the procedure. But we already pushed those "blank"
        // layers representing normal control structures, so we need to
        // pop those off to clean up after ourselves (before passing the
        // error along).
        for (let i = 0; i < depth; i++) {
          callStack.pop();
        }
        throw error;
      }
    }

    callStack.push(procedure);
    try {
      yield* bound(...args);
    } finally {
      callStack.pop();
      for (let i = 0; i < depth; i++) {
        callStack.pop();
      }
    }
  };
}

Full example, in good working order.

*myCoolScript() {
  if ('foo' !== 'bar') {
    yield* this.sayAndWait('That makes sense!', 2);
    yield* this.recurse(+1, this.doSomethingElse)();
  } else {
    yield* this.thinkAndWait('Oh dear, oh dear', 3);
    while (this.fruits.length > 0) {
      yield* this.recurse(+2, this.eatFruit)(this.fruits[Math.floor(Math.random() * this.fruits.length)]);
    }
  }
}

*doSomethingElse() {
  yield* this.recurse(+1, this.myCoolScript)();
}

*eatFruit(fruit) {
  if (Math.random() > 0.25) {
    if (Math.random() > 0.25 /* no really */) {
      yield* this.recurse(+2, this.myCoolScript)();
    }
  }
}

Notes on this one:

• We're representing the syntactical depth as the first argument for this.recurse. It's impossible to "magically" compute this number short of inserting it during a transpilation step, because runtime JavaScript can't distinguish between the nested ifs above and if (Math.random() > 0.25 && Math.random() > 0.25), for example. We just have to code it, and that's that.
• But we avoid any other syntactical buffoonery. We only care about the stack when we're evaluating a custom block, so why bother dealing with it at all, otherwise? We skip the .push(null) and the try..finally .pop(), and so on—that's all handled inside this.recurse.
• The guts of recurse aren't very nice, but we can improve them in various ways that aren't really essential. The external interface (to user code) would be the same.
• We're "currying" now, to line up closer with how this.warp() is used. We also renamed the function from enter to recurse, since enter sounds like it has a corresponding exit. (Of course, recurse handles its own "exiting" cleanup behavior.)

[towerofnix]

That's the last real example, but we have one more short code blurb to share:

*doSomethingRecursive(x, n) {
  if (n <= 0) {
    return;
  }

  // `whatever` and `whateverElse` can never possibly route
  // to a nested `doSomethingRecursive`, i.e. the graph from
  // this point deeper is completely separate. there is thus
  // no need for a `this.recurse()` call.
  if (x > 20) {
    yield* this.whatever(x);
  } else {
    yield* this.whateverElse(x);
  }

  yield* this.recurse(0, this.doSomethingRecursive)(n - 1);
}

Routing? Graphing!? What is this!

Well, we're pretty sure we can statically create a nice and simple static graph of which custom blocks run which other custom blocks. (Or themselves.) If we detect cycles at all (setting aside detecting the "depth" of these cycles for simplicity's sake), then within those cycles, procedure calls need to use this.recurse. But if you're exiting a cycle, then you don't need to insert any blank entries... because, by definition, there is no possible way that any code evaluated inside that function will ever lead back to any of the functions currently in the call stack.

The caveat is that if the custom block you're entering is part of a totally different cycle, then unfortunately, we still need to use this.recurse... because we still need to perform the initial callStack.push() with the new function that might get recursed back to (from the new cycle). This could be avoided if custom procedures innately just always pushed and popped themselves when called (with some adjustments to this.recurse, obviously). But that's only reasonable through decorators. So... decorators win again?

[towerofnix]

OK, that's everything. We leave this conversation open and mostly free of our own opinions, although in messaging we did tell you we'll probably agree with the general directions you're thinking, lol. Interested to hear your thoughts! Please feel welcomed to ask questions if anything is unclear.