Eliminating superclass lookup in the VM (and dynamic composition of behavior)

Nathanael Schärli n.schaerli at gmx.net
Wed Dec 11 21:37:18 UTC 2002


Stephen

> While doing this, a thought has occurred to me: does it even 
> make sense to have the VM traverse a superclass chain when 
> looking for a method? Why not just have the VM just look at 
> the single method dictionary directly attached to a behavior 
> and manage the visibility, etc of methods in Smalltalk?

Your observation is good. This is in fact precisely what would happen if
you took our current trait prototype implementation and only used trait
composition instead of inheritance: each class would then have a method
dictionary containing a key for all the method it understands and this
key would be associated to the appropriate method which can be shared
between multiple classes.

> I guess what I'm really after is the ability to have more 
> control over the manner in which behavior is composed.

That is exactly what I am after, too. I truly believe that there are
much better (static and dynamic) composition models than inheritance. I
think that traits are just a first *little* step in this direction. In
fact, we have many more exciting ideas in mind and we are just about to
start working on some of them. (Don't worry, in parallel I'm going to
make sure that the current Traits implementation can be released soon
:). 

However, I'm less interested in the details of how to organize and
lookup the methods. In my eyes, this is finally just an implementation
issue. Much more important is to have the right model at a conceptual
level. In my eyes, the conceptual side of a model is what finally
decides whether it is going to be successful in practice. 

Thus, the key thing is to come up with a model that makes it "easy and
straightforward" for a programmer to transform his ideas into a program
and that causes these programs to have "good" properties. In case of a
compositional model, this means that it should give a programmer
powerful and highlevel means of composition, but it should also make
sure that the resulting code is well understandable, easy to maintain,
stable with respect to changes, etc.

Once you have a conceptual model with nice properties, the
implementation is just a "technical exercise", and it can of course be
done in different ways. Typically you encounter the same
space-performance trade-off as in nearly all the other kind of
implementations. As an example, just consider traits:

a) In my current prototype implementation, traits are implemented by
simply creating new entries in the method dictionaries of the classes
that use th traits and associate them to the trait methods. Since traits
mainly used to organize the behavior within a class and not so much to
replace inheritance, this implemenatation is not too bad because the
method dictioneries usually don't get too big, and so there is not too
much overhead by storing the extra-associations.

b) Alternatively, traits could be implemented by patching the VM lookup
algorithm so that it actually searches all the traits that are
associated to a class in the same way as it now searches the class
chains. Like that, we would not have to create these extra associations
in the method dictionaries. instead, we only need the VM to know what
traits are used by each class. 

In our prototype implementation, we decided for implementation a),
because it avoids patching the VM lookup and it is surely the fastest.
However, if we would see that traits are used so often that the
additional space of the associations in the method dictionary would be
too much of a trade-off, we could of course choose implementation b)
instead. As I said above, this is finally just a question of
implementation! The conceptual model (the way people program, etc.) is
not at all affected by that. In fact, they don't even have to know about
that! They only thing the avarage programmer wants to know is the
conceptual side of the model: How can I program? How can I compose
traits? How can I resolve conflicts? etc.


> One issue with it would be super sends.

Yes, super-sends would be an issue. But since super is statically bound
in single-inheritance it can actually be solved rather easily. Just make
sure that every method that uses super-sends knows what method (or what
selector) it actually calls to. 

In general, there is another down-side of this approach you should take
into account. When you store all the selectors that are understood by a
class in a method dictionary, this means that the VM has less work when
invoking a method, but it also means that you have to do this work when
a programmer is modifying the system. (Instead of doing some work at
runtime, you need to do it "at compile time").

As an exmaple, consider what would happen if you change one method in
the class Object. In fact, you need to make sure that you update all the
subclasses where this method is not overidden! In an exreme case, this
can be quite a lot of work! In particular, it can get a bit nasty if
super-calls are involved. Then, you also have to make sure that all the
methods that refer to the changed method via super are now referring to
the new method. 

One way to make this easier is by never pointing to methods directly,
but only indirectky via a "method-wrapper". Whenever you update a
method, you then just put the new method in the old wrapper and all the
pointers to the wrapper are still correct. However, this again
intrdoduces a performance and space penalty.


Well, as in most other implementation questions, there are many slightly
different techniques that all have specific characteristic in the
"performance-space-simplicity" space. It would be possible to reason
about them forever, but I think I should better go to bed now ;)

Cheers,
Nathanael



> -----Original Message-----
> From: squeak-dev-admin at lists.squeakfoundation.org 
> [mailto:squeak-dev-admin at lists.squeakfoundation.org] On 
> Behalf Of Stephen Pair
> Sent: Wednesday, December 11, 2002 4:41 PM
> To: squeak-dev at lists.squeakfoundation.org
> Subject: Eliminating superclass lookup in the VM (and dynamic 
> composition of behavior)
> 
> 
> I've been messing with the idea of traits recently (I need 
> them for adding transactional behavior to arbitrary classes 
> in the system).  To satisfy my immediates needs, I've built a 
> "mini-traits" capability (to hold me over until Andrew and 
> Nathanael gets their stuff out).  Anyway, I've found myself 
> managing the visibility of trait methods in my Smalltalk code.
> 
> While doing this, a thought has occurred to me: does it even 
> make sense to have the VM traverse a superclass chain when 
> looking for a method? Why not just have the VM just look at 
> the single method dictionary directly attached to a behavior 
> and manage the visibility, etc of methods in Smalltalk?  
> Primitive method dictionaries (those designed for consumption 
> by the VM) would be nothing more than flattened views of the 
> methods that are applicable to a given class.  Methods that 
> access instance variables should be the only ones that might 
> need a physically different compiled form.  This would also 
> have a side benefit of allowing subclasses to have a 
> different instance variable orderings than their 
> superclasses...which in turn might facilitate more creative 
> ways of composing behavior.
> 
> I mean heck; we even have places in the Smalltalk code where 
> we have to flush the VM method cache...these places would be 
> exactly where we would want to reconstruct the primitive 
> method dictionaries.
> 
> I've found that I'm managing the visibility of trait methods 
> by controlling what happens when adding an removing methods, 
> etc.  It occurred to me that if I can do this with relative 
> ease with traits, why not do it with normal inheritance?
> 
> Has this been done before?
> 
> - Stephen
> 
> 




More information about the Squeak-dev mailing list