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

Thomas Lord lord at emf.net
Sun Sep 16 00:07:30 EDT 2007


I should also warn, and Shiro pretty much also said
as much:

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

-t


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
> stuff.
>
>
> 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.
>
> -t
>
>
>
> 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
>>
>>
>>
>>
>>
>>
>>   
>
> ------------------------------------------------------------------------
>
> _______________________________________________
> Snow-users-list mailing list
> Snow-users-list at iro.umontreal.ca
> https://webmail.iro.umontreal.ca/mailman/listinfo/snow-users-list
>   



More information about the Snow-users-list mailing list