5 ms·

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 comp

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...

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...