Demystifying "most Smalltalk’s don't directly support multiple inheritance"

List,

haven't you heard that Smalltalk and Squeak do not directly support  
multiple inheritance, time and again? But that Perl, Python and Ruby do  
(to some extent)?
- http://www.google.com/search?q=python+ruby+multiple+inheritance

Well, that is not the case for Smalltalk since the time that VMs are  
implemented by using the specs of the Blue Book.

I have attached a small .st file which demonstrates that the *unchanged*  
VM *must* support multiple inheritance (for message sends), or else it  
won't work properly. It's a matter of view on what the VM does for you :-D

With the exception of support code for exceptions [pun intended] the  
attached examples work on VMs which implement the super send from the Blue  
Book.

The first example demonstrates that multiple inheritance works; in this  
example it is also checked that the requesting method qualifies (that the  
instances qualify is checked at fileIn time).

The second example does a message tally and shows that there is less than  
50% overhead when possible walkbacks are guarded at every multiple  
inheritance message send.

The third example employs the existing method cache of the VM (the  
original Squeak VM) for multiple inheritance message sends and thus  
minimizes the overhead to less than 5% (and the demo is written in .st  
code :-)

Again, this all exists *unchanged* for decades. It only had to be brought  
to the surface?

-------

I would be very interested to see if my examples run on other platforms  
and VMs, please post your experience. Thank you.

It'd be equally interesting if the approach had been used before.

/Klaus

Klaus D. Witzel puso en su mail :


DoIt: " MessageTally spyOn: [ | aCupWith |
        aCupWith := CaffeeWithMilk newLatteMacchiato.
        10000 timesRepeat: [aCupWith veryMuchSugar]] "

Here I got on Mac

 1267 tallies, 1273 msec.

**Tree**
99.8% {1270ms} CaffeeWithMilk>>veryMuchSugar
  47.0% {598ms} CaffeeWithMilk>>DoIt
    |46.7% {594ms} ProcessorScheduler>>nextReadyProcess
    |  22.7% {289ms} LinkedList>>isEmpty
    |  22.6% {288ms} Array(SequenceableCollection)>>reverseDo:
  26.8% {341ms} CaffeeWithMilk(Object)>>doesNotUnderstand:
    |12.2% {155ms} MessageNotUnderstood(Exception)>>signal
    |  |11.8% {150ms} MethodContext(ContextPart)>>handleSignal:
    |  |  7.5% {95ms} BlockContext>>valueWithPossibleArgs:
    |11.5% {146ms} MessageNotUnderstood>>message:
  22.3% {284ms} CaffeeWithMilk(SuperclassX)>>internalSwitchSenderToParent:
    |17.7% {225ms} UndefinedObject(Object)>>->
    |  |16.0% {204ms} Association>>key:value:
    |2.7% {34ms} CompiledMethod>>numLiterals
  3.1% {39ms} BlockContext>>onDNU:do:

**Leaves**
22.7% {289ms} LinkedList>>isEmpty
22.6% {288ms} Array(SequenceableCollection)>>reverseDo:
16.0% {204ms} Association>>key:value:
11.5% {146ms} MessageNotUnderstood>>message:
9.0% {115ms} BlockContext>>valueWithPossibleArgs:

**Memory**
    old            +0 bytes
    young        -25,012 bytes
    used        -25,012 bytes
    free        +25,012 bytes

**GCs**
    full            0 totalling 0ms (0.0% uptime)
    incr        550 totalling 356ms (28.0% uptime), avg 1.0ms
    tenures        0
    root table    0 overflows


But your code deserve more deep study, and I thanks for it.

Edgar



       
       
               
___________________________________________________________
1GB gratis, Antivirus y Antispam
Correo Yahoo!, el mejor correo web del mundo
http://correo.yahoo.com.ar 

Hi Edgar,

on Fri, 23 Jun 2006 01:14:20 +0200, you wrote:
That output is from a non 3.9 image. On a 3.9 image you would see that the  
debugger benefits from the implementation of traits, it has better means  
for finding out which class and selector a method is actually used at  
run-time. Here's the difference:

- 1132 tallies, 1132 msec.

**Tree**
97.9% {1108ms} CaffeeWithMilk>>veryMuchSugar
   52.9% {599ms} CaffeeWithMilk(SugarService)>>sugar
     |52.7% {597ms} ProcessorScheduler>>nextReadyProcess
>
> But your code deserve more deep study, and I thanks for it.

