5 ms·

The 1960's elegance behind Go's regexp

32 points by Dawny33 10y ago

ggambetta 10y ago
"[A regex is] a style of describing character strings. If a string successfully describes a regex, then it is called a match" Shouldn't that be "if a regex successfully describes a string"? I'm confused.
cestith 10y ago
I stopped reading when a post in 2017 compared anything to perl 5.8.7 which is older than what CentOS 5 shipped. Perl 5.8.x was EOL in 2008. 5.10 was EOL in 2009. The currently maintained versions are 5.22.3 and 5.24.1 and major redesign, refactoring, and rework has been done in the system including the regex parser. It went in the meantime from being a primarily recursive, backtracking NFA to using a DFA when possible, being primarily iterative, and only recursing when necessary. Anyone intentionally picking a more than decade old version whose major version line was end-of-life nearly a decade ago to compare to their new hotness has completely invalidated the evidence for their arguments. All the great things the slides might say may still be true, but they are unsupported by these charts.
- lexpar 10y ago
  I don't think the author 'intentionally' picked it. Like all the other graphics in the presentation, it looks to have been sourced from somewhere else. Edit: https://swtch.com/~rsc/regexp/regexp1.html https://swtch.com/~rsc/regexp/regexp1.html All the graphics come from the above, and no mention of the original article it was taken from. Nice.
  - cestith 10y ago
    Plagiarism v. cherry-picking (or is that pit-picking in this case)... It's difficult to say which is the bigger ethical issue. Both are extremely dishonest and misleading.
moomin 10y ago
Seriously, can we stop fetishising old approaches and papers? Yes, there's some tricks we've missed along the way, but there's a thread of alchemical thinking in our community that is just plain unproductive.
- clock_tower 10y ago
  > there's a thread of alchemical thinking in our community You write that as if Lisp isn't the Philosopher's Stone. :)
  - moomin 10y ago
    LOL. Yeah, The Clojure community has a bit of that as well, but it's married to a genuine interest in stealing great ideas from new papers and other languages.
- kaosjester 10y ago
  It would be easier to take this comment seriously if Go wasn't a modern re-implementation of ALGOL 68.
  - Ericson2314 10y ago
    60s regex with 60s language. Hmm, I wonder which area (regular language parsing or programming theory) has seen more research since then :D.
- papaf 10y ago
  I think your argument would have more weight if this presentation wasn't sharing the front page with the story about a 9.6 inch IPad that has 100s of comments. What Apple does next is a tech fetish. Personally, I'd rather read about regexps. We have a word for reading about old techniques where I am from -- we call it "learning".
- kmicklas 10y ago
  > Seriously, can we stop fetishising old approaches and papers? The entire existence of Go is predicated on fetishizing old approaches, unfortunately.
