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

Thomas Lord lord at emf.net
Sat Sep 15 18:45:45 EDT 2007

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)

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.


More information about the Snow-users-list mailing list