inline function expansion

inline function expansion

[Lynn Winebarger]

Hi,

Is there a function that will let us see the result of inline function
expansion at the source level?   I see "byte-compile-preprocess" and
"byte-compile-inline-expand" as possibilities, but neither has a
docstring.

If I use define-inline, I would like to be able to verify that the
result is what I expect, or vice versa, that I understand what the
result will be well enough to have the correct expectation.

Thanks,
Lynn

Re: inline function expansion

[Basile Starynkevitch]

On 5/7/23 16:32, Lynn Winebarger wrote:
> Hi,
>
> Is there a function that will let us see the result of inline function
> expansion at the source level?   I see "byte-compile-preprocess" and
> "byte-compile-inline-expand" as possibilities, but neither has a
> docstring.
>
> If I use define-inline, I would like to be able to verify that the
> result is what I expect, or vice versa, that I understand what the
> result will be well enough to have the correct expectation.
>
> Thanks,
> Lynn



My understand of the current trunk, updated and compiled daily from git, 
on Linux x86-64/64 Debian or Linux Ubuntu 12.2.0)GNU Emacs 30.0.50
Development version d5ab8b6f2459 on master branch; build date 2023-05-07 
is that such a function cannot exist.


On recent GNU emacs, the internal fonctions are JIT compiled (using 
gcclibjit from GCC 13) by the gccasmjit library, and we get:

> rimski.x86_64 ~ 19:38 .0 % ldd /usr/local/bin/emacs-30.0.50-trunk
>     linux-vdso.so.1 (0x00007ffea99f2000)
>     libtiff.so.6 => /lib/x86_64-linux-gnu/libtiff.so.6 
> (0x00007f84ce7d6000)
>     libjpeg.so.8 => /lib/x86_64-linux-gnu/libjpeg.so.8 
> (0x00007f84ce753000)
>     libpng16.so.16 => /lib/x86_64-linux-gnu/libpng16.so.16 
> (0x00007f84ce71b000)
>     libgif.so.7 => /lib/x86_64-linux-gnu/libgif.so.7 (0x00007f84ce710000)
>     libwebpdemux.so.2 => /lib/x86_64-linux-gnu/libwebpdemux.so.2 
> (0x00007f84ce70a000)
>     libwebp.so.7 => /lib/x86_64-linux-gnu/libwebp.so.7 
> (0x00007f84cdd91000)
>     libgtk-3.so.0 => /lib/x86_64-linux-gnu/libgtk-3.so.0 
> (0x00007f84cd400000)
>     libgdk-3.so.0 => /lib/x86_64-linux-gnu/libgdk-3.so.0 
> (0x00007f84cdc95000)
>     libz.so.1 => /lib/x86_64-linux-gnu/libz.so.1 (0x00007f84ce6ea000)
>     libpango-1.0.so.0 => /lib/x86_64-linux-gnu/libpango-1.0.so.0 
> (0x00007f84cdc2b000)
>     libharfbuzz.so.0 => /lib/x86_64-linux-gnu/libharfbuzz.so.0 
> (0x00007f84cd318000)
>     libcairo.so.2 => /lib/x86_64-linux-gnu/libcairo.so.2 
> (0x00007f84cd1f1000)
>     libgdk_pixbuf-2.0.so.0 => 
> /lib/x86_64-linux-gnu/libgdk_pixbuf-2.0.so.0 (0x00007f84ce6b9000)
>     libgio-2.0.so.0 => /lib/x86_64-linux-gnu/libgio-2.0.so.0 
> (0x00007f84cd01f000)
>     libgobject-2.0.so.0 => /lib/x86_64-linux-gnu/libgobject-2.0.so.0 
> (0x00007f84ccfbe000)
>     libglib-2.0.so.0 => /lib/x86_64-linux-gnu/libglib-2.0.so.0 
> (0x00007f84cce77000)
>     libSM.so.6 => /lib/x86_64-linux-gnu/libSM.so.6 (0x00007f84ce6ae000)
>     libICE.so.6 => /lib/x86_64-linux-gnu/libICE.so.6 (0x00007f84cdc0c000)
>     libX11.so.6 => /lib/x86_64-linux-gnu/libX11.so.6 (0x00007f84ccd39000)
>     libdbus-1.so.3 => /lib/x86_64-linux-gnu/libdbus-1.so.3 
> (0x00007f84ccceb000)
>     libXrandr.so.2 => /lib/x86_64-linux-gnu/libXrandr.so.2 
> (0x00007f84cdbff000)
>     libXinerama.so.1 => /lib/x86_64-linux-gnu/libXinerama.so.1 
> (0x00007f84cdbfa000)
>     libXfixes.so.3 => /lib/x86_64-linux-gnu/libXfixes.so.3 
> (0x00007f84cdbf2000)
>     libXext.so.6 => /lib/x86_64-linux-gnu/libXext.so.6 
> (0x00007f84cdbdb000)
>     libxml2.so.2 => /lib/x86_64-linux-gnu/libxml2.so.2 
> (0x00007f84ccb01000)
>     libtinfo.so.6 => /lib/x86_64-linux-gnu/libtinfo.so.6 
> (0x00007f84ccacf000)
>     libselinux.so.1 => /lib/x86_64-linux-gnu/libselinux.so.1 
> (0x00007f84ccaa2000)
>     libfreetype.so.6 => /lib/x86_64-linux-gnu/libfreetype.so.6 
> (0x00007f84cc9d8000)
>     libfontconfig.so.1 => /lib/x86_64-linux-gnu/libfontconfig.so.1 
> (0x00007f84cc98a000)
>     libgnutls.so.30 => /lib/x86_64-linux-gnu/libgnutls.so.30 
> (0x00007f84cc78f000)
>     libm.so.6 => /lib/x86_64-linux-gnu/libm.so.6 (0x00007f84cc6a6000)
>     libjansson.so.4 => /lib/x86_64-linux-gnu/libjansson.so.4 
> (0x00007f84cc696000)
>     libgmp.so.10 => /lib/x86_64-linux-gnu/libgmp.so.10 
> (0x00007f84cc613000)
>     libgccjit.so.0 => /lib/x86_64-linux-gnu/libgccjit.so.0 
> (0x00007f84ca400000)
>     libXi.so.6 => /lib/x86_64-linux-gnu/libXi.so.6 (0x00007f84cc5ff000)
>     libXcomposite.so.1 => /lib/x86_64-linux-gnu/libXcomposite.so.1 
> (0x00007f84cdbd2000)
>     libc.so.6 => /lib/x86_64-linux-gnu/libc.so.6 (0x00007f84ca000000)
>     libzstd.so.1 => /lib/x86_64-linux-gnu/libzstd.so.1 
> (0x00007f84ca34c000)
>     liblzma.so.5 => /lib/x86_64-linux-gnu/liblzma.so.5 
> (0x00007f84ca31a000)
>     libLerc.so.4 => /lib/x86_64-linux-gnu/libLerc.so.4 
> (0x00007f84ca295000)
>     libjbig.so.0 => /lib/x86_64-linux-gnu/libjbig.so.0 
> (0x00007f84ca284000)
>     libdeflate.so.0 => /lib/x86_64-linux-gnu/libdeflate.so.0 
> (0x00007f84ca271000)
>     /lib64/ld-linux-x86-64.so.2 (0x00007f84ce87c000)
>     libgmodule-2.0.so.0 => /lib/x86_64-linux-gnu/libgmodule-2.0.so.0 
> (0x00007f84ca26a000)
>     libpangocairo-1.0.so.0 => 
> /lib/x86_64-linux-gnu/libpangocairo-1.0.so.0 (0x00007f84ca259000)
>     libpangoft2-1.0.so.0 => /lib/x86_64-linux-gnu/libpangoft2-1.0.so.0 
> (0x00007f84ca23f000)
>     libfribidi.so.0 => /lib/x86_64-linux-gnu/libfribidi.so.0 
> (0x00007f84ca222000)
>     libcairo-gobject.so.2 => 
> /lib/x86_64-linux-gnu/libcairo-gobject.so.2 (0x00007f84ca217000)
>     libatk-1.0.so.0 => /lib/x86_64-linux-gnu/libatk-1.0.so.0 
> (0x00007f84c9fd8000)
>     libepoxy.so.0 => /lib/x86_64-linux-gnu/libepoxy.so.0 
> (0x00007f84c9ea3000)
>     libatk-bridge-2.0.so.0 => 
> /lib/x86_64-linux-gnu/libatk-bridge-2.0.so.0 (0x00007f84c9e67000)
>     libxkbcommon.so.0 => /lib/x86_64-linux-gnu/libxkbcommon.so.0 
> (0x00007f84c9e21000)
>     libwayland-client.so.0 => 
> /lib/x86_64-linux-gnu/libwayland-client.so.0 (0x00007f84c9e10000)
>     libwayland-cursor.so.0 => 
> /lib/x86_64-linux-gnu/libwayland-cursor.so.0 (0x00007f84ca20b000)
>     libwayland-egl.so.1 => /lib/x86_64-linux-gnu/libwayland-egl.so.1 
> (0x00007f84ca206000)
>     libXcursor.so.1 => /lib/x86_64-linux-gnu/libXcursor.so.1 
> (0x00007f84c9e04000)
>     libXdamage.so.1 => /lib/x86_64-linux-gnu/libXdamage.so.1 
> (0x00007f84c9dff000)
>     libthai.so.0 => /lib/x86_64-linux-gnu/libthai.so.0 
> (0x00007f84c9df2000)
>     libgraphite2.so.3 => /lib/x86_64-linux-gnu/libgraphite2.so.3 
> (0x00007f84c9dcb000)
>     libpixman-1.so.0 => /lib/x86_64-linux-gnu/libpixman-1.so.0 
> (0x00007f84c9d1f000)
>     libxcb-shm.so.0 => /lib/x86_64-linux-gnu/libxcb-shm.so.0 
> (0x00007f84c9d1a000)
>     libxcb.so.1 => /lib/x86_64-linux-gnu/libxcb.so.1 (0x00007f84c9cf0000)
>     libxcb-render.so.0 => /lib/x86_64-linux-gnu/libxcb-render.so.0 
> (0x00007f84c9ce0000)
>     libXrender.so.1 => /lib/x86_64-linux-gnu/libXrender.so.1 
> (0x00007f84c9cd3000)
>     libmount.so.1 => /lib/x86_64-linux-gnu/libmount.so.1 
> (0x00007f84c9c8f000)
>     libffi.so.8 => /lib/x86_64-linux-gnu/libffi.so.8 (0x00007f84c9c84000)
>     libpcre2-8.so.0 => /lib/x86_64-linux-gnu/libpcre2-8.so.0 
> (0x00007f84c9bea000)
>     libuuid.so.1 => /lib/x86_64-linux-gnu/libuuid.so.1 
> (0x00007f84c9be1000)
>     libbsd.so.0 => /lib/x86_64-linux-gnu/libbsd.so.0 (0x00007f84c9bca000)
>     libsystemd.so.0 => /lib/x86_64-linux-gnu/libsystemd.so.0 
> (0x00007f84c9afa000)
>     libicuuc.so.72 => /lib/x86_64-linux-gnu/libicuuc.so.72 
> (0x00007f84c98fb000)
>     libbrotlidec.so.1 => /lib/x86_64-linux-gnu/libbrotlidec.so.1 
> (0x00007f84c98ee000)
>     libexpat.so.1 => /lib/x86_64-linux-gnu/libexpat.so.1 
> (0x00007f84c98c3000)
>     libp11-kit.so.0 => /lib/x86_64-linux-gnu/libp11-kit.so.0 
> (0x00007f84c9784000)
>     libidn2.so.0 => /lib/x86_64-linux-gnu/libidn2.so.0 
> (0x00007f84c9763000)
>     libunistring.so.2 => /lib/x86_64-linux-gnu/libunistring.so.2 
> (0x00007f84c95af000)
>     libtasn1.so.6 => /lib/x86_64-linux-gnu/libtasn1.so.6 
> (0x00007f84c9598000)
>     libnettle.so.8 => /lib/x86_64-linux-gnu/libnettle.so.8 
> (0x00007f84c9548000)
>     libhogweed.so.6 => /lib/x86_64-linux-gnu/libhogweed.so.6 
> (0x00007f84c9500000)
>     libisl.so.23 => /lib/x86_64-linux-gnu/libisl.so.23 
> (0x00007f84c9200000)
>     libmpc.so.3 => /lib/x86_64-linux-gnu/libmpc.so.3 (0x00007f84c94dc000)
>     libmpfr.so.6 => /lib/x86_64-linux-gnu/libmpfr.so.6 
> (0x00007f84c9423000)
>     libstdc++.so.6 => /lib/x86_64-linux-gnu/libstdc++.so.6 
> (0x00007f84c8e00000)
>     libgcc_s.so.1 => /lib/x86_64-linux-gnu/libgcc_s.so.1 
> (0x00007f84c91dc000)
>     libatspi.so.0 => /lib/x86_64-linux-gnu/libatspi.so.0 
> (0x00007f84c91a3000)
>     libdatrie.so.1 => /lib/x86_64-linux-gnu/libdatrie.so.1 
> (0x00007f84c9418000)
>     libXau.so.6 => /lib/x86_64-linux-gnu/libXau.so.6 (0x00007f84c9412000)
>     libXdmcp.so.6 => /lib/x86_64-linux-gnu/libXdmcp.so.6 
> (0x00007f84c940a000)
>     libblkid.so.1 => /lib/x86_64-linux-gnu/libblkid.so.1 
> (0x00007f84c916c000)
>     libmd.so.0 => /lib/x86_64-linux-gnu/libmd.so.0 (0x00007f84c915f000)
>     libcap.so.2 => /lib/x86_64-linux-gnu/libcap.so.2 (0x00007f84c9153000)
>     libgcrypt.so.20 => /lib/x86_64-linux-gnu/libgcrypt.so.20 
> (0x00007f84c8cb8000)
>     liblz4.so.1 => /lib/x86_64-linux-gnu/liblz4.so.1 (0x00007f84c9130000)
>     libicudata.so.72 => /lib/x86_64-linux-gnu/libicudata.so.72 
> (0x00007f84c6e00000)
>     libbrotlicommon.so.1 => /lib/x86_64-linux-gnu/libbrotlicommon.so.1 
> (0x00007f84c910d000)
>     libgpg-error.so.0 => /lib/x86_64-linux-gnu/libgpg-error.so.0 
> (0x00007f84c90e7000)


