Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Patterns embedding Streams do not terminate when a stream yields nil #4642

Open
jamshark70 opened this issue Nov 17, 2019 · 6 comments
Open

Patterns embedding Streams do not terminate when a stream yields nil #4642

jamshark70 opened this issue Nov 17, 2019 · 6 comments

Comments

@jamshark70
Copy link
Contributor

@jamshark70 jamshark70 commented Nov 17, 2019

Environment

  • SuperCollider version: 3.10
  • Operating system: irrelevant

Steps to reproduce

Here are some exciting ways to enter an infloop state, and possibly be forced into a hard shutdown.

// DON'T RUN THESE unless you have saved all your work

// this case, we already knew about
p = Pbind(\dur, Pn(Pseries(0.1, 0.1, 4).iter, inf)).trace.play;

// here is a stealth case -- you think this will quit Pseq-ing but it doesn't
(
p = Pbind(
	\dur, Pseq([
		Pfin(1, Pseries(0.1, 0.1, 6).iter),  // A stream
		Pfin(1, Pseries(1.0, 0.1, 2).iter)   // B stream
	], inf)
).trace.play;
)

( 'dur': 0.1 )  A
( 'dur': 1.0 )  B
( 'dur': 0.2 )  A
( 'dur': 1.1 )  B
( 'dur': 0.3 )  A
( 'dur': 0.4 )  A <<-- huh?
( 'dur': 0.5 )  A
( 'dur': 0.6 )  A

And now both A and B have run out of things to do, but Pseq will keep blindly trying to embed them -- reach for your power button...

Expected vs. actual behavior

In general, we say that when a pattern encounters nil, it should stop itself and pass the nil upward to parents, to stop the entire chain.

But embedInStream currently has no mechanism to do this. It's possible for it to embed zero items and return the next inval to the caller, and the caller is completely unaware that any sort of termination condition happened.

It is very bizarre to me that Pseq will just "skip over" dead streams silently ("huh?" above).

Currently we don't see this problem very often because the normal cases are:

  • When we use ListPatterns, Pn and other patterns that embed subpatterns, usually we won't be embedding to start from the beginning of the subpattern, so we tend not to use Streams here. (If it were common, I expect we would have a lot of reports of hangs -- but we don't have those reports, so I suppose this is a rare case.)

  • Stream-in-pattern tends to be reserved for arguments like number of repeats, which are polled once on embedding.

supercollider/rfcs#4 proposes ways to handle variable-length rests (a common user requirement). I believe interlacing rests into other sequences will be the most common use case. This will require .asStream or the .iter synonym. I'm concerned that this may make the current flaw in the design more visible.

I don't have a good solution currently. The return value from embedInStream is already used for the event-in-process. I'm not sure we can just return nil here because Pseq([a, b, c], 1).asStream.next (no inval) is also a common use case. It's a quite nasty design flaw.

EDIT: Maybe the subpattern could detect the condition and nil.yield? Haven't tried it, out of time for the moment.

@jamshark70

This comment has been minimized.

Copy link
Contributor Author

@jamshark70 jamshark70 commented Nov 17, 2019

Maybe the subpattern could detect the condition and nil.yield?

I kinda think this is right actually. We could say it like this: "Somebody called embedInStream on me, and I expected to yield at least once but I didn't." In that case, a strong argument could be made that the right thing to do is to terminate the calling stream (by yielding nil). Currently we just return to the caller, which may embed the same object again.

It has to be the receiver of embedInStream that checks, because only it knows if it expected to yield. You could have, e.g., Pfin({ 2.rand }, ...) with a 50% chance of count being 0 -- meaning "I expected not to yield anything and I didn't" = no stop condition. (But count > 0 means, expected to yield at least once.)

@eleses

This comment has been minimized.

Copy link
Contributor

@eleses eleses commented Mar 14, 2020

Maybe the subpattern could detect the condition and nil.yield?

How would the sub-pattern "detect the condition" though? You'd need a new flag to pass to the sub-pattern telling it that "you'd better yield something because I'm calling you in a tight loop". Without a flag like this, you'd have to end every embedInStream in every pattern with a nil.yield just in case the pattern-stream is being embedded in a tight loop in its parent.

If I get your proposal right, Pn (100, p{}) would yield"100 nils". This would break some existing semantics on appending patterns, e.g if you do

Pseq( [p{}, p{"yep".yield}], 1).asStream.nextN(4) // -> [ yep, nil, nil, nil ]

this presently works by producing one "yep" followed by nil, but with your proposal (as I understand it) it would be equivalent with

Pseq( [p{nil.yield}, p{"yep".yield}], 1).asStream.nextN(4) // -> [ nil, yep, nil, nil ]

which discards the output of Pseq's 2nd sub-pattern for the purposes of most Patterns that would embed this Pseq as they usually "stop and return" from their embedInStream on the first nil encountered.

