GNU bug report logs - #42147
28.0.50; pure vs side-effect-free, missing optimizations?

Previous Next

Full log

View this message in rfc822 format

From: Andrea Corallo <andrea_corallo <at> yahoo.it>
To: Mattias Engdegård <mattiase <at> acm.org>,  Stefan Monnier <monnier <at> iro.umontreal.ca>
Cc: Paul Eggert <eggert <at> cs.ucla.edu>, 42147 <at> debbugs.gnu.org
Subject: bug#42147: 28.0.50; pure vs side-effect-free, missing optimizations?
Date: Sat, 4 Jul 2020 16:13:48 +0000 (UTC)

[Message part 1 (text/plain, inline)]

Mattias Engdegård <mattiase <at> acm.org> writes:

> 3 juli 2020 kl. 21.05 skrev Andrea Corallo <andrea_corallo <at> yahoo.it>:
>
>> attached the updated version of the patch updating the pure function
>> classification.
>
> Thanks Andrea! Philipp Stephani raised the interesting question of (essentially) whether 'car' is pure. For the purposes of the current constant folding in the byte compiler the answer is yes, but perhaps you have wider ambitions in your work?
>
> Clearly, (car X) cannot be moved past some operations with side-effects if X is aliased:
>
> (let* ((x (list 'a))
>        (y (car x)))
>   (f x)
>   y)
>
> Here, (car x) cannot be sunk past the call to f despite x remaining unchanged (assuming lexical binding).
> It would be useful to know more exactly what notion of purity you require.

Thanks for the observation, today I was studying the situation.

I think the notion of purity has to be the same one we use in the byte
compiler.  The trickiness is in if the considered object is immutable or
not.  The optimizer must stay in the boundary of what is allowed in this
regard.

To put in elisp what I think ATM:

(defun aaa ()
  (let ((x (list 1 2)))
    (1+ (car x)) ; <= legally optimizable
    ))

(defun bbb ()
  (let ((x (list 1 2)))
    (f x)        ; f is not pure
    (1+ (car x)) ; <= cannot optimize
    ))

(defun ccc ()
  (let ((x '(1 2)))
    (f x)        ; f is not pure
    (1+ (car x)) ; <= legally optimizable because immutable
    ))

(defun ddd ()
  (let ((x (list 1 2)))
    (f x)        ; f is pure
    (1+ (car x)) ; <= legally optimizable
    ))

Now given we are not constant folding `cons' we are not materializing
conses, as a consequence of these three example we would optimize only
`ccc' if we include `car' as pure.  AFAIU this is correct given
modifying an immutable object in `f' would be undefined.

So yes for me `car' is pure and I think we should add it to the list.

BTW reading the code of the native compiler I realized I am already
extrapolating for use a very similar list of optimizable functions to the one
proposed.  I still think would quite cleaner to classify these in
byte-opt.el.

Attached the updated patch where I'm adding car, car-safe, cdr,
cdr-safe, max, min.

Feedback welcome

Thanks

  Andrea

[0001-Add-a-number-of-functions-to-pure-fns-bug-42147.patch (text/x-patch, attachment)]

Previous Next

GNU bug tracking system
Copyright (C) 1999 Darren O. Benham, 1997,2003 nCipher Corporation Ltd, 1994-97 Ian Jackson.