[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
description language classes & the Meta-Object Protocol
[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.
Date: Mon, 25 Jul 88 16:12:16 PDT
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
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
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
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