harpocrates 10y ago
The article by Russ Cox [0] (from which the initial Perl vs. Thompson NFA graph is taken) is a much more informative read. Also, I'm not sure why this always gets brought up as being a big deal: CS is all about making the right tradeoffs and I agree that sometimes there are cool tricks that let you _almost_ have your cake an eat it. But here, there is no such trick: backtracking has always been exponential and finite state automata have always been linear. No surprises. [0] https://swtch.com/~rsc/regexp/regexp1.html https://swtch.com/~rsc/regexp/regexp1.html
- wohlergehen 10y ago
  Respectively exponential or linear in the input size. The NFA in exchange is exponential in the states (or rather, it's deterministic counterpart is).
- btilly 10y ago
  There are some more gotchas. The finite state automata can potentially be exponential in the size of the regular expression you feed it. (Its states are set of states in the NFA.) Subexpression matching is more complex to implement and can make that exponential superexponential. (You have to go from sets of states to ordered sets of states.) And these catastrophic expressions get much easier when you add in lookaheads, look behinds, and so on.
- lobster_johnson 10y ago
  The lack of lookahead is a pain in Go's regexp engine, and this cascades to the various apps that use it, such as Prometheus and Kubernetes. Mainly, it means it's super awkward — arguably so awkward it's completely impractical, because the result ends up being unreadable and probably slow — to do negative matching, i.e. exclusion.
- glangdale 10y ago
  Full disclosure - I work on the Hyperscan project at Intel github.com/01org/hyperscan Regular expression implementation is fun and many interesting things have been done in this area. We are partial to the work of Gonzalo Navarro (in terms of summary papers) and the Glushkov construction, which predates the Thompson NFA construction and IMO is better in a number of ways for fast implementation. I quite enjoyed the Russ Cox posts, but they are a very partial and idiosyncratic picture of regular expression implementation. RE2 is one point in the automata-style regex implementation space; Hyperscan is another, and there a bunch of other distinct and interesting approaches (e.g. the work from the Parabix guys, various hardware and GPGPU implementations, etc).
davidw 10y ago
Looks like Tcl has been doing it right for a while...
stymaar 10y ago
Slightly off-topic: BurntSushi wrote a Go binding[1] for the Rust regex engine[2] (he is also the author) which shares the same approach (finite automata) but has a more polished, highly optimized implementation. It could be useful in some scenario for people facing performance issues with Go's regex engine. [1] https://github.com/BurntSushi/rure-go https://github.com/BurntSushi/rure-go [2] https://github.com/rust-lang/regex https://github.com/rust-lang/regex
gumby 10y ago
TL;DR we use a subset of today's common regexps which allowed us to go lightning fast (as long as you don't need lookahead). Oh, and I'll neglect to be clear about that. Nothing wrong in making the tradeoff but I didn't see it in the text.
deleted 10y ago
[deleted]
jhallenworld 10y ago
I think the Thompson NFA matcher could be pushed further if someone would bother to do it. One example is that since it finds all solutions to a given regular expression, it could be used within a larger backtracking matcher to support back-references. Consider: (a+)(a+)=\1 With an input like: aaaaa=aa The matcher will find these strings by the time it gets to the '=': (a)(aaaa)= (aa)(aaa)= (aaa)(aa)= (aaaa)(a)= Each match will end up as a separate still-existing thread in the Thompson matcher. Instead of pruning them as soon as possible, keep them and recursively match the rest of the string with the back-reference set in turn to each until a match is found.
- burntsushi 10y ago
  If I understand your idea right, then this is actually being done! https://github.com/google/fancy-regex https://github.com/google/fancy-regex
legulere 10y ago
I do not get why there still is so much of a hype for regular expressions. They are hard to read and maintain. They have a relatively large syntax. Edge-cases are easy to get wrong with them.

32 points by Dawny33 10y ago

"[A regex is] a style of describing character strings. If a string successfully describes a regex, then it is called a match" Shouldn't that be "if a regex successfully describes a string"? I'm confused.

cestith 10y ago

I stopped reading when a post in 2017 compared anything to perl 5.8.7 which is older than what CentOS 5 shipped. Perl 5.8.x was EOL in 2008. 5.10 was EOL in 2009. The currently maintained versions are 5.22.3 and 5.24.1 and major redesign, refactoring, and rework has been done in the system including the regex parser. It went in the meantime from being a primarily recursive, backtracking NFA to using a DFA when possible, being primarily iterative, and only recursing when necessary. Anyone intentionally picking a more than decade old version whose major version line was end-of-life nearly a decade ago to compare to their new hotness has completely invalidated the evidence for their arguments. All the great things the slides might say may still be true, but they are unsupported by these charts.

lexpar 10y ago
I don't think the author 'intentionally' picked it. Like all the other graphics in the presentation, it looks to have been sourced from somewhere else. Edit: https://swtch.com/~rsc/regexp/regexp1.html https://swtch.com/~rsc/regexp/regexp1.html All the graphics come from the above, and no mention of the original article it was taken from. Nice.
- cestith 10y ago
  Plagiarism v. cherry-picking (or is that pit-picking in this case)... It's difficult to say which is the bigger ethical issue. Both are extremely dishonest and misleading.

moomin 10y ago

Seriously, can we stop fetishising old approaches and papers? Yes, there's some tricks we've missed along the way, but there's a thread of alchemical thinking in our community that is just plain unproductive.

clock_tower 10y ago
> there's a thread of alchemical thinking in our community You write that as if Lisp isn't the Philosopher's Stone. :)
- moomin 10y ago
  LOL. Yeah, The Clojure community has a bit of that as well, but it's married to a genuine interest in stealing great ideas from new papers and other languages.
kaosjester 10y ago
It would be easier to take this comment seriously if Go wasn't a modern re-implementation of ALGOL 68.
- Ericson2314 10y ago
  60s regex with 60s language. Hmm, I wonder which area (regular language parsing or programming theory) has seen more research since then :D.
