Re: Perl 5's non-greedy matching can be TOO greedy!
On Thu, 14 Dec 2000, Nathan Torkington wrote: Deven T. Corzine writes: I haven't even SEEN an example where the current behavior is actually preferable than my proposed behavior, have you? (And I'd expect at least a FEW, though I suspect there are probably more counterexamples.) I think the biggest problem with your idea is that it requires the engine to keep looking even after it finds a match, to see if there's another shorter match. This would make *every* match much much slower, potentially heatdeathoftheuniverse slower. I like the current semantics because it's very easy to visualize the engine acting on your instructions and stopping as soon as it finds a match. I am a programmer, and I prefer programs to descriptions. Not at all. I don't want it to keep looking after it finds the first match. I want it to make sure that match isn't unnecessarily long, if non-greedy matching was in use. Conceptually (I don't think this would be a good implementation), you find the first match as the current engine does, then search for the smallest possible match WITHIN that first match. Since it will already be as short as possible from the starting point, this amounts to advancing the starting point as far as possible without changing the ending point, as long as it still matches. Deven
Re: Perl 5's non-greedy matching can be TOO greedy!
On 14 Dec 2000, Randal L. Schwartz wrote: "Deven" == Deven T Corzine [EMAIL PROTECTED] writes: Deven I haven't even SEEN an example where the current behavior is Deven actually preferable than my proposed behavior, have you? (And Deven I'd expect at least a FEW, though I suspect there are probably Deven more counterexamples.) If I want the leftmost B that is followed by the shortest number of characters to get to a D, I write /B.*?D/. The "leftmost" part keeps getting left out of regex discussions, and maybe that's why you're thrown off. But it's a pretty consistent overriding factor. That's not an example, that's a hypothetical. I meant that I've never seen a concrete, realistic example where the current behavior is more beneficial to the programmer than my proposed behavior. (I imagine in most cases, it will be a moot point, since the match will usually be the same.) If you want something odd like "not necessarily the leftmost", then you'll need to speak more. But "leftmost" is fundamental to the design of regex. Don't mess with that. Or don't call it a regex any more. Strange argument. Greedy matching was once considered fundamental to the design of regex, and the "leftmost" behavior is 100% consistent with greedy matching. Yet Perl 5 added non-greedy modifiers, changing a fundamental aspect of every preceding regex system, and still called it a regex... Extending the design of the regex system to allow for non-greedy matching was an excellent extension, and made Perl 5's regular expressions far more powerful than anyone else's. But they're certainly different than before. I wish I had been involved in the discussions when the idea of non-greedy matching was proposed and the details ironed out. I don't think my ideas would have had the same kind of concerted opposition back then as now... Deven
Re: Perl 5's non-greedy matching can be TOO greedy!
"Deven" == Deven T Corzine [EMAIL PROTECTED] writes: Deven What surprised me was how vigorously people would defend the Deven status quo, and insist on the correctness of the current Deven behavior without thinking it through. No, I thought it through quite completely. As have others. Deven Given how invested people are in the exact current behavior, I Deven now believe it was a poor choice of words to describe it as a Deven "flaw", simply because it presumed an implied consensus on the Deven higher-level semantics that obviously wasn't there. Quite the opposite. You seem to be one of the very few who expects it to act other than as documented. Deven It seems to have been interpreted as a value judgement on my Deven part, which it wasn't. It merely occurred to me that Perl 6 Deven might provide an opportunity to eliminate a minor quirk in the Deven regular expression system. I didn't mean to imply that the Deven current behavior is BAD, simply that it's not quite right (at Deven least in my mind) -- since there's serious disagreement about Deven this, I'd like to make a shift in terminology and start Deven referring to this behavior as a "semantic anomaly" rather than Deven a "flaw" or a "bug", and hope that will be a more neutral term. It's not an anomoly at all. It comes out completely accurate with some very simple rules for how regex works. Admit it... it bit you, and you are just refusing to believe that you don't have a complete and accurate model for how regex work. Please, admit this, and we can MOVE ON. Deven Hopefully, we can have a rational discussion about whether this Deven semantic anomaly is real or imagined, what impact "fixing" it Deven would have on the implementation (if it's deemed real), and Deven whether it's worth "fixing". You can't fix what isn't broken. Deven If the final decision is not to change the current behavior, Deven for whichever reason, I'd like to see this documented in an RFC Deven that says "here's what was requested and why it isn't going to Deven be done". I'll volunteer to help with that (even if I remain Deven in the minority), whether by summarizing or cutting and pasting Deven arguments made in this discussion... Changing the regex to do what you wish would make regex in Perl entirely unlike the regex in every other language. Not gonna happen. Deven The pattern in question is "b.*?d". Obviously, this matches Deven "b", followed by something else, followed by "d". What Deven "something else" should be is the issue at hand. That portion Deven of the regexp is just ".*?" -- the "." matches any character Deven (except newlines, depending on the mode), the "*" modifies the Deven "." to match "zero or more" of "any character", and the "?" Deven modifies the ".*" to match "zero or more" of "any character", Deven but "matching the minimum number of times possible". No. This is where you are off. .* and .*? match the same types of things. Just that when given the choice, .*? leans towards the shorter version, and .* leans toward the longer. All the ? does is change the *bias* in the face of *choices*. But the overriding rules of a regex match are "left most first". So the first b will match at the first possible b. And then we run out as many "." matches as we can. No wait, it's ?, so we run out as few "." matches as we can, until we can match a "d". Bingo, we got a match! That's the rules. They're very easy to grasp. The leftmost match is found with the required semantics. You don't keep going on looking for a shorter match. Deven Hence, Deven the ".*?" can be summarized as "match anything, but keep the Deven match as short as possible". No, that's an incorrect description. No wonder you are confused. Deven Am I really the only one who views it this way? Must I stand Deven alone? Yes. Go stand in the corner. :) Deven If we lived in that ideal world, what behavior would be Deven expected and preferred? The current one. If you muck with "leftmost match wins", not only will you break most existing programs, you will SLOW EVERYTHING DOWN, because we have to keep going on even after we already have a match! -- Randal L. Schwartz - Stonehenge Consulting Services, Inc. - +1 503 777 0095 [EMAIL PROTECTED] URL:http://www.stonehenge.com/merlyn/ Perl/Unix/security consulting, Technical writing, Comedy, etc. etc. See PerlTraining.Stonehenge.com for onsite and open-enrollment Perl training!
Re: Perl 5's non-greedy matching can be TOO greedy!
"Deven" == Deven T Corzine [EMAIL PROTECTED] writes: Deven As for special-case rules, I believe that my proposed modification would Deven REMOVE a special-case semantic rule, at the cost of added complexity at the Deven implementation level. (The cost decision of whether that added complexity Deven is worthwhile is a separate consideration.) No, it would break a much higher overriding rule of "left most match wins". That's at the top of the chart. You're *adding* an exception to that. Tell me how you can do that without breaking much existing code. Deven And I'd really appreciate it if everyone would refrain from Deven suggesting that I don't understand the behavior. I understand Deven it fine; I just don't agree with it. In the language of the Deven Supreme Court, "I respectfully dissent." Just because I don't Deven perfectly agree with the semantics that were chosen doesn't Deven mean I don't understand them. You don't understand the motivation, apparently. That's what I'm referencing. -- Randal L. Schwartz - Stonehenge Consulting Services, Inc. - +1 503 777 0095 [EMAIL PROTECTED] URL:http://www.stonehenge.com/merlyn/ Perl/Unix/security consulting, Technical writing, Comedy, etc. etc. See PerlTraining.Stonehenge.com for onsite and open-enrollment Perl training!
Re: Perl 5's non-greedy matching can be TOO greedy!
On 15 Dec 2000, Randal L. Schwartz wrote: "Deven" == Deven T Corzine [EMAIL PROTECTED] writes: Deven As for special-case rules, I believe that my proposed modification would Deven REMOVE a special-case semantic rule, at the cost of added complexity at the Deven implementation level. (The cost decision of whether that added complexity Deven is worthwhile is a separate consideration.) No, it would break a much higher overriding rule of "left most match wins". That's at the top of the chart. You're *adding* an exception to that. Tell me how you can do that without breaking much existing code. Can you give a concrete, real-life example of code that my proposed change would actually break, not a contrived hypothetical case design to break? Adding the requirement for "\@" in double-quoted strings broke a LOT of Perl 4 code. I doubt this would break much at all. Deven And I'd really appreciate it if everyone would refrain from Deven suggesting that I don't understand the behavior. I understand Deven it fine; I just don't agree with it. In the language of the Deven Supreme Court, "I respectfully dissent." Just because I don't Deven perfectly agree with the semantics that were chosen doesn't Deven mean I don't understand them. You don't understand the motivation, apparently. That's what I'm referencing. I don't understand the motivation behind taking leftmost matching to such extremes. I understand the importance of leftmost matching in general; this is a particular situation where I believe it's being taken a little too far for the good of the whole. However, some of the comments that have been made seem to imply that I'm simply ignorant about regular expressions and I need to learn them better. My questioning the behavior arises out of philosophy, not ignorance. Deven
Re: Perl 5's non-greedy matching can be TOO greedy!
On Thu, 14 Dec 2000, Jeff Pinyan wrote: You could use my sexeger technique to get this behavior (possibly): $string = "aaabbbcccdddeee"; # regex to be reversed: /b(.*?)d/ $revstr = reverse $string; ($match) = $revstr =~ /d(.*?)b/; No, that doesn't quite work. It works when you unroll the .*? loop: # regex to be reversed: /b([^bd]*)d/ ($match) = $revstr =~ /d([^bd]*)b/; But then why would you use sexeger at all, when you can unroll the loop in the forward direction? ($match) = $string =~ /b([^bd]*)d/; I'm not asking for help with workarounds. If I ever need to workaround the current behavior, I won't have any trouble doing so. It's just that (on a philosophical note) I don't believe this is something that should require a workaround. Obviously, others disagree. Deven
Re: Perl 5's non-greedy matching can be TOO greedy!
On Thu, 14 Dec 2000, James Mastros wrote: On Thu, Dec 14, 2000 at 04:10:12PM -0500, Deven T. Corzine wrote: The crux of the problem is that non-greedy qualifiers don't affect the "earliest match" behavior, which makes the matches more greedy than they really ought to be. Right. We've got a terminoligy issue. There's two axes here: Not the only terminology issue, but I've addressed that in other messages. Greed: Greedy by default. Will try to match as many chars after its starting point as possible. Non-greedy will try to match as few chars after its starting point as possible, and is denoted by putting a '?' after a quantifer. Lazyness: Eager by default. An eager assertation will try to match as early as possible. It isn't possible to use lazy assertations at present. (Not simply, anyway. It's probably possible to combine other (?) features to get the same effect.) You seem to want the choice between greedy, eager assertations, and non-greedy, lazy assertations. If you came up with a good way to specify along both axes, I think we'd have a winner. I want the maximum level of OVERALL consistency for regular expressions as a whole, rather than immutable adherence to the "leftmost trumps nongreedy" rule currently in place. Most of the time, I agree with the precedence of leftmost over nongreedy. The example I gave is a case where I believe the strict adherence to the leftmost rule actually introduces complexity and makes the regular expression system less self-consistent. I don't know if anyone else will ever believe me or not. Deven
Re: Perl 5's non-greedy matching can be TOO greedy!
On Fri, 15 Dec 2000, Deven T. Corzine wrote: Not at all. I don't want it to keep looking after it finds the first match. I want it to make sure that match isn't unnecessarily long, if non-greedy matching was in use. Conceptually (I don't think this would be a good implementation), you find the first match as the current engine does, then search for the smallest possible match WITHIN that first match. Since it will already be as short as possible from the starting point, this amounts to advancing the starting point as far as possible without changing the ending point, as long as it still matches. Actually, I'm not sure -- it's conceivable that the ending point would ALSO move inward for a different starting point within the original match. But the ending point should NEVER be advanced further -- that's where the "leftmost over nongreedy" rule should apply instead... Deven
Re: Perl 5's non-greedy matching can be TOO greedy!
Please give it a rest. I think everybody got it by now. Everybody understands how the current implementation works and what the semantics are, and you disagree with the current semantics. I think that's the end of story since changing current default semantics is simply not an option. We can't break all the existing programs that depend on the current stinginess semantics, period. Now move on. -- $jhi++; # http://www.iki.fi/jhi/ # There is this special biologist word we use for 'stable'. # It is 'dead'. -- Jack Cohen
Re: Perl 5's non-greedy matching can be TOO greedy!
"Deven T. Corzine" [EMAIL PROTECTED] writes:
I've yet to see a concrete example of where the current behavior is
helpful,
What about matching C comments?
($first_comment) = $code =~ m!(/\*.*?\*/)!s;
# (ignore issues with quoted strings in $code
Works correctly under the current behavior. It would break under you
proposal (if I understand your proposal correctly).
More generally, it seems to me that you're hung up on the description
of "*?" as "shortest possible match". That's an ambiguous
simplification of what "*?" means. It might better be described as
"match until you find a match for the rest of the regex" ('d' in your
example). If oversimplifications in the documentation led you to
believe that "*?" meant something it was never intended to mean, then
perhaps the documentation should be clarified. But the meaning of
"*?" should not be changed.
Final point: In your example, /b[^bd]*d/ does what you want, and is
arguably easier to understand. Can you think of any examples where
it's not this easy to get the behavior you desire?
Re: Perl 5's non-greedy matching can be TOO greedy!
More generally, it seems to me that you're hung up on the description
of "*?" as "shortest possible match". That's an ambiguous
Yup, that's a bit confusing. It's really "start matching as soon as
possible, and stop matching as soon as possible". (The usual greedy
one is, of course, "keep matching as long as possible".) The initial
invariant part, "start as soon as possible", is the de facto and de
jure (at least POSIX 1003.2, but probably also Single Unix)
definition, and therefore rather non-negotiable.
simplification of what "*?" means. It might better be described as
"match until you find a match for the rest of the regex" ('d' in your
--
$jhi++; # http://www.iki.fi/jhi/
# There is this special biologist word we use for 'stable'.
# It is 'dead'. -- Jack Cohen
Re: Perl 5's non-greedy matching can be TOO greedy!
On 15 Dec 2000, Randal L. Schwartz wrote: "Deven" == Deven T Corzine [EMAIL PROTECTED] writes: Deven What surprised me was how vigorously people would defend the Deven status quo, and insist on the correctness of the current Deven behavior without thinking it through. No, I thought it through quite completely. As have others. You and others spent plenty of time thinking this through a long time ago. I wish I had been involved with that process, to raise these points then. Have you thought it through NOW, on a purely semantic level (in isolation from implementation issues and historical precedent), or are you rejecting the idea out-of-hand because you believe you've already given the matter enough consideration? Deven Given how invested people are in the exact current behavior, I Deven now believe it was a poor choice of words to describe it as a Deven "flaw", simply because it presumed an implied consensus on the Deven higher-level semantics that obviously wasn't there. Quite the opposite. You seem to be one of the very few who expects it to act other than as documented. Really? I haven't taken a survey, but I did ask one co-worker for his first impression of what the regexp (from my example) would match. Not being an experienced Perl programmer, but being familiar with regular expressions, he believed he understood the idea of non-greedy matching. His expectation? That would match "bd", not "d". Is it that few people expect this, or that they get smacked down so fast when they suggest it that they never dare raise the question again? Deven It seems to have been interpreted as a value judgement on my Deven part, which it wasn't. It merely occurred to me that Perl 6 Deven might provide an opportunity to eliminate a minor quirk in the Deven regular expression system. I didn't mean to imply that the Deven current behavior is BAD, simply that it's not quite right (at Deven least in my mind) -- since there's serious disagreement about Deven this, I'd like to make a shift in terminology and start Deven referring to this behavior as a "semantic anomaly" rather than Deven a "flaw" or a "bug", and hope that will be a more neutral term. It's not an anomoly at all. It comes out completely accurate with some very simple rules for how regex works. It's an anomaly in my mind. Whether it's a real anomaly or an imaginary one, I left that one up in the air for the moment. Personally, I believe the anomaly is real, but quite dependent on the perspective from which you view the situation. Yes, the existing rules are accurate, predictable and simple. Are they the BEST possible rules, or just what made the most sense at the time? Admit it... it bit you, and you are just refusing to believe that you don't have a complete and accurate model for how regex work. Please, admit this, and we can MOVE ON. Actually, it's never bit me. I only discovered it by experimenting with contrived examples to see exactly how the new (at that time) non-greedy matching feature worked. I thought the behavior was a little odd, but the explanation made enough sense that it didn't seem worth arguing about. Now that Perl 6 is on the horizon, it seems time to consider the idea. I have yet to run into a real-life situation where this anomaly really matters much. Which might be an argument not to worry about it. But the fact that I was already extremely familiar with greedy regexps, and (at first) surprised by this behavior, makes me wonder what's the best way. Deven Hopefully, we can have a rational discussion about whether this Deven semantic anomaly is real or imagined, what impact "fixing" it Deven would have on the implementation (if it's deemed real), and Deven whether it's worth "fixing". You can't fix what isn't broken. I put "fixing" in quotes because it depends on whether it's broken or not. I did the same thing that everyone else is doing, skipping the first part of the discussion on the assumption that the answer was OBVIOUS. Well, it clearly isn't as obvious as we all believe, since what seems obvious to me and what seems obvious to you are in conflict. Everyone keeps trying to frame it as my presumed "misunderstanding" of how it should work, when it's actually a question of perspective. Since nobody seems willing to contemplate this from the perspective that I'm presenting, it's difficult to conclude whether or not it's actually broken. Everyone simply assumes I'm wrong and doesn't care beyond that. Deven If the final decision is not to change the current behavior, Deven for whichever reason, I'd like to see this documented in an RFC Deven that says "here's what was requested and why it isn't going to Deven be done". I'll volunteer to help with that (even if I remain Deven in the minority), whether by summarizing or cutting and pasting Deven arguments made in this discussion... Changing the regex to do what you wish would make regex in Perl
Re: Perl 5's non-greedy matching can be TOO greedy!
More generally, it seems to me that you're hung up on the description of "*?" as "shortest possible match". That's an ambiguous Yup, that's a bit confusing. It's really "start matching as soon as possible, and stop matching as soon as possible". (The usual greedy one is, of course, "keep matching as long as possible".) The initial invariant part, "start as soon as possible", is the de facto and de jure (at least POSIX 1003.2, but probably also Single Unix) definition, and therefore rather non-negotiable. It's like people who write /^.*fred/ instead of /.*fred/. They are forgetting something critical: where the Engine starts the serach. --tom
Re: Perl 5's non-greedy matching can be TOO greedy!
Have you thought it through NOW, on a purely semantic level (in isolation from implementation issues and historical precedent), I've said it before, and I'll say it again: you keep using the word "semantic", but I do not think you know what that word means. --tom
Re: Perl 5's non-greedy matching can be TOO greedy!
[I delayed responding to this message because it was the longest.] On Thu, 14 Dec 2000, Tom Christiansen wrote: No question that's how it's been implemented. But WHY would anyone want such behavior? When is it beneficial? It is beneficial because this is how it's always been, because it is faster, because it is more expressive, because it is more powerful, because it is more intuitive, and because it is more perlian. Nice summary, but I'm not buying what you're selling in the elaboration. In elaboration: 0) All NFAs before POSIX acted this way. It is historically consistent and perfectly expected. First, all those older regular expression systems were inherently greedy matching algorithms. There is absolutely no conflict between earliest match and greedy matching. The conflict only arises when non-greedy matching is introduced into the equation. Second, by referring to NFA's, you're already dropping down to a lower level, and as I said in a prior message, you've lost the gestalt by then. Once you drop to that level (and stop referencing the semantics of the whole), my point is moot, because it no longer makes sense at that level. Finally, historical precedent is a always a justification not to change anything. Of course, that argued against the wonderful regex extensions that Perl 5 added, since they went against the way "it's always been"... 1) It is obviously faster to come to an answer earlier on in the execution than it would be to come to an answer later. It's like an expression whose evaluation short-circuits. Also, when the matching sematics permit back tracking and back references, the combinatoric possibilities can easily explode into virtual unsolvability as the 2**N algorithm loses its race to the heat death of the universe. Yes, if Perl did overall-longest or overall-shorted, this would produce a more predictable time; however, as we see with DFAs and POSIX NFAs, this prediction plays out as guaranteed *WORST-CASE* time. It is not acceptable to make everyone pay the worst-case time. Never penalize the whole world for the needs or desires or the few. I don't think it should be implemented unless the cost is small or applied only to those situations where it's wanted despite the cost. However, I don't believe it would NECESSARILY be slower to execute -- yes, there's more complexity. The price for that complexity must be paid, but it may be payable in memory by making a larger (but equally fast) NFA for the regular expression. Or maybe it can't. I don't know, because I have not investigated it. It's premature to simply assume it MUST be slower. 2) Consider the simple case, /A|B/. In your overall longest/shortest, guaranteed worst-case time, both submatch A and submatch B must be calculated, and then the lengths of their matches both be compared. Perl, fortunately, does not do that. Rather, the first one in that sequence wins. That means that under the current scheme, the patterns /A|B/ and /B|A/ have different semantics. Under your worst-case scheme, they do not. Because /A|B/ and /B|A/ mean something different, more expressivity is provided. This is the same scenario, albeit expressed slightly differently, as your situation. The issues manifest in both are equivalent. Then that is another semantic anomaly, because the alternation is supposed to mean that one or the other pattern matches. Logically, "or" should be communitive. If they're not quite, that's another disconnect between the high-level model and the implementation. Maybe /A|B/ and /B|A/ _do_ mean different things to the engine, but they do NOT mean different things in the high-level semantics -- except when you force the high-level semantics to change by fiat, to match the implementation. 3) This leads to increased power. It's like the difference between a short-circuiting "or" and one that blindly plods ahead trying to figure something out even when all is for naught. Compare AB with AB, for example. If A is 0, then B need not be computed, yet in the second version, one runs subexpression B nevertheless. If according to the rules of one particular system, patX and patY mean different things, whereas in a second system, they are completely interchangeable, then the first system can express nuances that the second one cannot. When you have more nuances, more expressivity, then you have more power, because you can say things you could not otherwise say. Why do C and its derivatives such as Perl have short-circuiting Boolean operators? Because in older languages, such as Fortran and Pascal, where you did not have them, one quickly found that this was cumbersome and annoying. It's a question of speed vs. correctness. Correctness is important, but occasionally a little incorrectness is worthwhile for increased speed. Short-circuiting in C
