Re: [PATCH, RFC] Macros expansion changes, robust symbol macros, and constant propagation

[Stefan Monnier]

>>> - removes Fmacroexpand and implements macroexpand-1 and macroexpand in lisp
>> Sounds good (indeed for gv.el we want macroexpand-1).  Do you have some
>> measurement of the performance impact?
> On my machine, macroexpand is about 30% slower than the old version,
> depending on environment size.

I think a good measurement is "load a whole bunch of *.el files", which
will spend time in eager macro-expansion (as well as a bit of `read' and
a bit of `eval', plus a bit of coding-system decode which could be
optimized away, ideally, but isn't yet).  30% slowdown for such
a test-case would be definitely considered "too costly".

> No, it's a correctness issue. This comment in the old lexical
> symbol-macrolet code (commented out in head) hints at the problem:
[...]
> idempotent on fully expanded forms. That doesn't work when it comes to
> symbol macro shadowing, as the author of the comment above figured out.

That author is damn clever!
OK, I remember the problem, indeed.

>> BTW, I see you sometimes strip the macroexpand-already-expanded tag.
>> Can't this lead again to repeated expansion?
> Yes, but only in a harmless way.  See above.

I still don't understand what guarantees that it's always harmless.

>>> - adds symbol-macros to the core, in macroexp
>> I don't think I like this: CL's symbol-macro is *very* rarely used, so
>> for now I'd rather keep it in cl-macs.el.
> Ah, but we use symbol macros to do constant propagation, and we want
> constant propagation to be in the core!

I'm not convinced symbol-macro is a good way to perform
constant propagation.  See my comment below.

> We need this analysis for optimizing let bindings.  cconv's analysis is
> similar in some respects, and I looked into using it, but cconv's
> analysis does both more (closure candidates) and less (reference
> analysis) than what we need

"More" is not a problem, I think.  As for "less", it might be easy to
address it.

> --- besides, it has a very inconvenient interface.

That is true.  But there are fairly good performance reasons for it.

>> It's only used for cl--expr-contains, so it should be in cl-macs.el, not
>> in macroexp.el.  And I'm really not sure this complexity is warranted
>> for those uses: does it fix actual bugs?
> We'll be using it for other tasks too.  Also, any unsafe code
> transformation is a bug.

Yes, but I'm not convinced it's really unsafe.  It is sometimes less
aggressive than it could, but that's not a problem.

> If we have a robust analysis engine, why not use it everywhere?

Because that can be very costly.

>>> - changes cl-defsubst so that it works like regular defsubst
>> Doesn't this break setf on defstruct slots?
> Yes, but I fixed it by restoring the old explicit-accessor code.  Having
> gv depend on compiler macros is scary.

But it's efficient.  A single symbol property provides both features at
the same time.

> A compiler macro should be pure optimization.  Code shouldn't depend
> on compiler macros for correctness.

That boat a sailed a long time ago.  We regularly depend on
compiler-macros for correctness (many CL functions are used in files
that do (eval-when-compiler (require 'cl))).  Emacs is not Common-Lisp.
And it's not like the code will misbehave: the compilation will simply
fail if the compiler-macro is absent, so it's still semantically
pretty clean.

>>> +(defun byte-optimize-do-constant-propagation (let-form)
[...]
>>> +           (macroexpand-all
>>> +            `(symbol-macrolet-shadowable
>>> +                 ,(nreverse const-bindings)
>>> +               ,@body)))))))
>> How does this handle the case where the var is first bound to a constant
>> and later setq'd?
> Oops. That code didn't make it into the patch. The intent is to use
> macroexp-analyze-free-variables to make mutated variables ineligible for
> this optimization.

Yuck!  The above is already pretty bad, and adding
macroexp-analyze-free-variables will make it even worse: optimizing
a let according to the above code takes time O(size(exp)).  Plus another
O(size(exp)) for macroexp-analyze-free-variables (actually, this one can
be even O(size(exp)^2) or so because at each step it can manipulate
data-structures that can grow with size(exp)).  And this for every
nesting level, so you get a serious O(N^2) behavior overall, sliding
towards O(N^3), just to optimize away some const bindings.

Not good.

The "immutable" info is already computed by cconv, so you could instead
change cconv to output code where the immutable let bindings
are annotated.

>>> (push (list temp) cl--loop-bindings)
>>> (setq form `(if (setq ,temp ,cond)
>>> -                                ,@(cl-subst temp 'it form))))
>>> +                                (symbol-macrolet-shadowable ((it ,temp))
>>> +                                  ,@form))))
>> Why not (setq form `(let ((it ,cond)) (when it ,@form)))?
> In dynamically bound code, we want the `it' symbol to be lexically
> scoped.

I don't think anyone really cares about that.

> I suppose it doesn't matter all that much, but if we have
> robust symbol-macro machinery, why not use it?

Because the (let ((it ,cond)) (when it ,@form)) is simpler and cleaner?

Also it will be more efficient for the lexical-binding code (as
discussed recently, in lexical-binding, `let' is cheaper than `setq').

OK, yes, it sucks in one respect: you'll get spurious warnings about
`it' being unused.  But that's a general problem we need to solve in
any case.

>>> +(defalias 'cl-letf 'letf)
>>> +(defalias 'cl-letf* 'letf*)
>> I don't think I want to have letf in the core

> I really don't like letf.  That said, we need it in the core if we have
> symbol macros in the core and we want to preserve existing
> symbol-macrolet behavior.

That's OK, since I still don't want symbol-macro in the core.

>> (but I'd like to change cl-letf so that in the case of
>> simple-variable bindings, those should be dynamically scoped, even in
>> lexical-binding code).
> I'm not sure this change makes sense.  It'd break existing code and
> break optimizations that depend on letf boiling down to regular let in
> simple cases.

Not sure what optimizations you're thinking of.  And I'm not talking
about not using `let', I'm just talking about marking those `let' as
dynamically-scoped.

> I'm not sure what problem it would solve either.

For non-variables, the semantics of `letf' is consistent with the
general semantics of dynamic scoping, but not that of lexical scoping.
E.g. in lexical scoping

  (funcall (let ((x 4)) (lambda () x)))

will always return 4.  But 

  (funcall (letf ((<PLACE> 4)) (lambda () <PLACE>)))

will usually not return 4 if <PLACE> is, say, `(car l)'.
The semantics of `letf' on PLACE match the semantic of
dynamically-scoped `let' on a variable.
  
> If users need to do something like this, they can use letf on
> (symbol-value variable)

Much less efficient, and comes with all kinds of warts when the variable
is buffer-local.  Better use a straightforward dynamically scoped `let'.

>>> +                (push `(define-setf-expander ,accessor (cl-x)
>> You can't use define-setf-expander here since it requires cl.el.
> Thanks for the reminder.  The original code used define-setf-expander,
> so I kept it.

I fixed the original code, then commented it out.  Your patch removes
the commented out fixed code and replaces it with the old non-fixed code.
I don't guarantee that the commented out code still works, but IIRC it
was working at some point.

>>> -                                               nil)
>>> +                                               (and unsafe (list argn 
>>> argv)))
>> Why undo this recent change?
> Copypasta from a slightly stale local copy.  Thanks for spotting the error.

OK, makes sense.  Then also keep the underscore on the _unsafe arg.

>>> +    (`(lambda ,arglist . ,body)
>>> +     (macroexp-analyze-free-variables
>> This form should never appear in macroexpanded code.
> It can appear in macroexpanded subtrees.  Try (macroexpand-all '(setq
> foo (lambda (x) (1+ x)))).

Then you have a bug somewhere: `lambda' is a macro, so a macroexpanded
expression should never have the shape (lambda ...).

>>> +    (`(closure ,cells ,arglist . ,body)
>> And this one shouldn't either.
> Hrm --- what if somebody substitutes a function by value into a form,
> and that function's value happens to be a closure form?

That's a bug in that somebody's code: (fboundp 'closure) => nil.

>> (defvar macroexp--sm-environment-tag
>> (make-symbol "--macroexp--sm-environment-tag--")
> Because if you hit C-M-x with point inside (say, to update the
> docstring), you define macroexp--sm-environment-tag to a new value and
> wreak havoc with any stored macro environments.

I prefer to say "don't do that" than to uglify the code the way you did.

> Using a keyword symbol instead of an uninterned one, since we'll never
> have a function with a keyword-symbol name --- right?

Yup.

>>> +    (`(function (lambda . ,_))
>>> +     ;; macroexpand-all has special logic to detect lambda in function
>>> +     ;; position, so we need a special case here too.
>> I don't understand the comment.
> Without this clause,

This clause is very much needed (it is *the* clause that deals with
`lambda', i.e. it is the normal case, not the "special case"), indeed.
I just don't understand what the comment is trying to say.

>>> +(defconst macroexpand-already-expanded
>>> +  (if (boundp 'macroexpand-already-expanded)
>>> +      (symbol-value 'macroexpand-already-expanded)
>>> +    (make-symbol "--macroexpand-already-expanded--"))
>> Again: why not a defvar?  Also, we could define it as an interned
>> well-known symbol.  E.g. macroexp--already-expanded.
> In this case, I think an interned well-known symbol will work.  I'd
> prefer making it a keyword symbol, though, in order to highlight its
> special effects.

I'd rather stay away from using keywords as valid functions.

>> Also, all that macroexpand-1 code should ideally be in macroexp.el
>> rather than in subr.el.  Maybe that introduces bootstrapping problems,
>> but IIRC it can be made to work (I played around with such a thing
>> during the cl-lib.el work).
> I'll try to make it work.  The cyclic dependencies on macroexp make me
> nervous, though.  What's so bad about putting things in subr?

Nothing serious.  "macroexp.el" is just the natural home of such a function.

> The macro environment should hold everything you need to expand a form
> in a given lexical environment.  By making the correct interpretation of
> the macro environment depend on a dynamic variable outside the
> environment itself, you introduce the possibility of subtle error ---
> you effectively give macro environments dynamic extent!

We already do that: macros like symbol-macrolet rely on
the dynamically scoped macroexpand-all-environment.

What other uses (besides symbol-macrolet) do you have for that
macroexpand-environment-hook-tag?

>>> +(defun memq-car (key alist)
>> Let's leave it close to its users, with a macroexp- prefix for now.
> What if I want to implement it in C after all?

We'll cross that bridge when we get there.


        Stefan