Hacker News Reader

Comment by dan-dev | Hacker News Reader

Yes and straighforwardly so if you use character classes as your basic building blocks. Here I implemented a Haskell implementation that is easily extandable to include complements: https://github.com/dan-blank/hgrep-smallcore (I like this project because it translates ERE compliant regexes - sans negated character sets - down to only 4 constructs, one of which being character classes). It implements https://www.ccs.neu.edu/home/turon/re-deriv.pdf, character classes are described in 4.2.

I actually had complement in it as a 5th construct, but when the submission came closer and the examiners found some errors in my logic (my fault for not writing good enough unit tests!), I took complement out again when cleaning the project up.

View on HN

I tried to test your program because I'm pretty sure your techniques can't be used in a general purpose regex engine. (I've long wanted to make use of regex derivatives somehow, but I don't think it's feasible because of the downsides of building up a full DFA.) More to the point, I also suspected that you might be using a sparse representation for transitions in your DFA if the alphabet of your DFA is indeed all of Unicode. This is also problematic because it tends to make search time quite a bit slower.

In any case, I built your program with 'stack install' but got this when I tried to use it with Unicode:

    $ hgrep-exe '^\pL{42}$' OpenSubtitles2018.raw.sample.en
    hgrep-exe: Maybe.fromJust: Nothing

I get the same for '\w{42}'. Hmm, maybe you don't support counted repetitions? OK, '\w' works, but is it Unicode aware?

    $ echo 'β' > /tmp/beta
    $ echo 'b' /tmp/b
    $ hgrep-exe '\w' /tmp/beta
    $ hgrep-exe '\w' /tmp/b
    $

Hmmm, no, but '\w' doesn't seem to work at all... I can't seem to get much working:

    $ hgrep-exe '[a-z]' /tmp/b
    $ hgrep-exe 'b' /tmp/b
    b

OK, so a simple literal search works.

I don't know. I'm not sure how to do a Unicode stress test with your tool.

Thank you for trying out my tool!

Not that this was just an university project that is far from polished, and certainly not fast!

* I don't think it supports '\w' - is that part of the ERE? (otherwise I will lower my claim in the project description)

* Repetition works like this: {1,3}, did not add the syntactic sugar

---------

My setup:

me:~/hgrep-smallcore$ echo 'awd え bbb c' > test

me:~/hgrep-smallcore$ /home/me/.local/bin/hgrep-exe 'f' test

me:~/hgrep-smallcore$ /home/me/.local/bin/hgrep-exe 'b{1,3}' test

awd え bbb c

me:~/hgrep-smallcore$ /home/me/.local/bin/hgrep-exe 'え' test

awd え bbb c

I think you should probably cut out the ERE thing entirely. Or maybe say it's "inspired" by ERE. Otherwise, it's not really that close at all. Notice that not even 'hgrep-exe '[a-z]' /tmp/b' worked for me either. That's certainly in EREs. So are things like '[[:word:]]', which also doesn't seem to work. There's also collating symbols and equivalence classes and some other junk.

But upon looking at the POSIX ERE spec, yes, it looks like technically things like \w, \d and \s are not in it. But most ERE implementations, including both BSD grep and GNU grep, support constructs like \w. (Yet another reason to cast a suspicious eye on folks who obsess about portability. Portability means following a spec, not using whatever your tool lets you do. And most tools let you do far more than what's in the spec because the spec---especially one like POSIX---is usually divorced from the reality of what's useful.)

I understand your tool is a university project. The main point I'm trying to drive home here is that there are folks in this thread that seem to not be keen on acknowledging engineering challenges and are instead only looking at the theory. Unicode, for example, is an enormous engineering challenge. It's not difficult because getting it correct is difficult, it's difficult because making it correct and fast is not straight-forward. As you show, using a naive representation (sparse transitions, hash sets for states) will give you correctness without much complexity. But that's not usually what we mean when we talking about supporting Unicode in general purpose regex engines. Because "general purpose" means folks expect it to be minimally fast.

Ah! I was only referring to ERE as specced by POSIX, yes.

> It's not difficult because getting it correct is difficult, it's difficult because making it correct and fast is not straight-forward.

It seems to me that you take my project as a proxy for whether regex derivations are a feasible way to deal with unicode-ready regexes that also support complements and so on. That was not my intention, I was merely attempting to show an easy implementation of regex derivations that can deal with unicode and can be extended to support complements. With this project and the paper I linked, it seems to me that answering whether this particular kind of constructing regex DFAs is a possible way to achieve what you are looking for or not should be rather straightforward.

(To my last knowledge, a regex complement is not easy to add in the presence of extra features like backtracing and lookahead.)

> With this project and the paper I linked, it seems to me that answering whether this particular kind of constructing regex DFAs is a possible way or not should be rather straightforward.

Yes, you're correct. It just isn't that interesting because it will fall over in any kind of real practical usage. :-) Full disclosure, I'm the author of ripgrep, so I have some particularly relevant experience in the specific domain of making regexes work well for the masses. (It also forms my bias with what I care about.)

