apply-generic-functionIn my attempt to move towards MOPing up my own cl-kitten, I am going through all of the art of the metaobject protocol as planned. Remember that at his OOPSLA keynote in 1997 The Computer Revolution Hasnât Happened Yet, Kay gives The Art of the Metaobject Protocol as the most important modern book. Without belabouring this context, let us say that I have high aspirations for our cl-kitten (kitten).
Anyway, to take AMOP seriously, I am going through its exercises here seriously. I am using common lisp, emacs, eev and slime, but you can probably get where Iâm coming from even if youâre not.
The gist is to get to know the fundamentals of ANSI CLâs object orientation inside and out, where the inside is metacircularly, basically an object oriented program in lisp. Read what Simon Dobson says.
I noticed that Simon Dobson (mastodon) wrote about the art of the metaobject protocol about a year ago, though I needed to at least finish chapter one and its one exercise before reading what Simon said. I am very interested in Simonâs annotated lisp bibliography.
Exercise 1.1 The Closette implementation of generic function invocation offers numerous possibilities for memoizing meta-level computations. Modify
apply-generic-functionso that it memoizes previous results ofcompute-applicable-methods-using-classes. What are the conditions under which your memoized values remain valid?
apply-generic-function(defun apply-generic-function (gf args)
(let ((applicable-methods
(compute-applicable-methods-using-classes
gf (mapcar #'class-of (required-portion gf args)))))
(if (null applicable-methods)
(error "No matching method for the ~@
generic function ~S,~@
when called with arguments ~:S." gf args)
(apply-methods gf args applicable-methods))))
compute-applicable-methods-using-classes(defun compute-applicable-methods-using-classes (gf required-classes)
(sort
(copy-list
(remove-if-not #'(lambda (method)
(every #'subclassp
required-classes
(method-specializers method)))
(generic-function-methods gf)))
#'(lambda (m1 m2)
(method-more-specific-p m1 m2 required-classes))))
One of closetteâs simplifications is that method redefinition is defined to be an error, so we only need to check that the required classes are the same. The problem is to rewrite apply-generic-function with memoization, not to modify the classes. I guess that sort could be avoided.
I lexically closed a hash table keyed by generics, containing hash tables using EQUAL keyed by lists of classes.
(let ((prev-appl-generics (make-hash-table)))
(flet ((get-or-create (gf required-classes)
(let* ((that-gf (or (gethash gf prev-appl-generics)
(setf (gethash gf prev-appl-generics)
(make-hash-table :test 'equal))))
(those-methods
(or (gethash required-classes that-gf)
(setf (gethash required-classes that-gf)
(progn
(print "memoizing..~%")
(compute-applicable-methods-using-classes
gf required-classes))))))
(values those-methods))))
(defun apply-generic-function (gf args)
(let ((applicable-methods
(get-or-create gf (mapcar #'class-of (required-portion gf args)))))
(if (null applicable-methods)
(error "No matching method for the ~@
generic function ~S,~@
when called with arguments ~:S." gf args)
(apply-methods gf args applicable-methods))))
(values
(apply-generic-function 'foo '(bar baz))
(apply-generic-function 'foo '(a b c))
(apply-generic-function 'foo '(d e f))
(apply-generic-function 'foo '(1 2 3))
)))
I faked out the actual infrastructure with macros that just tag lists with symbols.
(macrolet ((required-portion (gf args) `(values (cons 'required ,args)))
(apply-methods (gf args applicable-methods)
`(values (cons 'applied ,applicable-methods)))
(compute-applicable-methods-using-classes (gf required-classes)
`(values (cons 'required ,required-classes))))
(let ((prev-appl-generics (make-hash-table)))
(flet ((get-or-create (gf required-classes)
(let* ((that-gf (or (gethash gf prev-appl-generics)
(setf (gethash gf prev-appl-generics)
(make-hash-table :test 'equal))))
(those-methods
(or (gethash required-classes that-gf)
(setf (gethash required-classes that-gf)
(progn
(print "memoizing..~%")
(compute-applicable-methods-using-classes
gf required-classes))))))
(values those-methods))))
(defun apply-generic-function (gf args)
(let ((applicable-methods
(get-or-create gf (mapcar #'class-of (required-portion gf args)))))
(if (null applicable-methods)
(error "No matching method for the ~@
generic function ~S,~@
when called with arguments ~:S." gf args)
(apply-methods gf args applicable-methods))))
(values
(apply-generic-function 'foo (list 'bar 'baz))
(apply-generic-function 'foo (list 'a 'b 'c))
(apply-generic-function 'foo (list 'd 'e 'f))
(apply-generic-function 'bar (list 'd 'e 'f))
(apply-generic-function 'foo (list 1 2 3))
))))
As we might expect, output
"memoizing..~%"
"memoizing..~%"
"memoizing..~%"
"memoizing..~%"
(APPLIED REQUIRED #<BUILT-IN-CLASS COMMON-LISP:SYMBOL>
#<BUILT-IN-CLASS COMMON-LISP:SYMBOL> #<BUILT-IN-CLASS COMMON-LISP:SYMBOL>)
(APPLIED REQUIRED #<BUILT-IN-CLASS COMMON-LISP:SYMBOL>
#<BUILT-IN-CLASS COMMON-LISP:SYMBOL> #<BUILT-IN-CLASS COMMON-LISP:SYMBOL>
#<BUILT-IN-CLASS COMMON-LISP:SYMBOL>)
(APPLIED REQUIRED #<BUILT-IN-CLASS COMMON-LISP:SYMBOL>
#<BUILT-IN-CLASS COMMON-LISP:SYMBOL> #<BUILT-IN-CLASS COMMON-LISP:SYMBOL>
#<BUILT-IN-CLASS COMMON-LISP:SYMBOL>)
(APPLIED REQUIRED #<BUILT-IN-CLASS COMMON-LISP:SYMBOL>
#<BUILT-IN-CLASS COMMON-LISP:SYMBOL> #<BUILT-IN-CLASS COMMON-LISP:SYMBOL>
#<BUILT-IN-CLASS COMMON-LISP:SYMBOL>)
(APPLIED REQUIRED #<BUILT-IN-CLASS COMMON-LISP:SYMBOL>
#<BUILT-IN-CLASS COMMON-LISP:FIXNUM> #<BUILT-IN-CLASS COMMON-LISP:FIXNUM>
#<BUILT-IN-CLASS COMMON-LISP:FIXNUM>)
There were three different method signatures for the five returns:
(symbol symbol symbol) for my symbol-tagged (bar baz) for foo(symbol symbol symbol symbol) for the tagged (a b c) and (d e f) for foobar (d e f), the class list is memoized separately(symbol fixnum fixnum fixnum) for foo for (1 2 3)Just memoizing in hash tables is the usual technique I think. Closette has already used hash table lookups in its infrastructure. This âcompiler optimizationâ seems kind of hidden because I thought we should not modify the protocolâs classes and generics.
The conditions under which my memoization remains valid is for generics to be EQ, and list of classes for the generic specialisations to be EQUAL. Closette does not allow redefinitions.
To be fair, I just faked the real internals using macrolet to just pass on tagged arguement lists so it has not been seen TRULY WORKING.
The first exercise was a simple request for memoization, and I think I fulfilled it, but let everyone know what you did instead on the Mastodon thread please.
Please do share common lisp bits like this whereever and whenever occurs to you, like Dobsonâs writing. Ignorance of lisp is a particularly pressing problem in the world of computing (also called, the world).
screwlisp proposes kittens