Hi Tom,
I'm confused -- I think Snow already "supports" SCSH, platform-wise. Unless you mean that SCSH's abstractions for processes and other shell objects should be separated out packaged? That reminds me, though -- what about a common interface for doing FFI stuff? That'd let us add bindings for any number of other languages / libraries (Snow support for GLib, anyone?)
But, yeah -- SREs! Shamefully enough, I wasn't aware of Olin Shivers' spec (http://www.ccs.neu.edu/home/shivers/papers/sre.txt) until just now. I really like the syntax, but it seems like he intended SREs to be used in conjunction with a Scheme platform's (e.g., SCSH) native regexp implementation / API... which sort of leaves us where we were. Any thoughts on Dorai Sitaram's portable regexp implementation (http://www.ccs.neu.edu/home/dorai/pregexp/pregexp.html)? - Hide quoted text -
On 9/14/07, Thomas Lord lord@emf.net wrote:
Julian Graham wrote:
Hi Schemers and Snow maintainers,
I'm curious as to whether there are any particular modules / functionality people really want to see ported to Snow. (I believe Kirill Lisovsky is working on getting SSAX packaged up.) How about a common API for regular expressions? SRFIs? (If so, any in particular?)
A probably crazy and too ambitious idea: SCSH (and SREs).
Those would be very good for duct-taping together systems that mix Scheme programs with other kinds of program in typical host environments.
-t
Afficher les réponses par date
Julian Graham wrote:
Hi Tom,
I'm confused -- I think Snow already "supports" SCSH, platform-wise. Unless you mean that SCSH's abstractions for processes and other shell objects should be separated out packaged? That reminds me, though -- what about a common interface for doing FFI stuff? That'd let us add bindings for any number of other languages / libraries (Snow support for GLib, anyone?)
I meant that SCSH should be factored out and the best practical approximation of a portable implementation be provided.
One strategy for a portable implementation might be to treat subprocesses and/or network connections as the ultimate primitive, and then to write a little portable (to unix-like systems) server than can execute simplified SCSH "process forms". I'm not sure it's worth the bother, though: SCSH requires a few system calls but that's essentially all it really requires.
But, yeah -- SREs! Shamefully enough, I wasn't aware of Olin Shivers' spec (http://www.ccs.neu.edu/home/shivers/papers/sre.txt) until just now. I really like the syntax, but it seems like he intended SREs to be used in conjunction with a Scheme platform's (e.g., SCSH) native regexp implementation / API... which sort of leaves us where we were. Any thoughts on Dorai Sitaram's portable regexp implementation (http://www.ccs.neu.edu/home/dorai/pregexp/pregexp.html)?
- Hide quoted text -
It will be too slow to be of much use on most implementations. Perhaps it has utility as a reference implementation.
The most practical thing for Snow would be to mostly avoid stacking up dependencies on the details of regexps and to make sure that systems that natively offer Posix or Perl regexps can take advantage of that. Sad but true.
-t
On 9/14/07, Thomas Lord lord@emf.net wrote:
Julian Graham wrote:
Hi Schemers and Snow maintainers,
I'm curious as to whether there are any particular modules / functionality people really want to see ported to Snow. (I believe Kirill Lisovsky is working on getting SSAX packaged up.) How about a common API for regular expressions? SRFIs? (If so, any in particular?)
A probably crazy and too ambitious idea: SCSH (and SREs).
Those would be very good for duct-taping together systems that mix Scheme programs with other kinds of program in typical host environments.
-t
Snow-users-list mailing list Snow-users-list@iro.umontreal.ca https://webmail.iro.umontreal.ca/mailman/listinfo/snow-users-list
It will be too slow to be of much use on most implementations. Perhaps it has utility as a reference implementation.
The most practical thing for Snow would be to mostly avoid stacking up dependencies on the details of regexps and to make sure that systems that natively offer Posix or Perl regexps can take advantage of that. Sad but true.
Yes, it probably is too slow.
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.?)
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
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
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.
Yes, fair enough.
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.
Right. So, working with the assumption (which I think is kind of reasonable) that most of the Scheme platforms that Snow supports are really just wrappers for a native POSIX implementation that present said implementation in some way consistent with the mores of that platform, I went through the list looking for a reasonable common subset of basic regexp functionality. So here's a proposal for a Snow regexp API --
(regexp-compile str) ;; Compile a string into a regexp object
;; Return a match object for a compiled regexp and a string, ;; (optionally) using explicit substring addressing (regexp-match pattern str [start] [end])
;; Perform regexp replacement on a string using a compiled ;; regexp -- replacement will first be inserted after first-match ;; and will be inserted for no more than max-matches matches. ;; [not sure if this is the right way to present this function...] (regexp-replace pattern str replacement [first-match] [max-matches])
(regexp? pattern) ;; type checking for compiled regexp objects
(regexp-match? match) ;; type checking for match structures
;; the number of matches in a match structure (regexp-match:count match)
;; the start index of match n (regexp-match:start match [n])
;; the end index of match n (regexp-match:end match [n])
What do people think?
Julian Graham wrote:
So here's a proposal for a Snow regexp API --
(regexp-compile str) ;; Compile a string into a regexp object
Fine, but specify the input language -- the regexp language. If you take my advice, it will have just *, |, [], and ()
It's ok if the Scheme binding has to translate from a portable true regular expression syntax into whatever the system uses natively (e.g., posix, perl, whatever).
;; Return a match object for a compiled regexp and a string, ;; (optionally) using explicit substring addressing (regexp-match pattern str [start] [end])
There should be no such thing as a "match object". If you want things like sub-exp positions, I'm saying don't use the posix re features for that or perl's --- write that stuff in Scheme, using the true regular expression matcher as the "inner loop".
;; Perform regexp replacement on a string using a compiled ;; regexp -- replacement will first be inserted after first-match ;; and will be inserted for no more than max-matches matches. ;; [not sure if this is the right way to present this function...] (regexp-replace pattern str replacement [first-match] [max-matches])
(regexp? pattern) ;; type checking for compiled regexp objects
(regexp-match? match) ;; type checking for match structures
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.
;; the number of matches in a match structure (regexp-match:count match)
;; the start index of match n (regexp-match:start match [n])
;; the end index of match n (regexp-match:end match [n])
What do people think?
I played with several APIs while I worked on Rx (a pretty heavy-duty regexp engine). I like:
(matches? compiled-pattern str [start [end]]) => boolean Does the entire string fit the pattern?
(find-start compiled-pattern str [start [end]]) => integer | #f Find the starting position (only) of the first match. This is computationally less complex than finding both the start and end positions and it is often useful just to have the start.
(find-match compiled-pattern str [start [end]]) => integer integer Find the leftmost-longest match
That's all you need to duplicate (and surpass) the functionality of full Posix regexps and Perl regexps using portable Scheme code. And, those are all easy to do on top of either a Perl or Posix engine.
Something you can't really do portably but that "would be nice" is to have a first class object for a match-in-progress. As in:
(define dfa (start-matcher compiled-pattern str [start [end]])) (advance-dfa-to-final-state! dfa) (can-continue? dfa) (final-state-indicates-match? dfa) (current-position dfa) etc.
Those kinds of primitives turn out to be *extremely* handy once you have them but there is no way to achieve them without doing some performance critical regexp-engine hacking -- so I doubt they could work in Snow at just this moment.
--------------- a little non-sequitor but while I'm thinking of it:
The huge, huge wins of using true regular expressions are, sure, you can use either a posix or perl back-end, and sure, it encourages the development of some useful scheme libraries layered on top but, also:
True regular expressions, in contrast to both Posix and Perl patterns in their general form, have very reliable performance characteristics and very modest memory requirements. They are a rock solid component that you can deploy with confidence in an application. The fancier regexp languages that are popular today are all flakey and hard to control -- they have pretty hard to predict or control performance in many common cases.
-t
Fine, but specify the input language -- the regexp language. If you take my advice, it will have just *, |, [], and ()
Sure, but most of the Scheme interpreters we're talking about already accept a broader regexp syntax (usually it's POSIX). And I thought we were going for performance -- meaning that a pass-thru to the interpreter's regexp API (which, in turn, is often a pass-thru to a native implementation -- glibc, etc.) is the way to go. Still, given that different interpreters accept different regexp "extensions," I agree that some normalization is required. How to do it, though, without actually implementing much regexp logic in this package?
It's ok if the Scheme binding has to translate from a portable true regular expression syntax into whatever the system uses natively (e.g., posix, perl, whatever).
Right -- I'd think it would even be desirable.
There should be no such thing as a "match object". If you want things like sub-exp positions, I'm saying don't use the posix re features for that or perl's --- write that stuff in Scheme, using the true regular expression matcher as the "inner loop".
Fair enough -- I'd just like to avoid situations in which there's no way to prevent the Scheme interpreter from doing a lot of work that we're just going to discard. E.g., I can't think of a way (besides memoization) to implement your (find-start ...) function on top of, say, Guile's regexp implementation (which is a pass-thru to glibc's native implementation) that doesn't involve the overhead of doing a complete match just to obtain the position of the first submatch. So, yeah, I agree that match structures are kind of bullshit, but the majority (maybe all) of the Scheme interpreters we're dealing with here produce them -- I think it's slightly less bullshit when they present a match as an S-expr of, say, (([start] . [end]) ([start] . [end]) ...). Given that the shitty, opaque match structures can be translated into these somewhat more useful S-exprs, well... you know, is that a palatable alternative?
That's all you need to duplicate (and surpass) the functionality of full Posix regexps and Perl regexps using portable Scheme code. And, those are all easy to do on top of either a Perl or Posix engine.
Easy, sure, but how efficient is it?
Julian Graham wrote:
Fine, but specify the input language -- the regexp language. If you take my advice, it will have just *, |, [], and ()
Sure, but most of the Scheme interpreters we're talking about already accept a broader regexp syntax (usually it's POSIX). And I thought we were going for performance -- meaning that a pass-thru to the interpreter's regexp API (which, in turn, is often a pass-thru to a native implementation -- glibc, etc.) is the way to go.
I'm trying to tell you something about the architecture of regexp matchers and why it (arguably -- again, the BS caution) matters.
To get from "true regular expressions" to POSIX or Perl regexps you write a back-tracking search engine that, in its "leaf node" evaluations calls out to a true-regular expression engine.
My bet is that if that backtracking search part is coded in portable Scheme atop nothing more than native "true regular expressions" then:
1. Yes, there's a *slight* performance hit, but not unbearable. 2. There's a huge gain in utility.
Going the other way and encouraging people to depend on either POSIX or Perl expressions is going to strand a lot of code under a pretty hefty dependency on ad hoc, legacy APIs and implementations of those APIs. True regular expressions hit a more "timeless" note.-t
Still, given that different interpreters accept different regexp "extensions," I agree that some normalization is required. How to do it, though, without actually implementing much regexp logic in this package?
Release early, release often. Just have the core package do nothing more than true regexps and hope that, later, intermediate things are filled in. I think you'll be surprised how just writing application code directly with true regular expressions works out nicely.
It's ok if the Scheme binding has to translate from a portable true regular expression syntax into whatever the system uses natively (e.g., posix, perl, whatever).
Right -- I'd think it would even be desirable.
Yes.
There should be no such thing as a "match object". If you want things like sub-exp positions, I'm saying don't use the posix re features for that or perl's --- write that stuff in Scheme, using the true regular expression matcher as the "inner loop".
Fair enough -- I'd just like to avoid situations in which there's no way to prevent the Scheme interpreter from doing a lot of work that we're just going to discard. E.g., I can't think of a way (besides memoization) to implement your (find-start ...) function on top of, say, Guile's regexp implementation (which is a pass-thru to glibc's native implementation) that doesn't involve the overhead of doing a complete match just to obtain the position of the first submatch.
Hehe. Some tricks:
Caution: I'm not *intimately* familiar with glibc's current internals so details will vary but, these are the right tricks to think about anyway.
Notice that the POSIX regexec function takes an argument for the output of match positions and subexpression match positions -- an array of "match data". And also notice that you pass an "nmatch" parameter that says how many of those subexpressions you want to know about (how big your array is).
The trick is that good matchers (I think glibc is one) are likely to be lazy in computing those match positions -- it won't but for the ones you ask for. You should get best-practical performance by asking just for the extent of the overall match.
Thus, you get a pretty good FIND-MATCH if you only ask for the overall extent of the match and, while it isn't quite optimal, you get a reasonable portable definition of FIND-START by running FIND-MATCH and discarding the second return value.
Ambitious implementors are unlikely to have profound difficulty optimizing FIND-START, if they choose to, even if they are mostly just using glibc or Rx or whatever.
So, yeah, I agree that match structures are kind of bullshit, but the majority (maybe all) of the Scheme interpreters we're dealing with here produce them -- I think it's slightly less bullshit when they present a match as an S-expr of, say, (([start] . [end]) ([start] . [end]) ...). Given that the shitty, opaque match structures can be translated into these somewhat more useful S-exprs, well... you know, is that a palatable alternative?
Don't try to maximize inclusion of every little "feature" in all the implementations. You just need a good basis set and then implementors can catch up by optimizing that basis set later.
That's all you need to duplicate (and surpass) the functionality of full Posix regexps and Perl regexps using portable Scheme code. And, those are all easy to do on top of either a Perl or Posix engine.
Easy, sure, but how efficient is it?
THAT is exactly the high risk question here. I have a very, very strong hunch that it's fast enough. This is based on my experience implementing this stuff in C in contexts where I was doing things like counting instructions and adding up cycles during optimization. I *think* it'll be fast enough. That's all I've got for ya. (We could get deeper into the tech internals of regexps but... I got a day job to keep up with :-)
-t
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
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
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@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
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
snow-users-list@iro.umontreal.ca