Why is this function not pure

Question

I just spent a significant amount of time debugging an issue that boils down to the following:

(defun my-new-alist ()
  `((x . nil)))

(setq a (my-new-alist))
(setq b (my-new-alist))

(push 1 (alist-get 'x a))
b ;; ((x . 1))

I expected a and b to be independent of each other (that is, I expected my-new-alist to be pure. Instead, it seems to create a new list when the defun is executed, and always return a reference to that very list. Part of my confusion stems from comparing with the following:

(defun my-new-list ()
  nil)

(setq a (my-new-list))
(setq b (my-new-list))

(push 1 a)
a ;; => (1)
b ;; => nil

Note also that anti-quoting the nil part fixes the issue, it seems; that is, the following function doesn't exhibit the problem:

(defun my-new-alist ()
  `((x . ,nil)))

What is the significant difference between the list and alist examples? Which parts of the ELisp manual discuss this issue? Why does antiquoting the nil part fix things?

This question is similar to, but not the same as, Proper reinitialization of a list? What is happening under the hood?. The answers to that question doesn't discuss why using nil isn't a problem, nor do they explain why antiquoting nil makes a difference. Additionally, I am looking for references in the Emacs lisp manual.

Answer 1

This does require precision to state correctly; I'll give it a go.

Whenever a form is read in, read is creating some lisp structure as it goes. The result of reading the text "(defun my-new-alist () `((x . nil)))" is a list of four elements, 'defun, 'my-new-alist, nil, and finally (quote ((x . nil))). When you eval this list, eval creates a function object using the caaar and caaaar as the argument list and the body, and assigns it to the environment using the name in the caar. This is straight forward.

Now when you call the function, it has to eval the body in the environment created by extending the environment of the call site by creating new bindings for the formal paramters in the arglist and the values from the call (this is just dynamic scope, and isn't actually relevant here, since your arglist is nil). The first thing it evaluates here is the call to the quote special form. quote is a form and not a function, because it specifically returns its argument without evaluating it, whereas all the arguments to a function call are evaluated automatically. Thus all calls to my-new-alist return a reference to the same list, in fact to the list that was created when this form was read.

Now we look at push. If we look in the ELisp manual, on the List Variables page (run M-x (info "(elisp)List Variables") to jump right to it), we see that "[push] creates a new list whose CAR is ELEMENT and whose CDR is the list specified by LISTNAME, and saves that list in LISTNAME." We also see that push is equivalent to (setf LISTNAME (cons ELEMENT LISTNAME)). In this case, that's (setf (alist-get 'x a) (cons 1 (alist-get 'x a)). This actually changes the value of the cdr in your alist to point to the newly-created cons. Anyone who has a reference to the alist will then see this new cons.