Back in the Usenet days, questions came up all the time about matching substrings that do not contain whatever. It’s technically possible without an explicit NOT operator because regular languages are closed under complement — along with union, intersection, Kleene star, etc. — but a bear to get right by hand for even simple cases.
Unbounded lookarounds without performance penalty at search time are an exciting feature too.
2) password generator from regex constraints (16+ chars, at least on upper case char, etc). Just take the intersection of all constraints and generate random matches from that:
The author mentions that they found Mamouras et al. (POPL 2024), but not the associated implementation. While the Rust implementation is not public, a Haskell implementation can be found here: https://github.com/Agnishom/lregex
This is very interesting. I'm a bit skeptical about the benchmarks / performance claims because they seem almost too good to be true but even just the extended operators alone are a nice improvement over existing regex engines.
The post mentions they also have a native library implemented in Rust without dependencies but I couldn't find a link to it. Is that available somewhere? I would love to try it out in some of my projects but I don't use .NET so the NuGET package is of no use to me.
I love regular expression derivatives. One neat thing about regular expression derivatives is they are continuation-passing style for regular expressions. The derivative is "what to do next" after seeing a character, which is the continuation of the re. It's a nice conceptual connection if you're into programming language theory.
Low-key hate the lack of capitalization on the blog, which made me stumble over every sentence start. Great blog post a bit marred by unnecessary divergence from standard written English.
It's your personal style. Researchers have their quirks, don't listen to the industry suits saying dumb shit like "it's unprofessional" you can mask if you're looking for a job at Google in the future, but for now enjoy being yourself and say fuck you to the lazy socially imposed dogma of this particular community
> how does RE# find the leftmost-longest match efficiently? remember the bidirectional scanning we mentioned earlier - run the DFA right to left to find all possible match starts, then run a reversed DFA left to right to find the ends. the leftmost start paired with the rightmost end gives you leftmost-longest. two linear DFA scans, no backtracking, no ambiguity.
I'm pretty sure that should say "the leftmost start paired with the leftmost end".
This also implies that the algorithm has to scan the entire input to find the first match, and the article goes on to confirm this. So the algorithm is a poor choice if you just want the first match in a very long text. But if you want all matches it is very good.
F# is one of the biggest 'What could have beens'. Great language, that just didn't hit the right time, or reach critical mass of the gestalt of the community.
I convinced one boss to let me spike out a project with it. I was in love with OCaml at the time. OCaml's docs are... I'm just going to say it, they're terrible. F# on the other hand, has fantastic docs. In the end, the only real gripe I had was the significant whitespace. I'm just not a fan.
Worth mentioning (haven’t checked if the paper talks about this) that while the industry mostly forgot about derivatives and extended REs (i.e. REs with intersection and negation), academia did not. Unfortunately, there have been some pretty discouraging results: the DFA for an extended RE (including a lazy DFA implemented using derivatives, as here) is worst-case doubly exponential in the length of the expression[1], not just exponential as for normal REs. So there is a potential reason not to support intersections in one’s RE matcher, even if they are enticingly easy to implement in terms of derivatives (and even if I personally like to see experimentation in this direction).
It should be possible to directly compile this library to native code and use it in any other language. Maybe adding some C-style wrappers will be needed.
OMRN is a regex compiler that leverages Common Lisp's compiler to produce optimized assembly to match the given regex. It's incredibly fast. It does omit some features to achieve that, though.
Calling this RE# (resharp), when there is a much more popular and established product already named R# (ReSharper, by JetBrains) in the. NET world will probably hurting your SEO and/or could potentially cause some legal grief.
Don has always been the language design BDFL, but has ensured it was community driven since at least 2012.
In all practicality the team at Microsoft has always been the main drivers of the F# project. It comes with the territory when you’re the primary group maintaining the compiler, core library, SDK, FSI, and Editor integrations.
One thing I don't understand is what does _* mean? It seems like the paper refers to .* (which I understand) and _* (which I don't) in sometimes the same context? Normally _* would mean "an underscore zero or more times".
29 comments
[ 3.7 ms ] story [ 64.1 ms ] threadFYI some code snippets are unreadable in 'light mode' ("what substrings does the regex (a|ab)+ match in the following input?")
https://ieviev.github.io/resharp-webapp/
Back in the Usenet days, questions came up all the time about matching substrings that do not contain whatever. It’s technically possible without an explicit NOT operator because regular languages are closed under complement — along with union, intersection, Kleene star, etc. — but a bear to get right by hand for even simple cases.
Unbounded lookarounds without performance penalty at search time are an exciting feature too.
1) regex equivalence checker (check if intersection of complements is empty):
https://gruhn.github.io/regex-utils/equiv-checker.html
2) password generator from regex constraints (16+ chars, at least on upper case char, etc). Just take the intersection of all constraints and generate random matches from that:
https://gruhn.github.io/regex-utils/password-generator.html
The post mentions they also have a native library implemented in Rust without dependencies but I couldn't find a link to it. Is that available somewhere? I would love to try it out in some of my projects but I don't use .NET so the NuGET package is of no use to me.
Low-key hate the lack of capitalization on the blog, which made me stumble over every sentence start. Great blog post a bit marred by unnecessary divergence from standard written English.
Why do people do this? They capitalize names, so clearly their shift key works. Do they do it feel special or like some sort of rebel?
i see enough slop and Look At Me on a daily basis. i don't want it to look like an ad or a LinkedIn post in 2026.
> how does RE# find the leftmost-longest match efficiently? remember the bidirectional scanning we mentioned earlier - run the DFA right to left to find all possible match starts, then run a reversed DFA left to right to find the ends. the leftmost start paired with the rightmost end gives you leftmost-longest. two linear DFA scans, no backtracking, no ambiguity.
I'm pretty sure that should say "the leftmost start paired with the leftmost end".
This also implies that the algorithm has to scan the entire input to find the first match, and the article goes on to confirm this. So the algorithm is a poor choice if you just want the first match in a very long text. But if you want all matches it is very good.
[1] https://www.sciencedirect.com/science/article/pii/S030439751...
- https://github.com/telekons/one-more-re-nightmare
- https://applied-langua.ge/posts/omrn-compiler.html
OMRN is a regex compiler that leverages Common Lisp's compiler to produce optimized assembly to match the given regex. It's incredibly fast. It does omit some features to achieve that, though.
Don Syme seem to no longer be acting as the project lead, and I didn't hear of any successor
Compared to most actively developed languages F# look very stale currently
In all practicality the team at Microsoft has always been the main drivers of the F# project. It comes with the territory when you’re the primary group maintaining the compiler, core library, SDK, FSI, and Editor integrations.