How could I implement the push macro?

Can someone help me understand how push can be implemented as a macro? The naive version below evaluates the place form twice, and does so before evaluating the element form:

(defmacro my-push (element place)
  `(setf ,place (cons ,element ,place)))

But if I try to fix this as below then I'm setf-ing the wrong place:

(defmacro my-push (element place)
   (let ((el-sym    (gensym))
         (place-sym (gensym)))
     `(let ((,el-sym    ,element)
            (,place-sym ,place))
        (setf ,place-sym (cons ,el-sym ,place-sym)))))

CL-USER> (defparameter *list* '(0 1 2 3))
*LIST*
CL-USER> (my-push 'hi *list*)
(HI 0 1 2 3)
CL-USER> *list*
(0 1 2 3)

How can I setf the correct place without evaluating twice?

Solution

Doing this right seems to be a little more complicated. For instance, the code for push in SBCL 1.0.58 is:

(defmacro-mundanely push (obj place &environment env)
  #!+sb-doc
  "Takes an object and a location holding a list. Conses the object onto
  the list, returning the modified list. OBJ is evaluated before PLACE."
  (multiple-value-bind (dummies vals newval setter getter)
      (sb!xc:get-setf-expansion place env)
    (let ((g (gensym)))
      `(let* ((,g ,obj)
              ,@(mapcar #'list dummies vals)
              (,(car newval) (cons ,g ,getter))
              ,@(cdr newval))
         ,setter))))

So reading the documentation on get-setf-expansion seems to be useful.

For the record, the generated code looks quite nice:

Pushing into a symbol:

(push 1 symbol)

expands into

(LET* ((#:G906 1) (#:NEW905 (CONS #:G906 SYMBOL)))
  (SETQ SYMBOL #:NEW905))

Pushing into a SETF-able function (assuming symbol points to a list of lists):

(push 1 (first symbol))

expands into

(LET* ((#:G909 1)
       (#:SYMBOL908 SYMBOL)
       (#:NEW907 (CONS #:G909 (FIRST #:SYMBOL908))))
  (SB-KERNEL:%RPLACA #:SYMBOL908 #:NEW907))

So unless you take some time to study setf, setf expansions and company, this looks rather arcane (it may still look so even after studying them). The 'Generalized Variables' chapter in OnLisp may be useful too.

Hint: if you compile your own SBCL (not that hard), pass the --fancy argument to make.sh. This way you'll be able to quickly see the definitions of functions/macros inside SBCL (for instance, with M-. inside Emacs+SLIME). Obviously, don't delete those sources (you can run clean.sh after install.sh, to save 90% of the space).