On 28 Aug 2002, Simon Cozens wrote: > [EMAIL PROTECTED] (Deven T. Corzine) writes: > > Would it be _possible_ to create a non-backtracking implementation of a > > Perl 6 pattern engine > > I don't believe that it is, but not just because of : and friends. > Why does it matter?
I'm not saying we should dump the operators -- if we get more power by assuming a backtracking implementation, maybe that's a worthwhile tradeoff. On the other hand, if we can keep the implementation possibilities more open, that's always a worthwhile goal, even if we're not sure if or when we'll ever take advantage of those possibilities, or if we even could... It seems like backtracking is a Bad Thing, in that it leads to reprocessing data that we've already looked at. On the other hand, it seems to be a Necessary Evil because of the memory costs of avoiding backtracking, and because we might have to give up valuable features without backtracking. It may be that backreferences already demand backtracking. Or some other feature might. I don't know; I haven't thought it through. If we must have backtracking, so be it. But if that's a tradeoff we're making for more expressive and powerful patterns, we should still at least make that tradeoff with our eyes open. And if the tradeoff can be avoided, that's even better. Deven