From mboxrd@z Thu Jan 1 00:00:00 1970 Path: main.gmane.org!not-for-mail From: Tom Lord Newsgroups: gmane.lisp.guile.user Subject: Re: Stupid module and pregexp questions Date: Tue, 29 Apr 2003 16:21:10 -0700 (PDT) Sender: guile-user-bounces+guile-user=m.gmane.org@gnu.org Message-ID: <200304292321.QAA04172@morrowfield.regexps.com> References: <877k9eobcv.fsf@raven.i.defaultvalue.org> NNTP-Posting-Host: main.gmane.org X-Trace: main.gmane.org 1051657735 8512 80.91.224.249 (29 Apr 2003 23:08:55 GMT) X-Complaints-To: usenet@main.gmane.org NNTP-Posting-Date: Tue, 29 Apr 2003 23:08:55 +0000 (UTC) Cc: guile-user@gnu.org Original-X-From: guile-user-bounces+guile-user=m.gmane.org@gnu.org Wed Apr 30 01:08:52 2003 Return-path: Original-Received: from monty-python.gnu.org ([199.232.76.173]) by main.gmane.org with esmtp (Exim 3.35 #1 (Debian)) id 19AeDU-0002Cx-00 for ; Wed, 30 Apr 2003 01:08:52 +0200 Original-Received: from localhost ([127.0.0.1] helo=monty-python.gnu.org) by monty-python.gnu.org with esmtp (Exim 4.10.13) id 19AeEN-0001gQ-03 for guile-user@m.gmane.org; Tue, 29 Apr 2003 19:09:47 -0400 Original-Received: from list by monty-python.gnu.org with tmda-scanned (Exim 4.10.13) id 19AeCw-0001V9-00 for guile-user@gnu.org; Tue, 29 Apr 2003 19:08:18 -0400 Original-Received: from mail by monty-python.gnu.org with spam-scanned (Exim 4.10.13) id 19AeCY-0000Ui-00 for guile-user@gnu.org; Tue, 29 Apr 2003 19:08:00 -0400 Original-Received: from 1cust79.tnt13.sfo8.da.uu.net ([65.234.195.79] helo=morrowfield.regexps.com) by monty-python.gnu.org with esmtp (Exim 4.10.13) id 19AeCD-0008D0-00 for guile-user@gnu.org; Tue, 29 Apr 2003 19:07:34 -0400 Original-Received: (from lord@localhost) by morrowfield.regexps.com (8.9.1/8.9.1) id QAA04172; Tue, 29 Apr 2003 16:21:10 -0700 (PDT) (envelope-from lord@morrowfield.regexps.com) Original-To: markj@cloaked.freeserve.co.uk In-reply-to: (message from MJ Ray on Tue, 29 Apr 2003 22:06:30 -0000) X-BeenThere: guile-user@gnu.org X-Mailman-Version: 2.1b5 Precedence: list List-Id: General Guile related discussions List-Help: List-Post: List-Subscribe: , List-Archive: List-Unsubscribe: , Errors-To: guile-user-bounces+guile-user=m.gmane.org@gnu.org Xref: main.gmane.org gmane.lisp.guile.user:1874 X-Report-Spam: http://spam.gmane.org/gmane.lisp.guile.user:1874 > 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))) [....] _______________________________________________ Guile-user mailing list Guile-user@gnu.org http://mail.gnu.org/mailman/listinfo/guile-user