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