GNU bug report logs - #17296
[PATCH] SRFI-1 'length+' raises an error unless passed a proper or circular list

Previous Next

To add a comment to this bug, you must first unarchive it, by sending
a message to control AT debbugs.gnu.org, with unarchive 17296 in the body.
You can then email your comments to 17296 AT debbugs.gnu.org in the normal way.

Toggle the display of automated, internal messages from the tracker.

Message #5 received at submit <at> debbugs.gnu.org (full text, mbox):

From: Mark H Weaver <mhw <at> netris.org>
To: bug-guile <at> gnu.org
Subject: [PATCH] SRFI-1 'length+' raises an error unless passed a proper or
 circular list
Date: Fri, 18 Apr 2014 15:26:48 -0400

[Message part 1 (text/plain, inline)]

According to the SRFI-1 spec, 'length+' must be passed a proper or
circular list.  It should raise an error when passed a non-pair or an
improper list, but instead it returns #f in such cases:

--8<---------------cut here---------------start------------->8---
scheme@(guile-user)> (use-modules (srfi srfi-1))
scheme@(guile-user)> (length+ 5)
$1 = #f
scheme@(guile-user)> (length+ 'x)
$2 = #f
scheme@(guile-user)> (length+ '(x . y))
$3 = #f
--8<---------------cut here---------------end--------------->8---

One side effect of this is that SRFI-1 'map', which uses 'length+' to
validate the arguments and find the shortest length, accepts improper
lists and non-pairs as arguments as long as one of the arguments is a
proper list:

--8<---------------cut here---------------start------------->8---
scheme@(guile-user)> (map + '(1 2) '(1 2 3 . 4))
$4 = (2 4)
scheme@(guile-user)> (map + '() 2)
$5 = ()
scheme@(guile-user)> (map + '(1) 2)
ERROR: In procedure cdr:
ERROR: In procedure cdr: Wrong type (expecting pair): 2
--8<---------------cut here---------------end--------------->8---

The attached patch fixes these problems.

     Mark

[0001-SRFI-1-length-raises-an-error-unless-passed-a-proper.patch (text/x-patch, inline)]

From 1daa266dd0a6381c58eba950dd935686dadee166 Mon Sep 17 00:00:00 2001
From: Mark H Weaver <mhw <at> netris.org>
Date: Fri, 18 Apr 2014 15:04:12 -0400
Subject: [PATCH] SRFI-1 'length+' raises an error unless passed a proper or
 circular list.

* libguile/srfi-1.c (scm_srfi1_length_plus): Rewrite to raise an error
  unless passed a proper or circular list, based on code from
  'scm_ilength'.

* test-suite/tests/srfi-1.test (length+): Add tests.
---
 libguile/srfi-1.c            | 30 +++++++++++++++++++++++++++---
 test-suite/tests/srfi-1.test |  7 ++++++-
 2 files changed, 33 insertions(+), 4 deletions(-)

diff --git a/libguile/srfi-1.c b/libguile/srfi-1.c
index 54c7e2a..a7ffeec 100644
--- a/libguile/srfi-1.c
+++ b/libguile/srfi-1.c
@@ -1,7 +1,7 @@
 /* srfi-1.c --- SRFI-1 procedures for Guile
  *
  * Copyright (C) 1995, 1996, 1997, 2000, 2001, 2002, 2003, 2005, 2006,
- *   2008, 2009, 2010, 2011 Free Software Foundation, Inc.
+ *   2008, 2009, 2010, 2011, 2014 Free Software Foundation, Inc.
  *
  * This library is free software; you can redistribute it and/or
  * modify it under the terms of the GNU Lesser General Public License
@@ -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);
+  size_t i = 0;
+  SCM tortoise = lst;
+  SCM hare = lst;
+
+  do
+    {
+      if (SCM_NULL_OR_NIL_P (hare))
+        return scm_from_size_t (i);
+      if (!scm_is_pair (hare))
+        scm_wrong_type_arg_msg (FUNC_NAME, 1, lst, "proper or circular list");
+      hare = SCM_CDR (hare);
+      i++;
+      if (SCM_NULL_OR_NIL_P (hare))
+        return scm_from_size_t (i);
+      if (!scm_is_pair (hare))
+        scm_wrong_type_arg_msg (FUNC_NAME, 1, lst, "proper or circular list");
+      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));
+
+  /* If the tortoise ever catches the hare, then the list must contain
+     a cycle.  */
+  return SCM_BOOL_F;
 }
 #undef FUNC_NAME
 
diff --git a/test-suite/tests/srfi-1.test b/test-suite/tests/srfi-1.test
index d40f8e1..9a2ed94 100644
--- a/test-suite/tests/srfi-1.test
+++ b/test-suite/tests/srfi-1.test
@@ -1,6 +1,7 @@
 ;;;; srfi-1.test --- Test suite for Guile's SRFI-1 functions. -*- scheme -*-
 ;;;;
-;;;; Copyright 2003, 2004, 2005, 2006, 2008, 2009, 2010, 2011 Free Software Foundation, Inc.
+;;;; Copyright 2003, 2004, 2005, 2006, 2008, 2009, 2010, 2011,
+;;;;   2014 Free Software Foundation, Inc.
 ;;;;
 ;;;; This library is free software; you can redistribute it and/or
 ;;;; modify it under the terms of the GNU Lesser General Public
@@ -1329,6 +1330,10 @@
     (length+))
   (pass-if-exception "too many args" exception:wrong-num-args
     (length+ 123 456))
+  (pass-if-exception "not a pair" exception:wrong-type-arg
+    (length+ 'x))
+  (pass-if-exception "improper list" exception:wrong-type-arg
+    (length+ '(x y . z)))
   (pass-if (= 0 (length+ '())))
   (pass-if (= 1 (length+ '(x))))
   (pass-if (= 2 (length+ '(x y))))
-- 
1.8.4

Message #10 received at 17296-done <at> debbugs.gnu.org (full text, mbox):

From: Mark H Weaver <mhw <at> netris.org>
To: 17296-done <at> debbugs.gnu.org
Subject: Re: bug#17296: [PATCH] SRFI-1 'length+' raises an error unless passed
 a proper or circular list
Date: Sun, 01 Jun 2014 20:56:21 -0400

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

> According to the SRFI-1 spec, 'length+' must be passed a proper or
> circular list.  It should raise an error when passed a non-pair or an
> improper list, but instead it returns #f in such cases:
>
> scheme@(guile-user)> (use-modules (srfi srfi-1))
> scheme@(guile-user)> (length+ 5)
> $1 = #f
> scheme@(guile-user)> (length+ 'x)
> $2 = #f
> scheme@(guile-user)> (length+ '(x . y))
> $3 = #f
>
> One side effect of this is that SRFI-1 'map', which uses 'length+' to
> validate the arguments and find the shortest length, accepts improper
> lists and non-pairs as arguments as long as one of the arguments is a
> proper list:
>
> scheme@(guile-user)> (map + '(1 2) '(1 2 3 . 4))
> $4 = (2 4)
> scheme@(guile-user)> (map + '() 2)
> $5 = ()
> scheme@(guile-user)> (map + '(1) 2)
> ERROR: In procedure cdr:
> ERROR: In procedure cdr: Wrong type (expecting pair): 2
>
> The attached patch fixes these problems.

Pushed to stable-2.0, commit a5186f506f69ef8a8accd234ca434efd13f302c9.

I'm closing this bug.

      Mark

Message #13 received at 17296 <at> debbugs.gnu.org (full text, mbox):

From: David Kastrup <dak <at> gnu.org>
To: 17296 <at> debbugs.gnu.org
Subject: Uh, wrong?
Date: Tue, 03 Jun 2014 19:30:23 +0200

[Message part 1 (text/plain, inline)]

I see that a patch has been committed.  It is conflicting with another
patch of mine and it does not follow from the srfi-1 specification.

To wit:

<URL:http://srfi.schemers.org/srfi-1/srfi-1.html#ImproperLists>

    Most procedures are defined only on proper lists -- that is, finite,
    nil-terminated lists. The procedures that will also handle circular
    or dotted lists are specifically marked. While this design decision
    restricts the domain of possible arguments one can pass to these
    procedures, it has the benefit of allowing the procedures to catch
    the error cases where programmers inadvertently pass scalar values
    to a list procedure by accident, e.g., by switching the arguments to
    a procedure call.

Note "allowing to catch".

Then we have

    Errors

    Note that statements of the form "it is an error" merely mean "don't
    do that." They are not a guarantee that a conforming implementation
    will "catch" such improper use by, for example, raising some kind of
    exception. Regrettably, R5RS Scheme requires no firmer guarantee
    even for basic operators such as car and cdr, so there's little
    point in requiring these procedures to do more. Here is the relevant
    section of the R5RS:

        When speaking of an error situation, this report uses the phrase
        "an error is signalled" to indicate that implementations must
        detect and report the error. If such wording does not appear in
        the discussion of an error, then implementations are not
        required to detect or report the error, though they are
        encouraged to do so. An error situation that implementations are
        not required to detect is usually referred to simply as "an
        error."

        For example, it is an error for a procedure to be passed an
        argument that the procedure is not explicitly specified to
        handle, even though such domain errors are seldom mentioned in
        this report. Implementations may extend a procedure's domain of
        definition to include such arguments.

So let's see how we have defined stuff here:

    list	A proper (finite, nil-terminated) list
    clist 	A proper or circular list
    flist 	A finite (proper or dotted) list 

For length+, we have

    length  list -> integer
    length+ clist -> integer or #f

    Both length and length+ return the length of the argument. It is an
    error to pass a value to length which is not a proper list (finite
    and nil-terminated). In particular, this means an implementation may
    diverge or signal an error when length is applied to a circular
    list.

    length+, on the other hand, returns #F when applied to a circular
    list.

    The length of a proper list is a non-negative integer n such that
    cdr applied n times to the list produces the empty list.

So the behavior for length+ on a dotted list is strictly unspecified.
It is not even stated "it is an error".

Functions like fold state:

     fold kons knil clist1 clist2 ... -> value

    The fold operation terminates when the shortest list runs out of values:

    (fold cons* '() '(a b c) '(1 2 3 4 5)) => (c 3 b 2 a 1)

    At least one of the list arguments must be finite.

Note the wording: "at least one of the list arguments must be finite",
not "at least one of the list arguments must be proper".  The definition
of the recursion for the single-list case again leaves the case of a
dotted list unspecified.

If we take a look at the reference implementation at
<URL:http://srfi.schemers.org/srfi-1/srfi-1-reference.scm>, we get

    (define (length+ x)			; Returns #f if X is circular.
      (let lp ((x x) (lag x) (len 0))
        (if (pair? x)
            (let ((x (cdr x))
                  (len (+ len 1)))
              (if (pair? x)
                  (let ((x   (cdr x))
                        (lag (cdr lag))
                        (len (+ len 1)))
                    (and (not (eq? x lag)) (lp x lag len)))
                  len))
            len)))

which _clearly_ treats dotted lists like regular lists with regard to
giving the length of the spine.

Incidentally, the reference implementation also contains

    ;;; R4RS, so commented out.
    ;(define (length x)			; LENGTH may diverge or
    ;  (let lp ((x x) (len 0))		; raise an error if X is
    ;    (if (pair? x)			; a circular list. This version
    ;        (lp (cdr x) (+ len 1))		; diverges.
    ;        len)))

which again would work on dotted lists just fine.  But I am not all that
interested in meddling with that.

At any rate, what I am getting at is that I was going to submit the
following patch as a part of a series fixing other bugs, bugs that I
need a working "get the length of a dotted list" operator for.  We don't
have any such operator in GUILE, and that's awkward.

[bap (text/x-diff, inline)]

commit 9539272d26f2954a253ed1365a6704ed197a79be
Author: David Kastrup <dak <at> gnu.org>
Date:   Mon Jun 2 15:05:55 2014 +0200

    Let length+ return the length of dotted lists rather than #f
    
    * 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.

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;
+  SCM tortoise = lst;
+  SCM hare = lst;
+
+  do {
+    if (!scm_is_pair (hare)) return scm_from_long (i);
+    hare = SCM_CDR(hare);
+    i++;
+    if (!scm_is_pair (hare)) return scm_from_long (i);
+    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));
+
+  /* If the tortoise ever catches the hare, then the list must contain
+     a cycle.  */
+  return SCM_BOOL_F;
 }
 #undef FUNC_NAME
 
diff --git a/module/srfi/srfi-1.scm b/module/srfi/srfi-1.scm
index 0806e73..bc72048 100644
--- a/module/srfi/srfi-1.scm
+++ b/module/srfi/srfi-1.scm
@@ -474,7 +474,7 @@ that result.  See the manual for details."
                      (or len1 len2))))
        (unless len
          (scm-error 'wrong-type-arg "fold"
-                    "Args do not contain a proper (finite) list: ~S"
+                    "Args do not contain a finite list: ~S"
                     (list (list list1 list2)) #f))
        (let fold2 ((knil knil) (list1 list1) (list2 list2) (len len))
          (if (zero? len)
@@ -601,7 +601,7 @@ has just one element then that's the return value."
                      (or len1 len2))))
        (unless len
          (scm-error 'wrong-type-arg "map"
-                    "Args do not contain a proper (finite) list: ~S"
+                    "Args do not contain a finite list: ~S"
                     (list (list l1 l2)) #f))
        (let map2 ((l1 l1) (l2 l2) (len len))
          (if (zero? len)
@@ -620,7 +620,7 @@ has just one element then that's the return value."
                       rest)))
        (if (not len)
            (scm-error 'wrong-type-arg "map"
-                      "Args do not contain a proper (finite) list: ~S"
+                      "Args do not contain a finite list: ~S"
                       (list (cons l1 rest)) #f))
        (let mapn ((l1 l1) (rest rest) (len len))
          (if (zero? len)
@@ -649,7 +649,7 @@ has just one element then that's the return value."
                      (or len1 len2))))
        (unless len
          (scm-error 'wrong-type-arg "for-each"
-                    "Args do not contain a proper (finite) list: ~S"
+                    "Args do not contain a finite list: ~S"
                     (list (list l1 l2)) #f))
        (let for-each2 ((l1 l1) (l2 l2) (len len))
          (unless (zero? len)
@@ -667,7 +667,7 @@ has just one element then that's the return value."
                       rest)))
        (if (not len)
            (scm-error 'wrong-type-arg "for-each"
-                      "Args do not contain a proper (finite) list: ~S"
+                      "Args do not contain a finite list: ~S"
                       (list (cons l1 rest)) #f))
        (let for-eachn ((l1 l1) (rest rest) (len len))
          (if (> len 0)
diff --git a/test-suite/tests/srfi-1.test b/test-suite/tests/srfi-1.test
index d40f8e1..9364ea2 100644
--- a/test-suite/tests/srfi-1.test
+++ b/test-suite/tests/srfi-1.test
@@ -1187,19 +1187,21 @@
     (pass-if-exception "proc arg count 4" exception:wrong-num-args
       (fold (lambda (x y z prev) x) 1 '(1 2 3) '(1 2 3)))
 
-    (pass-if-exception "improper first 1" exception:wrong-type-arg
-      (fold + 1 1 '(1 2 3)))
-    (pass-if-exception "improper first 2" exception:wrong-type-arg
-      (fold + 1 '(1 . 2) '(1 2 3)))
-    (pass-if-exception "improper first 3" exception:wrong-type-arg
-      (fold + 1 '(1 2 . 3) '(1 2 3)))
-
-    (pass-if-exception "improper second 1" exception:wrong-type-arg
-      (fold + 1 '(1 2 3) 1))
-    (pass-if-exception "improper second 2" exception:wrong-type-arg
-      (fold + 1 '(1 2 3) '(1 . 2)))
-    (pass-if-exception "improper second 3" exception:wrong-type-arg
-      (fold + 1 '(1 2 3) '(1 2 . 3)))
+    ;; For multiple list arguments, dotted lists are permitted by this
+    ;; implementation and a non-list is a zero-length dotted list
+    (pass-if "improper first 1"
+      (= 1 (fold + 1 1 '(1 2 3))))
+    (pass-if "improper first 2"
+      (= 3 (fold + 1 '(1 . 2) '(1 2 3))))
+    (pass-if "improper first 3"
+      (= 7 (fold + 1 '(1 2 . 3) '(1 2 3))))
+
+    (pass-if "improper second 1"
+      (= 1 (fold + 1 '(1 2 3) 1)))
+    (pass-if "improper second 2"
+      (= 3 (fold + 1 '(1 2 3) '(1 . 2))))
+    (pass-if "improper second 3"
+      (= 7 (fold + 1 '(1 2 3) '(1 2 . 3))))
 
     (pass-if (= 6 (fold + 1 '(2) '(3))))
     (pass-if (= 15 (fold + 1 '(2 3) '(4 5))))

[Message part 3 (text/plain, inline)]

I am not saying that your implementation of count+ is wrong.  It meets
the specs of srfi-1.  But so did the previous implementation.  And so
does mine.

And since there is otherwise no actual length operator of any kind
working for dotted lists, I want one.  The previous implementation was
actually trivially the same as

(define (length* lst)
  (catch 'wrong-type-arg
    (lambda () (length lst))
    (lambda _ #f)))

and consequently was trivial to write using existing length functions in
the C API.

And I need my variant of length+ to fix things like take-right which
currently bomb out on large lists with a VM error and are _required_ to
deal with _both_ proper and dotted lists.

Which is awkward to do without a length operator working on both proper
and dotted lists.

-- 
David Kastrup

Message #16 received at 17296 <at> debbugs.gnu.org (full text, mbox):

From: Mark H Weaver <mhw <at> netris.org>
To: David Kastrup <dak <at> gnu.org>
Cc: 17296 <at> debbugs.gnu.org
Subject: Re: bug#17296: Uh, wrong?
Date: Tue, 03 Jun 2014 22:55:42 -0400

David Kastrup <dak <at> gnu.org> writes:
> So the behavior for length+ on a dotted list is strictly unspecified.
> It is not even stated "it is an error".

Actually, it is.  At the end of the section that defines the "types"
such a "clist" and "flist", it states:

  It is an error to pass a circular or dotted list to a procedure not
  defined to accept such an argument.

While it is true that we are not required to signal an error, I'm wary
extending 'length+' in this way.  It also effectively extends 'map' and
'for-each' to support things like (map + '() 'foo), and thus potentially
affects many other procedures both inside and outside of Guile that use
'map' and 'for-each'.  Once we've done this, users are likely to grow
dependent on it and we can never go back.

> At any rate, what I am getting at is that I was going to submit the
> following patch as a part of a series fixing other bugs, bugs that I
> need a working "get the length of a dotted list" operator for.  We don't
> have any such operator in GUILE, and that's awkward.

It might be helpful to add such a procedure, but I don't think 'length+'
should be it.

   Regards,
     Mark

Message #19 received at 17296 <at> debbugs.gnu.org (full text, mbox):

From: David Kastrup <dak <at> gnu.org>
To: Mark H Weaver <mhw <at> netris.org>
Cc: 17296 <at> debbugs.gnu.org
Subject: Re: bug#17296: Uh, wrong?
Date: Wed, 04 Jun 2014 06:39:50 +0200

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

> David Kastrup <dak <at> gnu.org> writes:
>> So the behavior for length+ on a dotted list is strictly unspecified.
>> It is not even stated "it is an error".
>
> Actually, it is.  At the end of the section that defines the "types"
> such a "clist" and "flist", it states:
>
>   It is an error to pass a circular or dotted list to a procedure not
>   defined to accept such an argument.
>
> While it is true that we are not required to signal an error, I'm wary
> extending 'length+' in this way.  It also effectively extends 'map' and
> 'for-each' to support things like (map + '() 'foo), and thus potentially
> affects many other procedures both inside and outside of Guile that use
> 'map' and 'for-each'.  Once we've done this, users are likely to grow
> dependent on it and we can never go back.

That is true for _any_ particular choice for unspecified behavior.
_Including_ throwing an error as a means of checking input validity.

You are proposing providing functions _not_ defined in srfi-1 at all for
functionality that is clearly desirable even for implementing behavior
required by some functions in srfi-1.  Such functions can either be made
private, requiring the user to write his own, less efficient function
whenever he faces the same problem.  Or they can be provided publicly in
which case it is unlikely that the user will not grow dependent on them
and "we can never go back".

The reference implementation chose the behavior I propose.  The naming
choice of "length+" in srfi-1 has been made in a manner suggesting that
only one such additional length operator is needed as it is rather
generic and not just restricted to circular and dotted lists.

Basically, srfi-1 is sort of a have-one's-cake-and-eat-it-too
specification: the ability to throw errors on dotted lists is explicitly
mentioned as possibly helpful when a user mixes up arguments to
functions like fold, while at the same time there is no framework for
the explicit "accept dotted list also" kind of behavior put forward by
functions like drop-right or take-right.

It is also noteworthy that the reference implementation defines "length"
on dotted lists rather than erroring out, and in general is pretty
lenient regarding using dotted instead of proper lists.

This _is_ an ugly mess.  It is my personal opinion that at least with
regard to length+ we are better off following the reference
implementation.  I don't see the point in having something like

(map + '(1 2) '(1 2 3 . 4))

error out: it did not do so before your patch and definitely has an
obvious result.  I am not enthused over allowing

(map + '(1 2) 5) => '()

while balking at

(map + 5)

but with a single list, the "shortest finite list" clause does not
really come into play, and indeed the "help avoid user error early"
rationale seems particularly applicable.

My first implementation of take-right/drop-right just used "count" as it
does not seem to make sense to talk about dropping n elements from the
end of a dotted list given that even functions like "count" and "length"
are unspecified for dotted lists.

I was, however, surprised to figure out later that this is one area of
srfi-1 where lists were explicitly allowed to be dotted but not
circular.

>> At any rate, what I am getting at is that I was going to submit the
>> following patch as a part of a series fixing other bugs, bugs that I
>> need a working "get the length of a dotted list" operator for.  We
>> don't have any such operator in GUILE, and that's awkward.
>
> It might be helpful to add such a procedure, but I don't think
> 'length+' should be it.

I don't think the entire incoherent mess of what is and what is not
described that makes up srfi-1 should be like it is.  But that's what we
have to deal with.  Following the reference implementation in this
regard seems like the smallest evil to me.  If the standard had kept its
fingers off specifying behavior for _all_ list-like operations
(including the take-right and drop-right operators) we would not be in
this situation.  Whatever escape we choose, people will get to rely on
it.

-- 
David Kastrup

Message #22 received at 17296 <at> debbugs.gnu.org (full text, mbox):

From: Mark H Weaver <mhw <at> netris.org>
To: David Kastrup <dak <at> gnu.org>
Cc: 17296 <at> debbugs.gnu.org
Subject: Re: bug#17296: Uh, wrong?
Date: Wed, 04 Jun 2014 10:49:04 -0400

David Kastrup <dak <at> gnu.org> writes:

> Mark H Weaver <mhw <at> netris.org> writes:
>
>> David Kastrup <dak <at> gnu.org> writes:
>>> So the behavior for length+ on a dotted list is strictly unspecified.
>>> It is not even stated "it is an error".
>>
>> Actually, it is.  At the end of the section that defines the "types"
>> such a "clist" and "flist", it states:
>>
>>   It is an error to pass a circular or dotted list to a procedure not
>>   defined to accept such an argument.
>>
>> While it is true that we are not required to signal an error, I'm wary
>> extending 'length+' in this way.  It also effectively extends 'map' and
>> 'for-each' to support things like (map + '() 'foo), and thus potentially
>> affects many other procedures both inside and outside of Guile that use
>> 'map' and 'for-each'.  Once we've done this, users are likely to grow
>> dependent on it and we can never go back.
>
> That is true for _any_ particular choice for unspecified behavior.
> _Including_ throwing an error as a means of checking input validity.
>
> You are proposing providing functions _not_ defined in srfi-1 at all for
> functionality that is clearly desirable even for implementing behavior
> required by some functions in srfi-1.

If we want things like (map + - * /) to signal an error, then we need a
'length+' that signals an error when passed - or * or /.  In fact,
that's precisely what motivated me to make 'length+' more strict.

So, you and I are coming at this from different angles.  I want a strict
'length+' to implement 'map' and 'for-each', and you want a lax one to
implement 'drop-right' et al.  It seems to me that we need both.

The fact that the SRFI-1 reference implementation of 'length+' is lax
very nearly swayed me over to your position, but there's a problem:
Guile's 'length+' has (always?) returned #f for dotted lists.  It would
be dangerous to silently change the behavior of this case from one
non-error to another non-error.  Programs could start silently
misbehaving without any clue that anything went wrong.

      Mark

Message #29 received at 17296 <at> debbugs.gnu.org (full text, mbox):

From: Mark H Weaver <mhw <at> netris.org>
To: David Kastrup <dak <at> gnu.org>
Cc: 17296 <at> debbugs.gnu.org
Subject: Re: bug#17296: Uh, wrong?
Date: Mon, 22 Sep 2014 13:34:42 -0400

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

> The fact that the SRFI-1 reference implementation of 'length+' is lax
> very nearly swayed me over to your position, but there's a problem:
> Guile's 'length+' has (always?) returned #f for dotted lists.  It would
> be dangerous to silently change the behavior of this case from one
> non-error to another non-error.  Programs could start silently
> misbehaving without any clue that anything went wrong.

BTW, I looked at the discussion archive for SRFI-1 looking for wisdom
about whether we should eventually make 'length+' lax or not.  I
discovered that Olin Shivers (SRFI-1 author) was in favor of making
essentially all SRFI-1 procedures tolerant of dotted lists, a position
he expressed concisely as "everything is a list", since non-null
non-pairs such as "foo", 2, and even? are naturally regarded as dotted
lists of length 0.

It turns out that he was overwhelming overruled on this.  Some of the
most respected people in the Scheme world agreed it was a bad idea, and
in fact not a single other participant agreed with him.

So he grudgingly changed the spec to reflect the consensus, but he left
his reference implementation as he preferred.

A good summary of the reasons against Olin's preference was given here:

  http://srfi.schemers.org/srfi-1/mail-archive/msg00052.html

If you're curious, here's a threaded index of the entire discussion:

  http://srfi.schemers.org/srfi-1/mail-archive/threads.html

Search for "Everything is a list" for Olin's position, and the threads
following "Re: SRFI-1 round 3 discussion", where Olin tried to defend
his position, then tried to sell a compromise, and finally gave in
completely.

    Regards,
      Mark

Previous Next

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