Re: [PATCH] Avoid `SCM_VALIDATE_LIST ()'

[Neil Jerram]

Hi Ludovic,

I'm sorry but I'm still really struggling to see how this change helps us...

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

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