You are welcome :)

/Klaus

Klaus D. Witzel puso en su mail :

> That output is from a non 3.9 image. On a 3.9 image you would see that the
> debugger benefits from the implementation of traits, it has better means
> for finding out which class and selector a method is actually used at
> run-time. Here's the difference:

Karl, here is the same on new 7035.
I have a question now.
Could be possible have something like your exercise on non Traits image ?
What is needed on image if VM what follows Blue Book have this unknown (to
me) power ?
Very, very thanks

Edgar


 - 757 tallies, 764 msec.

**Tree**
99.7% {762ms} CaffeeWithMilk>>veryMuchSugar
  64.2% {490ms} CaffeeWithMilk(SugarService)>>sugar
    |63.5% {485ms} ProcessorScheduler>>nextReadyProcess
    |  32.0% {244ms} LinkedList>>isEmpty
    |  29.2% {223ms} Array(SequenceableCollection)>>reverseDo:
  18.8% {144ms} CaffeeWithMilk(Object)>>doesNotUnderstand:
    |14.5% {111ms} MessageNotUnderstood(Exception)>>signal
    |  |13.1% {100ms} MethodContext(ContextPart)>>handleSignal:
    |  |  4.1% {31ms} MethodContext>>tempAt:
    |  |  2.8% {21ms} MessageNotUnderstood class(Exception class)>>handles:
    |  |  2.4% {18ms} BlockContext>>ensure:
    |  |    2.1% {16ms} primitives
    |2.5% {19ms} primitives
  9.8% {75ms} CaffeeWithMilk(SuperclassX)>>internalSwitchSenderToParent:
    |2.8% {21ms} CompiledMethod>>numLiterals
    |2.2% {17ms} UndefinedObject(Object)>>->
    |2.2% {17ms} primitives
  5.5% {42ms} BlockContext>>onDNU:do:

**Leaves**
32.2% {246ms} LinkedList>>isEmpty
29.2% {223ms} Array(SequenceableCollection)>>reverseDo:
4.1% {31ms} MethodContext>>tempAt:
3.0% {23ms} BlockContext>>ensure:
2.5% {19ms} CaffeeWithMilk(Object)>>doesNotUnderstand:
2.2% {17ms} CaffeeWithMilk(SuperclassX)>>internalSwitchSenderToParent:

**Memory**
    old            +0 bytes
    young        -31,428 bytes
    used        -31,428 bytes
    free        +31,428 bytes

**GCs**
    full            0 totalling 0ms (0.0% uptime)
    incr        85 totalling 86ms (11.0% uptime), avg 1.0ms
    tenures        0
    root table    0 overflows




               
_________________________________________________________
Horóscopos, Salud y belleza, Chistes, Consejos de amor:
el contenido más divertido para tu celular está en Yahoo! Móvil.
Obtenelo en http://movil.yahoo.com.ar

On Fri, 23 Jun 2006 11:44:05 +0200, Edgar wrote:
> Klaus D. Witzel puso en su mail :
>
>> That output is from a non 3.9 image. On a 3.9 image you would see that  
>> the
>> debugger benefits from the implementation of traits, it has better means
>> for finding out which class and selector a method is actually used at
>> run-time. Here's the difference:
>
> Karl, here is the same on new 7035.

Looks good :)

> I have a question now.
> Could be possible have something like your exercise on non Traits image ?

Sure. The demo only *looks* nicer on images with 3.9 traits. The  
functionality does not depend on traits.

> What is needed on image if VM what follows Blue Book have this unknown  
> (to
> me) power ?

Three things:

1 - a way to access " thisContext sender ", " thisContext sender method ",  
" thisContext sender method literals " (this is in #switchSenderToParent:  
in my examples). inspect the three quoted expressions on Squeak and on the  
other VM and compare for differences. the literals must be accessible for  
read and write. this is usually the case when, since Smalltalk/2.x,  
support for the debugger is present (can do stack manipulation, code  
execution simulation, etc, all needed in support of a decent debugger). so  
these base functions exist for us for being reused :-)

2 - a guarantee that the VM does indeed follow the Blue Book for super  
sends. the compiler knows this and puts the class in which a method was  
compiled into the method's last literal (you should have seen that when  
you inspected the above expressions), from where the VM then starts lookup  
when it interpretes the super send bytecode.

