8 ms·

Fair point about the parenthetical, though I would say both the engine and the language are crucial, depending on what role you're playing in the system. The s

by chubot 6y ago

Fair point about the parenthetical, though I would say both the engine and the language are crucial, depending on what role you're playing in the system. The setup I think of: you have "domain experts" writing policies with regexes, software engineers who embed the engine in an application, and operators of the entire service. My usages of regexes for "big data" followed that pattern, and I imagine the DPI applications of Hyperscan do too. A lot of those rules are accumulated over time, are not easy to rewrite, and require testing. If you have a thousand regexes in one dialect painfully crafted over years, you can't just change the engine. It would break the whole application. So that is why I emphasize the language. Backtracking engines are more common, and the language and the "code" written in the language has to be changed before you can change the engine. That happened at least partially at Google 10+ years ago, migrating from PCRE to RE2. But yes, if you're an operator, you will be looking at it from the engine perspective. Obviously it is not enough to change the patterns themselves. (The backreference point is interesting, although I'll probably leave it out of my mental model until someone implements it :) ) ---- Also the point of Eggex is to treat regexes more abstractly, like a real language. Just like I don't write C++ code for GCC or Clang, I don't write regexes for a specific engine. I have ported regexes between engines many times. The typical application I've worked on uses multiple engines. Hell a one line shell script using grep and awk uses multiple engines!!! Tangent: reminds me of this paper: https://www3.cs.stonybrook.edu/~dongyoon/papers/FSE-19-LinguaFranca.pdf https://www3.cs.stonybrook.edu/~dongyoon/papers/FSE-19-Lingu...

glangdale 6y ago
This is very true. It was something I admit I found more than a bit irritating; a number of Hyperscan DPI customers just started regarding Hyperscan as a "fact of nature" and would simply start coding around weaknesses or avoiding patterns that didn't work as well. I would much have preferred that they complain and have us fix things for them. IMO there's still a lot of scope for a better regex engine; backtracking engines have a lot of expressiveness for better or worse and I'm not convinced that they are as bad as people say. Systems like Hyperscan are somewhat niche in that they throw a lot of stuff overboard in pursuit of scale (lots of regexes at once), performance and "streaming" (the ability to pause matching with a fixed-sized amount of context and restart). Despite its hype, RE2 is not that great either - it's a couple engines taped together with some fairly opinionated design policies that has become big enough to be a "fact of nature" at a big influential company ("I guess that's how a regex engine works").
- chubot 6y ago
  Hm I don't really think RE2 is even that influential (unfortunately IMO). Rust is the only new language whose engine borrows its design AFAIK. For example, I was disappointed to learn that Julia uses PCRE. ---- I think backtracking is firmly in the past because it causes too many problems in practice [1], but I think there's scope for a text matching engine that's built on top of regular languages, but more expressive. As mentioned here and on lobste.rs recently, regular languages aren't expressive enough for syntax highlighting (or lexing most programming languages in their entirety). But it doesn't take much to make them more expressive, WHILE meaning these properties: 1. linear-time and constant space 2. Composition by OR Backtracking fails at both properties. Backtracking is bad. Like you say with backreferences, there should be something more expressive than regular languages that maintains both properties (and it's likely to be useful). Example of tiny mechanism on top of regular languages: When Are Lexer Modes Useful? http://www.oilshell.org/blog/2017/12/17.html http://www.oilshell.org/blog/2017/12/17.html https://lobste.rs/s/m24zv1/xi_editor_retrospective#c_p3zadg https://lobste.rs/s/m24zv1/xi_editor_retrospective#c_p3zadg ----- Here's an implementation idea for such a text matching engine: (1) Start with re2c, because it has some different scaling properties than other engines https://news.ycombinator.com/item?id=23665569 https://news.ycombinator.com/item?id=23665569 The compile time and code size are linear with respect to the number of patterns. What was very surprising to me is that the compiled C code starts off slower than interpreters, but scales better as you increase the number of patterns. (2) Write a WebAssembly backend for it. Compiling its C output to WebAssembly is not likely to be great, because it uses gotos on every line, and gotos in WebAssembly need the Relooper algorithm last time I checked. (3) Now add a linear-space constant-time VM on top. As a test of this property, it should be able to express LL(1) parsing and LALR(1) parsing. Something like "lexer modes" should also fall out trivially. I believe this strategy saves a bunch of work, and has some desirable properties: - an entire RE front end, handling captures and such in DFAs: https://arxiv.org/abs/1907.08837 https://arxiv.org/abs/1907.08837 . I'm sure re2c is slower than Hyperscan, but as you hint, I think it's also more general and widely used. - wasm could be more palatable to embed than other VMs. There are multiple implementations of it. - wasm avoids dealing with C code and assembly code. It has a few high quality JITs. - The first version of wasm has a ton of limitations (lack of GC, rich interfaces to the host), but this application hits none of them. It's a perfect problem for it. (I'm also pretty sure this hasn't been done, but I could be wrong. I googled "re2c wasm" and found that it is used in some wasm tools, but I think that's unrelated: https://chromium.googlesource.com/external/github.com/WebAssembly/wabt/+/binary_0xc/README.md https://chromium.googlesource.com/external/github.com/WebAss... ) And it's also significantly different than RE2 or rust/regex, if that's your complaint :) If any of that is interesting feel free to contact me at any method listed here: http://www.oilshell.org/ http://www.oilshell.org/ (email, zulip, etc.) ----- [1] https://lobste.rs/s/m24zv1/xi_editor_retrospective#c_pyfpv1 https://lobste.rs/s/m24zv1/xi_editor_retrospective#c_pyfpv1
