noprompt

> "But I don't think they address the problem inherent in Frak - there's no way to insure that the expression gives the intended result against an arbitrary input."

I've made sure to thoroughly test the patterns produced by frak. They've also passed muster with another project where frak has proven to be a good idea (see this issue https://github.com/guns/vim-clojure-static/pull/28). While they are not full optimized (yet), I'm fairly sure they are correct. If you have found a counter example, please open an issue.

> "The results with "barber" are indeterminate since the input string "bar" matches (^bar$) as well as (bar)."

The next point release will allow users to specify an exact match. Initially, this wasn't an option because Clojure has two functions `re-find` and `re-match` for relaxed and strict matches respectively.

  user> (re-find #"bar" "barber")
  "bar"
  user> (re-find #"^bar$" "barber")
  nil

> "I think VerbalExpressions suffers from a bit of the same conceptual problem as Frak - though perhaps to a lesser degree."

There is nothing conceptually wrong with what VerbalExpressions or frak attempt to do. They may not provide value to everyone, but they are useful contributions and have tangible benefits.

> "That problem is treating Regular Expressions as something other than the formal description of a language."

Why is that a problem?

It has been shown it's possible to use regular expressions as a means to perform arithmetic. Is that too a problem?

I don't think so.

Formality is a great thing and necessary. But it can also be the opposite. While I'll agree understanding it is important, I'll contend getting hung up on it is dangerous.

> "But that's what a regular expression is used for - testing an arbitrary string for membership within the set of valid strings of the language formally described by the regular expression."

Formally yes. And if it were always more performant to use a regular expression for this task, I would encourage the use of this tool to do so. However, depending on the data structure containing the strings, it may be more performant to simply search that.

> "it is one character longer than what was produced"

It's not about the length of the pattern that matters. Rather, it's the performance characteristics of the underlying state machine once the expression is compiled.

> "Why not use the simplest possible syntactic sugar?"

  (?:Clojure|Clojars|ClojureScript)

While this is certainly easier to read and understand, it will have performance drawbacks when using an NFA engine where backtracking is a real thing. It will also have a larger number of states when compared with the alternative.

  Cloj(?:ure(?:Script)?|ars)

Suppose I am interested in testing if "ClojureScript" is a member of the set of strings described by the first expression. To be in a final state I will have to enter no fewer than 25 states and backtrack twice. With the second expression I will only need to enter 13 states before being in a final state and will not backtrack at all.

For small patterns the choice to use something like frak is arguably splitting hairs; you won't gain much other than you didn't have to write an expression. But for enormous patterns, like the one I share in the README, there are real benefits from the sort of optimization frak provides.

Apparently the Perl community has been doing this for years. :)

This is an excellent use case.

I would not use this as a replacement to test the membership of a string in a collection of strings. That's a terrible use case. I've done benchmarks comparing membership checking and regular expression testing and the former is almost always significantly faster and requires less overhead.

With regard to ranges, it's another one of the areas I have yet to look in to. The question you have to answer is: will [r-z] generate fewer states?

As far as case insensitivity, well, that's usually just an optional flag.

This isn't something I would recommend using for everyone. But it does have use cases that make it appealing and useful. The same thing could be said about VerbalExpressions.

While it's true `[:alpha:]|[:lower:]` (even better `([:alpha:]|[:lower:])` or just `[:alpha:]`) would work to match "foo", "bar", "baz", etc.; it would also match "turduken" or epsilon (""). This isn't always what you want.

One nice thing about generating a regular expression in this manor, is it's arguably much easier to maintain. Instead of having a heavy pattern to refactor or, god help you, append to, you simply add another string to your list and be on your way. Plus you get the potential memory savings and performance benefits.

In the case of VerbalExpressions, the `or` method could use the same technique as frak to improve the quality of the expressions it emits. While on the subject, VerbalExpressions could also borrow some good ideas from is Christophe Grand's regex library: https://github.com/cgrand/regex.

Edit: Forgot some colons.

These expansions are certainly possible and I'm planning to investigate whether they have performance benefits. One interesting discovery we made last weeks is that `(a|b|c)` actually produces a larger state table than `[abc]`. This was both the case for Java and Vim. While the performance gains are minute, nevertheless, they are gains.

I haven't checked if "a{4}", for example, is faster than "aaaa" or produces fewer states. But it's something I am interested in. I just haven't had enough time this week.

On it's way this week. See the reply above.

There will be a JavaScript version available this later week, both for nodejs and the browser. If you want to try out the command line version see issue #2 for instructions.

Actually, frak doesn't generate patterns that require an exact match. I use Clojure's `re-matches` function (for exact matches) in the example and the tests to show and ensure the generated patterns work as expected. Clojure has another function called `re-find` which is a bit more relaxed. An expression like #"bar" will fail with the string "barn" using `re-matches` but succeed with re-find. I plan to include an option for generating regexes that require exact matches.

Isn't that more or less the same as what it already does? That is by telling frak which words you want to match you're implying you don't want to match anything else.

Of course, you could generate two patterns; one with the words you do want to match and the other with words you don't. Then simply handle the logic in your program.

Because that's not why I wrote frak. Originally, I wrote it to help eliminate backtracking and, indirectly, minimize the state table of two enormous regular expressions within Vim's Clojure syntax file (the README has a link in the "Why?" section by the way).

Vim uses an NFA style engine and it was obvious to me that backtracking with these patterns would be an issue. Since we went to such great lengths to provide the most accurate regular expression highlighting possible for Clojure, which is pretty damn accurate, I figured we might as well try to make it performant. It turns out our efforts were not in vain.

Have a look at this pull request: https://github.com/guns/vim-clojure-static/pull/28.

This is interesting. Thank you for sharing the link to this paper.

At the moment I believe I have something that looks similar Figure 1, however, the algorithm is nothing to write home about. I wrote the initial version one afternoon and didn't do a tremendous amount of research regarding the problem. In fact, most of the commits I've made to the project have been to the README! I definitely would like to work towards something that more closely resembles Figure 2 and emit the most optimal regular expression possible. Naturally that means I would be rewriting most of it. :)

Again, thanks for sharing this.