description language classes & the Meta-Object Protocol

[jrose@Sun.COM (John Rose)]

[This is a message which I sent a week and a half ago to the commonloops
mailing list.  I have since learned that this is a more appropriate list
to mail such discussions to, so I'm reposting.  If you've already
seen this, sorry for the redundancy.  I've changed nothing in the message.
				-- John

Original header:
Date: Mon, 25 Jul 88 16:12:16 PDT
To: commonloops.pa@xerox.com]

I'm going to describe a way I'd like to use the Meta-Object Protocol.
Hopefully, readers of this list will either tell me why it's a
misuse, or assure me that the Meta-Object Protocol will support
what I have in mind.

Start with a description language L.  That is, terms in L denote
predicates over some universe U; they describe objects in U.
(You could also call L a pattern language.)  There is some efficient
Lisp function L-APPLY which applies an L-term to a U-object and returns
T or NIL, depending on whether the term describes the object.

There is one other property of L:  There is a Lisp function L-LESSP
which takes any two L-terms t1, t2 and compares them, returning T or NIL,
depending on whether t1 entails t2 for all U-objects.  This is
a partial order on the description language.  Think of it this
way:  Less specific terms are greater than more specific ones.

Finally, define *L-TOP* to be the L-term which is greater than
all other L-terms (the least specific element).

(It is possible and useful to make L into a lattice by adding Lisp
functions L-MEET and L-JOIN, but I don't think that is necessary for
this discussion.)

I'd like to define a Meta-Class L-CLASS which models L.  In particular,
each L-term would correspond to an L-CLASS.  An L-term's L-CLASS would
have as instances all U-objects which match the L-term.  Note that
an L-CLASS does not necessarily support MAKE-INSTANCE:  As befits
a description language, the L-CLASSes merely impose structure on
a pre-existing space of U-objects.

Methods arguments can be specialized with L-CLASS specializers;
such arguments are assumed to be U-objects, and the method
is applied only to arguments that match the specializer.
That is, the L-CLASS protocol wraps the method body with code
which uses L-APPLY to filter out U-objects which don't match
the specializer.  This is just like STANDARD-CLASS dispatching,
except that L-APPLY can interpret L-terms using any algorithm
whatsoever.

If a generic is applied to a U-object, there will in general
be several methods which apply; they must be ordered most
specific first.  The computation of this ordering is done
with the L-LESSP predicate.  This works much like STANDARD-CLASS
method ordering.  When the specializers of applicable methods
are not linearly ordered (this case corresponds to class multiple
inheritance) , the L-CLASS must specify some sort of linearization,
so that CALL-NEXT-METHOD will be useful.

In any case, when a U-object is handed to a generic function
with L-CLASS specializers, only methods with specializers
that correctly describe the U-object are invoked, and then
in a reasonable order determined by description specificity.

You know, object oriented languages supply two very distinct services
that are often confused:  Representation management, and argument
dispatching.  Abstract types can be built from concrete representations,
often drawn from a rich set of possibilities (e.g., C++).  Abstract
functions can be built, piece by piece, from methods, each applicable
to a limited set of arguments; the OOL supplies the glue logic which
makes sure that each method gets the right kinds of arguments.
The distinction between the two services is based on this observation:
It is not necessary that the set of representations be identical
with the set of dispatchable types.  (In practice, it's often useful
to tightly coordinate the two services, since the OOL system can
then optimize representations for fast dispatch.)

Description language classes supply the argument dispatch service
only.  (By contrast, facilities like DEFSTRUCT construct representations
without dispatch services.)

