Hi Ludovic,
I'm sorry but I'm still really struggling to see how this change helps us...
2008/9/1 Ludovic Courtès <[EMAIL PROTECTED]>:
> 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. :-)
Not necessarily. It depends what happens inside the loop, on each
iteration, and whether the iteration time is significant in comparison
with that.
> It doesn't feel right to impose that overhead "just" for the sake of
> type-checking.
What overhead? (Quantifiably, I mean.)
Another slight concern is that this change seems to me to take us
further away from one of Mikael's possible ideas for the future: being
able to completely _remove_ a lot of the typechecking that we
currently do, because we instead carry around some representation of
what we already know about arguments.
I don't believe anyone's worked this all out yet, but, for example, if
the arg to scm_reverse() was generated by some other function that is
known only to produce proper lists, then the arg might be represented
as (<proper-list> . the-actual-list), and obviously then the
SCM_VALIDATE_LIST in scm_reverse() can be completely skipped. If the
validation code is interleaved with the actually-doing-something code,
it becomes more difficult to skip (in some hypothetical future).
> Type-checking using `list?' in these cases was actually overzealous
> since neither RnRS nor SRFI-1 require it.
OK, but on its own I don't think this is a strong reason for change.
> 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.
That's pretty horrible as far as code complexity and maintenance are concerned!
>> Did you find the use of SCM_VALIDATE_LIST () causing a problem in real
>> practical code?
>
> What does that mean?
Did you (or someone else) see a performance problem in a real,
moderately complex application, which you analyzed and discovered to
be significantly caused by these SCM_VALIDATE_LIST() invocations?
> Real practical code using `memq' behaves just as
> if it called `memq' twice, that's it.
Yes (or perhaps 3 or more times...). And Scheme is slower than C, so
should we all drop Scheme?
This kind of argument is premature optimization, which is well known
to be misguided. (Isn't it?)
>>> 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". :-)
! :-)
Do we really need to continue this discussion? I just don't see
anything helpful about this change.
But perhaps I'm misunderstanding. Surely there must be _some_ clear
benefit, which motivated you to work on this - can you say what that
was?
I guess I should just finish off the email though, for completeness...
>> 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).
I'm afraid this doesn't make sense to me. A list isn't "'() 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!'.)
Yes, indeed, sorry.
> 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.
I agree that one can't always cater for every bit of code of there,
but I need a better reason to risk breakage than I'm seeing at the
moment.
Regards,
Neil
