byte-opt.el addition - optimize list of compile-time constants

byte-opt.el addition - optimize list of compile-time constants

[Zack Weinberg]

Consider a construct like the following, which might appear in a major
mode definition.  (This example is from my half-written major mode for
editing GCC machine descriptions.  These are mostly Lisp-like but
contain large blocks of embedded C, which it would be nice to apply
c-mode to.  The MMM library tries to make that possible.  It doesn't
work very well with c-mode right now, but that's irrelevant to this email.)

(when (require 'mmm-auto nil t)
  (mmm-add-classes
   '((md-embedded-c
      :submode c-mode
      :front "^{"
      :back "^}"
      :include-front t
      :include-back t
      ;; If the 'back' } is on a line by itself, include the carriage
      ;; return too; this makes the submode background highlight look
      ;; less strange.
      :back-offset #'(lambda () (when (eq (following-char) ?\n)
                                  (forward-char 1)))
      )))

One would like the anonymous :back-offset function to be
byte-compiled.  This does not happen (with 21.3.1) because the byte
compiler does not look inside a quoted form for lambda expressions.

I can make it get byte-compiled by using ` instead of ':

(when (require 'mmm-auto nil t)
  (mmm-add-classes
   `((md-embedded-c
      :submode c-mode
      :front "^{"
      :back "^}"
      :include-front t
      :include-back t
      ;; If the 'back' } is on a line by itself, include the carriage
      ;; return too; this makes the submode background highlight look
      ;; less strange.
      :back-offset #'(lambda () (when (eq (following-char) ?\n)
                                  (forward-char 1)))
      )))

The byte compiler then sees, after ` gets macroexpanded,

  (list (list
          'md-embedded-c
          :submode 'c-mode
          :front "^{"
          :back "^}"
          :include-front t
          :include-back t
          :back-offset (function (lambda () ...))))

and it *does* look into that for the nested lambda and compile it.
However, the cost of this is a substantially less efficient byte-code
sequence for the outer form.  Instead of having the entire
S-expression in the constant vector, each individual component goes
into the vector, and a rather lengthy byte-code sequence is generated
to execute the (list (list ...)) at runtime.  This does not matter
terribly much for *this* example, which is going to be executed once
when the file is loaded, but I can easily imagine circumstances where
it would matter.  I can work around this by writing (eval-when-compile
...) around the `(...) form, but that's just plain ugly.

I dug through the byte-compiler a bit and determined that it makes no
attempt whatsoever to optimize (list ...) expressions.  So I wrote a
basic byte-optimize-list function, and here it is, suitable for being
slapped into byte-opt.el.