Notice the dependency on libgccjit.so.0, which is provided by GCC 12 or 
GCC 13 suitably configured


That thing is used in GNU emacs source code. Look into its ffile 
emacs/src/comp.c (line 553, etc... 4689)


On the same system the Ubuntu emacs don't use libgccjit.

But perhaps I misunderstood your question?


Regards.


NB. My pet open source project is http://refpersys.org/ (an inference 
engine project, GPLv3+) and source code on 
https://github.com/RefPerSys/RefPerSys .... feel free to contact me 
(Basile Starynkevitch) by email to basile@starynkevitch.net or 
basile.starynkevitch@cea.fr (both near Paris in France)  about it.

-- 
Basile Starynkevitch                  <basile@starynkevitch.net>
(only mine opinions / les opinions sont miennes uniquement)
92340 Bourg-la-Reine, France
web page: starynkevitch.net/Basile/

Re: inline function expansion

[Philip Kaludercic]

Lynn Winebarger <owinebar@gmail.com> writes:

> Hi,
>
> Is there a function that will let us see the result of inline function
> expansion at the source level?   I see "byte-compile-preprocess" and
> "byte-compile-inline-expand" as possibilities, but neither has a
> docstring.

What I usually do is just to invoke M-x disassemble, but you won't be
viewing the code transformation on source-level.  I am not sure if
inlineing happens on a s-expression level like with macros, or if the
byte-code optimiser just inlines the definition instead of generating
code funcall.

> If I use define-inline, I would like to be able to verify that the
> result is what I expect, or vice versa, that I understand what the
> result will be well enough to have the correct expectation.

Isn't the idea of inlining that the behaviour/effect of invoking a
function shouldn't change, just that the resulting code might be more
efficient?

> Thanks,
> Lynn

Re: inline function expansion

[Lynn Winebarger]

On Sun, May 7, 2023 at 3:48 PM Philip Kaludercic <philipk@posteo.net> wrote:
> Lynn Winebarger <owinebar@gmail.com> writes:
>
> > Hi,
> >
> > Is there a function that will let us see the result of inline function
> > expansion at the source level?   I see "byte-compile-preprocess" and
> > "byte-compile-inline-expand" as possibilities, but neither has a
> > docstring.
>
> What I usually do is just to invoke M-x disassemble, but you won't be
> viewing the code transformation on source-level.  I am not sure if
> inlineing happens on a s-expression level like with macros, or if the
> byte-code optimiser just inlines the definition instead of generating
> code funcall.

I know that define-inline uses compiler macros so that the function
symbol is bound to an ordinary function while the compiler interprets
the symbol as a macro.

So, what I'd like is something like compiler-macroexpand-all.

>
> > If I use define-inline, I would like to be able to verify that the
> > result is what I expect, or vice versa, that I understand what the
> > result will be well enough to have the correct expectation.
>
> Isn't the idea of inlining that the behaviour/effect of invoking a
> function shouldn't change, just that the resulting code might be more
> efficient?

The main thing I am interested in is the ability to do compile-time
evaluation on constant expressions.  I'm trying to design/implement a
way of defining generic methods so that the specialization may be
determined (or explicitly constructed) at compile time and compiled to
a non-generic function call, and left to dynamic dispatch otherwise.
I think inline functions, or at least the technique used in
implementing them, will have to be a component in that.  I really need
to be able to see the expanded code to know if I'm using it correctly,
though.   It's something along the lines of the interface-based
generics found in C#, so you can write generic code based on a set of
defined interfaces, and ways to implement those interfaces, then
instantiate those generic methods with particular realizations of the
interfaces.  Then those instantiations would be simple function calls.
On the other hand, the generic function could be called at run time
with objects that are wrapped by a realization of the interface.  They
should both give the same semantics (unless late-binding would cause
different dispatching), but in the former case the composition of the
functions implementing the interfaces would happen by inlining and not
require intermediate allocation of wrapper objects....

Lynn

Lynn

Re: inline function expansion

[Emanuel Berg]

Lynn Winebarger wrote:

>> Isn't the idea of inlining that the behaviour/effect of
>> invoking a function shouldn't change, just that the
>> resulting code might be more efficient?
>
> The main thing I am interested in is the ability to do
> compile-time evaluation on constant expressions.

What exactly are "constant expressions" in the context of
this discussion?

The same as this?

  https://www.stroustrup.com/sac10-constexpr.pdf

> I'm trying to design/implement a way of defining generic
> methods so that the specialization may be determined (or
> explicitly constructed) at compile time and compiled to
> a non-generic function call, and left to dynamic
> dispatch otherwise.

Okay, so what would be the gain(s) of having such
a capability?

-- 
underground experts united
https://dataswamp.org/~incal

Re: inline function expansion

[Lynn Winebarger]

On Mon, May 8, 2023 at 12:15 AM Emanuel Berg <incal@dataswamp.org> wrote:
> >> Isn't the idea of inlining that the behaviour/effect of
> >> invoking a function shouldn't change, just that the
> >> resulting code might be more efficient?
> >
> > The main thing I am interested in is the ability to do
> > compile-time evaluation on constant expressions.
>
> What exactly are "constant expressions" in the context of
> this discussion?
>
> The same as this?
>
>   https://www.stroustrup.com/sac10-constexpr.pdf
>
See https://www.gnu.org/software/emacs/manual/html_node/elisp/Inline-Functions.html#index-inline_002dconst_002dp

> > I'm trying to design/implement a way of defining generic
> > methods so that the specialization may be determined (or
> > explicitly constructed) at compile time and compiled to
> > a non-generic function call, and left to dynamic
> > dispatch otherwise.
>
> Okay, so what would be the gain(s) of having such
> a capability?

A structured way to write generic code without paying a substantial
run-time cost.  Pretty much the same case as for define-inline, except
applied to generic methods.

Lynn

Re: inline function expansion

[Lynn Winebarger]

On Sun, May 7, 2023 at 3:48 PM Philip Kaludercic <philipk@posteo.net> wrote:
> What I usually do is just to invoke M-x disassemble, but you won't be
> viewing the code transformation on source-level.  I am not sure if
> inlineing happens on a s-expression level like with macros, or if the
> byte-code optimiser just inlines the definition instead of generating
> code funcall.
>
So, https://debbugs.gnu.org/cgi/bugreport.cgi?bug=60450 says
macroexpand-all does in fact expand compiler macros, although
macroexpand does not.  If that's the intended behavior then I can just
use that function.   It may still be a bug, though.

Lynn

Re: inline function expansion

[Lynn Winebarger]

On Sun, May 7, 2023 at 3:48 PM Philip Kaludercic <philipk@posteo.net> wrote:
> Lynn Winebarger <owinebar@gmail.com> writes:
> > If I use define-inline, I would like to be able to verify that the
> > result is what I expect, or vice versa, that I understand what the
> > result will be well enough to have the correct expectation.
>
> Isn't the idea of inlining that the behaviour/effect of invoking a
> function shouldn't change, just that the resulting code might be more
> efficient?

