How could I implement the push macro?

2019-07-10 17:23发布

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?

2条回答
兄弟一词,经得起流年.
2楼-- · 2019-07-10 17:49

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

查看更多
仙女界的扛把子
3楼-- · 2019-07-10 17:52

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:

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

  2. 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?

  3. 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?

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

查看更多
登录 后发表回答