Re: inline function expansion

[Lynn Winebarger <owinebar@gmail.com>]

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