papaf 10y ago
I think your argument would have more weight if this presentation wasn't sharing the front page with the story about a 9.6 inch IPad that has 100s of comments. What Apple does next is a tech fetish. Personally, I'd rather read about regexps. We have a word for reading about old techniques where I am from -- we call it "learning".
kmicklas 10y ago
> Seriously, can we stop fetishising old approaches and papers? The entire existence of Go is predicated on fetishizing old approaches, unfortunately.

harpocrates 10y ago

The article by Russ Cox [0] (from which the initial Perl vs. Thompson NFA graph is taken) is a much more informative read. Also, I'm not sure why this always gets brought up as being a big deal: CS is all about making the right tradeoffs and I agree that sometimes there are cool tricks that let you _almost_ have your cake an eat it. But here, there is no such trick: backtracking has always been exponential and finite state automata have always been linear. No surprises. [0] https://swtch.com/~rsc/regexp/regexp1.html https://swtch.com/~rsc/regexp/regexp1.html

wohlergehen 10y ago
Respectively exponential or linear in the input size. The NFA in exchange is exponential in the states (or rather, it's deterministic counterpart is).
btilly 10y ago
There are some more gotchas. The finite state automata can potentially be exponential in the size of the regular expression you feed it. (Its states are set of states in the NFA.) Subexpression matching is more complex to implement and can make that exponential superexponential. (You have to go from sets of states to ordered sets of states.) And these catastrophic expressions get much easier when you add in lookaheads, look behinds, and so on.
lobster_johnson 10y ago
The lack of lookahead is a pain in Go's regexp engine, and this cascades to the various apps that use it, such as Prometheus and Kubernetes. Mainly, it means it's super awkward — arguably so awkward it's completely impractical, because the result ends up being unreadable and probably slow — to do negative matching, i.e. exclusion.
glangdale 10y ago
Full disclosure - I work on the Hyperscan project at Intel github.com/01org/hyperscan Regular expression implementation is fun and many interesting things have been done in this area. We are partial to the work of Gonzalo Navarro (in terms of summary papers) and the Glushkov construction, which predates the Thompson NFA construction and IMO is better in a number of ways for fast implementation. I quite enjoyed the Russ Cox posts, but they are a very partial and idiosyncratic picture of regular expression implementation. RE2 is one point in the automata-style regex implementation space; Hyperscan is another, and there a bunch of other distinct and interesting approaches (e.g. the work from the Parabix guys, various hardware and GPGPU implementations, etc).

davidw 10y ago

Looks like Tcl has been doing it right for a while...

stymaar 10y ago

Slightly off-topic: BurntSushi wrote a Go binding[1] for the Rust regex engine[2] (he is also the author) which shares the same approach (finite automata) but has a more polished, highly optimized implementation. It could be useful in some scenario for people facing performance issues with Go's regex engine. [1] https://github.com/BurntSushi/rure-go https://github.com/BurntSushi/rure-go [2] https://github.com/rust-lang/regex https://github.com/rust-lang/regex

gumby 10y ago

TL;DR we use a subset of today's common regexps which allowed us to go lightning fast (as long as you don't need lookahead). Oh, and I'll neglect to be clear about that. Nothing wrong in making the tradeoff but I didn't see it in the text.

deleted 10y ago

[deleted]

jhallenworld 10y ago

I think the Thompson NFA matcher could be pushed further if someone would bother to do it. One example is that since it finds all solutions to a given regular expression, it could be used within a larger backtracking matcher to support back-references. Consider: (a+)(a+)=\1 With an input like: aaaaa=aa The matcher will find these strings by the time it gets to the '=': (a)(aaaa)= (aa)(aaa)= (aaa)(aa)= (aaaa)(a)= Each match will end up as a separate still-existing thread in the Thompson matcher. Instead of pruning them as soon as possible, keep them and recursively match the rest of the string with the back-reference set in turn to each until a match is found.

burntsushi 10y ago
If I understand your idea right, then this is actually being done! https://github.com/google/fancy-regex https://github.com/google/fancy-regex

legulere 10y ago

I do not get why there still is so much of a hype for regular expressions. They are hard to read and maintain. They have a relatively large syntax. Edge-cases are easy to get wrong with them.