Re: SRFI-115 issues

[Alex Shinn <alexshinn@xxxxxxxxx>]

On Mon, Oct 21, 2013 at 6:37 AM, John Cowan <cowan@xxxxxxxxxxxxxxxx> wrote:

Alex Shinn scripsit:

> I've kept most IrRegex extensions, but made many of the non-POSIX
> ones optional, designated by the regexp-extended feature, and backref
> specifically gets its own feature regexp-backrefs.

This troubles me.  It leaves things too much up to the implementation,
and not enough flexibility for the user.  These extensions work only if
you have a backtracking NFA, which is inherently less efficient.  In
order to provide both efficiency and power, the implementation would
have to provide both an NFA (to be used in the general case) and a DFA
or Thompson-NFA (to be used if the extensions are not needed).  This is
what Perl does, but Perl is a rag-bag by nature.

I'd say: leave these things out of the main library, but add another
library that provides them but using the same API.  This way, the user
can load (srfi 115) or (srfi 115 extended) and get the most suitable
engine.  Of course, they can be the same engine if the implementer
doesn't care that much about speed.  If the user needs to load both,
using the R6RS/R7RS prefix feature makes both APIs available.

I think this is a recipe for confusion.  APIs will want to

allow regexps as parameters - which library should they

choose?

I actually need to separate the features better because

things like "non-greedy" repetitions can actually be

supported by non-backtracking implementations, "if" is

just a shortcut for "or" with a look-ahead, and I have to

think about whether it's possible for atomic/commit to

be supported without backtracking.

Ultimately with a little effort everything can be supported.

One trick to support backreferences in DFA impls is to

replace them with .* and use post-processing to verify.

So it's more a matter of what's readily available, not what's

possible.

That said, I _really_ think these should be a single

library.  If for whatever reason using two underlying

implementations is more practical, so be it - that's what

IrRegex does.  Backtracking implementations are

easy to write.

Also note, in addition to the features you can programmatically

use `valid-sre?'.

> regexp->sre is frequently requested in IrRegex. It is useful and the
> only argument against it is that it would require more memory for
> compiled regexps (linearly more for most implementations), but I'll
> wait to see if it's requested in the discussion.

I think it's an important thing to have.  The wording should allow for
either caching within the regexp object or decompilation, and should
warn that caching may produce a space leak.

I will include this in the next draft with a warning

that the SRE will be functionally equivalent but

may not be equal? to the SRE the regexp was

compiled from.

-- 

Alex