Re: Stupid module and pregexp questions

[Tom Lord]

       > 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.

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)))



[....]