Hi,

I see both in Closette and in PCL that the implementation of
`next-method-p` boils down to (taken from Closette):

`(lambda (args next-emfun)
(flet ((call-next-method (&rest cnm-args)
(if (null next-emfun)
(error "No next method for the~@
generic function ~S."
(method-generic-function ',method))
(funcall next-emfun (or cnm-args args))))
(next-method-p ()
(not (null next-emfun))))
(apply #'(lambda ,(kludge-arglist lambda-list)
,form)
args))))))

I'm curious if that same approach is used in all other implementations
out there.

I'm specifically curious about this choice to represent (at run-time)
the "no next method" (NNM) case as nil, forcing an `if` test in
`call-nex-method`.

PCL makes a lot of effort to optimize some of this code away, by
specializing the case where CNM and NNM aren't used, or are only called
directly (in which case they can be inlined via `macrolet`), but it does
boil down to the same thing:

(call-next-method-body (cnm-args)
`(if .next-method.
(funcall (if (std-instance-p .next-method.)
(method-function .next-method.)
.next-method.) ; for early methods
(or ,cnm-args ,',method-args)
,',next-methods)
(error "No next method.")))
(next-method-p-body ()
`(not (null .next-method.))))

In ELisp, I used a quite simplistic approach, very similar to Closette,
but I made a different optimization (with no measurement to know whether
it was worth the effort) based on an ugly gross hack: basically the
"next method" is always a function (when there's no next method, it's
a function that calls `no-next-method`), so `call-next-method` can
directly call it without needing the `if` test.

The ugly gross hack comes up in `next-method-p` where we need to
distinguish the "functions that calls `no-next-method`" from the other
functions. We recognize those by making sure we build them from the
same place in the code, so all those closures share the same code which
makes it possible to recognize them more-or-less reliably by comparing
to a "sample" of that function (it all breaks down in cases like when we
re-evaluate the code that builds those closures, as happens during
development/debugging but it's worked well enough in practice).

So I'm curious to know if other Common Lisp implementation have made
similar optimizations, and hopefully found less hideous ways to do it.

Stefan

PS: For the curious, the ugly gross hack looks like the code below,
which is even more ugly and gross than strictly needed, because closure
we have to compare with the one that calls `no-next-method` is actually
stuffed within another wrapper which basically does (lambda (&rest args)
(apply FUN (or args original-args))):

(defconst cl--generic-nnm-sample (cl--generic-no-next-method-function t t))
(defconst cl--generic-cnm-sample
(funcall (cl--generic-build-combined-method
nil (list (cl--generic-make-method () () t #'identity)))))

(defun cl--generic-isnot-nnm-p (cnm)
"Return non-nil if CNM is the function that calls `cl-no-next-method'."
;; ¡Big Gross Ugly Hack!
;; `next-method-p' just sucks, we should let it die. But EIEIO did support
;; it, and some packages use it, so we need to support it.
(catch 'found
(cl-assert (function-equal cnm cl--generic-cnm-sample))
(if (byte-code-function-p cnm)
(let ((cnm-constants (aref cnm 2))
(sample-constants (aref cl--generic-cnm-sample 2)))
(dotimes (i (length sample-constants))
(when (function-equal (aref sample-constants i)
cl--generic-nnm-sample)
(throw 'found
(not (function-equal (aref cnm-constants i)
cl--generic-nnm-sample))))))
(cl-assert (eq 'closure (car-safe cl--generic-cnm-sample)))
(let ((cnm-env (cadr cnm)))
(dolist (vb (cadr cl--generic-cnm-sample))
(when (function-equal (cdr vb) cl--generic-nnm-sample)
(throw 'found
(not (function-equal (cdar cnm-env)
cl--generic-nnm-sample))))
(setq cnm-env (cdr cnm-env)))))
(error "Haven't found no-next-method-sample in cnm-sample")))

On 2022-01-01, Stefan Monnier <monnier@iro.umontreal.ca> wrote:
> Hi,
>
> I see both in Closette and in PCL that the implementation of
> `next-method-p` boils down to (taken from Closette):
>
> `(lambda (args next-emfun)
> (flet ((call-next-method (&rest cnm-args)
> (if (null next-emfun)
> (error "No next method for the~@
> generic function ~S."
> (method-generic-function ',method))
> (funcall next-emfun (or cnm-args args))))
> (next-method-p ()
> (not (null next-emfun))))
> (apply #'(lambda ,(kludge-arglist lambda-list)
> ,form)
> args))))))
>
> I'm curious if that same approach is used in all other implementations
> out there.

There has to be some function call-next-method bound somehow, and it
needs to know the next method from somewhere. That would seem to
constrain how it can work to more or less this sort of thing.

