Re: [PATCH] Avoid `SCM_VALIDATE_LIST ()'

[Ludovic Courtès]

Hi Neil,

"Neil Jerram" <address@hidden> writes:

>> 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.

You're right, but it's always better to traverse the list once rather
than twice.  :-)

It doesn't feel right to impose that overhead "just" for the sake of
type-checking.

Type-checking using `list?' in these cases was actually overzealous
since neither RnRS nor SRFI-1 require it.

Note: We could change these functions to still diagnose what `list?'
diagnoses while avoiding `SCM_VALIDATE_LIST ()' such that only one list
traversal is done.  It boils down to implementing the tortoise and the
hare in each function, as shown in the `list-copy' patch.

> Did you find the use of SCM_VALIDATE_LIST () causing a problem in real
> practical code?

What does that mean?  Real practical code using `memq' behaves just as
if it called `memq' twice, that's it.  Whether that is a "problem"
depends on how often that happens, how long the list is, and how long
you're willing to wait.  :-)

>> 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...)

Yes, that's what I meant by "happily traverse circular lists".  :-)

> What do reverse* do on a circular list?  What do concatenate* do?

They keep reversing or concatenating---and it takes long!  :-)

> There are a few more specific comments below, but on balance, at the
> moment, I'm seeing more disadvantages here than benefit...

Again, if the disadvantage is that circular lists are not diagnosed, we
can add tortoise-and-hare protection to each function while still
avoiding double traversal.  I'm not sure it's worth it, though.

>> +** 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?

Right.

>> @@ -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.

It's a mechanical change: the code used to check for a proper list, I
just changed it to check for a list (i.e., '() or a pair).

> 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?

(I think that was `reverse!'.)

Portable RnRS code and code written without looking at `list.c' must use
`list?' before calling `reverse!' to protect from such situations.  So,
to me, that's not a concern.

Now, one could argue that there's code out there that relies on Guile's
undocumented over-restriction on input arguments.  That's always
possible, but hopefully sufficiently rare.

>> @@ -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?

So that "(list-copy 1)" raises an exception, rather than being silently
ignored (as is the case with `list-copy' from `srfi-1.c').  Again, a
mechanical change.

Thanks,
Ludo'.