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

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

[Mark H Weaver]

Hi Andy,

> commit d851e32fdc3d14804108f0389faa75a57599ced4
> Author: Andy Wingo <wingo-e+AXbWqSrlAAvxtiuMwx3w@public.gmane.org>
> 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".

Note that peval should not perform (in advance) any operations that
access _mutable_ memory, but accessing non-mutable memory should be
fine.

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* ?

>  (define *primitive-constructors*
>    ;; Primitives that return a fresh object.
> -  '(acons cons cons* list vector make-struct make-struct/no-tail))
> +  '(acons cons cons* list vector make-struct make-struct/no-tail
> +          car cdr vector-ref struct-ref))
>  
>  (define *effect-free-primitives*
>    `(values
> @@ -118,13 +119,11 @@
>      + * - / 1- 1+ quotient remainder modulo
>      not
>      pair? null? list? symbol? vector?
> -    car cdr
>      caar cadr cdar cddr
>      caaar caadr cadar caddr cdaar cdadr cddar cdddr
>      caaaar caaadr caadar caaddr cadaar cadadr caddar cadddr
>      cdaaar cdaadr cdadar cdaddr cddaar cddadr cdddar cddddr
> -    vector-ref
> -    struct? struct-vtable struct-ref
> +    struct? struct-vtable
>      bytevector-u8-ref bytevector-s8-ref
>      bytevector-u16-ref bytevector-u16-native-ref
>      bytevector-s16-ref bytevector-s16-native-ref

If you're going to move car and cdr from one set to the other, shouldn't
you do the same for caar, cadr, etc?  Also, if I'm correct in guessing
the reason for this change (accessing mutable memory), shouldn't the
bytevector-*-ref operations go as well?

    Thanks,
      Mark

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

[Ludovic Courtès]

Hi Mark,

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".
>
> Note that peval should not perform (in advance) any operations that
> access _mutable_ memory, but accessing non-mutable memory should be
> fine.

These operations need special care because they return a mutable object,
which must be protected against copy propagation, as in:

  (let ((x (cons (list 1) (list 2))))
    (set-car! (car x) 0)
    (car x))

We discussed this on IRC and failed to come up with a nice name, which
is why Andy kept this one.

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

> If you're going to move car and cdr from one set to the other, shouldn't
> you do the same for caar, cadr, etc?

No because they get reduced to a sequence of car & cdr.

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

Thanks,
Ludo’.

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

[Andy Wingo]

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/

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

[Ludovic Courtès]

Hi,

Andy Wingo <wingo@pobox.com> skribis:

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

Right, good point.

[...]

> `car' is pure -- if its argument is
> indeed a pair, then it has no side effects -- but it is not constant.

OK, got it!

(Though I think that the term ‘constant’, as used by GCC, is confusing.
I don’t have a better name to propose, though.)

[...]

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

Yes, agreed.

Thanks!

Ludo’.

PS: In that context, it must be quite a relief to work on a purely
    functional language...  :-)

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

[Noah Lavine]

Hello,

> (Though I think that the term ‘constant’, as used by GCC, is confusing.
> I don’t have a better name to propose, though.)

How about 'algebraic'? As in functions in basic algebra. (I know it
has a different meaning, though.)

Or alternatively, something referencing the lambda calculus, since all
lambda calculus functions have this property.

Noah

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

[Ludovic Courtès]

Hi,

>> (Though I think that the term ‘constant’, as used by GCC, is confusing.
>> I don’t have a better name to propose, though.)
>
> How about 'algebraic'? As in functions in basic algebra. (I know it
> has a different meaning, though.)

Hmm, I’m not convinced.

> Or alternatively, something referencing the lambda calculus, since all
> lambda calculus functions have this property.

Problem is that the eq?/equal? distinction doesn’t exist in the
beautiful world of λ calculus.  :-)

Thanks,
Ludo’.