Check if pattern is infinite

Questions
1

Is there a way to check if a pattern is infinite, say before you do

Pseq([1, 2, 3]).asStream.all

or is there perhaps a quark that makes it possible?

2

I believe you’ve just asked if SC solves the halting problem, which is undecidable: “In computability theory, the halting problem is the problem of determining, from a description of an arbitrary computer program and an input, whether the program will finish running, or continue to run forever. Alan Turing proved in 1936 that a general algorithm to solve the halting problem for all possible program–input pairs cannot exist.”

We’re not gonna do better than Turing here :wink:

But I did, some years ago, try to “estimateLength” of patterns. It’s not reliable – sort of an abandoned fragment – but it should search through patterns and tend toward inf if some subpattern has an infinite length.

Pseq([1, 2, Pn(3, inf)], 1).estimateLength  // inf

Pser([1, 2, Pn(3, inf)], 2).estimateLength  // inf but that's wrong

// Pswitch: 'which' pattern means the inf subpattern
// will never be embedded... but estimateLength doesn't
// know that, so it just returns inf
Pswitch([1, 2, Pn(3, inf)], Pwhite(0, 1, 6)).estimateLength

Use at your own risk. It should be OK for relatively simple Pseq, Prand, Pxrand etc. patterns. Complex patterns, don’t trust it.

ddwPatterns quark.

hjh

3

Many thanks for the insight and suggestion, I’ll look into the quark!

In the unreliable cases, will your method return inf even if it is finite, or the other way around, or still undecided?

For my use case it’s sufficient to know whether it is guaranteed to be finite or not, so a method like .isKnownToBeFinite could be useful.

I was thinking of adding methods like below, but I guess the method added to Object is questionable, since a new .embedInStream method could also be added to any class.

Just thinking out loud :slight_smile:

+ Object {
	isKnownToBeFinite {
		^true;
	}
}

+ Stream {
	isKnownToBeFinite {
		^false;
	}
}

+ Pattern {
	isKnownToBeFinite {
		^false;
	}
}

+ Pseq {
	isKnownToBeFinite {
		^((this.repeats != inf) && (this.list.collect({arg item; item.isKnownToBeFinite}).includes(false).not));
	}
}
4

Turing proved that there is no reliable algorithm that can determine this.

It may be possible to handle a subset of cases. If that subset includes most typical cases, then it may be useful – but it can’t be both complete and accurate.

I posted a couple of examples where it returns inf even when the pattern isn’t, so the first question is definitely yes. “Other way around,” probably not but this code is not tested rigorously enough to be sure.

hjh