Slate on a message-passing machine

[Jecel Assumpcao Jr]

Matthew Fulmer wrote on Sat, 2 Jun 2007 09:19:18 -0700
> For my Master's thesis, I will probably be working on a hardware
> architecture for efficiently executing object-oriented systems.
> Slate is definitely the most generic of these types of systems,
> and so I believe I should make the hardware directly applicable
> to slate, since all other object oriented semantics are a subset
> of those provided by Slate.

It is a good idea to aim for the most general case if possible. It is
also nice to have statistics which tell you what the most common case is
and how important it is to the overall performance of the system.

> For an example of the kind of hardware I am talking about,
> consider Jecel's Ring Network Architecture:
> http://www.merlintec.com:8080/hardware/19 . According to the
> example, the RNA architecture can send, lookup, and execute a
> message that is installed on a single receiver without software
> assistance. I wonder if this design can accommodate some, if not
> all, of the multi-dispatched message sends in slate. In other
> words, is there (hopefully large) a subset of slate
> message-passing semantics that can be resolved without resorting
> to sending extra messages?

You need to add the concept of "role", but other than that RNA would be
suitable for Slate. A message send would involve visiting several
different objects (also the case for inheritance in a single dispatch
version) but I like to think of that as several phases of a single
message send rather than extra messages, though both interpretations are
equally valid.
 
> I hazard to guess that a subset of slate does have the same
> semantics as the operation natively handled by RNA, but it may
> be somewhat small. This seems to be the case when there is
> exactly one method with the given selector, and the receivers
> all have NoRole. This could be resolved as a single-send to the
> method object with the receivers as arguments. Is this correct?

The case where I think Slate would be equivalent to Smalltalk/Self is
when an ancestor of the first argument implements the method with all of
the other arguments having NoRole. But it has been a while and I am
probably remembering the Slate terms wrong.

> To implement Slate on a single-dispatch architecture, I think
> selectors would be sent a single-dispatch valueWith:With ...,
> message. To resolve, I suppose one would calculate the distance
> for each method, then minimize it. This could probably be done
> in one trip around the loop in an RNA architecture if the
> messages are laid out in the correct order.

Slate's dispatch is a little less symmetric than it would seem at first
glance: there is a left-to-right bias. Another "quirk" is that you can't
declare a method where none of the arguments have their types defined.
So it doesn't implement fully generic functions like in CLOS, for
example. With these two restrictions it is possible to patch a
single-dispatch Virtual Machine very easily to implement Slate's
semantics. This should be of interest to anyone thinking of putting
Slate on top of Strongtalk, for example. The idea is simple enough that
I will describe it here:

You have a global cache which is given an object's type and a message
selector and will return either a method or a "token". This token is
just a special selector which is generated internally and known not to
match any user defined method.

So you put the leftmost argument and the message selector into the cache
and if you have a miss you do the normal lookup code. On a hit, if the
result is a method you simply execute it but if it is a token you put
the second argument and the token into the cache and so on until you
finally get a method to execute.

This is just double dispatch but without the trivial redirection methods
having to actually be written and compiled.
 
> Am I correct in this assessment of Slate's dispatch mechanism? I
> would like to make sure that whatever we build can be used to
> efficiently implement Slate. I am still not sure how the correct
> method is calculated. I don't understand whether it is some kind
> of recursive computation given the delegates of each receiver, a
> search that only cares about the distance from the receiver to
> the message role, or some combination of the two.

Note that as I said above, CLOS is actually a little more generic than
Slate. The description of Slate's dispatch can give you a wrong idea of
how things actually work, so you might want to look at the
implementation or the examples in Lee's papers.

-- Jecel