The only alternative is to reparse the string from the beginning (or from somewhere earlier in the string) and see if you happen to come out to the same place. This strikes me like one of those super-inefficient sorting algorithms where you shuffle the elements into a random order and then check to see if you happened to get them in order this time. If not, try a different guess. The intent of the verbiage in the synopsis is to rule out such a guessing implementation, which people tend to fall into because the notion of reversing the syntax tree is rather exotic until you think about it a while. But tree reversal is the right way to do it in a backtracking rule engine, so that's how Perl 6 will do it.

Thanks...

What would be interesting, if anybody is up for it, is an actual concrete example of a nonreversible patttern, in either perl5 or perl6 syntax (or both).

(?<=(a|aa))
[download]

is not permitted in perl5, because it is a variable length lookbehind. Glad to hear we get these in perl6.

Could someone throw out an example of what we can't do in perl6?

Maybe this is academic, but I like knowing the limits of pattern matching, as well as its power.

UPDATE: this seems to have just been answered, or at least a good attempt was made, by hv below, who must have been posting same time I was.

Simple patterns can be reversed: /foo/ can be reversed to /oof/.

Many more complex patterns can be reversed, though it isn't always obvious whether they'd match in exactly the same way: consider for example:

  "mississippi" ~~ /p<after (i.*?p)>/;
              # reverse to /(p.*?i)/ ??
              # or maybe   /(p.*i)/ ??
[download]

However other examples cannot be reversed at all: in general, this might include anything that involves code assertions. Precisely what constitutes a reversible pattern has not yet been fully characterised, and to some extent it will depend on what we decide are the invariants that must be preserved as in the example above.

Hugo

I think it should keep .*? as .*? on the theory that the actual underlying abstraction is "longest/shortest", not "earliest/latest".

I think code assertions can still work unless they make assumptions like "$1 is always bound before $2". (And I don't think we should reverse $1 and $2 for them. Reversing a lexical scope would be evil.)

But basically, I don't know what the limits are yet. All I know is that Perl 5 sets them too tight, and we can push them out a little. Rule matching can be more powerful than a locomotive, but there will always be a bit of kryptonite in the world. Language designers tend to concentrate on the locomotive rather than the kryptonite.

FWIW, relevant reading to this issue at sexeger.

SNIP:

"If we're able to look at the specific nodes of a regular expression, then we should be able to create a regex that works from the BACK of a string to the FRONT. What do I mean?

....."