bug#17485: [PATCH 1/3] Let length+ return the length of dotted lists rather than #f

[Mark H Weaver]

Hi David,

David Kastrup <address@hidden> 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 <address@hidden>
> ---
>  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