How could I implement the push macro?

Question

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?

Looking over the SBCL source, I see that they use the once-only macro to handle rplaca (see this link for more info http://stackoverflow.com/questions/9808928/understanding-how-to-implement-once-only-lisp-macro ). I would investigate rplaca for further understanding. — Paul Nathan, Aug 07 '12 at 22:43
@PaulNathan Can you please provide the SBCL version and source location you're looking at? Because I see `(defmacro-mundanely push (obj place &environment env) ...` in `src/code/early-setf.lisp` (SBCL 1.0.58), which doesn't use `once-only`. — Miron Brezuleanu, Aug 08 '12 at 07:27

score 4 · Accepted Answer · answered Aug 10 '12 at 06:25

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

score 1 · Answer 2 · answered Aug 08 '12 at 20:17

Taking a look at how the existing one (in SBCL, at least) does things, I see:

* (macroexpand-1 '(push 1 *foo*))

(LET* ((#:G823 1) (#:NEW822 (CONS #:G823 *FOO*)))
  (SETQ *FOO* #:NEW822))
T

So, I imagine, mixing in a combination of your version and what this generates, one might do:

(defmacro my-push (element place)
   (let ((el-sym  (gensym))
         (new-sym (gensym "NEW")))
     `(let* ((,el-sym  ,element)
             (,new-sym (cons ,el-sym ,place)))
        (setq ,place ,new-sym)))))

A few observations:

This seems to work with either setq or setf. Depending on what problem you're actually trying to solve (I presume re-writing push isn't the actual end goal), you may favor one or the other.
Note that place does still get evaluated twice... though it does at least do so only after evaluating element. Is the double evaluation something you actually need to avoid? (Given that the built-in push doesn't, I'm left wondering if/how you'd be able to... though I'm writing this up before spending terribly much time thinking about it.) Given that it's something that needs to evaluate as a "place", perhaps this is normal?
Using let* instead of let allows us to use ,el-sym in the setting of ,new-sym. This moves where the cons happens, such that it's evaluated in the first evaluation of ,place, and after the evaluation of ,element. Perhaps this gets you what you need, with respect to evaluation ordering?
I think the biggest problem with your second version is that your setf really does need to operate on the symbol passed in, not on a gensym symbol.

Hopefully this helps... (I'm still somewhat new to all this myself, so I'm making some guesses here.)

Interesting. The HyperSpec says the place form is only evaluated once, but it looks like SBCL knows that getting the value from a symbol twice is harmless. For a place form with a possible side effect it does: CL-USER> (macroexpand-1 '(push 4 (my-list-func))) (LET* ((#:G31 4) (#:G30 (CONS #:G31 (MY-LIST-FUNC)))) #:G30 (FUNCALL #'(SETF MY-LIST-FUNC) #:G30)). Does this form of SETF avoid a second evaluation somehow? — jjoelson, Aug 09 '12 at 13:28
When I actually run the above I get "Undefined function (SETF MY-LIST-FUNC)". Looks like the double evaluation problem is avoided by disallowing place forms which are not SETF-able on their own. Makes sense. — jjoelson, Aug 09 '12 at 13:34

How could I implement the push macro?

2 Answers2

Linked