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: Fri, 24 Oct 2003 15:58:18 -0700 (PDT) Sender: guile-user-bounces+guile-user=m.gmane.org@gnu.org Message-ID: <200310242258.PAA04035@morrowfield.regexps.com> References: <877k9eobcv.fsf@raven.i.defaultvalue.org> <877k96htat.fsf@raven.i.defaultvalue.org> <200305050618.XAA10052@morrowfield.regexps.com> NNTP-Posting-Host: deer.gmane.org X-Trace: sea.gmane.org 1067035664 22917 80.91.224.253 (24 Oct 2003 22:47:44 GMT) X-Complaints-To: usenet@sea.gmane.org NNTP-Posting-Date: Fri, 24 Oct 2003 22:47:44 +0000 (UTC) Cc: guile-user@gnu.org Original-X-From: guile-user-bounces+guile-user=m.gmane.org@gnu.org Sat Oct 25 00:47:42 2003 Return-path: Original-Received: from monty-python.gnu.org ([199.232.76.173]) by deer.gmane.org with esmtp (Exim 3.35 #1 (Debian)) id 1ADAib-000738-00 for ; Sat, 25 Oct 2003 00:47:42 +0200 Original-Received: from localhost ([127.0.0.1] helo=monty-python.gnu.org) by monty-python.gnu.org with esmtp (Exim 4.24) id 1ADAiF-0005Dn-RI for guile-user@m.gmane.org; Fri, 24 Oct 2003 18:47:19 -0400 Original-Received: from list by monty-python.gnu.org with tmda-scanned (Exim 4.24) id 1ADAhm-0005CO-4M for guile-user@gnu.org; Fri, 24 Oct 2003 18:46:50 -0400 Original-Received: from mail by monty-python.gnu.org with spam-scanned (Exim 4.24) id 1ADAhF-0004zE-6e for guile-user@gnu.org; Fri, 24 Oct 2003 18:46:49 -0400 Original-Received: from [65.234.195.244] (helo=morrowfield.regexps.com) by monty-python.gnu.org with esmtp (Exim 4.24) id 1ADAhD-0004yr-O6 for guile-user@gnu.org; Fri, 24 Oct 2003 18:46:16 -0400 Original-Received: (from lord@localhost) by morrowfield.regexps.com (8.9.1/8.9.1) id PAA04035; Fri, 24 Oct 2003 15:58:18 -0700 (PDT) (envelope-from lord@morrowfield.regexps.com) Original-To: ttn@glug.org In-reply-to: (message from Thien-Thi Nguyen on Sat, 25 Oct 2003 00:26:43 +0200) X-BeenThere: guile-user@gnu.org X-Mailman-Version: 2.1.2 Precedence: list List-Id: General Guile related discussions List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: guile-user-bounces+guile-user=m.gmane.org@gnu.org Xref: main.gmane.org gmane.lisp.guile.user:2321 X-Report-Spam: http://spam.gmane.org/gmane.lisp.guile.user:2321 > From: Thien-Thi Nguyen > From: Tom Lord > Date: Sun, 4 May 2003 23:18:08 -0700 (PDT) > Guile-dialect regexp choices should be (imho) no less casual than, > say, number-tower choices. > but a tower is an abstract model that is supported to varying degrees > when it comes to compilation down to the the physical layer. That's equally true of regexps. > why are surface regexp syntaxes different? I believe I said they were similar, not different -- so I'm not sure why you ask me why they are different. > sure, there are non-dfa-friendly approaches, so provide > non-dfa-requiring compilation for those. Although you're mostly posting ink-blots to the list today (or because of that) I'll say (loosely, but I think it could be tighted up): The chomsky hierarchy points to some platonic truth that has real and practical implications for programs. If you stick to the lower levels of the hierarchy, you get better performance guarantees than if you don't. In the history of the design of programming language, including regexp languages, we have on the one hand that abstract observation about performance along the chomsky hierarchy, and on the other hand the historical accident of standard regexp languages ignoring that observation. It's easy to tweak a backtracking "true regular expression" engine to add, for example, subexpression position capture and backreferencing. Perl regexps are an example of what happens if you plop yourself down on a sled at the top of that slippery slope. The history is easy to understand: on dinky-little 1970s hardware (for example) a dynamic pattern matching pretty much has to be implemented as a backtracking engine. If I give you source code to a backtracking engine, it's easy to make incremental tweaks to it which are very convenient -- but which also raise the nature of that engine on the scale of the chomsky hierarchy. The so-far (mostly) unasked question is whether we can achieve similar (practical, not theoretic) expressivity to those tweaked matchers _without_ climbing the chomsky hierarchy: can we be fast and convenient at the same time? > at the bottom it's all just fixed-width NANDs and NORs > (logically speaking)... What's your point? I don't see how that observation relates to choices in language or run-time system design. Are you off your meds? "nothing really matters, to me" -- Queen (Bohemian Rhapsody) -t _______________________________________________ Guile-user mailing list Guile-user@gnu.org http://mail.gnu.org/mailman/listinfo/guile-user