From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: Clinton Ebadi Newsgroups: gmane.lisp.guile.devel Subject: Re: [PATCH] Avoid `SCM_VALIDATE_LIST ()' Date: Mon, 08 Sep 2008 00:42:45 -0400 Message-ID: <873akbckoq.fsf@unknownlamer.org> References: <87hc90u9lb.fsf@gnu.org> <49dd78620809011409w8902d24q5734da921d6dfbff@mail.gmail.com> <49dd78620809061532i76ccf7a4rb0c2d838d51cb504@mail.gmail.com> NNTP-Posting-Host: lo.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii X-Trace: ger.gmane.org 1220848993 21815 80.91.229.12 (8 Sep 2008 04:43:13 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Mon, 8 Sep 2008 04:43:13 +0000 (UTC) To: guile-devel@gnu.org Original-X-From: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Mon Sep 08 06:44:08 2008 Return-path: Envelope-to: guile-devel@m.gmane.org Original-Received: from lists.gnu.org ([199.232.76.165]) by lo.gmane.org with esmtp (Exim 4.50) id 1KcYbd-0005sK-Lw for guile-devel@m.gmane.org; Mon, 08 Sep 2008 06:44:05 +0200 Original-Received: from localhost ([127.0.0.1]:54399 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1KcYad-00068X-Q7 for guile-devel@m.gmane.org; Mon, 08 Sep 2008 00:43:03 -0400 Original-Received: from mailman by lists.gnu.org with tmda-scanned (Exim 4.43) id 1KcYaW-00068S-Is for guile-devel@gnu.org; Mon, 08 Sep 2008 00:42:56 -0400 Original-Received: from exim by lists.gnu.org with spam-scanned (Exim 4.43) id 1KcYaU-000684-OS for guile-devel@gnu.org; Mon, 08 Sep 2008 00:42:55 -0400 Original-Received: from [199.232.76.173] (port=60007 helo=monty-python.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1KcYaU-000681-K1 for guile-devel@gnu.org; Mon, 08 Sep 2008 00:42:54 -0400 Original-Received: from deleuze.hcoop.net ([69.90.123.67]:48542) by monty-python.gnu.org with esmtps (TLS-1.0:RSA_AES_256_CBC_SHA1:32) (Exim 4.60) (envelope-from ) id 1KcYaU-0004Pm-5K for guile-devel@gnu.org; Mon, 08 Sep 2008 00:42:54 -0400 Original-Received: from cpe-071-065-238-103.nc.res.rr.com ([71.65.238.103] helo=localhost.localdomain) by deleuze.hcoop.net with esmtpsa (TLS-1.0:DHE_RSA_AES_256_CBC_SHA1:32) (Exim 4.63) (envelope-from ) id 1KcYaS-0000Oz-AC for guile-devel@gnu.org; Mon, 08 Sep 2008 00:42:52 -0400 In-Reply-To: (Han-Wen Nienhuys's message of "Mon\, 08 Sep 2008 00\:13\:23 -0300") User-Agent: Gnus/5.11 (Gnus v5.11) Emacs/22.2 (gnu/linux) X-detected-kernel: by monty-python.gnu.org: Linux 2.6 (newer, 1) X-BeenThere: guile-devel@gnu.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: "Developers list for Guile, the GNU extensibility library" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Original-Sender: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Errors-To: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Xref: news.gmane.org gmane.lisp.guile.devel:7620 Archived-At: Han-Wen Nienhuys writes: > Neil Jerram escreveu: >> 2008/9/2 Han-Wen Nienhuys : >>> If you are doing memq? for something you already know to >>> somewhere in front of the list [...] >> >> Why would you do that? In two senses: >> >> 1. I know memq gives you the tail of the list, but I usually use its >> result only as a true/false value Why would run use memq like that in >> a situation where you already know that it will give you true? >> >> 2. It feels unusual to me to have a long list, but in which certain >> kinds of values are known always to be near the front. That sounds >> like something that should really be represented as two (or more) >> separate lists. >> >> Have you observed this (the current usage of SCM_VALIDATE_LIST) as a >> performance problem in practice? > > No, but it feels strange to me that a function whose intrinsic function > does not require O(n) behavior, does require it in all cases. > > However, I find Mikael's argument that it complicates programming a lot > persuasive. How about something like (obviously better and in C): (define (detect-cycle lst fn) (let ((get-hare (lambda (lst) (if (and (pair? lst) (pair? (cdr lst))) (cddr lst) #f))) (get-tortoise (lambda (lst) (if (pair? lst) (cdr lst) (error "End of list hit"))))) (let detect ((tortoise lst) (hare (get-hare lst))) (fn tortoise) (cond ((eq? tortoise hare) (error "cycle detected")) (else (detect (get-tortoise tortoise) (get-hare hare))))))) ;;; example (define (cyclic-memq x lst) ;; Obviously a real version would want to catch an exception here ;; and return the proper value (detect-cycle lst (lambda (sublist) (if (eq? (car sublist) x) (error "x found"))))) In C the only burden would be defining one-use helper functions and a struct (or perhaps just a Scheme list since there would be at most one or two values each faked closure would need) for storing any data they would need. It would be a tad bit ugly, but would neatly (as neatly as can be done in C at least) allow every list traversing primitive function to avoid cycles (and still work on cyclic lists where the item was actually there) without traversing the entire list. The question then becomes whether the overhead of a bunch of indirect function calls would be an issue. Asymptotically this wouldn't matter (but neither does potentially traversing the entire list twice except that now your best and worst case are both N), but in reality with average list length and all... Perhaps a macro could be used instead (is it possible to pass entire blocks of code to a macro using something like CYCLE_DETECTING({ .... code ... }) in C?). It would be a very hairy macro, but would again give every list traversal primitive the ability to avoid spinning on cyclic lists or dying at the end of improper lists without having a separate implementation of the tortoise and hare algorithm in every function. -- Who will tend the garden when the snake swallows the light? Who will eat the decay when the worms have lost their sight? Who will rape the weak when there's nothing left to gain? Who will till the soil of these barren black remains?