5 ms·

That's not a true Regular Expression: it uses back-tracking, and to the author's credit, he notes that in the article. True regular expressions can't recognize

by bediger 16y ago

That's not a true Regular Expression: it uses back-tracking, and to the author's credit, he notes that in the article. True regular expressions can't recognize primes. It's important to keep these kind of distinctions in mind for two reasons. First, without clear, precisely defined categories of formal languages, you'll fail to recognize unsolvable (or undecidable) problems and waste a lot of time. Personally, I put "malware dectection" in this category, as determining whether a given file constitutes a virus seems equivalent to solving the halting problem. Second, sloppy usage like using "Regular Expression" for something else is one of those common usage issues that allow people to argue based on the name ("regular expression") to lure the unsuspecting in, but then fall back on extreme technicalities to trick people into agreeing with the argument when they might not otherwise have agreed. A lot like I've done in this comment.

eru 16y ago
To see some genuine regular expression trickery, see https://github.com/matthiasgoergens/Div7/blob/master/regex7 https://github.com/matthiasgoergens/Div7/blob/master/regex7 for a regular expression that recognizes decimal numbers that are divisible by 7. If you memorize that expression, you have a handy way to tell whether a number is divisible by 7.
- jarin 16y ago
  Boy, and I've been doing it the hard way all this time (num % 7 == 0).
- shasta 16y ago
  It's much easier to remember and apply the corresponding finite state machine, where you just keep track of the remainder mod 7 that you've seen thus far. Example: 48193. What's the remainder mod 7? 48 mod 7 = 6 -- First two digits 61 mod 7 = 5 -- Remainder thus far, appending next digit 59 mod 7 = 3 -- Remainder thus far, appending next digit 33 mod 7 = 5 -- Remainder thus far, appending next digit No more digits, so the answer is 5. (Edit: I did figure that you were almost certainly being sarcastic. I just wanted to point out that in its corresponding FSM form, we've memorized the transitions as children.)
  - eru 16y ago
    Yes, that's much easier. My comment wasn't meant to be serious. Check out how long that regular expression is. (Though it can be simplified further.) I actually generated the regular expression linked by compiling the finite state machine.
  - pronoiac 16y ago
    You're doing all the work of dividing by 7. There are shortcuts to checking divisibility [1] - 2, 3, 5, & 9 have the easiest shortcuts - but 7 is a complicated case, which I'd probably just divide out anyway. [1] http://en.wikipedia.org/wiki/Divisibility_rule#Divisibility_by_7 http://en.wikipedia.org/wiki/Divisibility_rule#Divisibility_...
    - eru 16y ago
      No, he's not doing the work of dividing by seven. That would need memory of around the same size as your number of digits of your input number. His state machine only reads one digit at a time and only needs to store a less-than-one-digit state. My regular expression is a joke on the usual divisibility rules. By the way, you can find your own divisibility rules. They are actually easy to find and prove, if you know a bit about cyclic groups / calculating with modulo. E.g. the rule for divisibility by F in hexadecimal is the same as the one for 9 in decimal. Divisibility by 11 or 101 or 1001, or 9, 99, 999 is also really simple.
- deleted 16y ago
  [deleted]
- robinhouston 16y ago
  A little while ago I wrote some Javascript code to compute a regular expression for deciding divisibility by any number, in any base: http://s3.boskent.com/divisibility-regex/divisibility-regex.html http://s3.boskent.com/divisibility-regex/divisibility-regex....
  - eru 16y ago
    You can find my Haskell version under https://github.com/matthiasgoergens/Div7/ https://github.com/matthiasgoergens/Div7/
lmkg 16y ago
I agree with you to a certain extent, but I think it's also important to realize that, just as languages evolve and dialects diverge, technical jargon evolves and diverges into dialects as well. To a large class of programmers, the non-DFA perl-type regex is more common and more important than the formally defined regular expression. The overlap is inconvenient, for exactly the reasons you state, and I wish it didn't exist, but it's unrealistic to expect one camp or the other to abandon their ingrained term for a common concept. For my part, I use "regular expression" for the DFA-expressible grammar and "regex(en)" for the string-processing facility. The most important thing is clarity, and as long as you're being clear about which type of regular expression you're talking about, the double-meaning may be twitch-inducing but it doesn't impede communication.
- eru 16y ago
  That's a reasonable convention. (Another less reasonable one, is to use the term `Frankenxpression'.)
- lloeki 16y ago
  Indeed I do the same kind of distinction with the exact same naming convention. Now this does not detract to the fact that this regex is quite elegant in its simplicity and we often assume our hardware+software stack to be actual Turing machines. Call me paranoid but finding such a simple expression and seeing it validate a number being a prime in such record times should have raised some alarms. Indeed, removing the "optimization" makes computing times go through the roof.
  - lukeschlather 16y ago
    I think you've completely missed the point of the exercise. This is not about optimization. It's about having a deep knowledge of how Perl-style regular expressions work.
    - lloeki 16y ago
      Sorry, this was not my intention to mean so: I used "optimization" for lack of finding the correct word regarding the role of the PCRE setting. My point was that the quickness of the initial results was fishy enough to doubt of the correctness of those results (and hence diving into regex engine probing), even before finding actual false positives.