Like I said, I wasn't necessarily trying to pick on you. There are others in this thread that are seemingly ignoring the engineering challenges, and only looking at the theory. Then using that as a basis to proclaim that regex engines are "stuck" in the 80s/90s.

Consider my perspective here: if someone pipes up and says, "yeah hey it is actually easy to add those kinds of features to regex engines." Well, then, it's important to include the caveats with that. That's what I see as my role in this thread. Otherwise, it looks like general purpose regex engines are crippled for no apparent reason.

Oh well, first of, thank you for writing ripgrep! Great work, love that tool and use it daily :)

All good, thank you for sharing your POV! I find both theory and the practical engineering feats quite interesting, and actually understood the original question as a theoretical question, not a question about general-purpose regex engine. Quite possibly that this is even how the asking person was intending it, in hindsight.

Last thing on topic (talking now about having complement and unicode in a usable regex engine): My personal, gut-feeling-based hunch is that by adding all these features not strictly related to regular languages, we kind of evolved our regex enginges and expectations towards them into a corner of the design space that works well, but might not work well when one adds complement. It feels like a constructivist world without negation and stuff on top that works, and reverse-engineering what works with negation and what not will likely be hard work. As a theory-ish kind of person (without much insight into regexes or formal grammars), I wish there would be some kind of insight into what are the atoms of a regex and which atoms can be combined witch which other atoms - I would bet that fancyFeatures and unicode+complement would have a high algorithmic complexity already in theory.

Any final tipps on the repo I linked to not disappoint users expectations? :)

I think you got it right by putting "university project" in the description. :-) I wrote my fair share of projects like that too.

