3 ms·

Agreed. I read the post because the result was so shocking. TIL that the computer-sciencey definition of RE isn't the only one in use.

wongarsu 3y ago
When programmers say regular expression they usually mean Perl Compatible Regular Expressions (PCRE). Or I guess PCRE-compatible expressions, since there are other implementations of the same syntax out there. If you go back far enough in time they were once regular expressions in the computer science sense, but then features got added, and now they are incredibly powerful but can take basically infinite memory and time. https://en.wikipedia.org/wiki/Perl_Compatible_Regular_Expressions https://en.wikipedia.org/wiki/Perl_Compatible_Regular_Expres...
- disconcision 3y ago
  funnily enough the original POSIX regular expressions (BRE) were strictly less powerful than regular expressions (CS sense), lacking a general alternation operator (though one was provided in ERE)
- chrismorgan 3y ago
  Although general PCRE syntax has clearly won, that’s distinct from the infinite-memory-and-time matter. Engines that don’t use backtracking and can search in linear time (O(regex-size × search-text-size)) have been making a serious comeback in recent years, at only the cost of not supporting lookaround assertions or backreferences. For example, the re2 library, or Rust’s regex crate, both of which are very popular.
  - knome 3y ago
    Russ Cox has an excellent write up on it. "Regular Expression Matching Can Be Simple And Fast" (2007) https://swtch.com/~rsc/regexp/regexp1.html https://swtch.com/~rsc/regexp/regexp1.html
    - eru 3y ago
      Alas that approach only works well for your basic regular expressions that support Kleene-Star, concatenation and union. Regular languages are also closed under intersection and taking prefix etc (see https://en.wikipedia.org/wiki/Regular_language#Closure_properties https://en.wikipedia.org/wiki/Regular_language#Closure_prope...), and if you want to expose those operators in your regular expressions, Russ Cox's technique doesn't really work.
      - knome 3y ago
        I suspect it should be possible to transform two intersected (K*,C,U) expressions into a new (K*,C,U) expression by walking over the two, dropping incompatible terms, reducing sets, and redistributing and expanding sub-expressions to combine the two, though I do not have time to take a serious look at this at the moment. I also suspect that this might result in a combinatorial explosion of fused terms, but that's irrelevant as we're only worried about whether intersection can be implemented in Russ Cox's method, not whether a regular expression might require several earths or so worth of RAM to hold :) Nothing in the wiki article mentions taking a prefix, but that just sounds like `(prefix|)`?
        eru 3y ago
        You can still explicitly build the finite automaton for your closure-extended regular language. That one might be big, but matching is still linear in the length of the text you are searching through. As you point out Russ Cox's method can not deal with complement and intersection. You can hack it up by putting a compiler in front, but then you might as well compile to finite automata directly. Or you use derivatives: https://en.wikipedia.org/wiki/Brzozowski_derivative https://en.wikipedia.org/wiki/Brzozowski_derivative or https://www.ccs.neu.edu/home/turon/re-deriv.pdf https://www.ccs.neu.edu/home/turon/re-deriv.pdf (or https://well-typed.com/blog/2020/06/fix-ing-regular-expressions/ https://well-typed.com/blog/2020/06/fix-ing-regular-expressi... for a Haskell flavour). > Nothing in the wiki article mentions taking a prefix, but that just sounds like `(prefix|)`? They implicitly mention prefixes, when they talk about 'the trio operations: string homomorphism, inverse string homomorphism, and intersection with regular languages.' If I remember right, the prefix operation is: Take a language L, restrict it to the strings that have the right prefix: `L' := L & (prefix.*)` then chop off that prefix from every member of L'. See https://en.wikipedia.org/wiki/Quotient_of_a_formal_language https://en.wikipedia.org/wiki/Quotient_of_a_formal_language which this is a special case of. The Brzozowski derivative article also explains it in more detail.
- finitemonkey 3y ago
  > and now they are incredibly powerful but can take basically infinite memory and time. Which is why the "RE" in the article is excrutiatingly slow, given that it needs to perform insane amounts of backtracking. In contrast, "real" regular expression checkers run in linear time. Also, nitpicking, but they take unbounded time. It's still finite.
  - petters 3y ago
    They said “basically,” so no need to nitpick. And I’m not sure about unbounded; surely it is bounded by a suitable exponential function?
    - cubefox 3y ago
      I think with "unbounded but finite" he meant potential infinity rather than actual infinity.
    - finitemonkey 3y ago
      > They said “basically,” so no need to nitpick. The inflationary use of "infinite" especially in tech crowds that should know better deserves pushback. There are models of computation that actually model infinite computation. A well-studied one is Büchi automata, basically a generalization of finite state automata to infinite sequences. > And I’m not sure about unbounded; surely it is bounded by a suitable exponential function? Nope. You can nest them and for any function that you give you can produce a RE that takes longer than that function to evaluate. (That's literally what "unbounded" means. There is no bound. Doesn't mean it's "infinite". All those computations terminate, which is literally what "finite" means in this context.)
- tannhaeuser 3y ago
  [flagged]
  - elros 3y ago
    So what is it that they mean, in your opinion?
    - tannhaeuser 3y ago
      https://en.m.wikipedia.org/wiki/Regular_expression https://en.m.wikipedia.org/wiki/Regular_expression
      - jkrems 3y ago
        And that article says: > Perl regexes have become a de facto standard, having a rich and powerful set of atomic expressions.

wongarsu 3y ago

When programmers say regular expression they usually mean Perl Compatible Regular Expressions (PCRE). Or I guess PCRE-compatible expressions, since there are other implementations of the same syntax out there. If you go back far enough in time they were once regular expressions in the computer science sense, but then features got added, and now they are incredibly powerful but can take basically infinite memory and time. https://en.wikipedia.org/wiki/Perl_Compatible_Regular_Expressions https://en.wikipedia.org/wiki/Perl_Compatible_Regular_Expres...

disconcision 3y ago
funnily enough the original POSIX regular expressions (BRE) were strictly less powerful than regular expressions (CS sense), lacking a general alternation operator (though one was provided in ERE)
chrismorgan 3y ago
Although general PCRE syntax has clearly won, that’s distinct from the infinite-memory-and-time matter. Engines that don’t use backtracking and can search in linear time (O(regex-size × search-text-size)) have been making a serious comeback in recent years, at only the cost of not supporting lookaround assertions or backreferences. For example, the re2 library, or Rust’s regex crate, both of which are very popular.
- knome 3y ago
  Russ Cox has an excellent write up on it. "Regular Expression Matching Can Be Simple And Fast" (2007) https://swtch.com/~rsc/regexp/regexp1.html https://swtch.com/~rsc/regexp/regexp1.html
  - eru 3y ago
    Alas that approach only works well for your basic regular expressions that support Kleene-Star, concatenation and union. Regular languages are also closed under intersection and taking prefix etc (see https://en.wikipedia.org/wiki/Regular_language#Closure_properties https://en.wikipedia.org/wiki/Regular_language#Closure_prope...), and if you want to expose those operators in your regular expressions, Russ Cox's technique doesn't really work.
    - knome 3y ago
      I suspect it should be possible to transform two intersected (K*,C,U) expressions into a new (K*,C,U) expression by walking over the two, dropping incompatible terms, reducing sets, and redistributing and expanding sub-expressions to combine the two, though I do not have time to take a serious look at this at the moment. I also suspect that this might result in a combinatorial explosion of fused terms, but that's irrelevant as we're only worried about whether intersection can be implemented in Russ Cox's method, not whether a regular expression might require several earths or so worth of RAM to hold :) Nothing in the wiki article mentions taking a prefix, but that just sounds like `(prefix|)`?
      - eru 3y ago
        You can still explicitly build the finite automaton for your closure-extended regular language. That one might be big, but matching is still linear in the length of the text you are searching through. As you point out Russ Cox's method can not deal with complement and intersection. You can hack it up by putting a compiler in front, but then you might as well compile to finite automata directly. Or you use derivatives: https://en.wikipedia.org/wiki/Brzozowski_derivative https://en.wikipedia.org/wiki/Brzozowski_derivative or https://www.ccs.neu.edu/home/turon/re-deriv.pdf https://www.ccs.neu.edu/home/turon/re-deriv.pdf (or https://well-typed.com/blog/2020/06/fix-ing-regular-expressions/ https://well-typed.com/blog/2020/06/fix-ing-regular-expressi... for a Haskell flavour). > Nothing in the wiki article mentions taking a prefix, but that just sounds like `(prefix|)`? They implicitly mention prefixes, when they talk about 'the trio operations: string homomorphism, inverse string homomorphism, and intersection with regular languages.' If I remember right, the prefix operation is: Take a language L, restrict it to the strings that have the right prefix: `L' := L & (prefix.*)` then chop off that prefix from every member of L'. See https://en.wikipedia.org/wiki/Quotient_of_a_formal_language https://en.wikipedia.org/wiki/Quotient_of_a_formal_language which this is a special case of. The Brzozowski derivative article also explains it in more detail.
finitemonkey 3y ago
> and now they are incredibly powerful but can take basically infinite memory and time. Which is why the "RE" in the article is excrutiatingly slow, given that it needs to perform insane amounts of backtracking. In contrast, "real" regular expression checkers run in linear time. Also, nitpicking, but they take unbounded time. It's still finite.
- petters 3y ago
  They said “basically,” so no need to nitpick. And I’m not sure about unbounded; surely it is bounded by a suitable exponential function?
  - cubefox 3y ago
    I think with "unbounded but finite" he meant potential infinity rather than actual infinity.
  - finitemonkey 3y ago
    > They said “basically,” so no need to nitpick. The inflationary use of "infinite" especially in tech crowds that should know better deserves pushback. There are models of computation that actually model infinite computation. A well-studied one is Büchi automata, basically a generalization of finite state automata to infinite sequences. > And I’m not sure about unbounded; surely it is bounded by a suitable exponential function? Nope. You can nest them and for any function that you give you can produce a RE that takes longer than that function to evaluate. (That's literally what "unbounded" means. There is no bound. Doesn't mean it's "infinite". All those computations terminate, which is literally what "finite" means in this context.)
tannhaeuser 3y ago
[flagged]
- elros 3y ago
  So what is it that they mean, in your opinion?
  - tannhaeuser 3y ago
    https://en.m.wikipedia.org/wiki/Regular_expression https://en.m.wikipedia.org/wiki/Regular_expression
    - jkrems 3y ago
      And that article says: > Perl regexes have become a de facto standard, having a rich and powerful set of atomic expressions.