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

Thomas Lord lord at emf.net
Sat Sep 15 22:51:38 EDT 2007

A big win about the explicit DFA-based API (though,
again, probably impractical for Snow, just now) is that
if you have that, then you can efficiently use regexps to
scan text that is not contiguous in memory (I didn't sketch
the API quite right to make that clear, sorry).    E.g., you
can stream in stuff very fast, scanning buffers using the DFA,
and driving your protocol engine that way.   Very fun

For fun: people should gleefully note the woes of Cisco
regarding regexps as reported on Slashdot today.   I don't
mean we should celebrate a nasty bug just that we should be
encouraged that investing in the engineering effort to make
really solid regexp engines has high social value.


Shiro Kawai wrote:
> From: Thomas Lord <lord at emf.net>
> Subject: Re: [Snow-users-list] high-priority snow packages and package naming
> Date: Sat, 15 Sep 2007 15:45:45 -0700
>> Please, no such thing as match structures.   They are a botched design
>> in Posix and Perl -- pure legacy.   Simulate them, better, in portable
>> scheme atop a "true regular expression" back-end.
> +1 for Tom Lord.
> Submatches not only twist engine implementation, but also there are
> incompatibilities in edge cases between implementations that can
> bite you some day, for exmaple:
> - If a capturing group matches more than once, which part of the
>   string should be a "submatch"?  The first one matching the group,
>   the last one?  Or every one of them should be saved and retrieved
>   as a list?  I think I've seen all three types.
> - If a capturing group may match an empty string, and it is inside
>   repetition, how should it match?  A naive implementation can yield
>   infinite loop, since it can match an arbitrary number of repetitions
>   of "empty string".   Perl engine and Ruby engine differ in the
>   interpretation of this case, though I don't remember the details.
> The advantage of having high-level stuff in Scheme is that we can
> set the semantics (or we can provide options) portably, instead
> of relying slighly differing underlying implementations and
> crossing our fingers to work.
> I'm not sure the performance impact (and not so optimistic as Tom,
> I guess), but if such portable high-level module is coming along,
> I'm willing to optimize Gauche's low-level regexp engine toward it.
> I heven't fully thought out Tom's suggested spec, but one concern
> is the representation of match position in string---Gauche doesn't
> like character index.  Internally Gauche's engine compiles given
> regexp in an FA that works for octet-stream, and it only calculates
> character index when requested (so, actually, in Gauche it may be
> faster to get matched substring rather than indices of a submatch,
> when the submatch is in the middle of a long mutibyte string.)
> It would be nice if the portable high-level layer assumes that
> the low-level engine returns implementation-dependent representation
> of matched positions, instead of "character index".
> --shiro

-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://webmail.iro.umontreal.ca/pipermail/snow-users-list/attachments/20070915/529a0881/attachment-0001.html 

More information about the Snow-users-list mailing list