Open towerofnix opened 4 months ago
Okay, so two bits of important implementation context:
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.)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.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();
}
This is the worst thing ever, but there are some useful things to note.
null
as padding.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)
.)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();
}
}
That isn't so bad, is it? Too bad it won't get much better from here...
this.enter
function, sort of modelling this.warp
. It works pretty well, but it's still an awkward syntax.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();
}
}
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.
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');
}
}
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.
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();
}
}
};
}
Notes on this one:
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 if
s above and if (Math.random() > 0.25 && Math.random() > 0.25)
, for example. We just have to code it, and that's that..push(null)
and the try..finally
.pop()
, and so on—that's all handled inside this.recurse
.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.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.)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?
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.
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:
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:this.callStack.push({why: 'myCoolScript'});
» Stack: [myCoolScript]this.callStack.push({why: 'if'});
» Stack: [myCoolScript, if]yield* this.sayAndWait('That makes sense!', 2);
» outputyield* this.doSomethingElse();
» enter custom block!this.callStack.push({why: 'doSomethingElse'});
» Stack: [myCoolScript, if, doSomethingElse]yield* this.myCoolScript();
» enter custom block!this.callStack.push({why: 'myCoolScript'});
» Stack: [myCoolScript, if, doSomethingElse, myCoolScript]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 includedoSomethingElse
, 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 includesmyCoolScript
... so it inserts a yield, here.OK, let's say the sky is falling!! Now
'foo' === 'bar'
! What happens this time!?this.callStack.push({why: 'myCoolScript'});
» Stack: [myCoolScript]this.callStack.push({why: 'if-else'});
» Stack: [myCoolScript, if-else]yield* this.thinkAndWait('Oh dear, oh dear', 3);
» outputthis.callStack.push({why: 'while'});
» Stack: [myCoolScript, if-else, while] (assuming we have any fruit, of course ✨)yield* this.eatFruit(this.fruits[...]);
» enter custom block!this.callStack.push({why: 'eatFruit'});
» Stack: [myCoolScript, if-else, while, eatFruit]this.callStack.push({why: 'if'});
» Stack: [myCoolScript, if-else, while, eatFruit, if] (assuming we're lucky)this.callStack.push({why: 'if'});
» Stack: [myCoolScript, if-else, while, eatFruit, if, if] (assuming we're lucky again)yield* this.myCoolScript();
» enter custom block!this.callStack.push({why: 'myCoolScript'});
» Stack: [myCoolScript, if-else, while, eatFruit, if, if, myCoolScript]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 intomyCoolScript
, 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!