2008/9/1 Ludovic Courtès <[EMAIL PROTECTED]>:
> Hello,
>
> This is a followup to this discussion:
>
> http://thread.gmane.org/gmane.lisp.guile.devel/7194
>
> The attached patch changes several list-related functions
reverse!, memq, memv, member, filter, filter!
SRFI-1: concatenate, concatenate!, member, remove, remove!
> so that they
> don't validate their input with `SCM_VALIDATE_LIST ()' since it's O(n).
I'm afraid I don't get your rationale, because all these functions are
O(n) anyway. (For reverse*, filter* and concatenate* I believe this
is obvious. For mem* and remove*, they should always be O(n) in
practice because it would be stupid to design a list structure where
the element being looked for or removed was not equally likely to be
anywhere along the list.)
I know you gave an example in the above-referenced thread, but IMO
that was a pathological one. Did you find the use of
SCM_VALIDATE_LIST () causing a problem in real practical code?
> A side-effect (besides performance improvements) is that all these
> functions will now happily traverse circular lists, and will silently
> deal with dotted lists. This is acceptable behavior IMO.
Are you sure about traversing circular lists? From my reading of your
patch, I would expect:
(memq 'not-in-the-list some-circular-list)
=>
(don't know, still waiting...)
:-)
What do reverse* do on a circular list? What do concatenate* do?
There are a few more specific comments below, but on balance, at the
moment, I'm seeing more disadvantages here than benefit...
Regards,
Neil
> diff --git a/NEWS b/NEWS
> index c2bed17..cfcd43b 100644
> --- a/NEWS
> +++ b/NEWS
> @@ -56,6 +56,13 @@ When you use GDS to evaluate Scheme code from Emacs, you
> can now use
> This makes these internal functions technically not callable from
> application code.
>
> +** Remove argument type checking with `list?' in some list-related functions
It's easy to read that as just "Remove argument type checking". Could
we say "Improve scalability of some list-related functions" instead,
and leave the type checking detail to the following para?
> +
> +Several list-related functions (e.g., `memq', `list-copy', etc.) used
> +R5RS `list?' to validate their arguments. However, `list?' has linear
> +complexity, so these functions have been changed to not resort to
> +`list?'.
> +
> ** `guile-config link' now prints `-L$libdir' before `-lguile'
> ** Fix memory corruption involving GOOPS' `class-redefinition'
> ** Fix build issue on Tru64 and ia64-hp-hpux11.23 (`SCM_UNPACK' macro)
> diff --git a/libguile/list.c b/libguile/list.c
> index a1a79a4..8b0a2e4 100644
> --- a/libguile/list.c
> +++ b/libguile/list.c
> @@ -1,4 +1,4 @@
> -/* Copyright (C) 1995,1996,1997,2000,2001,2003,2004
> +/* Copyright (C) 1995,1996,1997,2000,2001,2003,2004,2008
> * Free Software Foundation, Inc.
> *
> * This library is free software; you can redistribute it and/or
> @@ -367,15 +367,19 @@ SCM_DEFINE (scm_reverse_x, "reverse!", 1, 1, 0,
> "@code{reverse!}")
> #define FUNC_NAME s_scm_reverse_x
> {
> - SCM_VALIDATE_LIST (1, lst);
> if (SCM_UNBNDP (new_tail))
> new_tail = SCM_EOL;
> else
> - SCM_VALIDATE_LIST (2, new_tail);
> + SCM_ASSERT (scm_is_pair (new_tail) || SCM_NULL_OR_NIL_P (new_tail),
> + new_tail, 2, FUNC_NAME);
Why does new_tail need to satisfy this condition? Please either add a
comment to explain, or just remove.
> while (!SCM_NULL_OR_NIL_P (lst))
> {
> - SCM old_tail = SCM_CDR (lst);
> + SCM old_tail;
> +
> + SCM_VALIDATE_CONS (1, lst);
> +
> + old_tail = SCM_CDR (lst);
> SCM_SETCDR (lst, new_tail);
> new_tail = lst;
> lst = old_tail;
Note that if SCM_VALIDATE_CONS fails half way through the "list", the
input list will have been destructively modified such that it is
neither the same as when it started, nor a complete reversed list. Is
that a concern?
> @@ -546,7 +550,8 @@ SCM_DEFINE (scm_list_copy, "list-copy", 1, 0, 0,
> SCM * fill_here;
> SCM from_here;
>
> - SCM_VALIDATE_LIST (1, lst);
> + SCM_ASSERT (scm_is_pair (lst) || SCM_NULL_OR_NIL_P (lst),
> + lst, 1, FUNC_NAME);
Why impose this condition specifically on the head of the provided
list? Please either explain or remove.
>
> newlst = SCM_EOL;
> fill_here = &newlst;
> @@ -613,8 +618,13 @@ SCM_DEFINE (scm_memq, "memq", 2, 0, 0,
> "returned.")
> #define FUNC_NAME s_scm_memq
> {
> - SCM_VALIDATE_LIST (2, lst);
> - return scm_c_memq (x, lst);
> + for (; !SCM_NULL_OR_NIL_P (lst); lst = SCM_CDR (lst))
> + {
> + SCM_VALIDATE_CONS (2, lst);
> + if (scm_is_eq (SCM_CAR (lst), x))
> + return lst;
> + }
> + return SCM_BOOL_F;
> }
> #undef FUNC_NAME
>
> @@ -629,9 +639,9 @@ SCM_DEFINE (scm_memv, "memv", 2, 0, 0,
> "returned.")
> #define FUNC_NAME s_scm_memv
> {
> - SCM_VALIDATE_LIST (2, lst);
> for (; !SCM_NULL_OR_NIL_P (lst); lst = SCM_CDR (lst))
> {
> + SCM_VALIDATE_CONS (2, lst);
> if (! scm_is_false (scm_eqv_p (SCM_CAR (lst), x)))
> return lst;
> }
> @@ -650,9 +660,9 @@ SCM_DEFINE (scm_member, "member", 2, 0, 0,
> "empty list) is returned.")
> #define FUNC_NAME s_scm_member
> {
> - SCM_VALIDATE_LIST (2, lst);
> for (; !SCM_NULL_OR_NIL_P (lst); lst = SCM_CDR (lst))
> {
> + SCM_VALIDATE_CONS (2, lst);
> if (! scm_is_false (scm_equal_p (SCM_CAR (lst), x)))
> return lst;
> }
> @@ -884,9 +894,11 @@ SCM_DEFINE (scm_filter, "filter", 2, 0, 0,
> SCM walk;
> SCM *prev;
> SCM res = SCM_EOL;
> +
> SCM_ASSERT (call, pred, 1, FUNC_NAME);
> - SCM_VALIDATE_LIST (2, list);
> -
> + SCM_ASSERT (scm_is_pair (list) || SCM_NULL_OR_NIL_P (list),
> + list, 2, FUNC_NAME);
Same comment as above.
> +
> for (prev = &res, walk = list;
> scm_is_pair (walk);
> walk = SCM_CDR (walk))
> @@ -910,9 +922,11 @@ SCM_DEFINE (scm_filter_x, "filter!", 2, 0, 0,
> scm_t_trampoline_1 call = scm_trampoline_1 (pred);
> SCM walk;
> SCM *prev;
> +
> SCM_ASSERT (call, pred, 1, FUNC_NAME);
> - SCM_VALIDATE_LIST (2, list);
> -
> + SCM_ASSERT (scm_is_pair (list) || SCM_NULL_OR_NIL_P (list),
> + list, 2, FUNC_NAME);
Same comment as above.
> +
> for (prev = &list, walk = list;
> scm_is_pair (walk);
> walk = SCM_CDR (walk))