davisjam314 6y ago
---- Tangent: I am the author of the Lingua Franca paper. I hope you enjoyed it!
- chubot 6y ago
  Yes, it was very interesting, and related to my Eggex subproject (of the Oil shell, "our upgrade path from bash"): http://www.oilshell.org/release/latest/doc/eggex.html http://www.oilshell.org/release/latest/doc/eggex.html Basically the idea is to compile a new syntax to multiple engines. It's embedded in a shell and has a seamless upgrade path: http://www.oilshell.org/release/latest/doc/eggex.html#example-of-pattern-reuse http://www.oilshell.org/release/latest/doc/eggex.html#exampl... I'd be interested in your feedback on it! I think it's very related to Lingua Franca but if you disagree I'm also interested in that :) I think most "new language" projects are rightly met with skepticism, but the difference with Oil is that is emphasizes a transition path, and it's embedded in a significant piece of work (i.e. there are other projects like this, including ones from myself, but ironically I didn't want the extra dependency) Although I guess the obvious criticism is that Eggex almost entirely syntactic. If two regex engines have the same syntax but different semantics, it doesn't help you. But I have not found that to be a big issue in decades of using multiple engines, although admittely it relates to the subset of regexes I use. Eggex is more like a union of engines than an intersection, so maybe that's something to change ...

by chubot 6y ago

glangdale 6y ago

This is very true. It was something I admit I found more than a bit irritating; a number of Hyperscan DPI customers just started regarding Hyperscan as a "fact of nature" and would simply start coding around weaknesses or avoiding patterns that didn't work as well. I would much have preferred that they complain and have us fix things for them. IMO there's still a lot of scope for a better regex engine; backtracking engines have a lot of expressiveness for better or worse and I'm not convinced that they are as bad as people say. Systems like Hyperscan are somewhat niche in that they throw a lot of stuff overboard in pursuit of scale (lots of regexes at once), performance and "streaming" (the ability to pause matching with a fixed-sized amount of context and restart). Despite its hype, RE2 is not that great either - it's a couple engines taped together with some fairly opinionated design policies that has become big enough to be a "fact of nature" at a big influential company ("I guess that's how a regex engine works").

