[no subject]

[Bobrow.pa@Xerox.ARPA]

Message-Id: <850913-154150-2894@Xerox>

Scott,

Here are answers to the questions you asked about CommonLoops.
Your questions are in ""; our answers are in [[]].


"As I understand it, there is a new function-like object called a
discriminator that binds together a family of methods that all share the
same selector.  This discriminator does everything that a regular
function object does -- you can pass it around, funcall it or apply it
to arguments, lexically bind it to some selector symbol, globally bind
it by stuffing it into the selector symbol's function cell, and so on.
Even if this discriminator was defined by a bunch of (defmethod foo ...)
calls, it has no permanent tie to the symbol FOO.  You could move all of
the behaviors to BAR by (setf (symbol-function 'bar) (symbol-function
'foo)).  An anonymous discriminator can be created by
MAKE-DISCRIMINATOR, and additional methods can be added to the bundle by
SPECIALIZE.  A method can be removed from the bundle by REMOVE-METHOD.
There probably also should be a way to examine the constituent methods
of a discriminator -- this does not seem to be included in the
proposal."

[[There are two choices.  Either there is a new kind of funcallable
object in the system, which is of class discriminator, or one can use an
ordinary function in the symbol-cell, and provide a way of obtaining a
discriminator object associated with that function.  We have not seen
any need for it to be a closure, since there's little or no state.  The
function is composed from the definitions of the methods.  You are right
(and we use) "a way to examine the constituent methods of a
discriminator".  This is a method of the discriminator object.

The code for any method is wrapped with a compiler-let which points to
the method object, so that the run-super special form can know its
identity, and the identity of the discriminator.

Yes, the caching is so that, once you get into a discriminator with
specific classes, it doesn't have to chase up the type hierarchy. (The
chase isn't so complex, because each class contains a linearized list of
its superclasses, so you can use a simple iteration.) The cache is
global, and at any hint of trouble, the simplest thing to do is flush
the whole thing. Rebuilding cache entries (cache miss) isn't very
expensive. Yes, hashing on the discriminator itself is better than
hashing on the selector.

In the case of "all classic methods", i.e., all methods only
discriminate on the first argument, a cache-hit costs at most an extra
funcall and a type test. The type test is balanced off the ability to
assume the type throughout the rest of the definition, i.e, (defmethod
((x fixnum) ...) ...) can presume (declare (type fixnum x)). 

Presumably, but in an implementation-specific way, the second function
call can be eliminated. For example, in a typical implementation of Lisp
on stock hardware, the entry into the real method can be done by a jump
rather than a call, if calls are more expensive. In any case, the callee
(the implementation of the method) can't be dynamically changed or
relocated without the caller (the implementation of the discriminator)
knowing about it. Microcoded implementations have other mechanisms-- for
example, the type lookup and dispatch can be done entirely within the
original function call, if the call to the discriminator is detected by
the call microcode.

There's another option, which also reduces the cost of a cache-hit, but
uses a single-entry-cache-per-callee rather than a
many-entry-global-cache, that is simple and likely to be quite
effective. That is, for each discriminator, there is a single cache
element which knows the (exact) class that the discriminator was called
with, and the method that was invoked. Checking the cache involves
computing class-of, eq.

Where's the cache? The simplest place to put it is in the "function
definition cell", that is, the definition of the selector jumps right
into the "last" method, which begins with a simple preamble that asks,
"am I really the right method?" If not, it replaces itself with the
right definition and tries again. Under this scheme, the only additional
cost for a message pass (in the cache-hit case) is the type check!

Its likely that given (foo (the widget x)) that one might eliminate even
the initial function call. This is especially important for the
generated accessor methods, which must be given optimizers that "know"
how to compute them when the type of the argument is known. Better than
a user supplied declaration, the knowledge can be inferred directly if
you're in a method, e.g.

(defmethod paint ((x widget))
   ... (shape x) ...)

if shape is a slot of widget, it is fairly straightforward to infer that
it can be done with a direct access, especially if widget is a
"structure" (rather than, for example, a loops-class).

 

"The whole meta-class business sounds like a win, but without a much
more detailed description of what is controlled by the meta-class and
how
this is specified, it is impossible to tell whether this is going to
fly.  I can't even formulate the proper questions in this area until the
system is spelled out a bit more."

[[This is one of the major areas we are working on.  
Metaclasses at least have protocols for:
1) Instance creation
2) slot access 
     slow lookup and flexibility for various fast lookup schemes.
3) Computation of the class-precedence list
4) parsing of the actual defstruct (needless to say)
5) Determining what to do about inheriting from classes with
incompatible or at least different metaclasses.
]]

"If a new method is added to the system, is it necessary to go back and
recompile every function that calls the selector function in question?"

[[No, you never have to recompile callers! When you add a new method,
you have to clear any method caches which might be affected (we just
clear the global method-cache), and recompute (recompile) the
discriminator. Redefining an old method may have to do some of these but
not all -- it depends on how much the implementation knows about the
method other than how to get to it.]]

"This issue is closely related to the question of whether it is
permitted
to create type-restricted methods for the built-in functions in Common
Lisp.  The CommonLoops proposal dances around this issue and does not
seem to take a clear stand."