The incentive structure of academia that leads to software like that, though, is also a big reason why I left. The theory is super important (that's why I work on a regex engine that only provides support for regular languages), but I also think the engineering aspect is just as important. And academia, or at least the corner I was in, just did not care about the engineering side of things at all. This in turn leads to publishing results that are hard to reproduce, because if you don't share code that is at least somewhat robust, it's going to be very costly for someone else to build on your work.

Anyway, sorry about the side rant haha. But all good.

All good! And sorry for not making the effort to understand your position first, I want to work on that.

> The incentive structure of academia that leads to software like that, though, is also a big reason why I left. The theory is super important (that's why I work on a regex engine that only provides support for regular languages), but I also think the engineering aspect is just as important. And academia, or at least the corner I was in, just did not care about the engineering side of things at all. This in turn leads to publishing results that are hard to reproduce, because if you don't share code that is at least somewhat robust, it's going to be very costly for someone else to build on your work.

Totally get it. This also baffles me - papers in computer science that are hard to reproduce? Yes I know, publish or perish and all that BS. But I don't want to accept this: I mean I get it for psychology obviously, and then also material sciences and so on, but for compsci?... Next to proofs, programs are probably one of the most reproducible things that nature has given given us.

Good for me and many others that you cho(o)se to spend your time on building tools :)

Best not to get uppity on the subject of regexp when confronted with the great burntsushi… he can get irate.

> Full disclosure, I'm the author of ripgrep, so I have some particularly relevant experience in the specific domain of making regexes work well for the masses.

The unwashed ones?

> it looks like technically things like \w, \d and \s are not in [POSIX]

The relevant standard is UTS #18, it subsumes POSIX afaict. Do you think the same as me about it, namely that following and implementing it is essential?

We were talking about EREs, which are an artifact of POSIX, not UTS#18. So the relevant standard for this specific conversation is POSIX.

To redirect to UTS#18, I don't think UTS#18 subsumes POSIX. UTS#18 doesn't support [[=a=]] for example AFAIK. And UTS#18 more generally doesn't require locale support. UTS#18 Level 3 was actually removed from the spec, which is where "custom tailored" logic for specific locales used to live. On top of that, POSIX also specifies BREs which UTS#18 doesn't touch. So while there is overlap between POSIX and UTS#18, POSIX is not a strict subset of UTS#18. If you're speaking "conceptually" and less precisely, you can maybe say POSIX is subsumed by UTS#18 though. I don't really think about it that way though personally. They serve two different use cases that are still relevant today.

I think UTS#18 is a tortured document, but yes, the regex crate supports pretty much all of UTS#18 Level 1: https://github.com/rust-lang/regex/blob/master/UNICODE.md

Going beyond Level 1 is difficult.

Mostly irrelevant but those runtime errors are the main reason why I stopped using Haskell. Haskell is a great language with a great booming ecosystem, but if you can have uncaught exceptions in IO monads, and even unchecked errors in your pure code like that fromJust there, then what's the point? For all its ceremony is not much more functionally pure than JavaScript. And a language without purity as a concept like Rust has achieved frankly a more tight feeling of safety and great flexibility despite having a more simple typesystem. Imo Haskell has to drastically change like it did in the early 2000's to become competitive again.

I'm unconvinced by such things. From what I can tell, this is academia code. In academia code, regardless of programming language, folks often don't care about failure modes. (I speak from experience, as someone who used to be in academia.) So I'd be more inclined to pin it on academia's incentive structure than anything about programming languages.

I suppose you could use a programming environment that forbids partial functions, but I'm unclear on how productive that is.

> And a language without purity as a concept like Rust has achieved frankly a more tight feeling of safety and great flexibility despite having a more simple typesystem.

Haskell has 'fromJust' and Rust has 'unwrap'. They're both exactly equivalent and result in similarly poor failure modes. (Well, 'unwrap' usually at least gives you a line number.)

Yeah, but even better Rust has `except`, but that's besides the point. Rust doesn't pretend to by a pure language, it just promises to be a safe language as long as you don't use `unsafe`. Haskell makes a big fuss about how it's pure and productive because you have fewer bugs. And this is true as long as you're writing pure data processing or algorithmic code. But as soon as you stray from that and try to build a practical program, you'll need the IO monad and it sucks, even Java deals better with exceptions than Haskell. All the type class expressiveness in the world, and they couldn't figure out how to model exceptions. And it used to be that Haskell could just introduce backwards incompatible changes because it was a research language. But now Haskell is used widely in production, and even though it's in desperate need of a new Prelude, it's not gonna happen.

When someone who truly believed in that Haskell could be a proper modern programming tool and invested their hard work and frankly their genius into it, they Haskell leadership responded with skepticism and inaction. I bet if you gave Snoyman full dictatorship over a new Haskell prelude, it would be the best general purpose programming language by a mile for the next decade at least. Instead Haskell will remain as backwards as its ISO 8859-1 String type.

Yeah I think you're going places I don't care to follow. We were talking about a specific program, and I made the argument that the behavior of the program was more sharply determined by the incentive structure in which it was written. But you're kind of doubling down into a more general rant about Haskell that is actually totally divorced from the failure mode of the Haskell program in question.

I used to use Haskell too and I stopped using it for $reasons. Nothing to do with the prelude or its string type though. More about the nature of the language and paradigm itself.

Hold on! See: https://github.com/dan-blank/hgrep-smallcore/issues/1 Using `fromJust` is deeply frowned upon, and indeed a few eyebrows were raised then showing my code to the examiners. This and a handful other warts unfortunate, but few and easy to work around.

This function and others are in the prelude, but one can use other preludes that don't have these escape hatches.

This does not undermine the huge benefits that people get from having IO checked by the typesystem. Just as having tyepcasting in a language does not undermine the benefits of types in that language.

IO isn't checked by the type system if errors aren't checked by the type system. Haskell could be better, Haskell should have been better.

Nah, the type system is perfectly fine in this case: "Given (Just someValue), return someValue". Exactly what happened here, the precondition just was not fulfilled and I left the case dealing the unfulfilled precondition undefined. If one cares about such things, one should simply use one of the numerous alternative Preludes out there (to make sure to actually never use fromMaybe, head and the 3 other functions that nobodoy uses form the standard Prelude) and turn the warnings for incomplete pattern matches on. At least, thats how you could deal with it in real life.

If it is not practical matters that are the concern here, there are more than enough languages that only allow total functions and offer other sweet stuff. Haskell's main purpose was to be a lazy-by-default-language, and that people can actually write practical stuff in it is a nice side-effect.

Reply on news.ycombinator.com