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

> 3 juli 2020 kl. 21.05 skrev Andrea Corallo <andrea_corallo@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