Hi Neil,
"Neil Jerram" <[EMAIL PROTECTED]> 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'.