I was working off of the description in "Evolution of Emacs Lisp",
page 45, which gives the example of cl-type-p for evaluation of
constant expressions at compile-time via inline functions (figure 2):
(define-inline cl-typep (val type)
  (inline-letevals (val)
    (pcase (inline-const-val type)
      (`(not ,ty)
       (inline-quote (not (cl-typep ,val ',ty))))
      (`(eql ,v)
       (inline-quote (eql ,val ',v)))
      (`(satisfies ,pred) (inline-quote (funcall #',pred ,val)))
      ((and (pred symbolp) ty (guard (get ty 'cl-deftype-satisfies)))
       (inline-quote (funcall #',(get ty 'cl-deftype-satisfies) ,val)))
      ...
     (ty (error "Bad type spec: %s" ty)))))

The info documentation does not include any examples involving
inline-const-p, and in fact, I cannot find any code in the emacs lisp
directory, or in the source of a couple of thousand packages, that
makes use of inline-const-p or inline-const-val *other* than this
exact function.

I'd like to define inline- variants of pure subrs, e.g. arithmetic
operators, type-predicates, that evaluate during macroexpansion rather
than involving the compiler's optimization phase.  I think it will be
easier to ensure compile-time generic methods (e.g. a macro that
simply calls a generic method) will (or at least can) dispatch during
macro-expansion, without involving the byte-compiler's optimization
phase.  Unfortunately, I don't see how I can write something like
(define-inline inline-+ (&rest args)
   (if (seq-every-p #'inline-const-p args)
       (apply (eval-when-compile (symbol-function '+)) args)
    (inline-quote (,(eval-when-compile (symbol-function '+)) . ,args))))

Admittedly, I haven't actually tried the code above, but if I
understand the define-inline macro, the defun would include the "if"
statement, and that is not the intension.

I can still define the kind of inlined primitives described above
using a macro based on define-inline's approach of defining a compiler
macro and a defun, but I'm not seeing how to use the existing inline-*
machinery to do it.  Am I missing something?

Lynn

Re: inline function expansion

[Emanuel Berg]

Lynn Winebarger wrote:

> I was working off of the description in "Evolution of Emacs
> Lisp", page 45, which gives the example of cl-type-p for
> evaluation of constant expressions at compile-time via
> inline functions (figure 2)

I still don't know what constant expressions are, is it Elisp
pieces of source that all evaluate to something based only on
entities that themselves don't change, so the whole thing can
be optimized, i.e. replaced by this value so computation won't
be done over and over?

How do you check is something is a constant expression or not?

> The info documentation does not include any examples
> involving inline-const-p, and in fact, I cannot find any
> code in the emacs lisp directory, or in the source of
> a couple of thousand packages, that makes use of
> inline-const-p or inline-const-val *other* than this
> exact function.

Sounds like you found something interesting ...

> I'd like to define inline- variants of pure subrs, e.g.
> arithmetic operators, type-predicates, that evaluate during
> macroexpansion rather than involving the compiler's
> optimization phase.

But what does it matter when it happens, as long as it is done
when it is supposed to be used?

Compiling is a modular process with different stages. (It
would be interesting BTW to see a list of these stages, along
with the technical terms what is happening at each stage.
For example, you have used the word "dispatch" several times,
which I also haven't come across in the Elisp world
until now.)

> I think it will be easier to ensure compile-time generic
> methods (e.g. a macro that simply calls a generic method)
> will (or at least can) dispatch during macro-expansion,
> without involving the byte-compiler's optimization phase.

Okay now I see, you want to switch order, or duplicate the
optimization so it happens before as well, in your case so you
can have inline functions even at macro-expansion time?

But what will be the advantage of that compared to doing
it after? Unless you want to optimize and inline the
macro-expansion process as well ...

-- 
underground experts united
https://dataswamp.org/~incal

Re: inline function expansion

[Lynn Winebarger]

On Thu, May 11, 2023 at 3:11 AM Lynn Winebarger <owinebar@gmail.com> wrote:
> On Sun, May 7, 2023 at 3:48 PM Philip Kaludercic <philipk@posteo.net> wrote:
> > Lynn Winebarger <owinebar@gmail.com> writes:
> > > If I use define-inline, I would like to be able to verify that the
> > > result is what I expect, or vice versa, that I understand what the
> > > result will be well enough to have the correct expectation.
> >
> > Isn't the idea of inlining that the behaviour/effect of invoking a
> > function shouldn't change, just that the resulting code might be more
> > efficient?

In some languages, that is the definition.  But it can also be
interleaved with compile-time evaluation of constant-expressions to
provide a more structured alternative to defmacro.  At least, that's
how I read the motivation for define-inline versus defsubst.

The current implementation appears to be difficult to use in a
meaningful way - as per the below, I've only identified two cases that
make actual use of the facilities provided by define-inline beyond
those afforded by defsubst, and defsubst is much easier to use.  I've
been trying to work out how to provide the functionality define-inline
seeks to provide in a more convenient form without writing a
full-blown partial-evaluator.

> I was working off of the description in "Evolution of Emacs Lisp",
> page 45, which gives the example of cl-type-p for evaluation of
> constant expressions at compile-time via inline functions (figure 2):
> (define-inline cl-typep (val type)
>   (inline-letevals (val)
>     (pcase (inline-const-val type)
>       (`(not ,ty)
>        (inline-quote (not (cl-typep ,val ',ty))))
>       (`(eql ,v)
>        (inline-quote (eql ,val ',v)))
>       (`(satisfies ,pred) (inline-quote (funcall #',pred ,val)))
>       ((and (pred symbolp) ty (guard (get ty 'cl-deftype-satisfies)))
>        (inline-quote (funcall #',(get ty 'cl-deftype-satisfies) ,val)))
>       ...
>      (ty (error "Bad type spec: %s" ty)))))
>
> The info documentation does not include any examples involving
> inline-const-p, and in fact, I cannot find any code in the emacs lisp
> directory, or in the source of a couple of thousand packages, that
> makes use of inline-const-p or inline-const-val *other* than this
> exact function.

After some more investigation, the only other code I've seen that uses
define-inline to do more than defsubst would (as I understand it) is
in gnus-sum.el:
(define-inline gnus-summary-article-header (&optional number)
  "Return the header of article NUMBER."
  (inline-quote
   (gnus-data-header (gnus-data-find
      ,(or number
                           (inline-quote (gnus-summary-article-number)))))))
And I believe that occurence of "number" should be
"(inline-constant-val number)".
One example where there could be a use of define-inline's additional
functionality is in:
(define-inline cconv--var-classification (binder form)
  (inline-quote
   (cdr (assoc (cons ,binder ,form) cconv-var-classification))))

That could be changed to
(define-inline cconv--var-classification (binder form)
  (inline-quote
   (cdr (assoc ,(inline-quote ,(cons (inline-const-val binder)
(inline-const-val form))_ cconv-var-classification))))

It's a slight difference, but it is an example where computation could
be moved to compile-time.

From these example, it seems there are three capabilities afforded by
the underlying implementation technique of define-inline:

1) Computing subexpressions that are compile-time constants (that's
the cconv example)
2) Eliminating one or more parameters known at compile-time (that's
what cl-typep does)
3) A "constexpr" (in C++ parlance) constructor, "inline-quote"

Automating the first one involves identifying the maximal constant
expression containing each potentially constant parameter, which is
hard in general.  But if we restrict the language handled by the
inliner, it might be doable.  For example, if we could assume no
macros implicitly bind any identifiers already in use, and parameters
marked with &const as a guarantee  that the result of the function
does not vary based on state associated with them, maybe that would be
enough to determine non-trivial subexpressions pure subexpressions
above rather than forcing the user to identify them explicitly by
unquoting.  There's also a need to identify variables that may be
side-effected but which do not escape the inlined context, so the
inlined function is "const" with respect to them.  For example, in
(lambda (n) (let ((acc 1)) (while (> n 0) (setq acc (* n acc) n (1-
n))) acc)), the "while" form is "pure" because the value of the
function is constant with respect to it.  Alternatively, the while
form could be written in CPS style that eliminates the side-effects,
but the point of the restrictions is to avoid actually performing that
analysis.

For the second,  I'm thinking that what the programmer wants to
express is that if the "type" parameter is constant, then reducing all
forms with pure operators with respect to type is a "pure" macro in
the sense that it will always produce the same expression, and that
expression has no occurrences of "type".  For example,  (cl-typep x
'integer) => (integerp x).   ,This is "pure" as a function
transforming source code forms.  I'm thinking the user could mark the
"val" parameter with "&opaque" to indicate that the cl-typep inliner
should curry cl-typep to evaluate type at compile-type (when constant)
and produce an expression that has no references to "type" and does
not reference "val" while computing it.

The third item is interesting in the case of the cconv example, where
"cons" can be called at compile time if it occurs in a pure expression
that is evaluated at compile time, but otherwise should be deferred to
run-time, whether the arguments are constant or not.  This is possible
because most values in lisp can be stored in source expressions -
C++'s constexpr constructors explicitly require a return value of a
literal type.

Just for the terms of the debate, I think the exclusion of "assoc"
from being a "pure" function is incorrect, *if* we extend the notion
of constants to include pure functions (or restrict the notion of
constants to exclude non-pure functions).  Then assoc is pure because
when all three arguments are constant (i.e. the test function is
pure), then the value is constant.

Lynn

Re: inline function expansion

[Stefan Monnier]

> After some more investigation, the only other code I've seen that uses
> define-inline to do more than defsubst would (as I understand it) is
> in gnus-sum.el:
> (define-inline gnus-summary-article-header (&optional number)
>   "Return the header of article NUMBER."
>   (inline-quote
>    (gnus-data-header (gnus-data-find
>       ,(or number
>                            (inline-quote (gnus-summary-article-number)))))))
> And I believe that occurence of "number" should be
> "(inline-constant-val number)".

You're right, tho in practice number is either nil or non-constant, so
it doesn't make much difference.

> One example where there could be a use of define-inline's additional
> functionality is in:
> (define-inline cconv--var-classification (binder form)
>   (inline-quote
>    (cdr (assoc (cons ,binder ,form) cconv-var-classification))))
>
> That could be changed to
> (define-inline cconv--var-classification (binder form)
>   (inline-quote
>    (cdr (assoc ,(inline-quote ,(cons (inline-const-val binder)
> (inline-const-val form))_ cconv-var-classification))))

I think you can simplify that to:

    (define-inline cconv--var-classification (binder form)
      (inline-quote
       (cdr (assoc ,(cons (inline-const-val binder)
                          (inline-const-val form))
                   cconv-var-classification))))

but here as well, this optimization would never apply because those args
are never literal constants.  Worse: the failure of `inline-const-val`
would cause the whole inlining to fail :-(

To support this kind of optimization we'd need to add specific support
for it to `define-inline`.

> Automating the first one involves identifying the maximal constant
> expression containing each potentially constant parameter, which is
> hard in general.  But if we restrict the language handled by the
> inliner, it might be doable.  For example, if we could assume no
> macros implicitly bind any identifiers already in use, and parameters
> marked with &const as a guarantee  that the result of the function
> does not vary based on state associated with them, maybe that would be
> enough to determine non-trivial subexpressions pure subexpressions
> above rather than forcing the user to identify them explicitly by
> unquoting.

The driving principle behind `define-inline` is to not do any analysis
and leave that responsability in the hands of the users of
`define-inline` :-)

So we could/should add some special annotation like (inline-precompute
<FOO>) which treats <FOO> as an expression that builds a value and
precomputes it if all the `,<EXP>` that appear in it are
`inline-const-p`.

> For the second,  I'm thinking that what the programmer wants to
> express is that if the "type" parameter is constant, then reducing all
> forms with pure operators with respect to type is a "pure" macro in
> the sense that it will always produce the same expression, and that
> expression has no occurrences of "type".

Note that in the case of `cl-typep` the expansion may fail to fully
eliminate the "type" parameter, IIRC (i.e. it manages to inline/unroll
part of the recursion but not all of it because some part of the type is
not statically known or too complex).

> Then assoc is pure because when all three arguments are constant
> (i.e. the test function is pure), then the value is constant.

IIRC the reason it's not "pure" (for some definition of "pure") is
because it can signal an error.


        Stefan

Re: inline function expansion

[Lynn Winebarger]

On Fri, May 19, 2023 at 9:31 AM Stefan Monnier <monnier@iro.umontreal.ca> wrote:
> > After some more investigation, the only other code I've seen that uses
> > define-inline to do more than defsubst would (as I understand it) is
> > in gnus-sum.el:
> > (define-inline gnus-summary-article-header (&optional number)
> >   "Return the header of article NUMBER."
> >   (inline-quote
> >    (gnus-data-header (gnus-data-find
> >       ,(or number
> >                            (inline-quote (gnus-summary-article-number)))))))
> > And I believe that occurence of "number" should be
> > "(inline-constant-val number)".
>
> You're right, tho in practice number is either nil or non-constant, so
> it doesn't make much difference.

I'm just pointing out it is difficult to tell how to use the
facilities for compile-time evaluation provided by define-inline.
>
> > One example where there could be a use of define-inline's additional
> > functionality is in:
> > (define-inline cconv--var-classification (binder form)
> >   (inline-quote
> >    (cdr (assoc (cons ,binder ,form) cconv-var-classification))))
> >
> > That could be changed to
> > (define-inline cconv--var-classification (binder form)
> >   (inline-quote
> >    (cdr (assoc ,(inline-quote ,(cons (inline-const-val binder)
> > (inline-const-val form))_ cconv-var-classification))))
>
> I think you can simplify that to:
>
>     (define-inline cconv--var-classification (binder form)
>       (inline-quote
>        (cdr (assoc ,(cons (inline-const-val binder)
>                           (inline-const-val form))
>                    cconv-var-classification))))

Don't you need something to add a quote to the cons cell when "binder"
or "form" are not constant?
>
> but here as well, this optimization would never apply because those args
> are never literal constants.  Worse: the failure of `inline-const-val`
> would cause the whole inlining to fail :-(
Could inline--do-quote catch the throw?

> To support this kind of optimization we'd need to add specific support
> for it to `define-inline`.
>
> > Automating the first one involves identifying the maximal constant
> > expression containing each potentially constant parameter, which is
> > hard in general.  But if we restrict the language handled by the
> > inliner, it might be doable.  For example, if we could assume no
> > macros implicitly bind any identifiers already in use, and parameters
> > marked with &const as a guarantee  that the result of the function
> > does not vary based on state associated with them, maybe that would be
> > enough to determine non-trivial subexpressions pure subexpressions
> > above rather than forcing the user to identify them explicitly by
> > unquoting.
>
> The driving principle behind `define-inline` is to not do any analysis
> and leave that responsability in the hands of the users of
> `define-inline` :-)
>
> So we could/should add some special annotation like (inline-precompute
> <FOO>) which treats <FOO> as an expression that builds a value and
> precomputes it if all the `,<EXP>` that appear in it are
> `inline-const-p`.
>
> > For the second,  I'm thinking that what the programmer wants to
> > express is that if the "type" parameter is constant, then reducing all
> > forms with pure operators with respect to type is a "pure" macro in
> > the sense that it will always produce the same expression, and that
> > expression has no occurrences of "type".
>
> Note that in the case of `cl-typep` the expansion may fail to fully
> eliminate the "type" parameter, IIRC (i.e. it manages to inline/unroll
> part of the recursion but not all of it because some part of the type is
> not statically known or too complex).

I don't know what "too complex" would entail, but if it's not
statically known then the type arg isn't really a constant so it's not
really a failure.

>
> > Then assoc is pure because when all three arguments are constant
> > (i.e. the test function is pure), then the value is constant.
>
> IIRC the reason it's not "pure" (for some definition of "pure") is
> because it can signal an error.

The byte-opt.el code from v28.2.50 says it's because the third
argument may be an impure function:
         ;; `assoc' and `assoc-default' are excluded since they are
         ;; impure if the test function is (consider `string-match').
I'm not sure why the possibility of signaling an error alone would be
disqualifying.  For example, (+ 5 's) signals an error.

Also, I don't get why logand isn't considered a pure function - how
important is it to be able to run byte-code generated by a 32-bit
emacs in a 64-bit emacs (or vice-versa)?  I could see it making sense
historically, but is it still a useful property of byte-code?

Re: inline function expansion

[Stefan Monnier]

>> You're right, tho in practice number is either nil or non-constant, so
>> it doesn't make much difference.
> I'm just pointing out it is difficult to tell how to use the
> facilities for compile-time evaluation provided by define-inline.

Oh, that, yes the `define-inline` facility is hard to use, no doubt.
I'm not happy with it.  This is also reflected in the lack of doc
because it's difficult to document it much better than "look at the
code, try it out, and fiddle until it works" :-(

>>     (define-inline cconv--var-classification (binder form)
>>       (inline-quote
>>        (cdr (assoc ,(cons (inline-const-val binder)
>>                           (inline-const-val form))
>>                    cconv-var-classification))))
>
> Don't you need something to add a quote to the cons cell when "binder"
> or "form" are not constant?

Oh, you're right.

>> but here as well, this optimization would never apply because those args
>> are never literal constants.  Worse: the failure of `inline-const-val`
>> would cause the whole inlining to fail :-(
> Could inline--do-quote catch the throw?

It could, but it doesn't (and it would be an incompatible change).

>> IIRC the reason it's not "pure" (for some definition of "pure") is
>> because it can signal an error.
>
> The byte-opt.el code from v28.2.50 says it's because the third
> argument may be an impure function:
>          ;; `assoc' and `assoc-default' are excluded since they are
>          ;; impure if the test function is (consider `string-match').
> I'm not sure why the possibility of signaling an error alone would be
> disqualifying.  For example, (+ 5 's) signals an error.

Oh, you're right, sorry.  So the problem is if the test function is
constant but not pure.

> Also, I don't get why logand isn't considered a pure function

What makes you think it's not?

    ELISP> (symbol-plist 'logand)
    (gv-expander #f(compiled-function
    		(do place &rest masks)
    		#<bytecode -0xc7679d4528b2a2a>)
    	      side-effect-free t pure t)
    
    ELISP>

> How important is it to be able to run byte-code generated by
> a 32-bit emacs in a 64-bit emacs (or vice-versa)?

The Emacs tarball comes with all the `.elc` files, so it's important
that `.elc` files be portable across architectures.


        Stefan

Re: inline function expansion

[Lynn Winebarger]

On Sat, May 20, 2023 at 11:32 AM Stefan Monnier
<monnier@iro.umontreal.ca> wrote:
> >> You're right, tho in practice number is either nil or non-constant, so
> >> it doesn't make much difference.
> > I'm just pointing out it is difficult to tell how to use the
> > facilities for compile-time evaluation provided by define-inline.
>
> Oh, that, yes the `define-inline` facility is hard to use, no doubt.
> I'm not happy with it.  This is also reflected in the lack of doc
> because it's difficult to document it much better than "look at the
> code, try it out, and fiddle until it works" :-(

Couldn't most (all but 2) of the current instances be captured by a
simplified interface defsubst* defined along the lines of:
(defmacro defsubst* (name args &rest body)
  (let ((parameters (inline--get-parameters args)))
    `(define-inline ,name ,args
       (inline-letevals
        ,(inline--susbt*-bindings args)
        (inline-quote
         (cl-symbol-macrolet
             ,(mapcar (lambda (v) `(,v (,'\, ,v))) parameters)
           ,@body))))))

Where I've left the ugly details of handling lambda lists to
inline--get-parameters and inline--subst*-bindings.  I'm unclear on
why defsubst* is an improvement on defsubst.

> >>     (define-inline cconv--var-classification (binder form)
> >>       (inline-quote
> >>        (cdr (assoc ,(cons (inline-const-val binder)
> >>                           (inline-const-val form))
> >>                    cconv-var-classification))))
> >
> > Don't you need something to add a quote to the cons cell when "binder"
> > or "form" are not constant?
>
> Oh, you're right.
>
> >> but here as well, this optimization would never apply because those args
> >> are never literal constants.  Worse: the failure of `inline-const-val`
> >> would cause the whole inlining to fail :-(
> > Could inline--do-quote catch the throw?
>
> It could, but it doesn't (and it would be an incompatible change).

As far as I can tell, the only code that makes use of inline-const-val
is cl-typep, so the impact of any incompatibility should be (famous
last words) controllable.  Is the issue figuring out how to define
inline-letevals so that inline-const-val would be able to "see
through" it when the parameter is constant but be bound by it when it
is not constant?

> > The byte-opt.el code from v28.2.50 says it's because the third
> > argument may be an impure function:
> >          ;; `assoc' and `assoc-default' are excluded since they are
> >          ;; impure if the test function is (consider `string-match').
> > I'm not sure why the possibility of signaling an error alone would be
> > disqualifying.  For example, (+ 5 's) signals an error.
>
> Oh, you're right, sorry.  So the problem is if the test function is
> constant but not pure.
>
> > Also, I don't get why logand isn't considered a pure function
>
> What makes you think it's not?
>
Faulty memory - I was thinking of lsh as mentioned in this comment
from byte-opt.el:
;; Pure functions are side-effect free functions whose values depend
;; only on their arguments, not on the platform.  For these functions,
;; calls with constant arguments can be evaluated at compile time.
;; For example, ash is pure since its results are machine-independent,
;; whereas lsh is not pure because (lsh -1 -1)'s value depends on the
;; fixnum range.

> > How important is it to be able to run byte-code generated by
> > a 32-bit emacs in a 64-bit emacs (or vice-versa)?
>
> The Emacs tarball comes with all the `.elc` files, so it's important
> that `.elc` files be portable across architectures.

Interesting restriction.

Lynn

Re: inline function expansion

[Stefan Monnier]

[ Sorry, this also feel through.  ]

>> Isn't the idea of inlining that the behaviour/effect of invoking a
>> function shouldn't change, just that the resulting code might be more
>> efficient?

Indeed, but `define-inline` is a tool that lets you define the inliner
at the same time as the non-inlined definition, and it's up to the user
of `define-inline` to make sure the inliner gives the right result (tho
`define-inline` tries to make it easier to DTRT).

> I'd like to define inline- variants of pure subrs, e.g. arithmetic
> operators, type-predicates, that evaluate during macroexpansion rather
> than involving the compiler's optimization phase.

`define-inline` is definitely not meant for that use-case, since it's
designed to have a single definition that does both:
- define the inliner.
- define the non-inlined version of the code.

In your case, the non-inlined version is written elsewhere :-(

Instead, you want to use a "compiler macro".

Moving optimizations to the macroexpansion phase can have many benefits,
indeed (e.g. it lets those optimization affect the subsequent closure
conversion), but also downsides (you may get more warnings about chunks
of code over which you have no/little control, like "unused variable"
warnings in places where the vars is "used" by code that's optimized
away).

> I think it will be easier to ensure compile-time generic methods
> (e.g. a macro that simply calls a generic method) will (or at least
> can) dispatch during macro-expansion, without involving the
> byte-compiler's optimization phase.

I don't understand this, sorry.

> (define-inline inline-+ (&rest args)
>    (if (seq-every-p #'inline-const-p args)
>        (apply (eval-when-compile (symbol-function '+)) args)
>     (inline-quote (,(eval-when-compile (symbol-function '+)) . ,args))))

IIRC you definitely need an `inline-letvals` somewhere here.
But also this will define the non-inlined version as something along the
lines of:

    (defun inline-+ (&rest args)
       (if (seq-every-p ... args)
           (apply '+ args)
        (apply (symbol-function '+) args)))

which is much too slow IMO.


        Stefan

Re: inline function expansion

[Lynn Winebarger]

On Thu, May 18, 2023 at 2:29 PM Stefan Monnier <monnier@iro.umontreal.ca> wrote:
> > I think it will be easier to ensure compile-time generic methods
> > (e.g. a macro that simply calls a generic method) will (or at least
> > can) dispatch during macro-expansion, without involving the
> > byte-compiler's optimization phase.
>
> I don't understand this, sorry.

I'm trying to provide myself a tool for generic programming that
dispatches at compile time.  I've been writing too much repetitive
code, but I'm not a fan of ad hoc macros either.  Basically, I'm
trying to provide a C#-ish system for writing generic code
parameterized by interface requirements.  Then the generic method can
be moved to compile-time, with specialization on constant parameters
to dispatch to specialized code. Like cl-typep, except instead of an
explicit pcase form, calling a generic method.

> > (define-inline inline-+ (&rest args)
> >    (if (seq-every-p #'inline-const-p args)
> >        (apply (eval-when-compile (symbol-function '+)) args)
> >     (inline-quote (,(eval-when-compile (symbol-function '+)) . ,args))))
>
> IIRC you definitely need an `inline-letvals` somewhere here.

That's the issue - if you use inline-letvals, then the code can't make
use of constant values provided as operands.

> But also this will define the non-inlined version as something along the
> lines of:
>
>     (defun inline-+ (&rest args)
>        (if (seq-every-p ... args)
>            (apply '+ args)
>         (apply (symbol-function '+) args)))
>
> which is much too slow IMO.

I agree.

I posted a patch to emacs-devel for define-inline-pure-subr that
adapts the technique of define-inline.  I wanted to literally inline
the subr's into the code, but aside from the issue of not having
read-syntax for subrs (for some reason), some parts of core emacs
appear to rely on the car of a form being a symbol.

So I ended up defining a second symbol to hold the true definition,
with the compiler macro inserting a call to that symbol, while the
original symbol made into either a defun or defsubst.  The code copies
the plist of the original symbol to the second symbol so any
properties used by the byte-compiler/optimizer will be applied to the
new symbol as well.

Re: inline function expansion

[Stefan Monnier]

> I'm trying to provide myself a tool for generic programming that
> dispatches at compile time.

I still don't understand what you mean by that.
Do you mean that the programmers write

    (my-foo a b c)

and during macroexpansion this is turned into

    (my-foo-for-thurbies a b c)

when we somehow figure out that `a` is a "thurby"?

> I've been writing too much repetitive
> code, but I'm not a fan of ad hoc macros either.  Basically, I'm
> trying to provide a C#-ish system for writing generic code
> parameterized by interface requirements.

[ "generic code" and "interface requirements" are ... generic terms with
wildly different meanings in different communities, and I'm not familiar
enough with the C# world to guess what you mean by that.  ]

>> > (define-inline inline-+ (&rest args)
>> >    (if (seq-every-p #'inline-const-p args)
>> >        (apply (eval-when-compile (symbol-function '+)) args)
>> >     (inline-quote (,(eval-when-compile (symbol-function '+)) . ,args))))
>>
>> IIRC you definitely need an `inline-letvals` somewhere here.
>
> That's the issue - if you use inline-letvals, then the code can't make
> use of constant values provided as operands.

Are you sure?  I think the real problem is that `inline-const-p` is not
a function but a macro, so you can pass it as a first-class function.
E.g.:

    (define-inline my-plus (&rest args)
      (inline-letevals args
        (if (seq-every-p (lambda (x) (inline-const-p x)) args)
            (apply #'+ (mapcar (lambda (x) (inline-const-val x)) args))
          (inline-quote (+ . ,args)))))

seems to do (more or less) what your code illustrated.

>> But also this will define the non-inlined version as something along the
>> lines of:
>>
>>     (defun inline-+ (&rest args)
>>        (if (seq-every-p ... args)
>>            (apply '+ args)
>>         (apply (symbol-function '+) args)))
>>
>> which is much too slow IMO.
>
> I agree.
>
> I posted a patch to emacs-devel for define-inline-pure-subr that
> adapts the technique of define-inline.

I'm still not sure why you're not using a `compiler-macro` which seems
to be exactly what you're after.


        Stefan

Re: inline function expansion

[Lynn Winebarger]

On Fri, May 19, 2023 at 9:07 AM Stefan Monnier <monnier@iro.umontreal.ca> wrote:
> > I'm trying to provide myself a tool for generic programming that
> > dispatches at compile time.
>
> I still don't understand what you mean by that.
> Do you mean that the programmers write
>
>     (my-foo a b c)
>
> and during macroexpansion this is turned into
>
>     (my-foo-for-thurbies a b c)
>
> when we somehow figure out that `a` is a "thurby"?

For my purposes, an "interface" spec is just a list of method and slot
signatures associated to some object, which will be realized by a set
of bindings specified via special forms and bound to some name.
Then a compile-time generic f is a factoring of a regular generic into
a generic function of interface realizations that produces a concrete
runtime function.  I'm thinking to adopt the "place name" technique of
naming the concrete function by the form that created it, ie. \(f\
arg1-iface-realizer\ arg2-iface-realizer\ ...\).  Note the check is
that the realizer provides all the required signatures (a superset),
which is why I refer to it as a "constraint" on the interface
implementation.

Then the generic method could dispatch on simple wrappers created by
the iface-realizers.  If constructors are invoked at compile time when
they appear in constant expressions and have constant arguments, then
the generic multi-dispatch method specialized on those realizers can
inline the call to the specialized method in the compiler macro, while
a residual generic method could do the same dispatch at run-time.

But the point is to separate the expression of the algorithm from the
expression of the bindings that are used by the algorithm, without
resorting to either dynamic dispatch tables or ad hoc macros per
algorithm.

> > I've been writing too much repetitive
> > code, but I'm not a fan of ad hoc macros either.  Basically, I'm
> > trying to provide a C#-ish system for writing generic code
> > parameterized by interface requirements.
>
> [ "generic code" and "interface requirements" are ... generic terms with
> wildly different meanings in different communities, and I'm not familiar
> enough with the C# world to guess what you mean by that.  ]

I only hacked on C#'s generics for about a month a decade ago, so it
really is just my memory of the "flavor" of the generics being
expressed by constraints on interfaces.

>
> >> > (define-inline inline-+ (&rest args)
> >> >    (if (seq-every-p #'inline-const-p args)
> >> >        (apply (eval-when-compile (symbol-function '+)) args)
> >> >     (inline-quote (,(eval-when-compile (symbol-function '+)) . ,args))))
> >>
> >> IIRC you definitely need an `inline-letvals` somewhere here.
> >
> > That's the issue - if you use inline-letvals, then the code can't make
> > use of constant values provided as operands.
>
> Are you sure?  I think the real problem is that `inline-const-p` is not
> a function but a macro, so you can pass it as a first-class function
> E.g.:
>
>     (define-inline my-plus (&rest args)
>       (inline-letevals args
>         (if (seq-every-p (lambda (x) (inline-const-p x)) args)
>             (apply #'+ (mapcar (lambda (x) (inline-const-val x)) args))
>           (inline-quote (+ . ,args)))))
>
> seems to do (more or less) what your code illustrated.

But then inline-const-val will (and inline-const-p) will get the
symbol 'x as the operand, right?

>
> >> But also this will define the non-inlined version as something along the
> >> lines of:
> >>
> >>     (defun inline-+ (&rest args)
> >>        (if (seq-every-p ... args)
> >>            (apply '+ args)
> >>         (apply (symbol-function '+) args)))
> >>
> >> which is much too slow IMO.
> >
> > I agree.
> >
> > I posted a patch to emacs-devel for define-inline-pure-subr that
> > adapts the technique of define-inline.
>
> I'm still not sure why you're not using a `compiler-macro` which seems
> to be exactly what you're after.

I'm very finicky I suppose.  I want to get constant expression
evaluation as automatically as possible, to enable the compile-time
dispatch cleanly.  Or are you saying that generic methods can be
directly made into compiler macros?

I was thinking I needed the original symbol redefined to avoid
multiple macro expansions of the operands, as define-inline-pure-subr
expands its operands before returning, so returning the inline-form is
problematic.  I also  consider the property that inlining is
uncooperative with advice to be a feature, particularly for pure
functions.  After all, the advice facility makes every function
identified by a symbol impure.

Lynn

Re: inline function expansion

[Stefan Monnier]

>> I still don't understand what you mean by that.
>> Do you mean that the programmers write
>>
>>     (my-foo a b c)
>>
>> and during macroexpansion this is turned into
>>
>>     (my-foo-for-thurbies a b c)
>>
>> when we somehow figure out that `a` is a "thurby"?
>
> For my purposes, an "interface" spec is just a list of method and slot
> signatures associated to some object, which will be realized by a set
> of bindings specified via special forms and bound to some name.
> Then a compile-time generic f is a factoring of a regular generic into
> a generic function of interface realizations that produces a concrete
> runtime function.  I'm thinking to adopt the "place name" technique of
> naming the concrete function by the form that created it, ie. \(f\
> arg1-iface-realizer\ arg2-iface-realizer\ ...\).  Note the check is
> that the realizer provides all the required signatures (a superset),
> which is why I refer to it as a "constraint" on the interface
> implementation.
>
> Then the generic method could dispatch on simple wrappers created by
> the iface-realizers.  If constructors are invoked at compile time when
> they appear in constant expressions and have constant arguments, then
> the generic multi-dispatch method specialized on those realizers can
> inline the call to the specialized method in the compiler macro, while
> a residual generic method could do the same dispatch at run-time.
>
> But the point is to separate the expression of the algorithm from the
> expression of the bindings that are used by the algorithm, without
> resorting to either dynamic dispatch tables or ad hoc macros per
> algorithm.

I'm still lost.  An example might help.

>>     (define-inline my-plus (&rest args)
>>       (inline-letevals args
>>         (if (seq-every-p (lambda (x) (inline-const-p x)) args)
>>             (apply #'+ (mapcar (lambda (x) (inline-const-val x)) args))
>>           (inline-quote (+ . ,args)))))
>>
>> seems to do (more or less) what your code illustrated.
>
> But then inline-const-val will (and inline-const-p) will get the
> symbol 'x as the operand, right?

I don't think so.  Have you tried it (Edebug should work correctly)?

    ELISP> (macroexpand-all '(my-plus 5 y))
    (+ 5 y)
    ELISP> (macroexpand-all '(my-plus 5 6))
    11 (#o13, #xb, ?\C-k)
    ELISP> 

>> I'm still not sure why you're not using a `compiler-macro` which seems
>> to be exactly what you're after.
>
> I'm very finicky I suppose.  I want to get constant expression
> evaluation as automatically as possible, to enable the compile-time
> dispatch cleanly.  Or are you saying that generic methods can be
> directly made into compiler macros?

And here I'm lost as well.  AFAICT there's just as little "directly made
into" for define-inline as for compiler-macros (`define-inline` is just
a way to define a function and its `compiler-macro` in one go).

> I was thinking I needed the original symbol redefined to avoid
> multiple macro expansions of the operands,

`compiler-macro`s can decide to keep the call as-is without introducing
an infinite macro-expansion loop.

> After all, the advice facility makes every function identified by
> a symbol impure.

It's the mutability of the symbol (i.e. `fset`) rather than the advice
facility itself, but yes :-)


        Stefan

Re: inline function expansion

[Lynn Winebarger]

On Sat, May 20, 2023 at 11:48 AM Stefan Monnier
<monnier@iro.umontreal.ca> wrote:
> > For my purposes, an "interface" spec is just a list of method and slot
> > signatures associated to some object, which will be realized by a set
> > of bindings specified via special forms and bound to some name.
> > Then a compile-time generic f is a factoring of a regular generic into
> > a generic function of interface realizations that produces a concrete
> > runtime function.  I'm thinking to adopt the "place name" technique of
> > naming the concrete function by the form that created it, ie. \(f\
> > arg1-iface-realizer\ arg2-iface-realizer\ ...\).  Note the check is
> > that the realizer provides all the required signatures (a superset),
> > which is why I refer to it as a "constraint" on the interface
> > implementation.
> >
> > Then the generic method could dispatch on simple wrappers created by
> > the iface-realizers.  If constructors are invoked at compile time when
> > they appear in constant expressions and have constant arguments, then
> > the generic multi-dispatch method specialized on those realizers can
> > inline the call to the specialized method in the compiler macro, while
> > a residual generic method could do the same dispatch at run-time.
> >
> > But the point is to separate the expression of the algorithm from the
> > expression of the bindings that are used by the algorithm, without
> > resorting to either dynamic dispatch tables or ad hoc macros per
> > algorithm.
>
> I'm still lost.  An example might help.

For my purposes, interfaces and realizations of interfaces are just a
way to specify bindings of symbols in a more structured and
encapsulated way than raw macros.
I'm still spit-balling here, but I'm thinking a generic
compile-time-dispatched (inlineable) "max" might be defined along
these lines:

;; ordering interface has two parameters
(define-interface ordering (bool-T elt-T)
  ;; return value of `lt' method satisfies bool-T interface
  (method (bool-T lt) (elt-T a) (elt-T b)))

(define-realized-interface integer-ordering (ordering boolean integer)
  ;; bind lt method to built-in `<'
  (method lt <))

(defgeneric max (< a b)
  "Determine the larger of a and b according to <")

(define-inline-method max ((ordering <) &opaque a b)
  "Determine the larger of a and b according to ordering <"
  ;; < is treated syntactically as a dispatcher
  (if (< lt a b) a b))

;; because elisp does not allow applications in the operator position
(define-inlined-method integer-max (max integer-ordering))
;; Alternatively,
;; (integer-ordering lt)  reduces at compile time to something like
;;  #s(interface-method
;;     #s(interface-realization
;;        #s(interface ordering boolean integer)
;;        <)
;;      lt
;;      <)
;; which `max' is specialized for by define-inline-method above, so
(defun integer-max (a b)
  ;; inlined by compile-time dispatch of the max generic method
  (max (integer-ordering lt) a b))

;; These should produce t
(= (max integer-ordering 5 6) (integer-max 5 6))
(= (max (integer-ordering lt) 5 6) (integer-max 5 6))
(macroexp-const-p (macroexpand-all '(max (integer-ordering lt) 5 6)))

>
> >>     (define-inline my-plus (&rest args)
> >>       (inline-letevals args
> >>         (if (seq-every-p (lambda (x) (inline-const-p x)) args)
> >>             (apply #'+ (mapcar (lambda (x) (inline-const-val x)) args))
> >>           (inline-quote (+ . ,args)))))
> >>
> >> seems to do (more or less) what your code illustrated.
> >
> > But then inline-const-val will (and inline-const-p) will get the
> > symbol 'x as the operand, right?
>
> I don't think so.  Have you tried it (Edebug should work correctly)?

Ok, now I see why inline--testconst-p expands to include a call to
macroexp-const-p.

> >> I'm still not sure why you're not using a `compiler-macro` which seems
> >> to be exactly what you're after.
> >
> > I'm very finicky I suppose.  I want to get constant expression
> > evaluation as automatically as possible, to enable the compile-time
> > dispatch cleanly.  Or are you saying that generic methods can be
> > directly made into compiler macros?
>
> And here I'm lost as well.  AFAICT there's just as little "directly made
> into" for define-inline as for compiler-macros (`define-inline` is just
> a way to define a function and its `compiler-macro` in one go).

Hopefully the example above clarified what I'm talking about - `max'
is specialized at compile-time, and reduced completely at compile-time
as well if all the arguments are constant.  Although I would change
"inline-const-p" to test for function purity (exclude stateful
closures or otherwise impure functions).

> > I was thinking I needed the original symbol redefined to avoid
> > multiple macro expansions of the operands,
>
> `compiler-macro`s can decide to keep the call as-is without introducing
> an infinite macro-expansion loop.
>
I was concerned about an exponential rather than infinite number of
expansions , though I may have just been thinking conservatively.

Lynn

Re: inline function expansion

[Lynn Winebarger]

On Sat, May 27, 2023 at 10:34 AM Lynn Winebarger <owinebar@gmail.com> wrote:
>
> On Sat, May 20, 2023 at 11:48 AM Stefan Monnier
> <monnier@iro.umontreal.ca> wrote:
> > > For my purposes, an "interface" spec is just a list of method and slot
> > > signatures associated to some object, which will be realized by a set
> > > of bindings specified via special forms and bound to some name.
> > > Then a compile-time generic f is a factoring of a regular generic into
> > > a generic function of interface realizations that produces a concrete
> > > runtime function.  I'm thinking to adopt the "place name" technique of
> > > naming the concrete function by the form that created it, ie. \(f\
> > > arg1-iface-realizer\ arg2-iface-realizer\ ...\).  Note the check is
> > > that the realizer provides all the required signatures (a superset),
> > > which is why I refer to it as a "constraint" on the interface
> > > implementation.
> > >
> > > Then the generic method could dispatch on simple wrappers created by
> > > the iface-realizers.  If constructors are invoked at compile time when
> > > they appear in constant expressions and have constant arguments, then
> > > the generic multi-dispatch method specialized on those realizers can
> > > inline the call to the specialized method in the compiler macro, while
> > > a residual generic method could do the same dispatch at run-time.
> > >
> > > But the point is to separate the expression of the algorithm from the
> > > expression of the bindings that are used by the algorithm, without
> > > resorting to either dynamic dispatch tables or ad hoc macros per
> > > algorithm.
> >
> > I'm still lost.  An example might help.
>
> For my purposes, interfaces and realizations of interfaces are just a
> way to specify bindings of symbols in a more structured and
> encapsulated way than raw macros.
> I'm still spit-balling here, but I'm thinking a generic
> compile-time-dispatched (inlineable) "max" might be defined along
> these lines:
>
My intention below is that define-inline-method is like applying the
generic function to the abstract interfaces, producing a function that
consumes the body as an argument.  So maybe there should be a
(define-inline-generic max (< a b))
that creates the dual-definition of max as a (generic) compiler macro
and generic function, with the method specializing max on
"realized-interface" arguments that successfully unify against the
supplied interface spec:
(max <-iface a-iface b-iface) = (lambda (<-realized a-realized
b-realized) ((lambda (a b) ...) (realized-interface-value a)
(realized-interface-value b)))

where "realized-interface-value" removes the wrapper used for
specialization.  Note that it also only does so for "opaque"
arguments, to allow the "<" argument to be treated as a fixed constant
when the call site provides a constant.  This definition should
specialize both the generic compiler macro and the generic function on
realizations of the specified interfaces for the arguments of max.
Technically, we need the following definitions:

;; these should be predefined constants
(define-interface null-interface)
(define-realized-interface null-realized)

In the code below, not specifying an interface for the a and b
arguments is the same as specifying the null-interface.

> ;; ordering interface has two parameters
> (define-interface ordering (bool-T elt-T)
>   ;; return value of `lt' method satisfies bool-T interface
>   (method (bool-T lt) (elt-T a) (elt-T b)))
>
> (define-realized-interface integer-ordering (ordering boolean integer)
>   ;; bind lt method to built-in `<'
>   (method lt <))
>
> (defgeneric max (< a b)
>   "Determine the larger of a and b according to <")
>
> (define-inline-method max ((ordering <) &opaque a b)
>   "Determine the larger of a and b according to ordering <"
>   ;; < is treated syntactically as a dispatcher
>   (if (< lt a b) a b))
>

And this
> ;; because elisp does not allow applications in the operator position
> (define-inlined-method integer-max (max integer-ordering))

should be
(define-inlined-method integer-max (max integer-ordering null-realized
null-realized))

> ;; Alternatively,
> ;; (integer-ordering lt)  reduces at compile time to something like
> ;;  #s(interface-method
> ;;     #s(interface-realization
> ;;        #s(interface ordering boolean integer)
> ;;        <)
> ;;      lt
> ;;      <)
> ;; which `max' is specialized for by define-inline-method above, so
> (defun integer-max (a b)
>   ;; inlined by compile-time dispatch of the max generic method
>   (max (integer-ordering lt) a b))
>
> ;; These should produce t
> (= (max integer-ordering 5 6) (integer-max 5 6))
> (= (max (integer-ordering lt) 5 6) (integer-max 5 6))
> (macroexp-const-p (macroexpand-all '(max (integer-ordering lt) 5 6)))
>


Lynn

Re: inline function expansion

[Stefan Monnier]

> For my purposes, interfaces and realizations of interfaces are just a
> way to specify bindings of symbols in a more structured and
> encapsulated way than raw macros.
> I'm still spit-balling here, but I'm thinking a generic
> compile-time-dispatched (inlineable) "max" might be defined along
> these lines:
>
> ;; ordering interface has two parameters
> (define-interface ordering (bool-T elt-T)
>   ;; return value of `lt' method satisfies bool-T interface
>   (method (bool-T lt) (elt-T a) (elt-T b)))
>
> (define-realized-interface integer-ordering (ordering boolean integer)
>   ;; bind lt method to built-in `<'
>   (method lt <))
>
> (defgeneric max (< a b)
>   "Determine the larger of a and b according to <")
>
> (define-inline-method max ((ordering <) &opaque a b)
>   "Determine the larger of a and b according to ordering <"
>   ;; < is treated syntactically as a dispatcher
>   (if (< lt a b) a b))
>
> ;; because elisp does not allow applications in the operator position
> (define-inlined-method integer-max (max integer-ordering))
> ;; Alternatively,
> ;; (integer-ordering lt)  reduces at compile time to something like
> ;;  #s(interface-method
> ;;     #s(interface-realization
> ;;        #s(interface ordering boolean integer)
> ;;        <)
> ;;      lt
> ;;      <)
> ;; which `max' is specialized for by define-inline-method above, so
> (defun integer-max (a b)
>   ;; inlined by compile-time dispatch of the max generic method
>   (max (integer-ordering lt) a b))
>
> ;; These should produce t
> (= (max integer-ordering 5 6) (integer-max 5 6))
> (= (max (integer-ordering lt) 5 6) (integer-max 5 6))
> (macroexp-const-p (macroexpand-all '(max (integer-ordering lt) 5 6)))

OK, that helps me understand a bit what you're talking about, thanks.

This example seems rather uninteresting (lots of extra code for very little
gain), so I strongly suspect this is not your prime-motivator.
What's the over-arching goal?

I think `define-inline` is definitely not a good starting point for
the above.  OTOH you might be able to layer your `define-inlined-method`
on top of the current `cl-generic.el`.  AFAICT the main thing you need is
some way to write a "call with enough «type» annotations" such that the
dispatch can be performed at compile time.

>> >> I'm still not sure why you're not using a `compiler-macro` which seems
>> >> to be exactly what you're after.
>> >
>> > I'm very finicky I suppose.  I want to get constant expression
>> > evaluation as automatically as possible, to enable the compile-time
>> > dispatch cleanly.  Or are you saying that generic methods can be
>> > directly made into compiler macros?
>>
>> And here I'm lost as well.  AFAICT there's just as little "directly made
>> into" for define-inline as for compiler-macros (`define-inline` is just
>> a way to define a function and its `compiler-macro` in one go).
>
> Hopefully the example above clarified what I'm talking about

Somewhat.  Still doesn't explain why you're focusing on `define-inline`
rather than `compiler-macro`.  A compiler macro is just like a macro
except:

- It shares its name with a function.
- The returned expansion should behave identically to the
  way the function call would behave.
- It's unspecified when or even *if* it's expanded (if it's not
  expanded, the function is called at runtime instead).
- It receives an additional argument (the whole sexp), which it can use
  to say "I don't want to expand anything this time, just call the
  function at runtime instead".

IOW it's a mechanism to implement compile-time (well,
macroexpansion-time in our case) optimizations.

> Although I would change "inline-const-p" to test for function purity
> (exclude stateful closures or otherwise impure functions).

I think that would be a mistake.  "const-p" doesn't mean that the return
value is pure but that the expression itself always returns the same value.


        Stefan

Re: inline function expansion

[Lynn Winebarger]

On Sun, May 28, 2023 at 10:57 AM Stefan Monnier
<monnier@iro.umontreal.ca> wrote:
> > For my purposes, interfaces and realizations of interfaces are just a
> > way to specify bindings of symbols in a more structured and
> > encapsulated way than raw macros.
> > I'm still spit-balling here, but I'm thinking a generic
> > compile-time-dispatched (inlineable) "max" might be defined along
> > these lines:
> >
> > ;; ordering interface has two parameters
> > (define-interface ordering (bool-T elt-T)
> >   ;; return value of `lt' method satisfies bool-T interface
> >   (method (bool-T lt) (elt-T a) (elt-T b)))
> >
> > (define-realized-interface integer-ordering (ordering boolean integer)
> >   ;; bind lt method to built-in `<'
> >   (method lt <))
> >
> > (defgeneric max (< a b)
> >   "Determine the larger of a and b according to <")
> >
> > (define-inline-method max ((ordering <) &opaque a b)
> >   "Determine the larger of a and b according to ordering <"
> >   ;; < is treated syntactically as a dispatcher
> >   (if (< lt a b) a b))
> >
> > ;; because elisp does not allow applications in the operator position
> > (define-inlined-method integer-max (max integer-ordering))
> > ;; Alternatively,
> > ;; (integer-ordering lt)  reduces at compile time to something like
> > ;;  #s(interface-method
> > ;;     #s(interface-realization
> > ;;        #s(interface ordering boolean integer)
> > ;;        <)
> > ;;      lt
> > ;;      <)
> > ;; which `max' is specialized for by define-inline-method above, so
> > (defun integer-max (a b)
> >   ;; inlined by compile-time dispatch of the max generic method
> >   (max (integer-ordering lt) a b))
> >
> > ;; These should produce t
> > (= (max integer-ordering 5 6) (integer-max 5 6))
> > (= (max (integer-ordering lt) 5 6) (integer-max 5 6))
> > (macroexp-const-p (macroexpand-all '(max (integer-ordering lt) 5 6)))
>
> OK, that helps me understand a bit what you're talking about, thanks.
>
> This example seems rather uninteresting (lots of extra code for very little
> gain), so I strongly suspect this is not your prime-motivator.

Both parts of that are true - I was trying to come up with the
smallest example that would illustrate the essence of the interface
specification and dispatch mechanism.

> What's the over-arching goal?

The overhead makes more sense if you want to replace NxM functions by
N interface realizations and M generic functions mediated through the
same interface(s).

My specific itch came about when I started rewriting my "unboxed"
package file management code to run in asynchronous batches, where
there are multiple types of files being managed, namely "source" files
(files in the package archive), installed files, and generated files
(e.g. elc and eln files), and I need to keep indexed collections of
each type in at least two contexts - one for the asynchronous batch
job, and one in the larger transaction split into batch jobs.  In this
case, there is one (or more) generic function, (each) with two
compile-time interface parameters, one with 3 realizations and one
with 2 (or more) realizations.

There are obviously other applications.  For example, a while ago I
provided an implementation of Nuutilla's transitive closure algorithm
with a set of very particular implementation choices.  With the sort
of mechanism described above, I could parameterize the code in terms
of the node, stack, and set implementation for various use
cases/performance characteristics.

>
> I think `define-inline` is definitely not a good starting point for
> the above.

If you mean literally the current implementation of define-inline, I'd
agree, except for the trick of defining both a compile-time (macro)
and a residual function.  I definitely see what I've described above
as a generalization of "define-inline" to generic functions (sans the
need for the inline-* syntax variants), particularly in the sense of
being able to see the inlining at source level using macroexpand-all.
AFAICT, there is no (meaningful) way to inline generic functions
currently,  Even if there were, what you would see after
macroexpand-all would be the code for performing the dynamic dispatch,
which is not particularly desirable.  What I'd like to see after
inlining a generic function is a call to the specific method
implementing the generic function in that case.  In that case the
inlined code is about the same size as the original code, but skips
both a function call and the dynamic calculation of the dispatch.
Plus, as a user, it's meaningful that the inlining transforms a call
to a user-defined function by a call to a (more specific) user-defined
function, rather than a bunch of dispatch code that is really full of
hairy implementation details (of generic functions).

To make the above concrete, I mentioned in my prior follow-up email
that a "define-inline-generic" form for the generic max would produce
a closure of the form
(lambda (<-realized a-realized b-realized) ((lambda (a b) ...)
(realized-interface-value a) (realized-interface-value b)))
But that inner lambda would actually be bound to a symbol (inspired by
the symbols used for generalized variables) generated by
#0=(intern (format "%S" `(max ,<-realized ,a-realized ,b-realized)))
So that the inlined form of (max (integer-ordering lt) a b) would be
(#0 a b), where the "realized-interface-value" of the opaque
parameters is simply the expression in the corresponding operand
position.

Another aspect that may not be clear is that the appearance of the
parameters in operator position correspond to where "define-inline"
would use "unquote", and everything else is implicitly
"inline-quote"-ed.

Finally, the system I described provides a kind of modular macro
system that could address some of the issues with macros noted in the
thread "bug#62762: circular dependencies in elisp files and make" on
the bug-gnu-emacs mailing list.  That is, if inlined-generic functions
were used in place of macros (where it makes sense), then you would
wind up with calls to those specialized functions that have the
realized-interface object encoded in the symbol, which is a kind of
dynamic linkage (assuming those function calls were not further
inlined). I'm not saying every instance of macros could be replaced by
one of these compile-time generics, but I'm sure there are some places
where they could be employed.


>  OTOH you might be able to layer your `define-inlined-method`
> on top of the current `cl-generic.el`.  AFAICT the main thing you need is
> some way to write a "call with enough «type» annotations" such that the
> dispatch can be performed at compile time.

I think that's the main point of designating parameters as "opaque",
so they aren't really specialized against, and only the non-opaque
parameters need to be wrapped in a form like (integer-ordering lt).
I'm still not certain that's enough to avoid needing a full-fledged
partial-evaluator embedded in the macroexpansion phase.

> >> >> I'm still not sure why you're not using a `compiler-macro` which seems
> >> >> to be exactly what you're after.
> >> >
> >> > I'm very finicky I suppose.  I want to get constant expression
> >> > evaluation as automatically as possible, to enable the compile-time
> >> > dispatch cleanly.  Or are you saying that generic methods can be
> >> > directly made into compiler macros?
> >>
> >> And here I'm lost as well.  AFAICT there's just as little "directly made
> >> into" for define-inline as for compiler-macros (`define-inline` is just
> >> a way to define a function and its `compiler-macro` in one go).
> >
> > Hopefully the example above clarified what I'm talking about
>
> Somewhat.  Still doesn't explain why you're focusing on `define-inline`
> rather than `compiler-macro`.  A compiler macro is just like a macro
> except:

I suppose I see the above as a kind of generalization of the kind of
thing your paper described "define-inline" doing for "cl-typep" to
generic functions.  I mean, I want the max inliner to be "max" itself,
specialized on some either s-expressions directly or some
specially-wrapped form of s-expressions.  I mean, that would be the
most elegant solution to my mind.

> - It shares its name with a function.
> - The returned expansion should behave identically to the
>   way the function call would behave.
> - It's unspecified when or even *if* it's expanded (if it's not
>   expanded, the function is called at runtime instead).
> - It receives an additional argument (the whole sexp), which it can use
>   to say "I don't want to expand anything this time, just call the
>   function at runtime instead".
>
> IOW it's a mechanism to implement compile-time (well,
> macroexpansion-time in our case) optimizations.
>
> > Although I would change "inline-const-p" to test for function purity
> > (exclude stateful closures or otherwise impure functions).
>
> I think that would be a mistake.  "const-p" doesn't mean that the return
> value is pure but that the expression itself always returns the same value.

I think you mean the argument value, not the return value?
But that's exactly what I mean - a pure function is immutable, and
other functions change with state, so that in the extensional sense
they are not equal even if they are eq.

For the purpose of partial evaluation, which I believe is the point of
inline-const-p, an expression `expr' is constant if
(equal (eval expr state0) (eval expr state1))
is true for all possible values of state0 and state1 (and eq is
inherently dependent on those state values, so is not a useful test
for this definition).

Clearly exprs that are syntactic literals are constants by this
definition.  Also, if `f' is a pure function, then (f C1 C2 .. Cn) for
constant expressions C1,..Cn is also a constant expression.  But that
is not the case for impure functions.  An example is `format', which
depends on the setting of variables used by the print functions.
(format "%S" '(<some complicated structure>)) may produce distinct
strings depending on the state, despite both arguments being literals.
Considering the semantic value of a function to be given a mapping
from "State -> Value -> Value", then `+' is constant function of state
while `format' is not.  Or, `+' is a constant, and `format' is not.

On the other hand, if that call to format is the body of a let
expression binding those (dynamic) variables to constants, then the
whole let expression will be a constant expression.  Likewise, lisp
constructors that have a readable print-syntax are not inherently
constant even if all arguments are constant expressions, but if such a
constant constructor expression appears as an argument to a pure
function in which all arguments are likewise either constant or
constant constructor expressions, then the expression as a whole (with
the pure function in operator position) will be constant according to
the definition above (i.e. (equal (eval expr state0) (eval expr
state1)) is true for all state0 and state1).

Lynn

Re: inline function expansion

[Stefan Monnier]

>> I think `define-inline` is definitely not a good starting point for
>> the above.
>
> If you mean literally the current implementation of define-inline, I'd
> agree, except for the trick of defining both a compile-time (macro)
> and a residual function.

I see.  I'm maybe too close to `define-inline`s design to see the larger
picture (FWIW, the driving design is to take a compiler-macro and use
it to generate the body of the function it is meant to optimize,
because it puts the user of `define-inline` in charge of making it
work, whereas the usual design is to start with the *function*'s body
and automatically infer how to inline it, but that requires figuring
out what should be inlined, avoiding name captures, etc..).

>>  OTOH you might be able to layer your `define-inlined-method`
>> on top of the current `cl-generic.el`.  AFAICT the main thing you need is
>> some way to write a "call with enough «type» annotations" such that the
>> dispatch can be performed at compile time.
> I think that's the main point of designating parameters as "opaque",
> so they aren't really specialized against, and only the non-opaque
> parameters need to be wrapped in a form like (integer-ordering lt).
> I'm still not certain that's enough to avoid needing a full-fledged
> partial-evaluator embedded in the macroexpansion phase.

Indeed, the difficulty I see is how to propagate info for cascading
inlines (when inlining one call exposes info that (should) make another
call inlinable).  In most compilers, this is just "normal business" done
by combining inlining with constant propagation, constant folding,
etc.. (which you can call "partial evaluation").  But if you want to do
it as part of macroexpansion, then you can't rely on the compiler's
constant propagation, and constant folding.

>> > Although I would change "inline-const-p" to test for function purity
>> > (exclude stateful closures or otherwise impure functions).
>>
>> I think that would be a mistake.  "const-p" doesn't mean that the return
>> value is pure but that the expression itself always returns the same value.
>
> I think you mean the argument value, not the return value?

No, I mean that `inline-const-p` tells us something about the EXP it receives,
and this something is not that this EXP's return value is pure, but that
this EXP always returns the same value.  It's arguably a misnomer, what
it really means is "do we already know what EXP will return?".

This is evidenced by the fact that when we generate the function,
the `inline-const-p` call is just replaced by t (because once we get to
the function, EXP has already been evaluated so of course we know the
value).

> But that's exactly what I mean - a pure function is immutable, and
> other functions change with state, so that in the extensional sense
> they are not equal even if they are eq.
>
> For the purpose of partial evaluation, which I believe is the point of
> inline-const-p, an expression `expr' is constant if
> (equal (eval expr state0) (eval expr state1))

I agree.  And indeed if `exp` is an expression which always returns
`insert` or `buffer-substring`, then

    (equal (eval expr state0) (eval expr state1))

is true, even though `insert/buffer-substring` are definitely not
pure functions.

> Clearly exprs that are syntactic literals are constants by this
> definition.  Also, if `f' is a pure function, then (f C1 C2 .. Cn) for
> constant expressions C1,..Cn is also a constant expression.

Indeed, tho currently `inline-const-p` doesn't take advantage of that.


        Stefan

Re: inline function expansion

[Lynn Winebarger]

On Sun, May 28, 2023 at 10:59 PM Stefan Monnier
<monnier@iro.umontreal.ca> wrote:
> >> I think `define-inline` is definitely not a good starting point for
> >> the above.
> >
> > If you mean literally the current implementation of define-inline, I'd
> > agree, except for the trick of defining both a compile-time (macro)
> > and a residual function.
>
> I see.  I'm maybe too close to `define-inline`s design to see the larger
> picture (FWIW, the driving design is to take a compiler-macro and use
> it to generate the body of the function it is meant to optimize,
> because it puts the user of `define-inline` in charge of making it
> work, whereas the usual design is to start with the *function*'s body
> and automatically infer how to inline it, but that requires figuring
> out what should be inlined, avoiding name captures, etc..).


It might be worth revisiting how I got to this approach.  As I
mentioned, this arose when trying to implement processing files of a
set of packages, which may include hundreds or even thousands of
packages (so tens of thousands of records for individual files), in
asynchronous chunks to reduce hours of processing to minutes if enough
cores are available.

My original (synchronous) approach used closures in the file records
to do the "right thing" for the type of file.  However, the collection
of file records ("database") is deeply recursive, so just exporting
the closure to an asynchronous job wrote out the entire collection,
prompting me to look at "generic" functions for dispatching correctly
without embedding a closure in the file records.  Such a procedure
needed at least two arguments for specialization, since each type of
file record has different indexing keys for different phases of
processing (whether synchronous or asynchronous).  For example, I copy
all elisp source files from the packages in a transaction before
updating the autoloads file in the target directory (containing all of
them in an "unboxed" location), and then byte-compiling them.  A key
that is guaranteed unique in one context (where files are in the
source directory) may not be so guaranteed in the target directory,
and the algorithm should be able to detect that as an error condition
at least.  In other cases, the destination files will have different
paths relative to the target directory than in the source directory
(usually package-relative for data files) to guarantee uniqueness.

So originally I was looking at how to use generic functions
specialized to dispatch on the type of file record structure and a
(constant) symbol for the correct key in a given context.  That's why
I was interested particularly in the definition of cl-typep.  I
consider hard-coding those symbols to be a very ugly approach.  I
actually started by writing up specialized functions for each case,
but it's too much repetition of the same code with slightly different
"parameters" (in the sense of macros).

> >>  OTOH you might be able to layer your `define-inlined-method`
> >> on top of the current `cl-generic.el`.  AFAICT the main thing you need is
> >> some way to write a "call with enough «type» annotations" such that the
> >> dispatch can be performed at compile time.
> > I think that's the main point of designating parameters as "opaque",
> > so they aren't really specialized against, and only the non-opaque
> > parameters need to be wrapped in a form like (integer-ordering lt).
> > I'm still not certain that's enough to avoid needing a full-fledged
> > partial-evaluator embedded in the macroexpansion phase.
>
> Indeed, the difficulty I see is how to propagate info for cascading
> inlines (when inlining one call exposes info that (should) make another
> call inlinable).  In most compilers, this is just "normal business" done
> by combining inlining with constant propagation, constant folding,
> etc.. (which you can call "partial evaluation").  But if you want to do
> it as part of macroexpansion, then you can't rely on the compiler's
> constant propagation, and constant folding.

Yes.  The problem with leaving it in the compiler proper is that the
output is byte-code.  I want a source-to-source transformation so I
can check that the output is what I would expect.  But as I mentioned
below, if I attempt to do it without taking over the entire
macroexpansion process, there's a risk of an exponential number of
macro-expansion visits to AST nodes, especially since some of the
checks for const-ness may already require multiple visits (for
constructor expressions - one to check that all arguments are const,
and one to actually evaluate it at compile-time *if* the whole
expression is constant).

I want to be clear that I don't see "interface" here in terms of types
or type inference, but as a way of writing modular macros.  There
could be some type-inferencing built on top of this mechanism, but
that's not really my purpose.  Like define-inline, I expect
define-inline-generic/define-inline-method (or whatever) to be
responsible for indicating where the constant-folding opportunities
are.  I just prefer marking the variables and generating all the rest
where possible.  If the appearance of parameters in the operator
position is considered to be a variant of "unquote", where the code
that would be in the "unquote" form is specified in the interface
realization (this is another way of giving the user control), then the
only remaining question is where the corresponding form of
"inline-quote" should go.  I think the correct answer must be "around
the whole body" of the function, since the user can always use
interfaces to define the sub-expressions that should be evaluated at
compile time if constant (and not marked opaque).

Alternatively, arguments not marked "&opaque" could be marked by
"&constexpr" or similar instead, and dropping the &opaque marker.  I
think I prefer marking &opaque because it's an unconditional state of
individual parameters (i.e. never evaluate at compile-time) where
&constexpr (or whatever) would mean "evaluate at compile-time if all
&constexpr operands expressions are constant".

I believe this could be used for an alternative, possibly friendlier,
form of define-inline, say define-inline*, so that

;; parameters appear as "unquote" operators in body...
(define-inline-template* f* (x1 .. xN &opaque y1 .. yM) body ...)
(define-inline* f (f* realization-x1 ... realization-xN realization-y1
... realization-yN))

would become

(define-inline f (x1 ... xN y1 ... yM)
   (inline-letevals (y1 ... yM)
     (let ((x1 (inline-const-value x1)) ... (xN (inline-const-value xN)))
       (inline-quote (progn
body)[x1/realization-x1,...xN/realization-xN,y1/realization-y1,...yM/realization-yM]))))

using the bracket notation for capture-free substitution.

> >> > Although I would change "inline-const-p" to test for function purity
> >> > (exclude stateful closures or otherwise impure functions).
> >>
> >> I think that would be a mistake.  "const-p" doesn't mean that the return
> >> value is pure but that the expression itself always returns the same value.
> >
> > I think you mean the argument value, not the return value?
>
> No, I mean that `inline-const-p` tells us something about the EXP it receives,
> and this something is not that this EXP's return value is pure, but that
> this EXP always returns the same value.  It's arguably a misnomer, what
> it really means is "do we already know what EXP will return?".

Ok, you meant the return value of EXP, or of (eval EXP), not of inline-const-p.

>
> This is evidenced by the fact that when we generate the function,
> the `inline-const-p` call is just replaced by t (because once we get to
> the function, EXP has already been evaluated so of course we know the
> value).
>
> > But that's exactly what I mean - a pure function is immutable, and
> > other functions change with state, so that in the extensional sense
> > they are not equal even if they are eq.
> >
> > For the purpose of partial evaluation, which I believe is the point of
> > inline-const-p, an expression `expr' is constant if
> > (equal (eval expr state0) (eval expr state1))
>
> I agree.  And indeed if `exp` is an expression which always returns
> `insert` or `buffer-substring`, then
>
>     (equal (eval expr state0) (eval expr state1))
>
> is true, even though `insert/buffer-substring` are definitely not
> pure functions.

I'm trying to understand your conclusion, and it seems to me there is
some kind of value/reference distinction going on here.

I used "equal" and "eval" above, but it might be better to use
"equal*" and "eval*" because we must compare values completely by
extension as "eq" is entirely missing.  So, for example, symbols must
be compared by name and some state-independent representation of the
ob-stack in which they are interned, with a nil ob-stack meaning never
equal*.  What this would entail for "functions" that are not
side-effect-free is an interesting question.  The answer depends on
how you intend to test for equality.  If I understand your point,
since the free variables in (functions like) insert and
buffer-substring resolve in whatever state is passed in, "function
name references" should be judged as equal, where closures with no
free variables can be tested extensionally by comparing their code and
environments.

OTOH, if the purpose of a "const-p" test is to discriminate when an
expression can be safely evaluated at compile-time, then this notion
of equality must fail.  For example, if we define
state1 := (eval '(mapcar #'insert '("foo" "bar")) state0)
state2 := (eval '(eval-when-compile (mapcar #'insert '("foo" "bar"))) state0)
then state1 will not equal state2.

But if you want to dispatch pcase on a subr value, i.e. (pcase
(inline-const-value x) (<clause> ... (#'insert <some code>) <clause>
...), then presumably dispatching the pcase at compile-time is the
desired result.  However, (funcall (inline-const-value x) "foo") would
not give the desired result (if x were bound to #'insert or
#'buffer-substring).

So, I would say, if function "f" has free variables x1,...,xN, then
"(eval* #'f state)" above must return something equivalent to
evaluating the expression (with lexical-binding in effect):

(let ((x1 (eval* 'x1 state)) ... (xN (eval* 'xN state)) (f #'f))
(lambda (&rest args) (apply f args)))

Or, we could replace the (eval* 'EXP state) with (eval-when-compile
EXP) for an equivalent effect.  If "f" is side-effect free, then the
last expression is a pure function.  If one of the variables xI has a
non-serializable value (like #'insert or #'buffer-substring), then the
result is an error when reading the value back in.

Unfortunately, since cl-typep is the only piece of code that (as far
as I know) actually makes use of inline-const-value, and, AFAIK, would
never expect a function like #'insert or #'buffer-substring in the
type argument, it's not clear how inline-const-value is intended to
behave in the "pcase" and "funcall" examples respectively.

This discussion has been helpful to me in hashing out the "right"
definition for what I'm calling interfaces/interface-realizations and
inlined-generics and inline-methods.  Thanks for the time you've spent
reading and responding.

Lynn