chubot 6y ago
Hm I don't really think RE2 is even that influential (unfortunately IMO). Rust is the only new language whose engine borrows its design AFAIK. For example, I was disappointed to learn that Julia uses PCRE. ---- I think backtracking is firmly in the past because it causes too many problems in practice [1], but I think there's scope for a text matching engine that's built on top of regular languages, but more expressive. As mentioned here and on lobste.rs recently, regular languages aren't expressive enough for syntax highlighting (or lexing most programming languages in their entirety). But it doesn't take much to make them more expressive, WHILE meaning these properties: 1. linear-time and constant space 2. Composition by OR Backtracking fails at both properties. Backtracking is bad. Like you say with backreferences, there should be something more expressive than regular languages that maintains both properties (and it's likely to be useful). Example of tiny mechanism on top of regular languages: When Are Lexer Modes Useful? http://www.oilshell.org/blog/2017/12/17.html http://www.oilshell.org/blog/2017/12/17.html https://lobste.rs/s/m24zv1/xi_editor_retrospective#c_p3zadg https://lobste.rs/s/m24zv1/xi_editor_retrospective#c_p3zadg ----- Here's an implementation idea for such a text matching engine: (1) Start with re2c, because it has some different scaling properties than other engines https://news.ycombinator.com/item?id=23665569 https://news.ycombinator.com/item?id=23665569 The compile time and code size are linear with respect to the number of patterns. What was very surprising to me is that the compiled C code starts off slower than interpreters, but scales better as you increase the number of patterns. (2) Write a WebAssembly backend for it. Compiling its C output to WebAssembly is not likely to be great, because it uses gotos on every line, and gotos in WebAssembly need the Relooper algorithm last time I checked. (3) Now add a linear-space constant-time VM on top. As a test of this property, it should be able to express LL(1) parsing and LALR(1) parsing. Something like "lexer modes" should also fall out trivially. I believe this strategy saves a bunch of work, and has some desirable properties: - an entire RE front end, handling captures and such in DFAs: https://arxiv.org/abs/1907.08837 https://arxiv.org/abs/1907.08837 . I'm sure re2c is slower than Hyperscan, but as you hint, I think it's also more general and widely used. - wasm could be more palatable to embed than other VMs. There are multiple implementations of it. - wasm avoids dealing with C code and assembly code. It has a few high quality JITs. - The first version of wasm has a ton of limitations (lack of GC, rich interfaces to the host), but this application hits none of them. It's a perfect problem for it. (I'm also pretty sure this hasn't been done, but I could be wrong. I googled "re2c wasm" and found that it is used in some wasm tools, but I think that's unrelated: https://chromium.googlesource.com/external/github.com/WebAssembly/wabt/+/binary_0xc/README.md https://chromium.googlesource.com/external/github.com/WebAss... ) And it's also significantly different than RE2 or rust/regex, if that's your complaint :) If any of that is interesting feel free to contact me at any method listed here: http://www.oilshell.org/ http://www.oilshell.org/ (email, zulip, etc.) ----- [1] https://lobste.rs/s/m24zv1/xi_editor_retrospective#c_pyfpv1 https://lobste.rs/s/m24zv1/xi_editor_retrospective#c_pyfpv1

davisjam314 6y ago

---- Tangent: I am the author of the Lingua Franca paper. I hope you enjoyed it!

chubot 6y ago
Yes, it was very interesting, and related to my Eggex subproject (of the Oil shell, "our upgrade path from bash"): http://www.oilshell.org/release/latest/doc/eggex.html http://www.oilshell.org/release/latest/doc/eggex.html Basically the idea is to compile a new syntax to multiple engines. It's embedded in a shell and has a seamless upgrade path: http://www.oilshell.org/release/latest/doc/eggex.html#example-of-pattern-reuse http://www.oilshell.org/release/latest/doc/eggex.html#exampl... I'd be interested in your feedback on it! I think it's very related to Lingua Franca but if you disagree I'm also interested in that :) I think most "new language" projects are rightly met with skepticism, but the difference with Oil is that is emphasizes a transition path, and it's embedded in a significant piece of work (i.e. there are other projects like this, including ones from myself, but ironically I didn't want the extra dependency) Although I guess the obvious criticism is that Eggex almost entirely syntactic. If two regex engines have the same syntax but different semantics, it doesn't help you. But I have not found that to be a big issue in decades of using multiple engines, although admittely it relates to the subset of regexes I use. Eggex is more like a union of engines than an intersection, so maybe that's something to change ...