Another point of evidence and then I'll shut up, really I will:
In Rx I have a true regular expression core and then a Posix search algorithm that calls out to that. An unusual aspect of the C code here is that it very clearly involves an ad hoc C-based implementation of one-shot continuations. This is part of why I think it would pay off hugely, in terms of utility, to just move all that weird stuff up into Scheme where you can express it directly and clearly.
-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@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@iro.umontreal.ca https://webmail.iro.umontreal.ca/mailman/listinfo/snow-users-list