From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: David Kastrup Newsgroups: gmane.lisp.guile.bugs Subject: bug#17485: [PATCH 1/3] Let length+ return the length of dotted lists rather than #f Date: Wed, 04 Jun 2014 06:57:54 +0200 Message-ID: <877g4x8e5p.fsf@fencepost.gnu.org> References: <87y4y6t0or.fsf@fencepost.gnu.org> <1401821778-19972-1-git-send-email-dak@gnu.org> <87wqcxtk65.fsf@yeeloong.lan> NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable X-Trace: ger.gmane.org 1401857957 8081 80.91.229.3 (4 Jun 2014 04:59:17 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Wed, 4 Jun 2014 04:59:17 +0000 (UTC) Cc: 17485@debbugs.gnu.org To: Mark H Weaver Original-X-From: bug-guile-bounces+guile-bugs=m.gmane.org@gnu.org Wed Jun 04 06:59:11 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 1Ws3I3-0001j2-Ug for guile-bugs@m.gmane.org; Wed, 04 Jun 2014 06:59:08 +0200 Original-Received: from localhost ([::1]:57268 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1Ws3I3-0004GP-Kw for guile-bugs@m.gmane.org; Wed, 04 Jun 2014 00:59:07 -0400 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:49678) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1Ws3Hz-0004G3-L6 for bug-guile@gnu.org; Wed, 04 Jun 2014 00:59:04 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1Ws3Hy-0001PN-C9 for bug-guile@gnu.org; Wed, 04 Jun 2014 00:59:03 -0400 Original-Received: from debbugs.gnu.org ([140.186.70.43]:44052) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1Ws3Hy-0001PE-8N for bug-guile@gnu.org; Wed, 04 Jun 2014 00:59:02 -0400 Original-Received: from Debian-debbugs by debbugs.gnu.org with local (Exim 4.80) (envelope-from ) id 1Ws3Hx-0001uJ-Ll for bug-guile@gnu.org; Wed, 04 Jun 2014 00:59:01 -0400 X-Loop: help-debbugs@gnu.org Resent-From: David Kastrup Original-Sender: "Debbugs-submit" Resent-CC: bug-guile@gnu.org Resent-Date: Wed, 04 Jun 2014 04:59: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.14018578927237 (code B ref 17485); Wed, 04 Jun 2014 04:59:01 +0000 Original-Received: (at 17485) by debbugs.gnu.org; 4 Jun 2014 04:58:12 +0000 Original-Received: from localhost ([127.0.0.1]:42929 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1Ws3H9-0001se-0i for submit@debbugs.gnu.org; Wed, 04 Jun 2014 00:58:11 -0400 Original-Received: from fencepost.gnu.org ([208.118.235.10]:35765 ident=Debian-exim) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1Ws3H6-0001sW-W6 for 17485@debbugs.gnu.org; Wed, 04 Jun 2014 00:58:09 -0400 Original-Received: from localhost ([127.0.0.1]:43071 helo=lola) by fencepost.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1Ws3H5-00059f-Rz; Wed, 04 Jun 2014 00:58:08 -0400 Original-Received: by lola (Postfix, from userid 1000) id 2DCD6DF6C2; Wed, 4 Jun 2014 06:57:54 +0200 (CEST) In-Reply-To: <87wqcxtk65.fsf@yeeloong.lan> (Mark H. Weaver's message of "Tue, 03 Jun 2014 23:42:26 -0400") User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/24.4.50 (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:7492 Archived-At: Mark H Weaver writes: > 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 =3D scm_ilength (lst); >> - return (len >=3D 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 =3D 0; > > Please use 'size_t' instead of 'long'. libguile/list.h:SCM_API long scm_ilength (SCM sx); libguile/list.c: SCM_DEFINE (scm_length, "length", 1, 0, 0,=20 (SCM lst), "Return the number of elements in list @var{lst}.") #define FUNC_NAME s_scm_length { long i; SCM_VALIDATE_LIST_COPYLEN (1, lst, i); return scm_from_long (i); } libguile/validate.h: #define SCM_VALIDATE_LIST_COPYLEN(pos, lst, cvar) \ do { \ cvar =3D scm_ilength (lst); \ SCM_ASSERT (cvar >=3D 0, lst, pos, FUNC_NAME); \ } while (0) _All_ of the existing list length operations including primitives like "length", "list?" and other stuff are based on "long". I understand your rationale, but it does not appear to make sense to follow it only in one place. The code actually was mostly a copy&paste job from scm_ilength which is at the core of "length". > 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*'? Given what cons* (and use of id* in syntax rules) does, the name seems inappropriate. length* would be a good name for (length* clist1 clist* ... ) returns the length of the shortest finite list in the given lists, #f if there is none. Which would be actually a rather nice building block to have for several srfi-1 functions and would basically not make us need length+ at all in its implementation. Of course, making it very likely that people "will depend on length*=E2=84= =A2". --=20 David Kastrup