Re: inline function expansion

[Lynn Winebarger <owinebar@gmail.com>]

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