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

Thomas Lord lord at emf.net
Fri Sep 14 19:38:17 EDT 2007


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



More information about the Snow-users-list mailing list