I'd have to think a bit more about the mathy part, but basically, with this approach it seems to me you'd be "screwing up" the (monoid) pattern identify element for sequencing, which is the empty pattern p{} if you make it semantically equivalent with p{nil.yield} (or nil) which is the pattern zero/absorbing/annihilating element since most embedInStream calls "stop pulling" and return when they see a nil. (It seems to me patterns form a "monoid with zero" with sequencing/concatenation, presently, at least on this level of abstraction i.e. only considering sequencing/concatenation. If you nuke the identity element for that, you'd be left with a "semigroup with zero", i.e. lose the ability to "do nothing" in pattern sequencing without flagging its stream termination as well. The patterns also form a monoid with the composition operation, i.e. with Pchain, and that monoid has identity element p {|x| x}, but that's a different story.)

By the way, I see this is the same issue you mentioned on the user forum. My proposal/impression, like I said there, is that this is not decently fixable without a routine/thread-level primitive like hasYielded with auto-reset semantics on invocation, i.e.

"something".yield;
// more stuff
this.hasYielded; // -> true
// more stuff but not yield
this.hasYielded; // -> false

Basically any Pattern that can cycle in a tight loop on a returning, but non-yielding sub-pattern would implement a check like this. E.g. in Pn presently essentially does (glossing over the optional key-filtering business that Pn can do):

embedInStream { | event |
    repeats.value(event).do { event = pattern.embedInStream(event) };
    ^event;
}

With "hasYielded" the same code would look like

embedInStream { | event |
    repeats.value(event).do {
        event = pattern.embedInStream(event);
        if {this.hasYielded.not} {^event}
    }
    ^event;
}

The advantage of my hasYielded-approach vs what you (seem to me to) propose above is that you don't have to modify every pattern embedInStream to force-yield nil instead of "just returning", which you'd have to do with your approach. Only the repeating patterns (that thus have the tight-loop potential) like Pn etc. would need this "hasYileded" check.

I suspect the (necessarily native) implementation of hasYielded would not be too hard since I’m guessing Routine "context switches" leave a trail at the CPP-level implementation, but I haven't actually checked the code.

My proposal also breaks the current semantics of some patterns like

Pn(p{ if([true, false].choose, {"work".yield}, {}) }, 2).asStream.nextN(10)

This currently has a 50% probability to do "work" on each of the two calls Pn does into the p{...} Prout. But with my proposal for Pn, if the first call into the Prout doesn't yield anything, the 2nd is never made by Pn, so the probability for the 2nd "work" to happen is now only 25% (i.e. conditional on the first "work" having happened.)

But at least this semantic change would be localized at Pn (and some other repeating wrapper) level(s), i.e. if you want the old semantics, you could "just use the old Pn"..., i.e. there could be a flag in Pn's (new)constructor e.g. call it "dontStopOnEmpty" that would give you the old (live-lock-prone) behavior by not checking hasYielded. (Or alternatively, we could make the newer/safe behavior the optional one, but that would have the downside of still biting newbies.)

It might be worth doing a RFC on these ideas, as this bug report doesn't seem to attract that much attention in itself.

@jamshark70

This comment has been minimized.

Copy link
Contributor Author

@jamshark70 jamshark70 commented Mar 14, 2020

I tend to agree with the hasYielded approach.

@eleses

This comment has been minimized.

Copy link
Contributor

@eleses eleses commented Mar 14, 2020

Actually we could make this more general and mostly backwards compatible at the same time. instead of quitting on the first empty sub-pattern (or just going on forever) we could have a maxEmptyRepeats argument to Pn, Pseq etc., with a decent default value, say 1000. (The implementation would be obvious based on hasYielded and a counter.) This would give us a backwards compatible behavior most of the time, but still prevent live-locks if the sub-pattern still doesn't yield anything after maxEmptyRepeats iterations.

I'll have to look at the C++ code now to see if Routine readily knows on that level whether it has yielded or no.

@jamshark70

This comment has been minimized.

Copy link
Contributor Author

@jamshark70 jamshark70 commented Mar 14, 2020

instead of quitting on the first empty sub-pattern (or just going on forever) we could have a maxEmptyRepeats argument to Pn, Pseq etc., with a decent default value, say 1000.

Thanks for this. That's an important case -- it is legit to embed a zero-length pattern as long as it will eventually yield something.

A limit of 20 or 50 would be enough, I think.

@eleses

This comment has been minimized.

Copy link
Contributor

@eleses eleses commented Mar 14, 2020

Actually, I was able to do implement a working "hasYielded" without touching any C code (like prRoutineYield in PyrPrimitive.cpp). I used the Halo from jitlib extension although this is just a convenience side-dictionary in my quick hack:

+ Object {

	yield {
		"Yield hack".postln; // wasn't sure this is actually overridable, but it is
		thisThread.addHalo(\hasYielded, true);
		^this.nativeYield;
	}

	nativeYield {
		_RoutineYield
		^this.primitiveFailed
	}
}

+  Thread {

	hasYielded {
		var retval = this.getHalo(\hasYielded);
		if(retval.isNil) {retval = false};
		this.addHalo(\hasYielded, false);
		^retval;
	}
}

Test with:

f = { 1.yield; }
n = {}

r = r { n.(); thisThread.hasYielded.postln; }
r.next;

r = r { f.(); thisThread.hasYielded.postln;  thisThread.hasYielded.postln; }
r.next; r.next; 

It seems to work, but it needs to be extended to cover alwaysYield, yieldAndReset etc. for production implementation.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Linked pull requests

Successfully merging a pull request may close this issue.

None yet
2 participants
You can’t perform that action at this time.