(defun byte-optimize-list (form)
   ; (list) -> nil
  (if (null (cdr form))
      nil

    ; (list X Y Z ...) -> (quote (X Y Z)) when X Y Z are all
    ; compile-time constants.  In addition to the set of things for
    ; which byte-compile-constp is true, detect embedded
    ; (function ...) expressions and compile them, which turns them
    ; into compile-time constants.

    (catch :nonconstant
      (let ((new-form
	     (mapcar (lambda (elem)
		       (if (consp elem)
			 (cond 
					; (quote X) -> X
			  ((eq (car elem) 'quote)
			   (car (cdr elem)))
			                ; (function X) -> byte-compiled X
			  ((eq (car elem) 'function)
			   (byte-compile (car (cdr elem))))
					; ??? (lambda ...) -> byte-compile it
			  ((eq (car elem) 'lambda)
			   (byte-compile elem))
			  (t (throw :nonconstant form)))
			 (if (byte-compile-constp elem)
			     elem
			   (throw :nonconstant form))))
		     (cdr form))))

	; If we get here, new-form is a list of constants; turn it
	; into a constant.
	(list 'quote new-form)))))

(put 'list 'byte-optimizer 'byte-optimize-list)

This does have several issues - I'm not proposing it be put in as is.
First, I'm unsure I'm unsure whether it is appropriate to detect and
byte-compile a bare lambda.  The manual dithers on the subject.

Second, I'm not sure why I'm even getting uncompiled lambdas in the
list.  Shouldn't the master byte-opt loop, operating depth-first, have
already done it?  Having to do it here means that if we have a list
which has several lambda expressions followed by something that isn't
a compile-time constant, we'll compile the lambdas, discover the
non-constant, throw away the compiled functions, and have to do them
over again later.

Rather less important is the question of whether I should be
trying to optimize lists that aren't entirely constants.  It is
possible that, e.g. given 

(list 1 2 3 (+ var1 var2) 4 5 6)

it would be appropriate to translate it to

(nconc '(1 2 3) (+ var1 var2) '(4 5 6))

But I can see that being not a good idea, as well, so I didn't do it.

Finally, I'm not sure about coding style.  The catch/let/mapcar/nested
conditionals sequence is rather ugly, IMO, but I couldn't think of a
better way.

Thoughts?

(please cc:, I'm not subscribed to emacs-devel.)

zw

Re: byte-opt.el addition - optimize list of compile-time constants

[Stefan Monnier]

> I dug through the byte-compiler a bit and determined that it makes no
> attempt whatsoever to optimize (list ...) expressions.  So I wrote a

The reason for this is that (eq (list 1) (list 1)) returns nil.
So the optimization which replaces (list 1) with '(1) can change the
behavior of the code.
Example:

   (defun foo () (list 1))
   ...
   (message "%s" (if (eq (foo) (foo)) "Optimized" "No optimization"))

Admittedly, such situations are relatively uncommon, but they do arise and
it is very difficult [read: impossible] to detect them,


        Stefan


PS: Note that `concat' has the same problem, and yet (concat "foo" "bar")
    is byte-optimized to "foobar".  The reason for the difference is that
    it so happens that such differences matter much less often for strings,
    and also that the optimzation has been used for such a long time that it
    can be considered as part of the semantics of `concat'.

Re: byte-opt.el addition - optimize list of compile-time constants

[Zack Weinberg]

Stefan Monnier <monnier@iro.umontreal.ca> writes:

>> I dug through the byte-compiler a bit and determined that it makes no
>> attempt whatsoever to optimize (list ...) expressions.  So I wrote a
>
> The reason for this is that (eq (list 1) (list 1)) returns nil.
> So the optimization which replaces (list 1) with '(1) can change the
> behavior of the code.

I was going to suggest that (list 1 2 3) or longer could be replaced
with (copy-list '(1 2 3)) in that case.  Three entries is the point at
which the generated bytecode starts being shorter for copy-list.
However, I see that copy-list is not a primitive, nor even a standard
function, but a CL function, so that won't fly.

> PS: Note that `concat' has the same problem, and yet (concat "foo" "bar")
>     is byte-optimized to "foobar".  The reason for the difference is that
>     it so happens that such differences matter much less often for strings,
>     and also that the optimzation has been used for such a long time that it
>     can be considered as part of the semantics of `concat'.

I seriously wonder how much would break if this optimization were
implemented for 'list'.  My suspicion is that people don't commonly
apply 'eq' to lists in the first place.

zw

Re: byte-opt.el addition - optimize list of compile-time constants

[Stefan Monnier]

> I seriously wonder how much would break if this optimization were
> implemented for 'list'.  My suspicion is that people don't commonly
> apply 'eq' to lists in the first place.

Well, try it:

  (put 'list 'byte-optimizer 'byte-optimize-pure-func)
  (put 'list* 'byte-optimizer 'byte-optimize-pure-func)
  (put 'cons 'byte-optimizer 'byte-optimize-pure-func)
  (put 'append 'byte-optimizer 'byte-optimize-pure-func)


-- Stefan

Re: byte-opt.el addition - optimize list of compile-time constants

[Paul Pogonyshev]

Zack Weinberg wrote:
> I seriously wonder how much would break if this optimization were
> implemented for 'list'.  My suspicion is that people don't commonly
> apply 'eq' to lists in the first place.

You are very wrong here.  While it will hardly break sane code,
`eq' is _very_ often applied to cons cells, e.g. lists.

Paul

Re: byte-opt.el addition - optimize list of compile-time constants

[Zack Weinberg]

Stefan Monnier <monnier@iro.umontreal.ca> writes:

>> I seriously wonder how much would break if this optimization were
>> implemented for 'list'.  My suspicion is that people don't commonly
>> apply 'eq' to lists in the first place.
>
> Well, try it:
>
>   (put 'list 'byte-optimizer 'byte-optimize-pure-func)
>   (put 'list* 'byte-optimizer 'byte-optimize-pure-func)
>   (put 'cons 'byte-optimizer 'byte-optimize-pure-func)
>   (put 'append 'byte-optimizer 'byte-optimize-pure-func)

  !! Symbol's function definition is void ((byte-optimize-pure-func))

I guess this is only in CVS Emacs?

zw

Re: byte-opt.el addition - optimize list of compile-time constants

[Stefan Monnier]

>> (put 'list 'byte-optimizer 'byte-optimize-pure-func)
>> (put 'list* 'byte-optimizer 'byte-optimize-pure-func)
>> (put 'cons 'byte-optimizer 'byte-optimize-pure-func)
>> (put 'append 'byte-optimizer 'byte-optimize-pure-func)

>   !! Symbol's function definition is void ((byte-optimize-pure-func))

> I guess this is only in CVS Emacs?

No, it's on the trunk as well:

   ~-0% cd ~/src/emacs/trunk/lisp/emacs-lisp/
   lisp/emacs-lisp-0% grep byte-optimize-pure-func byte-opt.el
   (put 'concat 'byte-optimizer 'byte-optimize-pure-func)
   (put 'symbol-name 'byte-optimizer 'byte-optimize-pure-func)
   (put 'regexp-opt 'byte-optimizer 'byte-optimize-pure-func)
   (put 'regexp-quote 'byte-optimizer 'byte-optimize-pure-func)
   (defun byte-optimize-pure-func (form)
   lisp/emacs-lisp-0% 

It's been that way since 2004-03-22.


        Stefan

Re: byte-opt.el addition - optimize list of compile-time constants

[Nick Roberts]

 > > I guess this is only in CVS Emacs?
 > 
 > No, it's on the trunk as well:
 > 
 >    ~-0% cd ~/src/emacs/trunk/lisp/emacs-lisp/
 >    lisp/emacs-lisp-0% grep byte-optimize-pure-func byte-opt.el
 >    (put 'concat 'byte-optimizer 'byte-optimize-pure-func)
 >    (put 'symbol-name 'byte-optimizer 'byte-optimize-pure-func)
 >    (put 'regexp-opt 'byte-optimizer 'byte-optimize-pure-func)
 >    (put 'regexp-quote 'byte-optimizer 'byte-optimize-pure-func)
 >    (defun byte-optimize-pure-func (form)
 >    lisp/emacs-lisp-0% 
 > 
 > It's been that way since 2004-03-22.

So its only in CVS Emacs. 21.3, the last release, came out in 2003

It appears that byte-optimize-pure-func used to be called byte-optimize-concat

Nick

Re: byte-opt.el addition - optimize list of compile-time constants

[Zack Weinberg]

Stefan Monnier <monnier@iro.umontreal.ca> writes:

>> I seriously wonder how much would break if this optimization were
>> implemented for 'list'.  My suspicion is that people don't commonly
>> apply 'eq' to lists in the first place.
>
> Well, try it:
>
>   (put 'list 'byte-optimizer 'byte-optimize-pure-func)
>   (put 'list* 'byte-optimizer 'byte-optimize-pure-func)
>   (put 'cons 'byte-optimizer 'byte-optimize-pure-func)
>   (put 'append 'byte-optimizer 'byte-optimize-pure-func)

I checked out CVS Emacs and tried this, and it fails catastrophically
during bootstrap; so I guess my intuition was wrong.  Optimizing list
or append with byte-optimize-pure-func causes errors like the following:

    In byte-optimize-lapcode:
    byte-opt.el:1748:45:Warning: `t' called as a function
    byte-opt.el:1970:52:Warning: `nil' called as a function

    In end of data: byte-opt.el:2044:1:Warning: the following
    functions are not known to be defined: t, nil

and optimizing cons causes

    In toplevel form:
    ../../emacs/lisp/emacs-lisp/byte-opt.el:1508:45:Error: Wrong type
    argument: sequencep, 0

-- both of these are from compiling byte-opt.el from 'make bootstrap'.

I'm interested in debugging this, but I don't know how to proceed.

I'll also point out that this does not solve the problem I am
interested in solving; with list optimized via
byte-optimize-pure-func, debug-on-entry byte-optimize-pure-func and
then execute

(disassemble 
  (lambda nil 
    `(:a 1 :b 2 
      :c #'(lambda nil (when (eq (following-char) ?\n) (forward-char 1))))))

and

(disassemble 
  (lambda nil 
    `(:a 1 :b 2 
      :c ,#'(lambda nil (when (eq (following-char) ?\n) (forward-char 1))))))

In the first case, byte-optimize-pure-func is never called and the
inner function is not compiled (I assume this is because ` is being
optimized to ' when there is no , or ,@ anywhere in its form).  In the
second place, byte-optimize-pure-func is called, but the optimization
fails because a (function ...) form appears inside the arguments to
list, which does not count as byte-compile-constp.  This is the other
problem I mentioned earlier - at the point at which the
'byte-optimizer function for list is called, the inner function has
not yet been compiled, contrary to the general principle that the byte
optimizer operates depth-first.

zw

Re: byte-opt.el addition - optimize list of compile-time constants

[Stefan Monnier]

> (disassemble 
>   (lambda nil 
>     `(:a 1 :b 2 
>       :c ,#'(lambda nil (when (eq (following-char) ?\n) (forward-char 1))))))
[...]
> second place, byte-optimize-pure-func is called, but the optimization
> fails because a (function ...) form appears inside the arguments to
> list, which does not count as byte-compile-constp.  This is the other

Hmm... we should probably update byte-compile-constp to accept
(function ...) just like it accepts (quote ...).

> problem I mentioned earlier - at the point at which the
> 'byte-optimizer function for list is called, the inner function has
> not yet been compiled, contrary to the general principle that the byte
> optimizer operates depth-first.

The "byte-optimizer" has two phases: one done before byte-compilation and
one after.  The byte-optimize-pure-func is done before.

As for your particular problem, there's an easier solution:

    (defun foo-aux nil (when (eq (following-char) ?\n) (forward-char 1))
    ...
    (lambda nil
      '(:a 1 :b 2 :c foo-aux))


-- Stefan

Re: byte-opt.el addition - optimize list of compile-time constants

[Zack Weinberg]

Stefan Monnier <monnier@iro.umontreal.ca> writes:

>> (disassemble 
>>   (lambda nil 
>>     `(:a 1 :b 2 
>>       :c ,#'(lambda nil (when (eq (following-char) ?\n) (forward-char 1))))))
> [...]
>> second place, byte-optimize-pure-func is called, but the optimization
>> fails because a (function ...) form appears inside the arguments to
>> list, which does not count as byte-compile-constp.  This is the other
>
> Hmm... we should probably update byte-compile-constp to accept
> (function ...) just like it accepts (quote ...).

Yes, that sounds like a good move.

>> problem I mentioned earlier - at the point at which the
>> 'byte-optimizer function for list is called, the inner function has
>> not yet been compiled, contrary to the general principle that the
>> byte optimizer operates depth-first.
>
> The "byte-optimizer" has two phases: one done before
> byte-compilation and one after.  The byte-optimize-pure-func is done
> before.

Right.  I was referring to the source optimizer.  Whatever the
consequence, this means the best the source optimizer can do is
convert my `(...) form to a '(...) form, and the inner lambda won't
get compiled.

I suppose I'm trying to fix the bug in the wrong place.  Really, what
I want is for the byte compiler to look inside complicated '(...)
forms for embedded lambda expressions, and compile them.  I think it's
byte-compile-quote that would be responsible for doing that?

> As for your particular problem, there's an easier solution:
>
>     (defun foo-aux nil (when (eq (following-char) ?\n) (forward-char 1))
>     ...
>     (lambda nil
>       '(:a 1 :b 2 :c foo-aux))

This is what I've done for the time being, but I consider it somewhat
infelicitous, which is why i'm flailing around trying to improve the
byte compiler.

zw

Re: byte-opt.el addition - optimize list of compile-time constants

[Stefan Monnier]

>>> problem I mentioned earlier - at the point at which the
>>> 'byte-optimizer function for list is called, the inner function has
>>> not yet been compiled, contrary to the general principle that the
>>> byte optimizer operates depth-first.
>> 
>> The "byte-optimizer" has two phases: one done before
>> byte-compilation and one after.  The byte-optimize-pure-func is done
>> before.

> Right.  I was referring to the source optimizer.  Whatever the
> consequence, this means the best the source optimizer can do is
> convert my `(...) form to a '(...) form, and the inner lambda won't
> get compiled.

No.  If you change byte-compile-constp to recognize `function', together
with marking the list/cons/append primitives as pure, it should work.

> I suppose I'm trying to fix the bug in the wrong place.

I don't think so.  At least if you want to solve it in the byte-compiler,
doing it at the source-level is probably not a bad idea.

> Really, what I want is for the byte compiler to look inside complicated
> '(...)  forms for embedded lambda expressions, and compile them.  I think
> it's byte-compile-quote that would be responsible for doing that?

That's dangerous because there can be a (lambda ...) form without
it actually being meant to be byte-compiled.

>> As for your particular problem, there's an easier solution:
>> 
>> (defun foo-aux nil (when (eq (following-char) ?\n) (forward-char 1))
>> ...
>> (lambda nil
>> '(:a 1 :b 2 :c foo-aux))

> This is what I've done for the time being, but I consider it somewhat
> infelicitous, which is why i'm flailing around trying to improve the
> byte compiler.

What's infelicitous about it?


        Stefan

Re: byte-opt.el addition - optimize list of compile-time constants

[Zack Weinberg]

Stefan Monnier <monnier@iro.umontreal.ca> writes:

>>>> problem I mentioned earlier - at the point at which the
>>>> 'byte-optimizer function for list is called, the inner function has
>>>> not yet been compiled, contrary to the general principle that the
>>>> byte optimizer operates depth-first.
>>> 
>>> The "byte-optimizer" has two phases: one done before
>>> byte-compilation and one after.  The byte-optimize-pure-func is done
>>> before.
>
>> Right.  I was referring to the source optimizer.  Whatever the
>> consequence, this means the best the source optimizer can do is
>> convert my `(...) form to a '(...) form, and the inner lambda won't
>> get compiled.
>
> No.  If you change byte-compile-constp to recognize `function', together
> with marking the list/cons/append primitives as pure, it should work.

How can it?  The best that the source optimizer can do is turn
`(... ,#'(lambda ...) ...) into '(... #'(lambda ...) ...).  This
happens *before* anything goes looking for nested functions to
compile.  And I already know that if I write '(... #'(lambda ...) ...), 
the function does not get compiled.

>> Really, what I want is for the byte compiler to look inside complicated
>> '(...)  forms for embedded lambda expressions, and compile them.  I think
>> it's byte-compile-quote that would be responsible for doing that?
>
> That's dangerous because there can be a (lambda ...) form without
> it actually being meant to be byte-compiled.

which is what (function ...) is for, right?  I am quite confused by
what the manual says about function vs. bare lambda expressions.

>>> (defun foo-aux nil (when (eq (following-char) ?\n) (forward-char 1))
>>> ...
>>> (lambda nil
>>> '(:a 1 :b 2 :c foo-aux))
>
>> This is what I've done for the time being, but I consider it somewhat
>> infelicitous, which is why i'm flailing around trying to improve the
>> byte compiler.
>
> What's infelicitous about it?

More reading, less everything-in-one-place-ness.  Basically the same
thing that's infelicitous about writing a separate defun for a simple
mapcar callback that will only be used in one place.

zw

Re: byte-opt.el addition - optimize list of compile-time constants

[Miles Bader]

> which is what (function ...) is for, right?  I am quite confused by
> what the manual says about function vs. bare lambda expressions.

A user might well have a constant list with (function (lambda ...))
embedded in it that _isn't_ intended to be executed; the compiler
simply cannot make assumptions like you suggest about the contents of
a constant list.

-Miles

Re: byte-opt.el addition - optimize list of compile-time constants

[Zack Weinberg]

Miles Bader <snogglethorpe@gmail.com> writes:

>> which is what (function ...) is for, right?  I am quite confused by
>> what the manual says about function vs. bare lambda expressions.
>
> A user might well have a constant list with (function (lambda ...))
> embedded in it that _isn't_ intended to be executed; the compiler
> simply cannot make assumptions like you suggest about the contents of
> a constant list.

I thought the whole point of (function ...) was to assert that the
lambda expression it contains *will* be used by execution.

zw

Re: byte-opt.el addition - optimize list of compile-time constants

[Miles Bader]

> > A user might well have a constant list with (function (lambda ...))
> > embedded in it that _isn't_ intended to be executed; the compiler
> > simply cannot make assumptions like you suggest about the contents of
> > a constant list.
> 
> I thought the whole point of (function ...) was to assert that the
> lambda expression it contains *will* be used by execution.

Yes, but that only applies if it occurs in an evaluable context. 
Anyplace else, all bets are off.

-Miles

Re: byte-opt.el addition - optimize list of compile-time constants

[Zack Weinberg]

Miles Bader <snogglethorpe@gmail.com> writes:

>> > A user might well have a constant list with (function (lambda ...))
>> > embedded in it that _isn't_ intended to be executed; the compiler
>> > simply cannot make assumptions like you suggest about the contents of
>> > a constant list.
>> 
>> I thought the whole point of (function ...) was to assert that the
>> lambda expression it contains *will* be used by execution.
>
> Yes, but that only applies if it occurs in an evaluable context. 
> Anyplace else, all bets are off.

That strikes me as just plain silly.  What's the point of a hint if it
doesn't always mean what it means?

And data structures containing code are common, and are in fact one of
the nicer things about Lisp in the first place - why pessimize them?

zw

Re: byte-opt.el addition - optimize list of compile-time constants

[Miles Bader]

> >> I thought the whole point of (function ...) was to assert that the
> >> lambda expression it contains *will* be used by execution.
> >
> > Yes, but that only applies if it occurs in an evaluable context.
> > Anyplace else, all bets are off.
> 
> That strikes me as just plain silly.  What's the point of a hint if it
> doesn't always mean what it means?

If there's a random arbitrary list constant in some code, how on earth
is the compiler supposed to tell what the intended meaning of
sub-components of the list are?!?  A sublist of the form (function
(lambda ...)) _could_ be a function constant intended to be extracted
from the list and executed, but it _also_ could be a list of keywords
for something, or a function constant that the user wants to interpret
himself; you just can't tell.

Consider C -- The sequence of characters "#define" has a meaning in a
code context, but the compiler can hardly go interpreting it inside of
string constants!

> And data structures containing code are common, and are in fact one of
> the nicer things about Lisp in the first place - why pessimize them?

The compiler can only optimize things that are safe to optimize, and this isn't.

-Miles

Re: byte-opt.el addition - optimize list of compile-time constants

[Stefan Monnier]

>> No.  If you change byte-compile-constp to recognize `function', together
>> with marking the list/cons/append primitives as pure, it should work.

> How can it?  The best that the source optimizer can do is turn
> `(... ,#'(lambda ...) ...) into '(... #'(lambda ...) ...).  This
> happens *before* anything goes looking for nested functions to
> compile.  And I already know that if I write '(... #'(lambda ...) ...),
> the function does not get compiled.

Hmm... you're right.  Tho it can call the byte-compiler, but that's not
quite as simple as I made it out to be.

>>> Really, what I want is for the byte compiler to look inside complicated
>>> '(...)  forms for embedded lambda expressions, and compile them.  I think
>>> it's byte-compile-quote that would be responsible for doing that?
>> 
>> That's dangerous because there can be a (lambda ...) form without
>> it actually being meant to be byte-compiled.

> which is what (function ...) is for, right?  I am quite confused by
> what the manual says about function vs. bare lambda expressions.

No.  `function' is s special form, like `quote' and `while'.  But we're
talking about sub-elements inside a quoted expression, i.e. random data
which we have no clue whether it'll ever be used as code or not.  In such
a context, neither `quote', nor `while' have any special meaning:
they're only symbols.

> More reading, less everything-in-one-place-ness.  Basically the same
> thing that's infelicitous about writing a separate defun for a simple
> mapcar callback that will only be used in one place.

By the way: getting back to your original example:

(when (require 'mmm-auto nil t)
  (mmm-add-classes
   '((md-embedded-c
      :submode c-mode
      :front "^{"
      :back "^}"
      :include-front t
      :include-back t
      ;; If the 'back' } is on a line by itself, include the carriage
      ;; return too; this makes the submode background highlight look
      ;; less strange.
      :back-offset #'(lambda () (when (eq (following-char) ?\n)
                                  (forward-char 1)))
      )))

How often is this code executed?  It doesn't smell like code you're using
inside a loop, so efficiency is really completely irrelevant: the extra
byte-codes and consing you get with backquotes is really a total non-issue.


        Stefan

Re: byte-opt.el addition - optimize list of compile-time constants

[Zack Weinberg]

Miles Bader <snogglethorpe@gmail.com> writes:

>> >> I thought the whole point of (function ...) was to assert that the
>> >> lambda expression it contains *will* be used by execution.
>> >
>> > Yes, but that only applies if it occurs in an evaluable context.
>> > Anyplace else, all bets are off.
>> 
>> That strikes me as just plain silly.  What's the point of a hint if it
>> doesn't always mean what it means?
>
> If there's a random arbitrary list constant in some code, how on earth
> is the compiler supposed to tell what the intended meaning of
> sub-components of the list are?!?

By reference to the language definition.  That's really what we're
quibbling about here - I'm saying the language should be defined such
that (function (lambda ...)) should indicate a function constant even
if arbitrarily nested within a (quote ...) form, you're saying it
shouldn't.

In evidence for my position I would like to point out that it is silly
for '(1 2 3 #'(lambda ...) 4 5 6) to mean something different than
(list 1 2 3 #'(lambda ...) 4 5 6), and the byte compiler compiles the
embedded lambda in the second case, so logically it ought to in the
first case as well.

Also, in Common Lisp the situation is clearly that the compiler _is_
entitled to compile (function ...) wherever it finds it - Emacs Lisp
is not the same thing, of course, but I see no reason for divergence
here.

zw

Re: byte-opt.el addition - optimize list of compile-time constants

[Stefan Monnier]

> In evidence for my position I would like to point out that it is silly
> for '(1 2 3 #'(lambda ...) 4 5 6) to mean something different than
> (list 1 2 3 #'(lambda ...) 4 5 6), and the byte compiler compiles the
> embedded lambda in the second case, so logically it ought to in the
> first case as well.

> Also, in Common Lisp the situation is clearly that the compiler _is_
> entitled to compile (function ...) wherever it finds it - Emacs Lisp
> is not the same thing, of course, but I see no reason for divergence
> here.

Note that the expression

     (list 1 2 (function (lambda () (with-current-buffer))))

can be rejected by the compiler (not enough arguments to the
with-current-buffer macro) whereas

     '(1 2 (function (lambda () (with-current-buffer))))

can't because it's just a quoted constant which just happens to look like
invalid code.


        Stefan

Re: byte-opt.el addition - optimize list of compile-time constants

[Miles Bader]

> Also, in Common Lisp the situation is clearly that the compiler _is_
> entitled to compile (function ...) wherever it finds it

Can you provide a reference for this?  Given that it's quite
dangerous, I'm skeptical of this claim.

Note that a possibly safer alternative would be to have the #' reader
macro expand into something less ambiguous during compilation (e.g., a
special non-interned symbol), which the byte-compiler could then
safely interpret inside of constants.  This may cause grief for
somebody that uses #' in a non-traditional way, and _expects_ to see
(function (lambda ...)), but that may be an acceptable price.

-Miles

Re: byte-opt.el addition - optimize list of compile-time constants

[Zack Weinberg]

Stefan Monnier <monnier@iro.umontreal.ca> writes:

>> which is what (function ...) is for, right?  I am quite confused by
>> what the manual says about function vs. bare lambda expressions.
>
> No.  `function' is s special form, like `quote' and `while'.  But we're
> talking about sub-elements inside a quoted expression, i.e. random data
> which we have no clue whether it'll ever be used as code or not.  In such
> a context, neither `quote', nor `while' have any special meaning:
> they're only symbols.

See the other thread of the discussion.

> By the way: getting back to your original example:
>
> (when (require 'mmm-auto nil t)
>   (mmm-add-classes
>    '((md-embedded-c
>       :submode c-mode
>       :front "^{"
>       :back "^}"
>       :include-front t
>       :include-back t
>       ;; If the 'back' } is on a line by itself, include the carriage
>       ;; return too; this makes the submode background highlight look
>       ;; less strange.
>       :back-offset #'(lambda () (when (eq (following-char) ?\n)
>                                   (forward-char 1)))
>       )))
>
> How often is this code executed?  It doesn't smell like code you're using
> inside a loop, so efficiency is really completely irrelevant: the extra
> byte-codes and consing you get with backquotes is really a total non-issue.

The outer code is executed only once when the library is loaded.  The
embedded lambda *is* executed in a loop, which is why I care about it
getting compiled.  As I said in the original message, it is easy to
come up with cases where the extra byte-codes and consing from
backquotes *are* performance-relevant, but given how badly it breaks
things to enable that optimization, I'm prepared to drop that (unless
someone wants to help me debug weird byte-compiler crashes).

zw

Re: byte-opt.el addition - optimize list of compile-time constants

[Stefan Monnier]

>> How often is this code executed?  It doesn't smell like code you're using
>> inside a loop, so efficiency is really completely irrelevant: the extra
>> byte-codes and consing you get with backquotes is really a total non-issue.

> The outer code is executed only once when the library is loaded.  The
> embedded lambda *is* executed in a loop, which is why I care about it
> getting compiled.

I understand that part, I'm only talking about the use of backquote to get
the lambda to be compiled at the cost of a few byte-codes and conses.

> As I said in the original message, it is easy to
> come up with cases where the extra byte-codes and consing from
> backquotes *are* performance-relevant, but given how badly it breaks
> things to enable that optimization, I'm prepared to drop that (unless
> someone wants to help me debug weird byte-compiler crashes).

The issue is not "can you come up with an example where it matters".
If you start from such a premise, code optimization is simply impossible
because there's always some example you can come up with that you still
haven't compiled right and for which all the optimizations you've written
turn into pessimizations.

Optimizers have to be pragmatic and start with "which *existing* code
*needs* to be optimized".  Your original example is *existing*, but doesn't
*need* to be optimized since it's not executed repeatedly.
Your hypothetical pathological case may *need* to be optimized but as long
as it's not *existing*, it's irrelevant.


        Stefan

Re: byte-opt.el addition - optimize list of compile-time constants

[Zack Weinberg]

Stefan Monnier <monnier@iro.umontreal.ca> writes:

> Note that the expression
>
>      (list 1 2 (function (lambda () (with-current-buffer))))
>
> can be rejected by the compiler (not enough arguments to the
> with-current-buffer macro) whereas
>
>      '(1 2 (function (lambda () (with-current-buffer))))
>
> can't because it's just a quoted constant which just happens to look like
> invalid code.

I'd say that the compiler can and should reject your second example
precisely so that the equivalence of the two forms can be preserved.

Miles Bader <snogglethorpe@gmail.com> writes:
>> Also, in Common Lisp the situation is clearly that the compiler _is_
>> entitled to compile (function ...) wherever it finds it
>
> Can you provide a reference for this?  Given that it's quite
> dangerous, I'm skeptical of this claim.

I was going by CLTL/1, which says "The value of function is *always*
the functional interpretation of [its argument]" (emphasis mine).
That's a little ambiguous (although, as standardese goes, pretty damn
clear (my brain may have been warped by the C standard's heinous
ambiguities)).

The most recent edition of the ANSI Common Lisp spec that I can find
online
[http://www.lispworks.com/reference/HyperSpec/Front/Contents.htm] says
basically the same thing, but goes on to observe that function objects
may not appear in quoted literals which are to be processed by
compile-file.  I'm not really sure what the implications are.  See
<http://www.lispworks.com/reference/HyperSpec/Issues/iss082_w.htm>.

> Note that a possibly safer alternative would be to have the #'
> reader macro expand into something less ambiguous during compilation
> (e.g., a special non-interned symbol), which the byte-compiler could
> then safely interpret inside of constants.  This may cause grief for
> somebody that uses #' in a non-traditional way, and _expects_ to see
> (function (lambda ...)), but that may be an acceptable price.

I don't think this is any better than saying that function always
means function, even if not evalled.

zw

Re: byte-opt.el addition - optimize list of compile-time constants

[Miles Bader]

> > Note that a possibly safer alternative would be to have the #'
> > reader macro expand into something less ambiguous during compilation
> > (e.g., a special non-interned symbol), which the byte-compiler could
> > then safely interpret inside of constants.  This may cause grief for
> > somebody that uses #' in a non-traditional way, and _expects_ to see
> > (function (lambda ...)), but that may be an acceptable price.
> 
> I don't think this is any better than saying that function always
> means function, even if not evalled.

I think you're wrong.  Special reader macros like #' are a lot less
ambiguous than simple arrangements of ordinary atoms like `function'
and `lambda'.

-Miles

Re: byte-opt.el addition - optimize list of compile-time constants

[Zack Weinberg]

Miles Bader <snogglethorpe@gmail.com> writes:

>> > Note that a possibly safer alternative would be to have the #'
>> > reader macro expand into something less ambiguous during compilation
>> > (e.g., a special non-interned symbol), which the byte-compiler could
>> > then safely interpret inside of constants.  This may cause grief for
>> > somebody that uses #' in a non-traditional way, and _expects_ to see
>> > (function (lambda ...)), but that may be an acceptable price.
>> 
>> I don't think this is any better than saying that function always
>> means function, even if not evalled.
>
> I think you're wrong.  Special reader macros like #' are a lot less
> ambiguous than simple arrangements of ordinary atoms like `function'
> and `lambda'.

Of 462 occurences of the string '(function (lambda' in the Emacs
sources, only about ten are not functions.  The exceptions are all
function-constructing routines, and I only saw one of those that was
not a defmacro.

I conclude from this that the breakage involved in having the compiler
look inside quoted forms for (function (lambda ...)) constructs and
compile them would be very limited indeed, and could probably be
reduced to none by (a) not doing this inside a defmacro, and (b)
catching all compile errors and leaving the form alone.

Certainly the breakage here is far less than that involved in my
original proposal of optimizing (list) of constants!

zw

Re: byte-opt.el addition - optimize list of compile-time constants

[David Kastrup]

Stefan Monnier <monnier@iro.umontreal.ca> writes:

>> (disassemble 
>>   (lambda nil 
>>     `(:a 1 :b 2 
>>       :c ,#'(lambda nil (when (eq (following-char) ?\n) (forward-char 1))))))
> [...]
>> second place, byte-optimize-pure-func is called, but the optimization
>> fails because a (function ...) form appears inside the arguments to
>> list, which does not count as byte-compile-constp.  This is the other
>
> Hmm... we should probably update byte-compile-constp to accept
> (function ...) just like it accepts (quote ...).

IIRC, this difference was the whole point of (function ...) in the
first place: that function objects could get optimized on
byte-compilation for better speed.

-- 
David Kastrup, Kriemhildstr. 15, 44793 Bochum

Re: byte-opt.el addition - optimize list of compile-time constants

[David Kastrup]

Zack Weinberg <zack@codesourcery.com> writes:

> Miles Bader <snogglethorpe@gmail.com> writes:
>
>>> >> I thought the whole point of (function ...) was to assert that the
>>> >> lambda expression it contains *will* be used by execution.
>>> >
>>> > Yes, but that only applies if it occurs in an evaluable context.
>>> > Anyplace else, all bets are off.
>>> 
>>> That strikes me as just plain silly.  What's the point of a hint if it
>>> doesn't always mean what it means?
>>
>> If there's a random arbitrary list constant in some code, how on
>> earth is the compiler supposed to tell what the intended meaning of
>> sub-components of the list are?!?
>
> By reference to the language definition.  That's really what we're
> quibbling about here - I'm saying the language should be defined
> such that (function (lambda ...)) should indicate a function
> constant even if arbitrarily nested within a (quote ...) form,
> you're saying it shouldn't.

Of course it shouldn't.  The purpose of quote is not to execute.
`function', when _executed_, creates a quoted function object, just
like `quote', when _executed_, creates a quoted data object.

If you write '(woozle '(woozle)), the inner `quote' gets retained and
does nothing, like I would expect from an inner `function'.

> In evidence for my position I would like to point out that it is
> silly for '(1 2 3 #'(lambda ...) 4 5 6) to mean something different
> than (list 1 2 3 #'(lambda ...) 4 5 6),

Says who?

> and the byte compiler compiles the embedded lambda in the second
> case, so logically it ought to in the first case as well.
>
> Also, in Common Lisp the situation is clearly that the compiler _is_
> entitled to compile (function ...) wherever it finds it

This would surprise me.

bash-3.00$ gcl
GCL (GNU Common Lisp)  Version(2.5.0) Wed Oct  9 10:33:12 CEST 2002
Licensed under GNU Library General Public License
Contains Enhancements by W. Schelter

>(setq zap '(1 2 3 (function (lambda (x) x))))

(1 2 3 #'(LAMBDA (X) X))

>(setq zap (list 1 2 3 (function (lambda (x) x))))

(1 2 3 (LAMBDA-CLOSURE () () () (X) X))


-- 
David Kastrup, Kriemhildstr. 15, 44793 Bochum

Re: byte-opt.el addition - optimize list of compile-time constants

[David Kastrup]

Zack Weinberg <zack@codesourcery.com> writes:

> Stefan Monnier <monnier@iro.umontreal.ca> writes:
>
> Miles Bader <snogglethorpe@gmail.com> writes:
>>> Also, in Common Lisp the situation is clearly that the compiler _is_
>>> entitled to compile (function ...) wherever it finds it
>>
>> Can you provide a reference for this?  Given that it's quite
>> dangerous, I'm skeptical of this claim.
>
> I was going by CLTL/1, which says "The value of function is *always*
> the functional interpretation of [its argument]" (emphasis mine).

But inside of a quoted list, `function' does not get evaluated, so its
value does not come into play in the first place.

-- 
David Kastrup, Kriemhildstr. 15, 44793 Bochum

Re: byte-opt.el addition - optimize list of compile-time constants

[Andreas Schwab]

Paul Pogonyshev <pogonyshev@gmx.net> writes:

> Zack Weinberg wrote:
>> I seriously wonder how much would break if this optimization were
>> implemented for 'list'.  My suspicion is that people don't commonly
>> apply 'eq' to lists in the first place.
>
> You are very wrong here.  While it will hardly break sane code,
> `eq' is _very_ often applied to cons cells, e.g. lists.

Also 'list' is sometimes intentionally used to create a new cons that can
be changed by side effect.  If it were optimized to a constant the side
effect would now change a literal.

Andreas.

-- 
Andreas Schwab, SuSE Labs, schwab@suse.de
SuSE Linux Products GmbH, Maxfeldstraße 5, 90409 Nürnberg, Germany
Key fingerprint = 58CA 54C7 6D53 942B 1756  01D3 44D5 214B 8276 4ED5
"And now for something completely different."

Re: byte-opt.el addition - optimize list of compile-time constants

[Thien-Thi Nguyen]

   From: Zack Weinberg <zack@codesourcery.com>
   Date: Wed, 08 Dec 2004 22:49:13 -0800

   the breakage [...] would be very limited indeed

even limited breakage is unacceptable.  an optimizer operates under a
sort of hippocratic oath -- don't make things worse!

if i as a user wrote (quote ...), that means i intend ... to be my
domain of play, not that of the byte compiler/optimizer/whatever.

if i wanted to expose something in ... to be non-opaque i would use
quasiquote.

what you propose to do would result in me not trusting (quote ...).
that's not good for my relationship w/ elisp.

thi

Re: byte-opt.el addition - optimize list of compile-time constants

[Richard Stallman]

    even limited breakage is unacceptable.  an optimizer operates under a
    sort of hippocratic oath -- don't make things worse!

Exactly.

Zack, would you please drop this discussion?  It won't go anywhere,
and it is taking up the time of people whose help I need in making
Emacs ready for release.