Wilfred 16y ago
> determining whether a given file constitutes a virus seems equivalent to solving the halting problem. In fact (for a sufficiently rigorous definition of virus), it is provably the case that we cannot determine whether a file is a virus, using an argument very similar to a halting problem proof. You might be interested in 'Computer viruses: theory and experiments' by Fred Cohen for the full working-out of the proof.
- bediger 16y ago
  Thanks for the tip on the Fred Cohen paper. I have seen arguments to the effect that since a virus doens't run with an infinite memory, you can indeed determine whether a disk file represents a virus or not. As Alfred North Whitehead once said: "Necessity is the mother of invention" is a silly proverb. "Necessity is the mother of futile dodges" is much nearer the truth."
- derefr 16y ago
  Viruses are really a matter of computer action given user intent—and therefore are able to be solved not just by detection of incongruous computer action, but also by detection of incongruous user intent. For example, imagine that instead of WIMP, all interactions with a computer occurred through a hierarchical, task-based UI (similar to, e.g., emacs org-mode) where you had to specify a high-level goal you wanted to accomplish before you could set about running programs to do it. If the computer knows that what you want to get done doesn't involve deleting files, then any program you run that does delete files has either been executed in error, or is acting not according to the user's command.
  - dexen 16y ago
    > If the computer knows that what you want to get done doesn't involve deleting files, then any program you run that does delete files has either been executed in error, or is acting not according to the user's command. Tell that the authors of certain popular PDF reader software, currently version X. Which, on the surface at least, has only one goal: display content of a PDF file. But scratch the surface and you note it may involve creation of temporary file of sorts. And perhaps loading additional libraries every now and then. And perhaps executing code contained in the document (if it's a form with validation code, for example). There are countless ways of achieving a goal, and which is better depends on situation. Pinning everything down to some one-true-way won't do. And expressing the possibilities is, well, designing & programming. With the usual assortment of bugs, up to and including vulnerabilities. So no, you can't have a secure system / virus detection based on user stating general high-level goal.
vog 16y ago
From the article: > The regex relies on backtracking and thus would not work with a DFA-based engine So the author already stated that strictly speaking, those are not true Regular Expressions. However, it would have been nice if he had stated this more clearly.
pufuwozu 16y ago
I read your comment and decided to do read up on some theory behind it. I came across this: http://cstheory.stackexchange.com/q/448/4052 http://cstheory.stackexchange.com/q/448/4052 From the highest rated answer: Larry Wall proposed that we use "regular expression" for the formalism Kleene proposed, and "regex" for expressions for the widely used extensions. It's a fairly widely followed convention. If you want to make it clear that you are talking about regular expressions in the formal languages sense, it is usually not difficult to translate into talk of regular languages.

by bediger 16y ago

eru 16y ago

To see some genuine regular expression trickery, see https://github.com/matthiasgoergens/Div7/blob/master/regex7 https://github.com/matthiasgoergens/Div7/blob/master/regex7 for a regular expression that recognizes decimal numbers that are divisible by 7. If you memorize that expression, you have a handy way to tell whether a number is divisible by 7.

jarin 16y ago
Boy, and I've been doing it the hard way all this time (num % 7 == 0).
shasta 16y ago
It's much easier to remember and apply the corresponding finite state machine, where you just keep track of the remainder mod 7 that you've seen thus far. Example: 48193. What's the remainder mod 7? 48 mod 7 = 6 -- First two digits 61 mod 7 = 5 -- Remainder thus far, appending next digit 59 mod 7 = 3 -- Remainder thus far, appending next digit 33 mod 7 = 5 -- Remainder thus far, appending next digit No more digits, so the answer is 5. (Edit: I did figure that you were almost certainly being sarcastic. I just wanted to point out that in its corresponding FSM form, we've memorized the transitions as children.)
- eru 16y ago
  Yes, that's much easier. My comment wasn't meant to be serious. Check out how long that regular expression is. (Though it can be simplified further.) I actually generated the regular expression linked by compiling the finite state machine.
- pronoiac 16y ago
  You're doing all the work of dividing by 7. There are shortcuts to checking divisibility [1] - 2, 3, 5, & 9 have the easiest shortcuts - but 7 is a complicated case, which I'd probably just divide out anyway. [1] http://en.wikipedia.org/wiki/Divisibility_rule#Divisibility_by_7 http://en.wikipedia.org/wiki/Divisibility_rule#Divisibility_...
  - eru 16y ago
    No, he's not doing the work of dividing by seven. That would need memory of around the same size as your number of digits of your input number. His state machine only reads one digit at a time and only needs to store a less-than-one-digit state. My regular expression is a joke on the usual divisibility rules. By the way, you can find your own divisibility rules. They are actually easy to find and prove, if you know a bit about cyclic groups / calculating with modulo. E.g. the rule for divisibility by F in hexadecimal is the same as the one for 9 in decimal. Divisibility by 11 or 101 or 1001, or 9, 99, 999 is also really simple.
