Weird Guile Scheme Behaviour

Weird Guile Scheme Behaviour

[Philip K.]

[-- Attachment #1: Type: text/plain, Size: 1902 bytes --]


Hi,

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 '()!

This seems weird, since my intuition, and that of the poster above, was
that all that should change in reverse-iota-2 is that the "start" symbol
should fall away.

It's obvious that this has something to do with the destructive
"append!", but I'm not quite sure what leads to this unexpected result.
Is it maybe a optimisation error? Any opinions?

[0]: https://lainchan.org/%CE%BB/res/12185.html#15066 (SFW)

-- 
	With kind regards,
	Philip K.

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 487 bytes --]

Re: Weird Guile Scheme Behaviour

[Neil Jerram]

Correct usage of append! usually requires (set! x (append! x ....)),
despite what you might think from the !.  I haven't read the rest of your
email carefully, but I wonder if that will make a difference?

Best wishes,
    Neil


On Fri, 13 Sep 2019 at 13:39, Philip K. <philip@warpmail.net> wrote:

>
> Hi,
>
> 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 '()!
>
> This seems weird, since my intuition, and that of the poster above, was
> that all that should change in reverse-iota-2 is that the "start" symbol
> should fall away.
>
> It's obvious that this has something to do with the destructive
> "append!", but I'm not quite sure what leads to this unexpected result.
> Is it maybe a optimisation error? Any opinions?
>
> [0]: https://lainchan.org/%CE%BB/res/12185.html#15066 (SFW)
>
> --
>         With kind regards,
>         Philip K.
>

Re: Weird Guile Scheme Behaviour

[Vladimir Zhbanov]

Philip,

On Fri, Sep 13, 2019 at 11:43:06AM +0200, Philip K. wrote:
> 
> Hi,
> 
> 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 '()!
> 
> This seems weird, since my intuition, and that of the poster above, was
> that all that should change in reverse-iota-2 is that the "start" symbol
> should fall away.
> 
> It's obvious that this has something to do with the destructive
> "append!", but I'm not quite sure what leads to this unexpected result.
> Is it maybe a optimisation error? Any opinions?


Well, if i understand the issue correctly, there are two issues :-)

1) The quotation from the Guile manual:

     ‘append’ doesn’t modify the given lists, but the return may share
     structure with the final OBJ.  ‘append!’ is permitted, but not
     required, to modify the given lists to form its return.


2) 'let' itself should return the last evaluated expression
(right?). The external 'let' does just so, and the internal 'let'
is irrelevant (apart from the issue with permission to 'append!',
shown above, to modify the value of its arguments) .

So, if you would use just 'append' instead of 'append!', you would
get just the value of 'numbers' (just '(start)) in the first case,
and the value of its 'cdr' in the second case (obviously, '()
:-)).  However, since 'append!' is used instead, it is
unpredictable for me (the behaviour of 'append!' is not
standardized), if it will change the value of 'numbers' itself, so
there are two cases you've got.

Well, dunno, which conditions force the Guile optimizer to choose
one of the strategies.  Seems, i would prefer internal 'let's in
both cases are thrown out.

-- 
  Vladimir

(λ)επτόν EDA — https://github.com/lepton-eda

Re: Weird Guile Scheme Behaviour

[Mark H Weaver]

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

Re: Weird Guile Scheme Behaviour

[Philip K.]

[-- Attachment #1: Type: text/plain, Size: 557 bytes --]

Mark H Weaver <mhw@netris.org> writes:

> 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.

Ah, that makes sense. I totally forgot about the difference between
'(start) and (list 'start).

>       Regards,
>         Mark

Thanks a lot for your response, helped my clear up understanding.

-- 
	With kind regards,
	Philip K.

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 487 bytes --]