Re: Stupid module and pregexp questions

[Ken Anderson]

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