Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

RE#: how we built the fastest regex engine in F#

iev.ee

Post reply on HN
Print view View original

61–70 of 90 posts

Re: RE#: how we built the fastest regex engine in F#

#61

Post by spankalee »

noelwelsh wrote: post #16

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 se…

It's so uncomfortable to read.

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?

Re: RE#: how we built the fastest regex engine in F#

#62

Post by ieviev »

noelwelsh wrote: post #16

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 se…

While i completely understand it, the lack of capitalization is just an indication that a human wrote this, it has to be imperfect

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.

Re: RE#: how we built the fastest regex engine in F#

#63

Post by trashface »

spankalee wrote: post #61
noelwelsh wrote: post #16

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 se…

It's so uncomfortable to read. 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?

Maybe they drafted it on a phone where capitalization is harder. My guess is the all-lowercase world is mostly people who do most of their text creation on phones and similar, not keyboards.

Re: RE#: how we built the fastest regex engine in F#

#64

Post by [deleted] »

someplaceguy wrote: post #51
mananaysiempre wrote: post #28

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]…

> 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 The authors seem to claim linear complexity: > the result is RE#, the first general-purpose regex engine to support intersection and complement with linear-time guarantees, and also the overall fastest regex engine on a large set of benchmarks

[deleted]

Re: RE#: how we built the fastest regex engine in F#

#65

Post by layer8 »

ieviev wrote: post #60
btown wrote: post #56

Earlier quoted context omitted.

> The second time the same (or similar) input is used these states are already created and it is linear. Does this imply that the DFA for a regex, as an internal cache, is mutable and persisted between inputs? Could this lead to subtle denial-of-service attacks, where inputs are chosen by an attacker to steadily increase the cached complexity - are there eviction techniques to guard against this? And how might this w…

Yes, most (i think all) lazy DFA engines have a mutable DFA behind a lock internally that grows during matching. Multithreading is generally a non-issue, you just wrap the function that creates the state behind a lock/mutex, this is usually the default. The subtle denial of service part is interesting, i haven't thought of it before. Yes this is possible. For security-critical uses i would compile the full DFA ahead…

> Multithreading is generally a non-issue, you just wrap the function that creates the state behind a lock/mutex, this is usually the default.

But you also have to lock when reading the state, not just when writing/creating it. Wouldn’t that cause lock contention with sufficiently concurrent use?

Re: RE#: how we built the fastest regex engine in F#

#66

Post by layer8 »

trashface wrote: post #63
spankalee wrote: post #61

Earlier quoted context omitted.

It's so uncomfortable to read. 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?

Maybe they drafted it on a phone where capitalization is harder. My guess is the all-lowercase world is mostly people who do most of their text creation on phones and similar, not keyboards.

I don’t really see how capitalization is harder on phones, I do it all the time.

Re: RE#: how we built the fastest regex engine in F#

#67

Post by layer8 »

ieviev wrote: post #62
noelwelsh wrote: post #16

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 se…

While i completely understand it, the lack of capitalization is just an indication that a human wrote this, it has to be imperfect 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.

I’m sorry, but omitting capitalization is slop as well, just not AI slop. I can’t read text like that for any length of time, it’s just super crappy.

Re: RE#: how we built the fastest regex engine in F#

#68

Post by noelwelsh »

ieviev wrote: post #62
noelwelsh wrote: post #16

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 se…

While i completely understand it, the lack of capitalization is just an indication that a human wrote this, it has to be imperfect 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.

No one will mistake your posts for LinkedIn slop. You actually have something to say, with coherent arguments presented in paragraphs containing multiple sentences.

If you want sentences without capitalization to be your thing, then go for it. It's just a weird hill to die on, taking away from the readability of your posts for no real reason.

Re: RE#: how we built the fastest regex engine in F#

#69

Post by ieviev »

layer8 wrote: post #65
ieviev wrote: post #60

Earlier quoted context omitted.

Yes, most (i think all) lazy DFA engines have a mutable DFA behind a lock internally that grows during matching. Multithreading is generally a non-issue, you just wrap the function that creates the state behind a lock/mutex, this is usually the default. The subtle denial of service part is interesting, i haven't thought of it before. Yes this is possible. For security-critical uses i would compile the full DFA ahead…

> Multithreading is generally a non-issue, you just wrap the function that creates the state behind a lock/mutex, this is usually the default. But you also have to lock when reading the state, not just when writing/creating it. Wouldn’t that cause lock contention with sufficiently concurrent use?

No, we do not lock reading the state, we only lock the creation side and the transition table reference stays valid during matching even if it is outdated.

Only when a nonexistent state is encountered during matching it enters the locked region.

Re: RE#: how we built the fastest regex engine in F#

#70

Post by ngruhn »

gbacon wrote: post #11

That’s beautiful work. Check out other examples in the interactive web app: 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…

I built a similar library in TypeScript (also based on regex derivatives). You can really built cool tools with complement / intersection. E.g.

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

Post reply on HN