Christophe Weblog Wiki Code Publications Music

Some time ago (call it half a decade or so), Jim Newton of Cadence and I did some work on extensible specializers: essentially coming up with a proof-of-concept protocol to allow users to define their own specializers with their own applicability and ordering semantics. That's a little bit vague; the concrete example we used in the writeup was a code walker which could warn about the use of unbound variables (and the non-use of bindings), and which implemented its handling of special forms with code of the form:

(defmethod walk ((expr (cons (eql 'quote))) env call-stack)
(defmethod walk ((var symbol) env call-stack)
  (let ((binding (find-binding env var)))
    (if binding
        (setf (used binding) t)
        (format t "~&unbound: ~A: ~A~%" var call-stack))))
(defmethod walk ((form (cons (eql 'lambda))) env call-stack)
  (destructuring-bind (lambda lambda-list &rest body) form
    (let* ((bindings (derive-bindings-from-ll lambda-list))
           (env* (make-env bindings env)))
      (dolist (form body)
        (walk form env* (cons form call-stack)))
      (dolist (binding bindings)
        (unless (used (cdr binding))
          (format t "~&unused: ~A: ~A~%" (car binding) call-stack))))))

The idea here is that it's possible to implement support in the walker for extra special forms in a modular way; while this doesn't matter very much in Common Lisp (which, famously, is not dead, just smells funny), in other languages which have made other tradeoffs in the volatility/extensibility space. And when I say “very much” I mean it: even SBCL allows extra special forms to be loaded at runtime; the sb-cltl2 module includes an implementation of compiler-let, which requires its own special handling in the codewalker which is used in the implementation of CLOS.

So modularity and extensibility is required in a code walker, even in Common Lisp implementations; in Cadence Skill++ it might even be generally useful (I don't know). In SBCL, the extensibility is provided using an explicit definer form; sb-cltl2 does

(defun walk-compiler-let (form context env)
  #1=#<implementation elided>)
(sb-walker::define-walker-template compiler-let walk-compiler-let)

and that's not substantially different from

(defmethod sb-walker:walk ((form (cons (eql 'compiler-let))) context env)

So far, so unexpected, for Lisp language extensions at least: of course the obvious test for a language extension is how many lines of code it can save when implementing another language extension. Where this might become interesting (and this, dear lazyweb, is where you come in) is if this kind of extension is relevant in application domains. Ideally, then, I'm looking for real-life examples of patterns of selecting ‘methods’ (they don't have to be expressed as Lisp methods, just distinct functions) based on attributes of objects, not just the objects' classes. The walker above satisfies these criteria: the objects under consideration are all of type symbol or cons, but the dispatch partly happens based on the car of the cons – but are there examples with less of the meta nature about them?

(I do have at least one example, which I will keep to myself for a little while: I will return to this in a future post, but for now I am interested in whether there's a variety of such things, and whether the generalization of specializer metaobjects is capable of handling cases I haven't thought of yet. Bonus points if the application requires multiple dispatch and/or non-standard method combination.)