deleted 16y ago
[deleted]
robinhouston 16y ago
A little while ago I wrote some Javascript code to compute a regular expression for deciding divisibility by any number, in any base: http://s3.boskent.com/divisibility-regex/divisibility-regex.html http://s3.boskent.com/divisibility-regex/divisibility-regex....
- eru 16y ago
  You can find my Haskell version under https://github.com/matthiasgoergens/Div7/ https://github.com/matthiasgoergens/Div7/

lmkg 16y ago

I agree with you to a certain extent, but I think it's also important to realize that, just as languages evolve and dialects diverge, technical jargon evolves and diverges into dialects as well. To a large class of programmers, the non-DFA perl-type regex is more common and more important than the formally defined regular expression. The overlap is inconvenient, for exactly the reasons you state, and I wish it didn't exist, but it's unrealistic to expect one camp or the other to abandon their ingrained term for a common concept. For my part, I use "regular expression" for the DFA-expressible grammar and "regex(en)" for the string-processing facility. The most important thing is clarity, and as long as you're being clear about which type of regular expression you're talking about, the double-meaning may be twitch-inducing but it doesn't impede communication.

eru 16y ago
That's a reasonable convention. (Another less reasonable one, is to use the term `Frankenxpression'.)
lloeki 16y ago
Indeed I do the same kind of distinction with the exact same naming convention. Now this does not detract to the fact that this regex is quite elegant in its simplicity and we often assume our hardware+software stack to be actual Turing machines. Call me paranoid but finding such a simple expression and seeing it validate a number being a prime in such record times should have raised some alarms. Indeed, removing the "optimization" makes computing times go through the roof.
- lukeschlather 16y ago
  I think you've completely missed the point of the exercise. This is not about optimization. It's about having a deep knowledge of how Perl-style regular expressions work.
  - lloeki 16y ago
    Sorry, this was not my intention to mean so: I used "optimization" for lack of finding the correct word regarding the role of the PCRE setting. My point was that the quickness of the initial results was fishy enough to doubt of the correctness of those results (and hence diving into regex engine probing), even before finding actual false positives.

Wilfred 16y ago

> determining whether a given file constitutes a virus seems equivalent to solving the halting problem. In fact (for a sufficiently rigorous definition of virus), it is provably the case that we cannot determine whether a file is a virus, using an argument very similar to a halting problem proof. You might be interested in 'Computer viruses: theory and experiments' by Fred Cohen for the full working-out of the proof.

bediger 16y ago
Thanks for the tip on the Fred Cohen paper. I have seen arguments to the effect that since a virus doens't run with an infinite memory, you can indeed determine whether a disk file represents a virus or not. As Alfred North Whitehead once said: "Necessity is the mother of invention" is a silly proverb. "Necessity is the mother of futile dodges" is much nearer the truth."
derefr 16y ago
Viruses are really a matter of computer action given user intent—and therefore are able to be solved not just by detection of incongruous computer action, but also by detection of incongruous user intent. For example, imagine that instead of WIMP, all interactions with a computer occurred through a hierarchical, task-based UI (similar to, e.g., emacs org-mode) where you had to specify a high-level goal you wanted to accomplish before you could set about running programs to do it. If the computer knows that what you want to get done doesn't involve deleting files, then any program you run that does delete files has either been executed in error, or is acting not according to the user's command.
- dexen 16y ago
  > If the computer knows that what you want to get done doesn't involve deleting files, then any program you run that does delete files has either been executed in error, or is acting not according to the user's command. Tell that the authors of certain popular PDF reader software, currently version X. Which, on the surface at least, has only one goal: display content of a PDF file. But scratch the surface and you note it may involve creation of temporary file of sorts. And perhaps loading additional libraries every now and then. And perhaps executing code contained in the document (if it's a form with validation code, for example). There are countless ways of achieving a goal, and which is better depends on situation. Pinning everything down to some one-true-way won't do. And expressing the possibilities is, well, designing & programming. With the usual assortment of bugs, up to and including vulnerabilities. So no, you can't have a secure system / virus detection based on user stating general high-level goal.

vog 16y ago

From the article: > The regex relies on backtracking and thus would not work with a DFA-based engine So the author already stated that strictly speaking, those are not true Regular Expressions. However, it would have been nice if he had stated this more clearly.

pufuwozu 16y ago

I read your comment and decided to do read up on some theory behind it. I came across this: http://cstheory.stackexchange.com/q/448/4052 http://cstheory.stackexchange.com/q/448/4052 From the highest rated answer: Larry Wall proposed that we use "regular expression" for the formalism Kleene proposed, and "regex" for expressions for the widely used extensions. It's a fairly widely followed convention. If you want to make it clear that you are talking about regular expressions in the formal languages sense, it is usually not difficult to translate into talk of regular languages.