3 - a means to make use of " [...] onDNU: #symbol do: [...] ". this is the  
classic #doesNotUnderstand: aMessage case wrapped into a convenient  
#onDNU:do: which either is already available in some form on the other VM  
or can be implemented to have the same functionality. my examples do not  
make use of any specific features of the exception passed to #onDNU:do:,  
so an implementation on another VM shouldn't be impossible.

> Very, very thanks

:)

> Edgar

Thank you Edgar for the feedback.

/Klaus

Klaus D. Witzel puso en su mail :

I have something to follow and try, very very thanks.

Edgar



       
       
               
___________________________________________________________
1GB gratis, Antivirus y Antispam
Correo Yahoo!, el mejor correo web del mundo
http://correo.yahoo.com.ar 

Hi Klaus!

I tried and I guess I understand how you did it.
Tricky, you use the literal for the super class reference to tell the  
VM to start the lookup in another class.

I think you might have problems with recursive calls (i.e., 'super  
foo' that is called twice by two different objects) and concurrency.


> The third example employs the existing method cache of the VM (the  
> original Squeak VM) for multiple inheritance message sends and thus  
> minimizes the overhead to less than 5% (and the demo is written  
> in .st code :-)

Your implementation relies on a doesNotUnderstand:. I am interested  
in knowing how can you have just a 5% overhead.

Cheers,
Alexandre

--
_,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:
Alexandre Bergel  http://www.cs.tcd.ie/Alexandre.Bergel
^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;.

Hi Alex,

on Sun, 25 Jun 2006 17:14:45 +0200, you wrote:
> Hi Klaus!
>
> I tried and I guess I understand how you did it.
> Tricky, you use the literal for the super class reference to tell the VM  
> to start the lookup in another class.
>
> I think you might have problems with recursive calls (i.e., 'super foo'  
> that is called twice by two different objects) and concurrency.

You're right and as many times before I appreciate your expertise! There  
is indeed a gap between the time of setting the super class reference  
(bytecode i-1) and when the VM starts using it (bytecode i+0). But from  
there on, method lookup and method activation is atomic.

It would be much better to keep the super class reference static  
(compile-time). Which is not hard to achieve, since every method has its  
own superclass field (either settable explicitly or traitified images have  
it anyways). Then a self send is looked up in one superclass hierarchy and  
a super send is looked up in another superclass hierarchy. Since an n-ary  
branch is reducible to a couple of 2-ary branches, we so have MI (as  
specified by the Blue Book :) and can forget expensive doesNotUnderstand:  
handling. We can discuss this further and deeper in offline mode if you  
like.

>> The third example employs the existing method cache of the VM (the  
>> original Squeak VM) for multiple inheritance message sends and thus  
>> minimizes the overhead to less than 5% (and the demo is written in .st  
>> code :-)
>
> Your implementation relies on a doesNotUnderstand:. I am interested in  
> knowing how can you have just a 5% overhead.

This demo runs in the documented setting and doesNotUnderstand: handling  
is accounted for by standard message tally with 5% (the reason is the VM  
method lookup cache which has one miss and from then on only hits. Let me  
know if something here remains unclear). Of course, more switches between  
more parents would incur more overhead.

> Cheers,
> Alexandre
>

/Klaus

Oops, I just did alt-s in Opera under WinXP and it DID NOT WORK :(

> You're right and as many times before I appreciate your expertise!  
> There is indeed a gap between the time of setting the super class  
> reference (bytecode i-1) and when the VM starts using it (bytecode i
> +0). But from there on, method lookup and method activation is atomic.

Yes, method lookup and method activation are atomic. But I had in  
mind if a super call does a Processor yield. The method containing  
the super invocation contains the ref of the second super class. But  
humm... perhaps it does not matter after all. If a method has to be  
lookup in other classes, then if will always have to be. I have to  
think a bit more...

But my general feeling is that multiple inheritance is complicated.  
Much more than traits. I was visiting the team of Bertrand Meyer in  
Zürich last week. I really wanted to understand the difference  
between stateless traits, stateful traits and multiple inheritance à  
la Eiffel. It seems that everything that can be done with state(less|
ful) traits can be done in Eiffel. The only difference is about  
complexity to achieve a particular behavior. With traits the  
flattening property makes the whole story simple, while in Eiffel the  
static type system makes it horribly complicated.

For instance, here an example in Eiffel:
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
class C1
feature
        foo is
                do
                        print ('1')
                end
end

class C2
inherit
        C1
                rename
                        foo as bar
                redefine
                        bar
                end
        bar is
                do
                        print ('2')
                end
end

f (a:C1) is
        do
                a.foo
        end

f (create {C2})
==> 2 " As C2 does not define a foo, this may be surprising..."
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

in f() foo is sent to a subtype of C1, but C2 does not have 'foo'!  
But it is still lookup because the compiler knows that foo was  
renamed in bar.

This is still a simple example. Things become very complicated with  
the ((in)famous) diamond pattern. Ambiguities need to be resolved  
with a dedicated keywords, 'select'. For example:
Let's assume 4 classes, C1, C2, C3, C4.

C1 defines a feature f.
C2 inherits from C1, and redefine f as 'print (A)'
C3 inherits from C3 and redefine f as 'print(B)'
C4 inherits from C2 and C3.

If you have:
c: C1
create {C4} c
c.f
==> Ambiguity!!!

Because two different paths are possible (C1, C2, C4 and C1, C3, C4).  
This needs a 'select' to remove the ambiguity.

For instance, if C3 is defined as:
C4 inherit C3
        rename
                f as g
        select
                g
        end

then:
c: C1
create {C4} c
c.f
==> B

Not trivial to determine it without being expert in Eiffel...

Cheers,
Alexandre
--
_,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:
Alexandre Bergel  http://www.cs.tcd.ie/Alexandre.Bergel
^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;.

Hi Alex,

on Mon, 26 Jun 2006 11:45:56 +0200, you wrote:
Right. The result of a method lookup is stored in the MethodContext,  
regardless of how the method was found (from cache or by traversing the  
superclass hierarchy). So no problem with Processor yield - storing the  
methodClass field followed by a super send can be made two adjacent  
bytecodes. And the possible aio (incl. Processor yield) would involve  
scheduling only at the message send boundary (right after  
activateNewMethod).

But again, I think that a static (compile-time) value for the methodClass  
field (a class which actually points to the desired superclass) is  
sufficient for MI.

> If a method has to be lookup in other classes, then if will always have  
> to be. I have to think a bit more...

:) Hint: after method activation the VM no longer looks to the caller's  
site (except when returning, of course).

> But my general feeling is that multiple inheritance is complicated. Much  
> more than traits.

Yes, the flatness (of traits) is what makes traits so uncomplicated.  
Having, OTHO, always the choice of which parent to lookup next needs a  
whole lot of discipline (seems to shine through between the lines in "The  
Power of Simplicity", which wouldn't have been possible without rigid  
discipline).

I agree that MI can have a disturbing and even a catastrophic downside,  
especially when combined with dynamic lookup.

> I was visiting the team of Bertrand Meyer in Zürich last week. I really  
> wanted to understand the difference between stateless traits, stateful  
> traits and multiple inheritance à la Eiffel. It seems that everything  
> that can be done with state(less|ful) traits can be done in Eiffel. The  
> only difference is about complexity to achieve a particular behavior.

Hey! Thank you for mentioning. I'd love to learn about that difference  
 from your point of view. When are you in Switzerland next time? Drop me an  
email.

> With traits the flattening property makes the whole story simple, while  
> in Eiffel the static type system makes it horribly complicated.
...
>
> Not trivial to determine it without being expert in Eiffel...

I'm not an expert in Eiffel but will take the opportunity and work through  
your examples, just for the fun of it. Thank you.

/Klaus

> Yes, the flatness (of traits) is what makes traits so  
> uncomplicated. Having, OTHO, always the choice of which parent to  
> lookup next needs a whole lot of discipline (seems to shine through  
> between the lines in "The Power of Simplicity", which wouldn't have  
> been possible without rigid discipline).
>
> I agree that MI can have a disturbing and even a catastrophic  
> downside, especially when combined with dynamic lookup.

Yep. But what does "OTHO" mean?

> Hey! Thank you for mentioning. I'd love to learn about that  
> difference from your point of view. When are you in Switzerland  
> next time? Drop me an email.

Sure, I will.

Cheers,
Alexandre
--
_,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:
Alexandre Bergel  http://www.cs.tcd.ie/Alexandre.Bergel
^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;.

On Fri, 30 Jun 2006 10:00:34 +0200, Alexandre Bergel  
<[hidden email]> wrote:
...
> Yep. But what does "OTHO" mean?

That was a typo, it should read OTOH.

FWIW:
- http://en.wikipedia.org/wiki/List_of_Internet_slang

BCNU, HAND, EoL ;-)

/Klaus