4 ms·

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

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 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 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.

burntsushi 4y ago
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.
- tinco 4y ago
  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.
  - dan-dev 4y ago
    Hold on! See: https://github.com/dan-blank/hgrep-smallcore/issues/1 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.
    - tinco 4y ago
      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.
      - dan-dev 4y ago
        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.
  - burntsushi 4y ago
    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.)
- dan-dev 4y ago
  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
  - burntsushi 4y ago
    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.
    - bmn__ 4y ago
      > 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?

burntsushi 4y ago

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.

tinco 4y ago
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.
- dan-dev 4y ago
  Hold on! See: https://github.com/dan-blank/hgrep-smallcore/issues/1 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.
  - tinco 4y ago
    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.
    - dan-dev 4y ago
      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.
- burntsushi 4y ago
  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.)
dan-dev 4y ago
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
- burntsushi 4y ago
  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.
  - bmn__ 4y ago
    > 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?