Bug (and promised fix): append

[Dirk Herrmann <dirk at ida dot ing dot tu-bs dot de>]

Hi!

I'm back from my skiing vacation and started looking at list.c
again.  I found the following bug:


guile> (define foo (list 1))
guile> (set-cdr! foo foo)
guile> foo
(1 . #0#)
guile> (append foo (list 1))
..... endless loop .....


The problem is, that only the last parameter of append is allowed to be
anything else than an improper list, but within append no checks for
circular structures are performed.

When trying to fix this problem, I added the tortoise and hare test to
the arguments, but when trying to do the whole scm_append function
right, I stumbled across the following problems:

* I'm not sure whether R5RS allows that append is called without
  any argument at all.  Guile allows append to be called without
  arguments, then returning an empty list.  This makes sense to me, but
  I'm not sure about the 'official' way.

* Should a 'rest' argument be checked for being a proper list?  I assume
  that a rest argument that is provided by the evaluator is guaranteed to
  be a proper list, but a user that calls such a function might provide
  something else.

  Looking at the code for append, I figured out that there are some checks
  performed for the rest arguments, like checking whether it is made up of
  cells and that a last element is guaranteed to be SCM_EOL.  However, it
  is not tested whether the list of rest arguments is circular.

  Thus the question:  Should we assume that rest arguments are typically
  provided by the evaluator and thus are guaranteed to be proper
  lists?  Or should rest arguments be checked to be proper lists, assuming
  that such functions might be called with inappropriate rest parameters
  by some users?  In that case we must consequently also check for
  circularity.

  * If we want full type checking for lists of rest arguments, I assume a
    lot of places have to be changed.  Further, this will lead to
    performance penalties, since in many places the 'tortoise and hare'
    algorithm (or something similar) will have to be used.

  * No type checking for lists of rest arguments might allow some code and
    execution time savings at some places (like in append), which could
    bring performance improvements at the cost of problems with user code
    calling such primitives from the C level.

  A solution could be to add an explicit test for a rest argument enclosed
  in #ifdef DEBUG (or similar).

As soon as I get the answers to these questions, I will finish and submit
my patch for scm_append.

Best regards,
Dirk Herrmann