Re: [PATCH] Avoid `SCM_VALIDATE_LIST ()'

["Neil Jerram" <neiljerram@googlemail.com>]

2008/9/1 Ludovic Courtès <ludo@gnu.org>:
> 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))