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 :
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)?
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 ?
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:
Klaus D. Witzel puso en su mail :
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 ?
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
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
- 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
Klaus D. Witzel puso en su mail :
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.
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
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
Hi Alex,
on Mon, 26 Jun 2006 11:45:56 +0200, you wrote:
Klaus wrote:
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.
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
On Fri, 30 Jun 2006 10:00:34 +0200, Alexandre Bergel Alexandre.Bergel@cs.tcd.ie 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
squeak-dev@lists.squeakfoundation.org
-
Alexandre Bergel -
Klaus D. Witzel -
Lic. Edgar J. De Cleene