GNU bug report logs - #17485
(srfi srfi-1) reduce-right does not scale, version 2.0.9

Previous Next

Full log

View this message in rfc822 format

From: David Kastrup <dak <at> gnu.org>
To: Mark H Weaver <mhw <at> netris.org>
Cc: 17485 <at> debbugs.gnu.org
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

Mark H Weaver <mhw <at> netris.org> writes:

> Hi David,
>
> David Kastrup <dak <at> gnu.org> 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
>>   <URL:http://srfi.schemers.org/srfi-1/srfi-1-reference.scm> 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 <dak <at> gnu.org>
>> ---
>>  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'.

libguile/list.h:SCM_API long scm_ilength (SCM sx);

libguile/list.c:
SCM_DEFINE (scm_length, "length", 1, 0, 0, 
           (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 = scm_ilength (lst); \
    SCM_ASSERT (cvar >= 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*™".

-- 
David Kastrup

Previous Next

GNU bug tracking system
Copyright (C) 1999 Darren O. Benham, 1997,2003 nCipher Corporation Ltd, 1994-97 Ian Jackson.