[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: Stupid module and pregexp questions
From: |
Ken Anderson |
Subject: |
Re: Stupid module and pregexp questions |
Date: |
Tue, 29 Apr 2003 20:04:41 -0400 |
At 04:21 PM 4/29/2003 -0700, Tom Lord wrote:
> > And then, of course, there's the issue of speed. Regexps are used for
> > enough processing that IMHO they must be matched by compiled, not
> > interpreted, code or they risk being unacceptably slow. [...]
>
> Compiled code is just interpreted code at a different level,
> surely? A good optimisation will often beat dropping down
> levels, and scheme allows easier optimisation while avoiding
> some typical errors. Do the minimum directly in C, IMHO.
>
>I have some experience in regexp implementation, so may I offer my
>$0.02?
>
>a) In popular use on unix, fairly low performance matchers dominate
> with the exception of apps like awk and grep. But when I say
> "fairly low performance" -- please don't misunderstand -- I'm
> oversimplifying. What really dominates are matchers that are
> pretty slow on patterns that are at all tricky, but that optimize
> some common cases like a constant-string pattern and patterns close
> to that. It mostly just doesn't occur to people to use regexps
> for problems that fall outside of those common cases.
>
>
>b) A really fast and general matcher, like Rx (as in hackerlab C
> library, not as in the ancient fork on the GNU FTP site), opens a
> lot of doors. You can apply dynamically generated regexps to
> applications that were previously out of reach. A nice example
> might be to write parsers for a really rich wiki language.
>
> To my mind, opening the door to applications like that through the
> provision of an extra fancy regexp engine is a neat thing to do --
> and is a way Guile could differentiate itself from other
> languages. At the same time, it takes a lot of code and it's
> touchy to tune -- so it risks violating the KISS principle.
>
> And, oh yeah -- you'll want shared substrings to make things really
> hum along nicely (ahem :-).
>
>
>Matchers of type (a) are butt simple to implement. (Hard to get right
>if you want to nail all the details to be Posix conformant, but the
>algorithms are pretty straightforward.) People have gotten a lot of
>milage by writing some in Java. I don't see any reason why a Scheme
>version couldn't be competitive -- but really, you'd need it to be
>compiled and to have at least a few relevant compiler optimizations.
>
>Matchers of type (b) are hard to implement. Really hard. And the
>competition among them boils down to O(1-3) instructions in critical
>loops, and to fast paths through exceptional but, alas, important
>non-common cases. There isn't a practical chance in hell of any
>Scheme compiler competing in this space in the next 5 years (at
>least). The compiler theory is arguably there -- but its practical
>application is quite a ways off.
>
>So whether you prefer (a) or (b), if you want competitive performance,
>you're stuck doing some compiler hacking if you choose to use an
>engine in Scheme. A serious but tractable amount of compiler hacking
>for (a) (catch up to Java, at least), a researchy amount for (b).
>
>So, "do the minimum in C": that means write the regexp engine in C,
>for all practical purposes.
I think there are alternatives more people should know about.
Henry Baker has a "Pragmatic parsing" paper:
http://citeseer.nj.nec.com/henry91pragmatic.html
that suggests writing tokenizers in a direct style. In terms of regular
expressions, its like writing the expression in a fully deterministic way.
This may sound bad at first, but i've written a tokenizer and its common lisp
compiler for CORBA IDL in a variation on this style and it was smaller than
Sun's input to LEX for the same task. It compiled into goto's not objects or
tables, so i suspect it was relatively fast.
The domain of regex matching requires a fairly narrow subset of Scheme so it
might be possible to do fairly well, but it ultimately depends on how good the
compiler is. At least in CL, with some work, you could get C like code
produced.
Another issue is when you should convert your regex from nondetermanistic form
to deterministic form. I've seen Java regex that require 25 seconds to
compile, so lazy compiling may pay off.
>Say: suppose I implement an Emacs buffer-like string type either as a
>gap buffer or, better, as a tree of some sort (perhaps a splay tree)
>-- a good question for your regexp engine is "can it handle a string
>that isn't contiguous in memory like that".
>
>-t
>
>(here's a snippet of what I do with mine -- the SRE-like expressions
>get compiled down to an extended version of Posix extended regexp
>syntax:)
>
>(begin
> (define wiki-paragraph-rules
> ;; (type test separator)
> ;;
> ;; Test is a structured regexp to be compiled in a larg `(| ...)'
> ;; of all of the test expressions. The leftmost-longest matching
> ;; test expression determines the type of the first paragraph in a
> ;; given string.
> ;;
> ;; `(separator string)' returns a list: `(paragraph remaining-string)',
> ;; separating the first paragraph from the rest of the string.
> ;;
> ;; The `test' expression and `separator' procedure can safely assume
> ;; that the string is not empty, and does not begin with any blank lines.
> ;;
>
> `((:form-feed (& (* ([] blank)) "\f" (* ([] blank)))
> ,(lambda (s) (one-line-separator s)))
> (:comment-line (& "%%%"(* ([^] "\n")))
> ,(lambda (s) (one-line-separator s)))
> (:rfc822ish (& (* ([] blank)) "+++" (* ([] blank)))
> ,(lambda (s) (ordinary-paragraph-separator s)))
>
> (:title (& "!" (+ ([^] "\n")))
> ,(lambda (s) (ordinary-paragraph-separator s)))
>
> (:card-boundary "\f---"
> ,(lambda (s) (one-line-separator s)))
>
> (:heading (& (* ([] blank))
> (+ "*")
> ([] blank)
> ([^] ")#*\n")
> (* ([^] "\n")))
> ,(lambda (s) (ordinary-paragraph-separator s)))
>
> (:menu (& (* ([] blank))
> "-*-*-"
> (* ([] blank)))
> ,(lambda (s) (one-line-separator s)))
>
> (:verbatim (& (* ([] blank)) "<<<" (* ([] blank)))
> ,(lambda (s) (verbatim-paragraph-separator s)))
>
> (:small-paragraph (& (* ([] blank)) "(((" (* ([] blank)))
> ,(lambda (s) (small-paragraph-separator s)))
>
> (:text-area (& (* ([] blank)) "?<<<" (* ([^] #\nl)))
> ,(lambda (s) (verbatim-paragraph-separator s)))
>
> (:one-line-verbatim (& "#" (* ([^] "\n")))
> ,(lambda (s) (one-line-separator s)))
>
> (:separator-line (& (* ([] blank)) "---" (* "-") (* ([] blank)))
> ,(lambda (s) (one-line-separator s)))
>
>
>
>[....]
>
>
>
>_______________________________________________
>Guile-user mailing list
>address@hidden
>http://mail.gnu.org/mailman/listinfo/guile-user
Re: Stupid module and pregexp questions, Robert Uhl, 2003/04/28
- Re: Stupid module and pregexp questions, MJ Ray, 2003/04/29
- Re: Stupid module and pregexp questions, Tom Lord, 2003/04/29
- Re: Stupid module and pregexp questions,
Ken Anderson <=
- Re: Stupid module and pregexp questions, tomas, 2003/04/30
- Re: Stupid module and pregexp questions, Tom Lord, 2003/04/30
- Re: Stupid module and pregexp questions, Tom Lord, 2003/04/30
Re: Stupid module and pregexp questions, Thien-Thi Nguyen, 2003/04/30
Re: Stupid module and pregexp questions, tomas, 2003/04/30
Re: Stupid module and pregexp questions, Tom Lord, 2003/04/30
Re: Stupid module and pregexp questions, Robert Uhl, 2003/04/30