Loose type checking in E

Mark S. Miller markm@erights.org
Mon, 12 Oct 1998 14:45:29 -0700


At 10:19 AM 10/12/98 -0700, Tyler Close wrote:
>...
>The use of iterators in the C++ STL is by far the most important feature in
>the library which is enabled by templates. ...
>
>This seems to me to be a very powerful advantage that was gained by doing
>less work rather than more.

Could you give a small example that cannot be coded well in Java using only
inheritance-based polymorphism?


>>>I am also still a little hung up on your process style concurrency scheme.
>>>Can one vat make a series of method calls on another vat in an atomic
>>>fashion? If so, how?
>>
>>No.  Between vats we only have asynchronous sends.  Otherwise E wouldn't be
>>deadlock-free.
>
>You have much more experience than I do at writing concurrent software;

Enough modestly, especially given the window system you wrote that you
describe below!  Your position agrees with the dominant position of the
industry, which has *vastly* more experience with concurrency that Agorics,
EC, erights.org, and the Actor tradition combined.


>however, it would seem to me that being deadlock-free is small consolation
>for not being able to make atomic operations and thus create serializable
>transactions.

Surely you don't mean this.  It reminds me of a tale that Gerald Wienberg
tells of consulting to a project that had a buggy but efficient algorithm
for some problem.  When he proposed a correct algorithm they objected that
it was three times less efficient than theirs.  He replied that if they
wanted an algorithm that didn't work, he could provide one much more
efficient than theirs.


>I feel stupid saying this, since you obviously have far more experience
>than I do; but I think that I have created a deadlock free, multi-threaded
>GUI library for Java.

Stop it!  No humbleness!  After all, who do you think you are to act so
humbly?

More seriously, E embodies a number of bold unconventional deviations from
the computer science common wisdom.  I'm very unlikely to be right about
all of them, and it would be amazing if I were right about most of them.
I'm counting on you all to help me debug this sucker before it's too late,
so please shoot away.


>... the tree protocol from database theory to create a sort of apartment
>based threading model ... quite simple to show
>that deadlock will not occur.

I'd like to hear more about this.  However, it fits a familiar pattern:
adopt a global convention for who-can-lock-who that doesn't produce cycles.
 The problem is composition: You've defined a window system around such a
convention.  Joe defines a database around another acyclic convention, and
so on.  If the only code executing with a lock held is within the
implementation of these subsystems, probably fine.  If client code, such as
the behavior of a newly defined widget, executes within this framework with
a lock held, then we've got a problem.  Client code is typically a client
of several different subsystems.  If your widget, executing with its widget
lock held, is a widget for updating a record of Joe's database, now the two
acyclic lock trees have been joined.  Can we now get a cycle?  I dunno, it
depends on *lots* of specifics.  What do you and Joe have to explain to the
widget creator -- under the constraint that you and Joe don't know about
each other -- so that such widget creators can confidently do their jobs
correctly, while not knowing about each other?

The one step we can take is to allow *one* globally known acyclic locking
convention.  Having allowed it, we need to prohibit the others -- the first
one uses up our capacity for such a convention.  Unfortunately, I think
I've got an inescapable need for one -- one vat debugging another.  The
debugee gets suspended pending action by the debugger.


>Anyways, the point of all of this is not to say "I can design a better
>library than the engineers at Javasoft". (Which is obviously a moot point!
>;) The point of this is that there are well defined, useable (and, dare I
>say, beautiful) protocols for avoiding deadlock in a multi-threaded
>environment. I don't think you can toss away multi-threading as
>"unworkable" simply because the engineers at Javasoft are ignorant of these
>protocols.

Do they all fit my characterization of anti-cycle conventions that don't
know how to compose with other anti-cycle conventions?  What about a
distributed environment?  What about a distributed adversarial environment?
 How about one where the participants checkpoint at times
mostly-uncoordinated with each other, and may at any point roll back to
their last checkpoint as a result of a crash-revive.  All these push for
looser coupling between Vats.  Ask me sometime about quakes.

In any case, I'm always in the mood to hear a beautiful protocol....


>>Correctness requires both that we maintain consistency and that we avoid
>>deadlock.
>
>Given that E only has asynchronous sends between vats, I fail to see how
>you can maintain consistency in transactions between vats.

We avoid inter-vat *transactions*.  More below.


>>I attribute this to the
>>asynchronously-coupled event-loop paradigm, which is really the Actor
>>paradigm in different clothing.
>
>I don't think I fully appreciate your reference to the Actor paradigm. What
>object-oriented computational model isn't the Actor / Use Case paradigm in
>different clothing?

Name conflict.  Search for "actor" in
http://wuarchive.wustl.edu/doc/misc/lang-list.txt for a good list of
references.  See especially "Foundations of Actor Semantics" by Clinger
ftp://publications.ai.mit.edu/ai-publications/pdf/AITR-633.pdf (which I'd
thought was out of print!!)  Also, take a look at all of the "Lambda the
ultimate" papers at
"http://www.ai.mit.edu/publications/pubsDB/pubsDB/onlinehtml".  (I thought
these were out of print too!!)  Most of all, study Joule
http://www.agorics.com/joule.html  

Being universal and concurrent, E cannot prevent you from building the
equivalent of distributed locking and transactions on top.  Of course, at
the resulting level of abstraction you will not be magically immune to
deadlock.  However, Actors is a *different way to think* about concurrency,
such that you (almost always) stop wanting distributed locking or
transactions.

For distributed programming, there's a much more important reason than
deadlock to avoid distributed transactions -- given the possibility of
network partition, you *cannot* implement classic distributed transactions
that don't get hung.  Given classic serializability, these hangs turns into
deadlock.  Ask me sometime about the coordinated attack problem.


	Cheers,
	--MarkM