For concreteness, I'll give several examples of description languages
that could be usefully treated as meta-classes:

  * Common Lisp types
    The Common Lisp type system is a description language.
    L-APPLY is TYPEP, and L-LESSP is SUBTYPEP, although the
    SUBTYPEP relation is not as rich as the corresponding
    mathematical subtyping relation.

  * standard classes
    If you forget about slots and consing, you can treat standard
    classes as predicates over their objects.  This example is
    just a special case of the previous.

  * object identity
    The EQL specializers support a trivial description language,
    where all classes are singletons (except *L-TOP*, which is the type T).
    Here, L-APPLY is only EQL (apart from *L-TOP*) and so is L-LESSP.

  * Lisp structure patterns
    Someone from the functional programming community wanted to
    have specializers which were structure templates.  Often
    the pattern matching incorporates the binding of variables
    to matched substructures for later access.  This sort of thing
    is extremely useful.  (For example, Lisp compilers seem always
    to have some a destructuring case macro, with which they
    analyze program syntax.)

    Interestingly, L-LESSP is straightforward to define for
    destructuring patterns; it roughly consists of applying
    the second pattern to the first.

  * user-interface event patterns
    This is the application which I've been recently thinking about,
    which triggered this note.  User-interface modules often want to
    filter the events they see to some small set of "interesting"
    events.  This can be done with an event pattern.  Suppose a key
    event has three attributes: 1. key making the transition, 2. type of
    transition (e.g., up, down, click), and 3. modifier key state.
    Then an event pattern would specify a value for each attribute,
    or specify a wildcard of some sort.

    Clearly this is a description language.  (In fact, it is a
    product language, made from three languages, one for each
    attribute.)  It is easy to define L-APPLY and L-LESSP.

    If a module wanted to handle a class of events, it could define
    a method on an appropriate generic function, specialized to the
    desired event pattern.  The event-pattern meta-class would have
    the responsibility of building the glue logic to dispatch
    incoming events to the correct handler.  It's good to centralize
    this logic, because it can then be optimized more readily,
    and redundant tests eliminated.

    CLOS double dispatch would help here too:  Event handlers could be
    specialized both to consumer-object mixins and event types.

  * string regular expressions
    The theory of regular languages is well understood, and regular
    expressions are useful in a wide variety of settings.  A regular
    expression meta-class could be used to define complex string handling
    functions in a modular fashion.  Regular languages can be compared
    for specificity, so an L-LESSP predicate can be defined.  Also,
    efficient methods are known for matching several regular
    expressions at once to a single string; the meta-class would
    use these methods to build efficient dispatch ("glue") logic,
    as in the previous example.

  * knowledge base queries
    Pick your favorite database query language.  It certainly supports
    an L-APPLY operation, and probably also supports an L-LESSP.
    Now, with the right L-CLASS, you can define generic functions over
    database entries.  (It may be more useful to manipulate __sets__
    of entries, so U would then be a power set of some sort.
    This does not hinder the applicability of CLOS.)

I hope I have shown that (1) description languages are common and
useful, that (2) a general class of description languages are
amenable to treatment within the CLOS generic function framework,
and that (3) descriptions are very useful as defmethod
specializers.  The conclusion is that the designers of the
Meta-Object protocol should be sure to provide for arbitrary
description languages (of the L-APPLY/L-LESSP sort).

Finally, here are some smaller open questions about description
language classes, along with some possible answers:

  * How should the L-CLASS specify a linearization of a partially
    ordered set of applicable methods?

    [It is sometimes useful to signal an error if there is not a linear
    ordering available.  This could the default, with a hook for other
    more permissive behavior.]

  * What if the L-LESSP relation is not always effectively computable?
    (E.g., LISP:SUBTYPEP gives up sometimes.)

    [Allow the L-LESSP relation to give up, and treat this outcome like
    incomparability.  It should be possible to signal an error here,
    while still doing something permissive on true incomparability.]

  * If the L-term has "wildcards" in it, how should the L-CLASS mediate
    the binding of the corresponding U-object subparts to names for
    use in method bodies?

    [I believe the current protocol (e.g., DEFINE-METHOD-COMBINATION)
    provides enough hooks for this.  The hook which asks a meta-class
    for dispatch code should also accept LET-bindings, which would
    be constructed along with the dispatch code, and wrapped around
    the affected method body.]

  * What sort of syntax should L-CLASS specializers have?

    [The (EQL ...) syntax should be extended, I think.  The basic
    idea is that EQL is a meta-class name, and the arguments to
    it are handed to the meta-class constructor, which then
    builds the appropriate class object.  This is probably already
    the intention of the CLOS designers, but I want to affirm
    that choice.]

Let me close with a suggestive example:

	(DEFMETHOD EVAL ((X (FORM `(,F . ,A))))
	  (APPLY (EVAL `#',F) (MAPCAR #'EVAL A)))

	(DEFMETHOD EVAL ((X (FORM `(IF ,P ,A ,B))))
	  (IF (EVAL P) (EVAL A) (EVAL B)))

This example uses a hypthetical description language called FORM,
whose terms are backquoted constructors, interpreted in reverse.
(Or, if you like, declaratively as opposed to imperatively.)
Note that the specificity ordering ensures that IF forms will
not get passed to the first method, even though they match
its specializer.

				-- John