append! non-tail recursion

append! non-tail recursion

[Kevin Ryde]

I noticed append! is implemented with a non-tail recursion.  Since
it's at the C level it needs quite a long list to provoke a problem,
but I thought to redo it with a loop.

The current code uses scm_last_pair, which has the effect of detecting
circular lists in the input.  Is that an intended feature, or merely a
side effect?

Plain append doesn't check for circular, I guess probably neither or
both should do it.


_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-devel

Re: append! non-tail recursion

[Kevin Ryde]

I ended up with this change,

        * list.c (scm_append_x): Use iterative style, to avoid non-tail
        recursion.

New code:

SCM_DEFINE (scm_append_x, "append!", 0, 0, 1,
            (SCM lists),
            "A destructive version of @code{append} (@pxref{Pairs and\n"
            "Lists,,,r5rs, The Revised^5 Report on Scheme}).  The cdr field\n"
            "of each list's final pair is changed to point to the head of\n"
            "the next list, so no consing is performed.  Return\n"
            "the mutated list.")
#define FUNC_NAME s_scm_append_x
{
  SCM ret, *loc;
  SCM_VALIDATE_REST_ARGUMENT (lists);

  if (SCM_NULLP (lists))
    return SCM_EOL;

  loc = &ret;
  for (;;)
    {
      SCM arg = SCM_CAR (lists);
      *loc = arg;

      lists = SCM_CDR (lists);
      if (SCM_NULLP (lists))
        return ret;

      if (!SCM_NULL_OR_NIL_P (arg))
        {
          SCM_VALIDATE_CONS (SCM_ARG1, arg);
          loc = SCM_CDRLOC (scm_last_pair (arg));
        }
    }
}
#undef FUNC_NAME


_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-devel