From: David Kastrup <dak@gnu.org>
To: Mark H Weaver <mhw@netris.org>
Cc: 17485@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 [thread overview]
Message-ID: <877g4x8e5p.fsf@fencepost.gnu.org> (raw)
In-Reply-To: <87wqcxtk65.fsf@yeeloong.lan> (Mark H. Weaver's message of "Tue, 03 Jun 2014 23:42:26 -0400")
Mark H Weaver <mhw@netris.org> writes:
> Hi David,
>
> David Kastrup <dak@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@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
next prev parent reply other threads:[~2014-06-04 4:57 UTC|newest]
Thread overview: 22+ messages / expand[flat|nested] mbox.gz Atom feed top
2014-05-13 10:47 bug#17485: (srfi srfi-1) reduce-right does not scale, version 2.0.9 David Kastrup
2014-06-01 23:41 ` Mark H Weaver
2014-06-02 7:59 ` David Kastrup
2014-06-03 18:56 ` bug#17485: [PATCH 1/3] Let length+ return the length of dotted lists rather than #f David Kastrup
2014-06-03 18:56 ` bug#17485: [PATCH 2/3] Rewrite take-right, drop-right, drop-right! David Kastrup
2014-06-04 3:29 ` Mark H Weaver
2014-06-04 3:45 ` Mark H Weaver
2014-09-20 14:56 ` Mark H Weaver
2014-09-20 15:15 ` David Kastrup
2014-09-22 17:15 ` Mark H Weaver
2014-09-22 18:40 ` David Kastrup
2014-06-03 18:56 ` bug#17485: [PATCH 3/3] Reimplement reduce-right in srfi-1 David Kastrup
2014-06-04 3:30 ` Mark H Weaver
2014-06-04 3:42 ` bug#17485: [PATCH 1/3] Let length+ return the length of dotted lists rather than #f Mark H Weaver
2014-06-04 4:57 ` David Kastrup [this message]
2014-06-04 10:09 ` David Kastrup
2014-06-05 13:57 ` David Kastrup
2016-06-21 14:42 ` bug#17485: (srfi srfi-1) reduce-right does not scale, version 2.0.9 Andy Wingo
2016-06-21 15:31 ` David Kastrup
2016-07-12 7:07 ` Andy Wingo
2016-07-12 7:43 ` bug#17485: Ugh, well David Kastrup
2016-07-12 13:54 ` Andy Wingo
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
List information: https://www.gnu.org/software/guile/
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=877g4x8e5p.fsf@fencepost.gnu.org \
--to=dak@gnu.org \
--cc=17485@debbugs.gnu.org \
--cc=mhw@netris.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).