I should add to this, just as a hint, that the API assumed for true regular expressions should use explicit substring addressing. E.g., the procedure that searches for a match shouldn't always search the entire string -- it should search within a given range of positions (start...end or start...len).
-t
Thomas Lord wrote:
Julian Graham wrote:
Just so I understand, though, you mean that a Snow regexp package should present a standard interface that maps to whatever the native implementation is for the Snow host in use? Any preferences as to what that interface would look like? Going with Snow's least common denominator approach, what's the set of regexp features that all Snow hosts have in common? (Compiled vs. non-compiled regexps; submatches; replacement; etc.?)
You better understand that this is such an open-ended opinion swap that no matter what answer I give, betting money would likely be that my answer is bullshit.
That said....
A "true regular expression" is one that can be implemented by a finite state machine. This tiny subset of regexp languages has just literals:
a b c
iteration and alternatives:
c(a|d)(a|d)*r
Forget "backreferences" and "anchors" and "reluctant operators" and "look-ahead" and all of that other crap -- true regular expressions are what matter most. They are the most performance critical thing -- the code where good implementations are differentiated from average ones by the number of instructions in an inner loop.
Every regexp engine in the world -- Perl, Posix, whatever -- will give you its own best performance for the subset "true regular expressions" and, essentially, every single one of them will give the exact same results for the same inputs and patterns.
Here is something whose performance would not suck:
a portable Scheme library that assumed fast, native true regular expressions, but that then added all the fancier features, as in Dorai's thing or Shiver's thing.
(So, maybe Dorai's library isn't such a bad idea after all.. I haven't seen the internals, though.)
That's the way to do it. And, indeed, Scheme would absolutely *shine* at regexp-based backtracking search with lookahead/lookbehind/other-context-matching based on a fast primitive for true regular expressions.
-t