Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!mnetor!uunet!husc6!hao!ames!ptsfa!ihnp4!inuxc!iuvax!pur-ee!uiucdcs!uiucdcsp!johnson
From: johnson@uiucdcsp.cs.uiuc.edu
Newsgroups: comp.lang.smalltalk
Subject: Re: Back to the future
Message-ID: <80500013@uiucdcsp>
Date: Mon, 24-Aug-87 10:00:00 EDT
Article-I.D.: uiucdcsp.80500013
Posted: Mon Aug 24 10:00:00 1987
Date-Received: Wed, 26-Aug-87 06:20:44 EDT
References: <245100012@orstcs>
Lines: 46
Nf-ID: #R:orstcs:245100012:uiucdcsp:80500013:000:2798
Nf-From: uiucdcsp.cs.uiuc.edu!johnson    Aug 24 09:00:00 1987


I think that futures were first used in Multilisp at MIT.  Whether that
system was the first to use them or not, there was a paper on futures
in Multilisp in TOPLAS a couple of years ago.  I seem to remember that
actor systems have used futures for awhile, too.

There was also a paper on futures in Smalltalk in OOPSLA'86.  I seemed
to have loaned out my copy of the proceedings, so I can't reference it
precisely.  However, the authors of the paper were Japanese and the title
of the paper was something like "Concurrent Smalltalk".  They did not
give any idea how futures were implemented, and gave them a different name.
They used atomic objects to limit parallelism.

It seems to me that futures and atomic objects are better mechanisms for
parallelism and synchronization for object-oriented programming than processes
and semaphores.  They encourage the programmer to think about the values
being passed rather than the flow of control.  Flow of control is usually
misleading, and seems especially so for object-oriented programming.

One of the features of Multilisp futures was that the interface to a future
was identical to that of their eventual values.  In other words, if a future
is going to return an integer then it can be added to another integer.
A process using the future is blocked if the future has not been evaluated.
The operation is resumed once the future "arrives".  Thus, a future could
be added to any Multilisp program by taking an expression and applying the
"future" function to it.  This made it very easy to turn a sequential program
into a parallel one.

If Smalltalk futures were like this then they would have to be objects
that could trap any message, check to see whether their value had been
calculated, and then forward the message to the value.  This is essentially
the same idea as an encapsulator, which was described in another OOPSLA'86
paper.  Encapsulators are implemented by overriding the doesNotUnderstand:
message.  Unfortunately, this message seems to be slow.  I am not sure if
this is just a byproduct of the interpreter that I am using.

I have thought of another mechanism that would make it easier to implement
special objects like futures and atomic objects---give each class its own
method lookup routine.  This would probably be stored in an instance variable
of the class.  Most classes have the same method lookup routine, but
encapsulator classes would each have their own.  An efficient interpreter
uses caching to reduce the number of method lookups, and method lookups are
expensive, so it doesn't make much difference if a method lookup takes another
memory reference or two.  If encapsulators like futures are used very much
then giving each class its own method lookup routine would probably improve
performance significantly.