Re: Weird Guile Scheme Behaviour

[Mark H Weaver <mhw@netris.org>]

Hi Philip,

philip@warpmail.net (Philip K.) writes:

> I was reading a thread on an imageboard[0] the other day, then I came
> across a most peculiar "bug", if it even is one. Since the original
> example was a bit dense (it tried to solve a problem someone else had
> posted, that's not relevant here), I tried to construct a minimal
> working example to discuss here.
>
> Compare
>
>     (define (reverse-iota-1 max)
>       (let ((numbers '(start)))
>         (let loop ((val 0))
>           (append! numbers
>                    (if (< max val)
>                        '()
>                        (begin
>                          (loop (1+ val))
>                          (list val)))))
>         numbers))
>
> and
>
>     (define (reverse-iota-2 max)
>       (let ((numbers '(start)))
>         (let loop ((val 0))
>           (append! numbers
>                    (if (< max val)
>                        '()
>                        (begin
>                          (loop (1+ val))
>                          (list val)))))
>         (cdr numbers)))
>
> (I know, the style is horrible, but that's not the point. Also, both
> have an internal state, so you have to re-eval the function every time
> before starting the function itself.)
>
> The only difference is in the last line. The first function returns the
> entire list (with the start symbol), and the second tries to chop it
> off.
>
> But what happens is that (reverse-iota-1 4) evals to '(start 3 2 1 0)
> while (reverse-iota-2 4) just returns '()!

The problem here is that '(start) is a *literal* list, and it's an error
to modify literals in Scheme.  In other words, modifying a literal
results in undefined behavior.  Like C string literals, Scheme literals
are actually part of the program text itself.

To fix this problem, instead of initializing 'numbers' to point to a
literal list, you must construct a fresh mutable list.  One way is by
replacing '(start) with (list 'start).

What's happening here is this: Since it's an error to modify a literal
list, and since the 'numbers' variable is never 'set!' within its
lexical scope (the only scope where a variable can possibly be set! in
Scheme), Guile's compiler is allowed to assume that 'numbers' will
always point to the literal '(start), and therefore that (cdr numbers)
can be optimized to '().

The other problem, as Neil and Vladimir correctly pointed out, is that
'append!' is permitted, but not required, to modify the original list.
Therefore, you must always do (set! numbers (append! numbers ...)) to
avoid relying on unspecified behavior.

Note that it's impossible in Scheme to implement an 'append!' procedure
that always modifies the original list.  Specifically, an empty list
cannot be destructively modified.  It can't be done for the same reason
that you cannot implement a C function with the following specification:

  struct pair { void *item; struct pair *next; };
  void appendx (struct pair *list_to_modify, struct pair *list_to_add);

This C function can only be implemented in the case where
'list_to_modify' has at least one element.  In that case, the 'next'
field of the last pair can be modified.  If 'list_to_modify' is NULL, it
can't be done, because 'appendx' doesn't have access to the variable
that contained NULL.

In Scheme, the same issues apply.  If there's at least one element in
the first list passed to 'append!', it can use 'set-cdr!' to modify the
last pair of the list.  If the first argument is '(), it can't be done.

In practice, that's the reason why 'append!' is specified the way it is.
However, I would advise against assuming that 'append!' will always
modify the original list if it's nonempty, because that fact, although
true of the current implementation, is not actually specified.

      Regards,
        Mark