[Snow-users-list] high-priority snow packages and package naming
lord at emf.net
Sun Sep 16 00:07:30 EDT 2007
I should also warn, and Shiro pretty much also said
Things like POSIX subexp position matching are
"just" a backtracking search that uses "true regular
expressions" as leaf nodes -- but don't underestimate
the high level of detail in getting it right. It's a tricky
algorithm and I'd be happy to explain it if things reach
a point where that becomes useful. (That's the only way
I got it: someone had to explain it to me.)
Thomas Lord wrote:
> 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".
> Snow-users-list mailing list
> Snow-users-list at iro.umontreal.ca
More information about the Snow-users-list