16 ms·

I'll be "that guy" -- this is not a regular expression [1]. A Perl regexp, sure. But backreferences are not part of the grammar of regular expressions, and mo

• dudeman13 5y ago
  Thanks for that. My initial reaction to the title was "wait, you can describe prime numbers using formal languages?". I could feel it in my guts that this would probably have some mind blowing Math/CS implications. A shame how I'm so rusty in my Mathematics and CS nowadays :(
  • aghilmort 5y ago
    had same immediate reaction, like whoa, huge if true, time to read the comments
• nickelpro 5y ago
  I'll be "the other guy" -- no one uses the term regex or regular expression in a programming context to mean a strictly regular language in the theoretical computer science sense. Nitpicking this point is ignorant of how the usage of the term has evolved within the programming community. Good. There's that obligative conversation over and done with.
  • eutropia 5y ago
    I’ll be the guy who postscripts that “hardmode” regexes would have important mathematical and computer science implications when/if they solve certain problems (like identifying primes). So it’s not pure pedantry, and there’s an important difference between “regexes to solve programming problems” and “regexes solving math problems”.
    • dpwm 5y ago
      "hardmode" regexes do have important computer science implications: they can be matched orders of magnitude faster [0]. Demonstrating the power of a regex engine by solving a problem like this is interesting and very clever, but it’s hopefully not used in production. [0] https://swtch.com/~rsc/regexp/regexp1.html https://swtch.com/~rsc/regexp/regexp1.html
      • eutropia 5y ago
        Yeah I think we agree here. I didn’t mean to assert that chomskian regular grammars or regexes satisfiable by a state machine hadn’t already been useful; I meant to say that because they have existing math implications and properties that new uses for them would imply connections to other maths, analogous computations, new proofs or ways to solve things, etc. And yeah, they’re faster because they can be statically compiled to the point of running strings “through” the expression rather than running the expression “on” the string, so to speak. (i.e as an FSM, iterating char by char the operations boil down to purely compare and branch to known destinations)
  • colanderman 5y ago
    Having worked in an industry where the linear vs. exponential performance implications of regular expressions and PCREs was crucial (intrusion protection systems), I'd just as soon software professionals stop being sloppy with terminology. Not to mention the plethora of mostly-but-not-totally compatible regexp languages which exist. C++ supports 6 [1], and that doesn't even include PCREs. Miscommunication about which language one is actually using is a common source of regexp bugs. [1] https://en.cppreference.com/w/cpp/regex/syntax_option_type https://en.cppreference.com/w/cpp/regex/syntax_option_type
    • earleybird 5y ago
      Yes, thank you. If you're sloppy with words you probably have other nasty habits. (apologies to Heinlein) There are reasons to employ regular languages with extensions (to not quite context free languages) but be clear about what you're talking about.
      • bawolff 5y ago
        I'd argue that if this is sloppy, then the use of "you" instead of "thou" is sloppy too. Using "you" for everything is confusing. How can i possibly know if you mean plural or singular? Sure some people might say "thou" is archaic, however so is using "regex" outside of academic contexts to mean regular languages. I don't see how one could justify one but not the other.
      • efitz 5y ago
        Grammar sticklers usually fail on this point: human languages are not static, stuck in place from the time the stickler learned the rules. The current state of a human language is defined by common usage. The purpose of a language is for people to be able to communicate ideas. Ideas exist all up and down a specificity spectrum, e.g. “regex” might mean a specific syntax or one of several syntaxes depending on context. Kind of like “kleenex” might refer to a specific brand or to the general concept of tissue. If 99.9% of people successfully (by their own measure, not yours) communicate what they mean when they use the term “regular expression”, but you are among the 0.1% for which that interaction fails, then I would argue that the problem is your pedantry, not the term. I’m not saying this to be mean; I have similar issues.
  • jltsiren 5y ago
    There is no such thing as the programming community. Only a huge number of partially overlapping communities using wildly different terminology. Some communities still talk about regular expressions in the original meaning (because labeled graphs are useful objects), just like some communities still use the word "algorithm" outside machine learning or "crypto" in non-blockchain contexts. I personally prefer using "regular expression" in the language-theoretic sense and "regex" or "regexp" for related concepts in programming languages and software.
    • dpwm 5y ago
      > I personally prefer using "regular expression" in the language-theoretic sense and "regex" or "regexp" for related concepts in programming languages and software. This is also what Larry Wall proposes: > [...] Pattern Matching, generally having to do with what we call "regular expressions", which are only marginally related to real regular expressions. Nevertheless, the term has grown with the capabilities of our pattern matching engines, so I'm not going to try to fight linguistic necessity here. I will, however, generally call them "regexes" (or "regexen", when I'm in an Anglo-Saxon mood). https://raku.org/archive/doc/design/apo/A05.html https://raku.org/archive/doc/design/apo/A05.html
      • thaumasiotes 5y ago
        > (or "regexen", when I'm in an Anglo-Saxon mood) There's some kind of idea going around that because the plural of "ox" is "oxen", plurals with -n must be triggered by a word ending in "x". So you see cutesy references to "boxen" or similar. But -n is just an ordinary plural marker; the same ending that makes "oxen" the plural of "ox" also makes "kine" the plural of "cow" and "children" the plural of "child". (In those last two cases, the words are sporting two plural markers in sequence.)
        • knome 5y ago
          >There's some kind of idea going around It's not new, by any stretch. I remember seeing such many references in the early 2000s and beyond. Doing some vague poking around textfiles.com, I didn't pull any easy to find 1980s 'boxen' references. It almost looks like it might have been the addition of 'unix boxen' to the 'new hacker dictionary' by esr which spread the joke into the mid-90s communities. I wasn't online at that point myself, so I can't speak from any personal experience. But the various hacker zines etc are using 'boxen' by the later 90s and early 2000s, which would allow for it to have spread through the folks of the time finding and trolling through esr's version of the 'hacker dictionary'. https://www.dourish.com/goodies/jargon.html https://www.dourish.com/goodies/jargon.html complains about esr adding unix references, and does not include any boxen references that are found in the http://cd.textfiles.com/hackersencyc/ETC/MISC/JARG_331.TXT http://cd.textfiles.com/hackersencyc/ETC/MISC/JARG_331.TXT version folks in the 90s would likely have spread around. edit: nope. definitely there in the 80s on usenet so he was just encoding existing slang usage, rather than introducing it, on this point. https://www.usenetarchives.com/view.php?id=net.wanted&mid=PDI0MkBjdmwuVVVDUD4 https://www.usenetarchives.com/view.php?id=net.wanted&mid=PD... more edit: considered the second oldest boxen reference in the usenet archive is esr himself, maybe he was the one pushing it :) https://www.usenetarchives.com/view.php?id=comp.sys.att&mid=PDFTRFNjNiM1UEQ1REs9ZXJpY0BzbmFyay51dS5uZXQ%2B https://www.usenetarchives.com/view.php?id=comp.sys.att&mid=...
  • Thorrez 5y ago
    >no one uses the term regex or regular expression in a programming context to mean a strictly regular language in the theoretical computer science sense. The RE2 library seems to: >loosely speaking, a regular language is a set of strings that can be matched in a single pass through the text using only a fixed amount of memory. https://github.com/google/re2/wiki/Syntax https://github.com/google/re2/wiki/Syntax Note that RE2 doesn't support backreferences.
  • firechickenbird 5y ago
    Regular expressions are Regular Languages, thus equivalent to deterministic finite state automata. These languages have very interesting properties due to their regularity (eg. pumping lemma), and they are a very small strict subset of Context-Free languages, which are also a strict subset of Turing-Complete languages. If you add recursion and backtracking to RegExps you easily go outside the Regular Languages class, and you probably end up in the TC class. Now you are dealing with an undecidable machine which is also very hard to define and reason about (and you also have two more problems). What's the point of calling it regular?
    • nickelpro 5y ago
      I'm hitting Poe's Law here, are you joking? Your average coding bootcamp kid cracking away in node and invoking the builtin regex engine has no idea what any of those words mean. To those programmers the words "regular expression" have become completely separated from their original etymology in lexical analysis. To them a regex means "input to a regex engine", and thus the term "use a regular expression" means "use a regex engine". It could be "use a froofroo boingo", for all the meaning the words hold. "Regular expression" just became the vernacular due to its origination in lexical analysis.
      • firechickenbird 5y ago
        Wow, I have no idea what regexps mean? I can write a book about regexps, and if you really want to learn what regexps are, let me know, we can scedule a session. Anyway, real REGUALR expressions belong to the regular languages class, thus equivalent to DFAs. Given a regexp, you can construct a DFA in O(2^n), where n is the number of operators in the regexp. Now this DFA will have a Linear time complexity match. If you extend regular expressions with backreferences, you can't build DFAs anymore, and you also lose the fundamental property of regularity: the pumping lemma for regular languages. Furthermore, the languages you can build with this extension go even outside the context-free class. Not only that: you are also dealing with an NP-complete matching. Again, why do you still call them regular?
        • 5y ago
  • bspammer 5y ago
    This isn’t entirely a pedantic thing. Cloudflare had an outage a couple of years ago which was caused by someone not knowing the difference: https://blog.cloudflare.com/details-of-the-cloudflare-outage-on-july-2-2019/ https://blog.cloudflare.com/details-of-the-cloudflare-outage...
• polski-g 5y ago
  I wish everytime an application said "regular expression" it meant PCRE. People say sed supports RE but it's so divorced from PCRE I end up using `| perl -pe ....`
• rurban 5y ago
  So left recursive is not regular, so not a language? Every simple language is defined recursively. Regularity just defines it as terminating, to avoid the simplicity of recursion. DFA is the absurdity, not NFA.
  • colanderman 5y ago
    What are you talking about? "Not a language?" "DFA is the absurdity?" I'm sorry, I don't follow.
    • rurban 5y ago
      read for example about the state explosion of DFA's: "It is important because NFAs can be used to reduce the complexity of the mathematical work required to establish many important properties in the theory of computation. For example, it is much easier to prove closure properties of regular languages using NFAs than DFAs." https://en.m.wikipedia.org/wiki/Nondeterministic_finite_automaton https://en.m.wikipedia.org/wiki/Nondeterministic_finite_auto... but more importantly look at the various attempts to the solve backtracking "problem" (stack overflow by unbounded recursion), as done recently in perl and pcre, which led to more insecure AND more unmaintainable regex code by converting their simple recursion to iterations on the heap. first it got much slower, as the state is now handled on the heap, and second it got much more insecure as DOS attacks can now exhaust the whole heap, not just around 1024 stack depths. and third, it got 10x more complicated, and unreadable. ad language: you can of course define a language by forbidding left recursion, which yacc folks would prefer. but you can define it much easier with left recursive parsers, like 10x smaller. of course you can always expand simple NFA's to deterministic DFA's at the cost of exponential state explosion and increased complexity. but it is a monstrosity only impractical CS folks prefer. SW engineers prefer the similar, faster and more secure NFA backtracking versions, as long as you count the stack depth.
      • colanderman 5y ago
        As I mentioned elsewhere, linear performance is a hard requirement for some domains such as intrusion prevention. Unbounded recursion isn't the primary problem; exponential runtime is. If state-space explosion is a concern, you can implement a non-backtracking regular expression matcher using term rewriting. For true regular expressions, the size of the rewritten terms are a function of the size of the pattern (and thus performance is linear). For non-regular expressions, this does not hold.
• pxx 5y ago
  you can use the pumping lemma (https://en.wikipedia.org/wiki/Pumping_lemma_for_regular_languages https://en.wikipedia.org/wiki/Pumping_lemma_for_regular_lang...) to do this proof trivially. it'll look something like {1^x : x is prime} is not a regular language. suppose it is a regular language. then by the pumping lemma there exists a p such that every string of length at least p can be written as w = xyz, where |y| >= 1, |xy| <= p [not an important observation for this proof], and we can "pump" a new string w' = xy^nz (for any n > 0) and have w' remain in L. let p' be the prime immediately above p. then the string w = 1^p' is in the language L and must be "pumpable" for some N = |y| > 0. Choose the number of times we "pump" (n in the expression xy^nz) to be p'. Then that would imply w' = 1^(p' + p' * N) is in the language L, a contradiction, as p' + p' * N has factors p' and (1 + N). Note we can also use the CFL pumping lemma to prove that this particular language is not context-free either; if we choose s = uvwxy, we can still just pump p' times; the new string just is of size p' * (1 + |v| + |x|), and |v| + |x| > 0.
  • colanderman 5y ago
    Fantastic! It's been 15 years since I've had to do those proofs, I'll use your proof to refresh my memory how they work.
  • thaumasiotes 5y ago
    > we can "pump" a new string w' = xy^nz (for any n > 0) While this is certainly true, I would prefer to note that n ≥ 0. n > 0 is just a special case of that. (You can see clearly that 0 repetitions will always be valid by considering the proof of the pumping lemma: since a regular expression is recognized by a finite state machine, the only way to recognize a string of length exceeding the (finite!) number of states in the machine is to visit some states more than once, which means traveling around a cycle in the state graph. The 'pumpable substring' of the pumping lemma is a path through such a cycle, and repeating it zero times corresponds to traveling around the cycle zero times. The rest of the path is just as valid as always.)
  • Capira 5y ago
    this is why I love hackernews
  • 5y ago
• petmon 5y ago
  "A Perl regexp, sure." is not part of the grammar of English because it lacks a verb.
  • 867-5309 5y ago
    perhaps you meant "does not follow". only the loose rules are "part of" besides, "it is" is implied in that sentence, so there's your verb
  • xigoi 5y ago
    Natural languages don't have a formal grammar.
• DyslexicAtheist 5y ago
  as the saying goes if your only tool is a hammer ... perl/regexp is obviously the wrong tool for the job. Finding new prime numbers, minting bitcoin, running seti@home, is what C++ exceptions have been invented for.
  • colejohnson66 5y ago
    Coming soon: “Mining Bitcoin at Compile Time using constexpr”
• tromp 5y ago
  While we're nitpicking, it doesn't check for prime numbers either. It checks for composite length.