Re: Stupid module and pregexp questions

[tomas]

On Tue, May 06, 2003 at 02:28:21AM -0700, Tom Lord wrote:

[I promised to come back after having a look at pregexp]

> It's really foolish, performance-wise, to do _all_ of a regexp engine
> in scheme until you can scan a string through a dfa table at <20
> instructions per character.   If some of the hard-core compilers are
> up to that, I'm impressed -- but I'm quite sure none of the
> interpreters are.   The interpreters will be off by no less than 1,
> and I'd expect 2 or 3 orders of magnitude (powers of 10, here).

After having a look at pregexp (in a way it's impressive: it implements
a compiler/matcher for a massive, Perl-like regexp language in just over
29K of Scheme. And it's fairly readable, even for a Scheme novice like
me), here's the results:

  - Yes, it is a classical backtracking implementation, Perl style.

  - It's completely done in Scheme, moving around with string-ref.

  - IMHO it doesn't stand a chance to compete, performance-wise with
    carefully written matchers (of the backtracking type: of course
    DFA ones are miles away, depending on input). Even with the best
    Scheme compilers available (I'm ready to bet my plush penguin on
    that ;-)

Still, as an educational tool, and as a display of Scheme's expressive
power, it's a jewel.

I don't think it was written with efficiency in mind -- rather with clarity.

Besides, it makes for a good proposal of how a regexp interface to Scheme[1]
might look like. And to me, this seems to be the most important thing
in this thread.

----------
[1] Of the backtracking type, that is.

Regards
-- tomas