Re: GNU Guile branch, stable-2.0, updated. v2.0.2-101-gd851e32

[Andy Wingo <wingo@pobox.com>]

Hello!

On Sun 25 Sep 2011 22:34, ludo@gnu.org (Ludovic Courtès) writes:

> Mark H Weaver <mhw@netris.org> skribis:
>
>>> commit d851e32fdc3d14804108f0389faa75a57599ced4
>>> Author: Andy Wingo <wingo@pobox.com>
>>> Date:   Fri Sep 23 18:02:05 2011 +0200
>>>
>>>     prevent propagation for memory-dependent operations like `car'
>>>     
>>>     * module/language/tree-il/primitives.scm (*primitive-constructors*):
>>>       Record car, cdr, vector-ref, and struct-ref as "constructors".
>>>       Comment to come later.
>>
>> If car, cdr, vector-ref and struct-ref are to be included in this set of
>> operations, it seems to me that the set should be renamed to something
>> other than "constructors".

I think that Ludovic and I were a bit confused about some things, as was
evident.  Specifically we were confusing identity, constant functions,
and pure functions.

Regarding identity, `cons' needs to return objects with identity.  These
expressions expressions are not the same:

  (define f
    (let ((pair (cons 1 2)))
      (lambda ()
        pair)))

  (define f
    (lambda ()
      (cons 1 2)))

Here we cannot propagate `pair' because then we would break (eq? (f)
(f)).  It's a question of identity.

Now, "constant functions".  Quoth GCC:

    `const'
         Many functions do not examine any values except their arguments,
         and have no effects except the return value.  Basically this is
         just slightly more strict class than the `pure' attribute below,
         since function is not allowed to read global memory.

This is the case for `+', for example.  If + is applied to constant
expressions then it is safe to propagate, because it computes the same
value, and doesn't reorder effects:

  (define g
    (let ((sum (+ 1 2)))
      (lambda ()
        sum)))

  (define g
    (lambda ()
      (+ 1 2)))

And of course this can fold to (lambda () 3).

Note, however, that `car' is *not* constant!  Its result depends on
mutable values, specifically, its argument.  For instance:

  (define h
    (let* ((pair (cons 1 2))
           (one (car pair)))
      (lambda ()
        one)))

  (define h
    (let ((pair (cons 1 2)))
      (lambda ()
        (car pair))))

Is this a correct transformation?  In this case, yes.  (If we can prove
that this is safe, then it can fold to (lambda () 1).)  But in general
to do this propagation we need to prove that nothing that can alias
`pair' will mutate its value.  `car' is pure -- if its argument is
indeed a pair, then it has no side effects -- but it is not constant.

>> Instead of moving those operations into the *primitive-constructors*
>> set, perhaps we should make a new set of primitives called something
>> like *primitive-mutable-accessors* ?
>
> Yes, though it’s not the accessor that’s mutable.  :-)
>
> ‘mutable-object-returning-primitive’ would be descriptive but is hard to
> read...

I think the real concern is not the mutability of the return value, but
rather of the arguments.

>> Also, if I'm correct in guessing the reason for this change (accessing
>> mutable memory), shouldn't the bytevector-*-ref operations go as well?
>
> No because they return an immutable object.

I think we got this wrong, Ludo, and we should probably create some list
of pure accessors for mutable data and put bytevector-*-ref in it, for
the same reason given above for `h'.

WDYT?

Andy
-- 
http://wingolog.org/