From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: Mark H Weaver Newsgroups: gmane.lisp.guile.bugs Subject: bug#17485: [PATCH 1/3] Let length+ return the length of dotted lists rather than #f Date: Tue, 03 Jun 2014 23:42:26 -0400 Message-ID: <87wqcxtk65.fsf@yeeloong.lan> References: <87y4y6t0or.fsf@fencepost.gnu.org> <1401821778-19972-1-git-send-email-dak@gnu.org> NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: text/plain X-Trace: ger.gmane.org 1401853405 30172 80.91.229.3 (4 Jun 2014 03:43:25 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Wed, 4 Jun 2014 03:43:25 +0000 (UTC) Cc: 17485@debbugs.gnu.org To: David Kastrup Original-X-From: bug-guile-bounces+guile-bugs=m.gmane.org@gnu.org Wed Jun 04 05:43:16 2014 Return-path: Envelope-to: guile-bugs@m.gmane.org Original-Received: from lists.gnu.org ([208.118.235.17]) by plane.gmane.org with esmtp (Exim 4.69) (envelope-from ) id 1Ws26d-0003cU-Qn for guile-bugs@m.gmane.org; Wed, 04 Jun 2014 05:43:16 +0200 Original-Received: from localhost ([::1]:57035 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1Ws26d-0006Rm-5Y for guile-bugs@m.gmane.org; Tue, 03 Jun 2014 23:43:15 -0400 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:59701) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1Ws26V-0006Qn-Tg for bug-guile@gnu.org; Tue, 03 Jun 2014 23:43:13 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1Ws26Q-0005cn-Fh for bug-guile@gnu.org; Tue, 03 Jun 2014 23:43:07 -0400 Original-Received: from debbugs.gnu.org ([140.186.70.43]:44026) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1Ws26Q-0005br-CS for bug-guile@gnu.org; Tue, 03 Jun 2014 23:43:02 -0400 Original-Received: from Debian-debbugs by debbugs.gnu.org with local (Exim 4.80) (envelope-from ) id 1Ws26P-0007iF-S9 for bug-guile@gnu.org; Tue, 03 Jun 2014 23:43:02 -0400 X-Loop: help-debbugs@gnu.org Resent-From: Mark H Weaver Original-Sender: "Debbugs-submit" Resent-CC: bug-guile@gnu.org Resent-Date: Wed, 04 Jun 2014 03:43:01 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 17485 X-GNU-PR-Package: guile X-GNU-PR-Keywords: Original-Received: via spool by 17485-submit@debbugs.gnu.org id=B17485.140185337929639 (code B ref 17485); Wed, 04 Jun 2014 03:43:01 +0000 Original-Received: (at 17485) by debbugs.gnu.org; 4 Jun 2014 03:42:59 +0000 Original-Received: from localhost ([127.0.0.1]:42903 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1Ws26M-0007hx-F5 for submit@debbugs.gnu.org; Tue, 03 Jun 2014 23:42:58 -0400 Original-Received: from world.peace.net ([96.39.62.75]:50663 ident=hope4) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1Ws26G-0007hg-V7 for 17485@debbugs.gnu.org; Tue, 03 Jun 2014 23:42:56 -0400 Original-Received: from 209-6-91-212.c3-0.smr-ubr1.sbo-smr.ma.cable.rcn.com ([209.6.91.212] helo=yeeloong.lan) by world.peace.net with esmtpsa (TLS1.0:RSA_AES_128_CBC_SHA1:16) (Exim 4.72) (envelope-from ) id 1Ws268-0000y5-P5; Tue, 03 Jun 2014 23:42:45 -0400 In-Reply-To: <1401821778-19972-1-git-send-email-dak@gnu.org> (David Kastrup's message of "Tue, 3 Jun 2014 20:56:16 +0200") User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/24.3 (gnu/linux) X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.15 Precedence: list X-detected-operating-system: by eggs.gnu.org: GNU/Linux 3.x X-Received-From: 140.186.70.43 X-BeenThere: bug-guile@gnu.org List-Id: "Bug reports for GUILE, GNU's Ubiquitous Extension Language" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: bug-guile-bounces+guile-bugs=m.gmane.org@gnu.org Original-Sender: bug-guile-bounces+guile-bugs=m.gmane.org@gnu.org Xref: news.gmane.org gmane.lisp.guile.bugs:7489 Archived-At: Hi David, David Kastrup writes: > * libguile/srfi-1.c (scm_srfi1_length_plus): Previously, length+ > returned #f for dotted lists. This leaves the user with no efficient > means for determining the length of dotted lists. While the Scheme > standard does not prescribe a behavior here, the reference > implementation at > indeed > returns the spine length (number of successive pairs in the cdr-chain) > of dotted lists rather than #f, providing a good endorsement of this > behavior. > > As one consequence, the multi-list implementations for map, fold, and > for-each will happen to accept dotted lists as the shortest list. > Previously, this caused an error late during processing. In general, rationales don't belong in the commit logs. As per the GNU coding standards, change logs should only summarize the changes made. > > Signed-off-by: David Kastrup > --- > libguile/srfi-1.c | 28 ++++++++++++++++++++++++++-- > module/srfi/srfi-1.scm | 10 +++++----- > test-suite/tests/srfi-1.test | 28 +++++++++++++++------------- > 3 files changed, 46 insertions(+), 20 deletions(-) > > diff --git a/libguile/srfi-1.c b/libguile/srfi-1.c > index aaa3efe..0db6388 100644 > --- a/libguile/srfi-1.c > +++ b/libguile/srfi-1.c > @@ -614,8 +614,32 @@ SCM_DEFINE (scm_srfi1_length_plus, "length+", 1, 0, 0, > "circular.") > #define FUNC_NAME s_scm_srfi1_length_plus > { > - long len = scm_ilength (lst); > - return (len >= 0 ? SCM_I_MAKINUM (len) : SCM_BOOL_F); > + /* This uses the "tortoise and hare" algorithm to detect "infinitely > + long" lists (i.e. lists with cycles in their cdrs), and returns #f > + if it does find one. > + > + Dotted lists are treated just like regular lists, returning the > + length of the spine. This is in conformance with the reference > + implementation though not explicitly defined in the standard. */ > + long i = 0; Please use 'size_t' instead of 'long'. > + SCM tortoise = lst; > + SCM hare = lst; > + > + do { > + if (!scm_is_pair (hare)) return scm_from_long (i); scm_from_size_t > + hare = SCM_CDR(hare); > + i++; > + if (!scm_is_pair (hare)) return scm_from_long (i); Ditto. > + hare = SCM_CDR(hare); > + i++; > + /* For every two steps the hare takes, the tortoise takes one. */ > + tortoise = SCM_CDR(tortoise); > + } > + while (!scm_is_eq (hare, tortoise)); Please follow the GNU conventions for indentation. > + > + /* If the tortoise ever catches the hare, then the list must contain > + a cycle. */ > + return SCM_BOOL_F; > } > #undef FUNC_NAME Otherwise, this function looks good to me, but I'd prefer to give it a new name and move it into list.c, rather than extending SRFI-1's 'length+'. Hmm, coming up with names is hard. Maybe 'length*'? Thanks, Mark