[[There's not a clear place to stand. Rather, there's a very narrow path
to tread between power and impact on current implementations. From the
point of view of simplifying the life of programmer's, its simplest to
make it so that you could specialize *any* built-in function. From the
point of view of the implementor, specializing built-in functions that
are declared inline can't work. CommonLoops flies and is useful taking
the most conservative stand -- i.e., no functions in Guy Steele's Silver
Book are specializable. A more aggressive stand can be taken later,
since it isn't incompatible at all.]]

"It is unclear to me how multiple meta-classes can coexist peacefully.
What is the proper specificity ranking between two methods with selector
FOO, when one has its first argument restricted to instances of class
BAR and the other has its first argument restricted to instances of
flavor BLETCH?  (I assume that there can not be both a class BAR and a
flavor BAR.)  Can a method have one argument that is a class-instance
and another that is a flavor-instance?  Which meta-class controls what
in such a case?"

[[The class name space itself is universal. (Class names are symbols, so
you can use packages, but one symbol denotes one and only one class.)
instances of "flavor-class" and "loops-class" aren't radically
different. The "include" relation is used for determining class
precidence. There's a method which determines the relation between two
classes, which returns one of 5 values

1) The classes are the same (EQ)
2) BAR includes BLETCH
3) BLETCH includes BAR
4) BAR and BLETCH are known disjoint (e.g., they're disjoint and it is
illegal to :include both simultaneously)
5) none of the above

This method can be specialized to handle special cases, e.g., if you
want to say that flavors can't mix in with classes, you can do it by
defining this as a method on flavors.

The only things the metaclass determines as far as method precedence
goes is what the ordered list of superclasses is. Thus, you can easily
have two methods, with selector FOO, when one has its first arg
restricted to BAR and the other has its first argument restricted to
instances of the flavor BLETCH. 

The current proposal requires explicit specification of the class of a
method (in the defmethod form).  We are considering an extension in
which the default class of the method is  determined by the
specification of the arguments.  Perhaps we should limit this to a class
specification of the first argument.  That is, defining BLETCH as a
flavor only says that methods which specify BLETCH are flavor-methods
(and have the implicit "with" and other kinds of method-combination
behavior) when BLETCH is the first-argument discriminator. This weighs
flavors-compatibility heavily toward those cases that actually occur in
flavors. ]]

"In the list of built-in Common Lisp types that are disallowed as method
type specifiers one finds INTEGER, yet INTEGER is used in several of the
examples.  Perhaps it is only INTEGER with additional range arguments
that is disallowed?" 

[[Yes, it was only the range-specifiers that were disallowed.]]

"The extension listed in II.A, individual specifiers, seems like a good
one.  However, I wonder if it is really advisable to twist up the
usual left-to-right specificity order in this one case.  Are indivduals
really so much more specific that they warrant this special treatment?
Some motivation for this odd exception would be useful."

[[We looked at a lot of examples. Division, for example, falls out
nicely, with divide-by-zero being a single special case. A lot of other
people have had troubles with that too.]]

"I don't understand the "annotated values" business, though I see
roughly what you are trying to do.  Some examples are critically needed
here."

[[Yes. This is an attempt to show how to do Loops-style active values,
as well as some of the more complex operations found in representation
systems such as range restrictions, when-filled methods and the like.
Its meant more as a hook for people who want to layer AI toolkits on top
of CommonLoops, and we're hoping to get more of them participating in
this area.]]

"In section II.B, I suppose that the variable-reference format is
necessary for emulating systems like flavors, but I wonder if the hairy
long form is really necessary.  If you're in a case this complex,
shouldn't you revert to the unambiguous function-call syntax rather than
resorting to a macro that hacks print names?"

[[This is a matter of religion, and we propose to have many churches --
we have different worshippers within Xerox.]]

"For the method-slots business, I don't even see what you are trying to
do.  Totally mysterious.  There is an example there, but it's awfully
hard to follow"

[[The idea is to capture the behavior that we already use in
Interlisp-D, and I spy in the Spice sources too. Its real common in most
operating systems. How do you TYO this stream? Well, you fetch the
TYO-FUNCTION of the stream and FUNCALL it. Wouldn't it be nice to have
it work the same way, but say it nicer? 

That's been the spirit of a lot of what CommonLoops is trying to do--
take current programming idioms and make them pretty. Thus, instead of
(taken from SEQ.SLISP):

(defun elt (sequence index)
  "Returns the element of SEQUENCE specified by INDEX."
  (if (listp sequence)
      (if (< index 0)
	  (error "~S: index too small." index)
	  (do ((count index (1- count)))
	      ((= count 0) (car sequence))
	    (if (atom sequence)
		(error "~S: index too large." index)
		(setq sequence (cdr sequence)))))
      (aref sequence index)))

you write

(defmethod elt ((sequence vector) index)
	(aref sequence index)

(defmethod elt ((sequence list) index)
	(if (< index 0)
	  (error "~S: index too small." index)
	  (do ((count index (1- count)))
	      ((= count 0) (car sequence))
	    (if (atom sequence)
		(error "~S: index too large." index)
		(setq sequence (cdr sequence))))


and get rid of all those seq-dispatch that hair up your code and make it
hard to read and modify. Maybe if you add a new method for a built-in
function you'll slow something down, but that's true if you redefine a
built-in function too. ]]

[[Regarding your questions about MLET and MLABELS, several people were
confused by the section in the paper.  We plan to re-write that section
soon and will send it out.]]


     ----- End Forwarded Messages -----