> I'm specifically curious about this choice to represent (at run-time)
> the "no next method" (NNM) case as nil, forcing an `if` test in
> `call-nex-method`.

Well, you need to be able to have a test to support next-method-p.

So suppose next-emfun is never null, such that it's a valid function
(which errors out if there is no next method).

Then next-method-p has to be able to know that it is that special
function. No problem, I suppose:

(next-method-p () (not (eq next-emfun) #'no-next-method-emfun))

That is going to backfire. If no-next-method-emfun is redefined,
simply by the containing module being reloaded, its EQ identity
will change. HOwever, it could be done like this:

(defun non-next-method-emfun () ...)

(defun non-next-method-emfunp (f) (not (eq f #'non-next-method-emfun)))

These functions sit in the same module. So if one is redefined, so is
the other.

I would still worry about some run-time mismatch. So that is to say,
some method dispatch is currently "live" and uses the old emfun, which
is dynamically redefined and so now the emfunp test doesn't recognize
it, having switched to the new one.

One way out is to have a secret argument to the emfun which it
recognizes and returns T or NIL.

(defun non-next-method-emfun (args)
(if (eq args 'sys:next-method-check)
nil ;; that's right, there is no next method
(error ...)))

Thus, we ask the function itself: are you the no-next-method
error function?

However, now all the method-dispatching wrappers have to be wrapped with
this test (and return T when args is sys:next-method-check), so I'm not
convinced we made things any better.

In TXR Lisp, I used a piece of somewhat like-minded trickery in the
implementation of delimited continuations.

If you pass the symbol sys:cont-poison to a continuation, it's a special
signal which means "please unwind the delimited continuation's stack
instead of resuming it".

Suppose our garbage collection supports some kinds of weak structures.

Imagine we have a "weak set" structure:

(defvar no-next-method-set (weak-set))

Then each time we redefine the no-next-method-emfun shim, we add it to
the set:

(defun no-next-method-emfun (args) ...)

(weak-set-add no-next-method-set #'no-next-method-emfun)

The redefinition of the function never takes place without adding the
new definition to the set, because they are adjacent top-level forms in
the same compiled file.

Then the no-next-method-p just does this:

(no-next-method-p () (weak-set-member-p no-next-method-set next-emfun))

At garbage collection time, the weak set will expunge all members which
are not reachable.

So with this we know whether the next-emfun is either the same function
as the current definition, or else a past definition (which is
necessarily still reachable, since that variable is referencing it, and
thus in the weak set).

I think the weak-set abstraction can be readily implemented in a Lisp
that has weak hash tables. The weak set members can simply be keys in in
a weak-key hash table, with T values.

> PCL makes a lot of effort to optimize some of this code away, by
> specializing the case where CNM and NNM aren't used, or are only called

That effort seems misplaced; eliminating unused flets is a pretty simple
optimization (and an important one, I'd expect Lisp compilers to have).

If a flet is not called, it can be deleted right at the abstract syntax
tree level. Like when you're generating code for flet, you check: does
this identifier have a use? If not, skip it. The use information can be
obtained even in a one-pass compiler by compiling the body first.

Maybe some important Lisps were missing that at the time PCL was
developed.

On 2022-01-02, Kaz Kylheku <480-992-1380@kylheku.com> wrote:
> That is going to backfire. If no-next-method-emfun is redefined,
> simply by the containing module being reloaded, its EQ identity
> will change. HOwever, it could be done like this:
>
> (defun non-next-method-emfun () ...)
>
> (defun non-next-method-emfunp (f) (not (eq f #'non-next-method-emfun)))
>
> These functions sit in the same module. So if one is redefined, so is
> the other.

I missed the obvious simplicity:

;; Defined once, never altered:
(defvar no-next-method-enfun (lambda (args) ...))

We just refer to that variable.

> I missed the obvious simplicity:
>
> ;; Defined once, never altered:
> (defvar no-next-method-enfun (lambda (args) ...))
>
> We just refer to that variable.

When we call `call-next-method` and there's no next method, it ends up
calling `no-next-method` with a set of arguments which depends on the
current method call (it includes the name of the generic function, and
the arguments passed to it), so it can be a constant function.
In practice you can make it so all those functions are instances that
all come from the same lambda in the source code, tho, which is how
ELisp's implementation detects that it is one of the "call
no-next-method function".

Stefan

> When we call `call-next-method` and there's no next method, it ends up
> calling `no-next-method` with a set of arguments which depends on the
> current method call (it includes the name of the generic function, and
> the arguments passed to it), so it can be a constant function.
^^^
cannot
Duh!

Stefan