Hi,
Common Lisp requires that macroexpansions be available for all macros
which are not one of the defined special forms. This is to help
writing portable code walkers: they know that they need recognize only
the known special forms (e.g. PROGN, GO, LET etc.) and can delegate
all the rest to MACROEXPAND/-1 (e.g. MULTIPLE-VALUE-BIND etc.).
Sometimes I wonder whether optimization is still possible --I fear
it's not-- when the compiler is given output resulting from
MACROEXPAND instead of the original forms. Expansions may become quite
convoluted, and *I* wouldn't easily recognize optimizable patters there.
My attention was drawn to this point by looking at some expansion of
J. Amsterdam's ITERATE macro.
As an example, here's what the compiler gets to see:
-- (MULTIPLE-VALUE-CALL #'LIST ...) appears where there once was
a simpler MULTIPLE-VALUE-SETQ.
(macroexpand-1'(iter(for (s) in-packages '("ITER"))(princ s)))
(WITH-PACKAGE-ITERATOR
(#:PACKAGE-ITERATOR-3849 '("ITER") :EXTERNAL :INTERNAL :INHERITED)
(LET* ((#:G3850 NIL) (S NIL))
(BLOCK NIL
(TAGBODY LOOP-TOP-NIL
(PROGN ; multiple-value-setq was here
(LET* ((#:G3851 (MULTIPLE-VALUE-CALL #'LIST (#:PACKAGE-ITERATOR-3849))))
(LET
((#:G3852
(SETQ #:G3850
(LET ((#:G3854 (CAR #:G3851))) (SETQ #:G3851 (CDR #:G3851))
#:G3854)))) ; that was (pop ...)
(SETQ S
(LET ((#:G3856 (CAR #:G3851))) (SETQ #:G3851 (CDR #:G3851)) #:G3856))
#:G3852)) ; pop again
(IF (NOT #:G3850) (GO LOOP-END-NIL)))
(PRINC S) (GO LOOP-TOP-NIL) LOOP-END-NIL)
NIL)))
As another example, let's follow an expansion of the
MULTIPLE-VALUE-BIND macro (it's not a special form in ANSI):
clisp> (macroexpand-1'(multiple-value-bind(x y)(foo) (prin1 (cons x y))))
(LET*
((#:G4953 (MULTIPLE-VALUE-LIST (FOO))) (X (POP #:G4953)) (Y (POP #:G4953)))
(PRIN1 (CONS X Y)))
T
clisp> (macroexpand-1'(multiple-value-list (foo)))
(MULTIPLE-VALUE-CALL #'LIST (FOO))
T
(defun foo-initial(z)
(multiple-value-bind (x y) (bar)
(prin1 (list x y z))))
(defun foo-semi (z) ; macroexpanded m-v-b
(let* ((mvl (multiple-value-list (bar)))
(x (pop mvl))
(y (pop mvl)))
(prin1 (list x y z))))
(defun foo-expanded (z) ; macroexpanded m-v-l
(let* ((mvl (multiple-value-call #'list (bar)))
(x (pop mvl))
(y (pop mvl)))
(prin1 (list x y z))))
(defun bar() (values 1 2))
(mapc #'compile '(foo-initial foo-semi foo-expanded))
(mapc #'disassemble '(foo-initial foo-semi foo-expanded))
Disassembly clearly shows that CLISP does not compile the
macroexpanded code as well as the original form:
Disassembly of function FOO-INITIAL
(CONST 0) = BAR
1 required argument
0 optional arguments
No rest parameter
No keyword parameters
9 byte-code instructions:
0 (CALL0 0) ; BAR
2 (NV-TO-STACK 2)
4 (LOAD&PUSH 1)
5 (LOAD&PUSH 1)
6 (LOAD&PUSH 5)
7 (LIST&PUSH 3)
9 (PUSH-UNBOUND 1)
11 (CALLS1 131) ; PRIN1
13 (SKIP&RET 4)
Disassembly of function FOO-SEMI
(CONST 0) = BAR
1 required argument
0 optional arguments
No rest parameter
No keyword parameters
14 byte-code instructions:
0 (CALL0 0) ; BAR
2 (MV-TO-LIST)
3 (PUSH)
4 (LOAD&CAR&PUSH 0)
6 (LOAD&CDR&STORE 1)
8 (LOAD&CAR&PUSH 1)
10 (LOAD&CDR&STORE 2)
12 (LOAD&PUSH 1)
13 (LOAD&PUSH 1)
14 (LOAD&PUSH 6)
15 (LIST&PUSH 3)
17 (PUSH-UNBOUND 1)
19 (CALLS1 131) ; PRIN1
21 (SKIP&RET 5)
Disassembly of function FOO-EXPANDED
(CONST 0) = #<SYSTEM-FUNCTION LIST>
(CONST 1) = BAR
1 required argument
0 optional arguments
No rest parameter
No keyword parameters
17 byte-code instructions:
0 (CONST 0) ; #<SYSTEM-FUNCTION LIST>
1 (MVCALLP)
2 (CALL0 1) ; BAR
4 (MV-TO-STACK)
5 (MVCALL)
6 (PUSH)
7 (LOAD&CAR&PUSH 0)
9 (LOAD&CDR&STORE 1)
11 (LOAD&CAR&PUSH 1)
13 (LOAD&CDR&STORE 2)
15 (LOAD&PUSH 1)
16 (LOAD&PUSH 1)
17 (LOAD&PUSH 6)
18 (LIST&PUSH 3)
20 (PUSH-UNBOUND 1)
22 (CALLS1 131) ; PRIN1
24 (SKIP&RET 5)
ITER> (foo-initial 3)
(1 2 3)
(1 2 3)
ITER> (foo-semi 3)
(1 2 3)
(1 2 3)
ITER> (foo-expanded 3)
(1 2 3)
(1 2 3)
They all work alike.
So what's there to learn?
a) That CLISP performs a poor job at optimization on this example or
b) can one rather expect this to be a symptom of a more general behaviour?
c) Should macros avoid MACROEXPAND as much as possible?
Similarly, I believe that it's easier to generate code for
BLOCK/RETURN-FROM than for the more general call/cc that a
(hypothetical) Scheme macro might expand into.
Regards,
Jorg Hohle
Telekom/T-Systems Technology Center
From: Paul F. Dietz
Subject: Re: Subject: is optimization still possible after macroexpand?
Date:
Message-ID: <4194B428.9020901@dls.net>
Joerg Hoehle wrote:
> Hi,
>
> Common Lisp requires that macroexpansions be available for all macros
> which are not one of the defined special forms. This is to help
> writing portable code walkers: they know that they need recognize only
> the known special forms (e.g. PROGN, GO, LET etc.) and can delegate
> all the rest to MACROEXPAND/-1 (e.g. MULTIPLE-VALUE-BIND etc.).
>
> Sometimes I wonder whether optimization is still possible --I fear
> it's not-- when the compiler is given output resulting from
> MACROEXPAND instead of the original forms. Expansions may become quite
> convoluted, and *I* wouldn't easily recognize optimizable patters there.
Of course it's possible. A lot of what you get in macroexpanded code
is the introduction of temporary variables, which can be removed again
with constant/copy propagation. The lack of a & operator in Lisp
makes it easier to do this kind of optimization safely.
This is not to say that a specific compiler will be doing all the
optimizations you expect.
Paul
From: Marco Baringer
Subject: Re: Subject: is optimization still possible after macroexpand?
Date:
Message-ID: <m2actnusgh.fsf@bese.it>
Joerg Hoehle <······@users.sourceforge.net> writes:
> Common Lisp requires that macroexpansions be available for all macros
> which are not one of the defined special forms. This is to help
> writing portable code walkers: they know that they need recognize only
> the known special forms (e.g. PROGN, GO, LET etc.) and can delegate
> all the rest to MACROEXPAND/-1 (e.g. MULTIPLE-VALUE-BIND etc.).
(except in the face of macrolet and symbolmacrolet)
> So what's there to learn?
> a) That CLISP performs a poor job at optimization on this example or
> b) can one rather expect this to be a symptom of a more general behaviour?
> c) Should macros avoid MACROEXPAND as much as possible?
a) no. obviously the compiler can only work with what it sees, and any
"user land" substitiuion of a form with its macroexpansion is going
to kill compiler optimiziations (or even just compiler-macros).
clisp does as bad as everyone (but it's particularly hurt since
there's such a difference in efficency between calling "builtins"
(writen in C) and calling byte coded functions).
2) yes.
c) no. i'll take the efficency hit if it allows me to use
iterate. should that particular iterate form turn out to be a
bettlo neck i'll come back and re-write it in such a fashion that
the particular lisp i'm interested in (be it clisp or cmucl or
openmcl) produces better code.
--
-Marco
Ring the bells that still can ring.
Forget your perfect offering.
There is a crack in everything.
That's how the light gets in.
-Leonard Cohen
Historically, many of the best Lisp and Scheme compilers have
expanded all forms into a very small core language before any
optimization is performed.
Less capable compilers are more likely to depend on recognizing
special cases at the level of the surface syntax, because this
can be done without having to implement powerful optimizations.
> Similarly, I believe that it's easier to generate code for
> BLOCK/RETURN-FROM than for the more general call/cc that a
> (hypothetical) Scheme macro might expand into.
You're comparing apples and oranges. The reason it's easier
to generate good code for a BLOCK/RETURN-FROM is that Common
Lisp allow the return continuation to be invoked at most once.
It is this semantic restriction that makes the difference, not
the syntactic level at which the return continuation is made
explicit.
Will