[Snow-users-list] high-priority snow packages and package naming

Thomas Lord lord at emf.net
Fri Sep 14 19:23:01 EDT 2007


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




More information about the Snow-users-list mailing list