Loose type checking in E

[Tyler Close]

At 02:45 PM 10/12/98 -0700, you wrote:
>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?

That's not the point. As was demonstrated by the JGL, it is possible to
code an STL like library in Java using inheritance-based polymorphism. As
was also demonstrated by the JGL, this library will suck.

One of the really neat things about templates in C++ is that you don't need
to create deep and complicated inheritance structures to get seamless
communication between separately developed code. E also has this really
neat advantage without doing anything at all.

>>>>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.

I think you probably have at least an order of magnitude of experience over
me. I just wanted to make sure that everybody knows that I know this before
I go shooting my mouth off, since I seem to be unable to do anything
without shooting my mouth off. Now that we all know that we all know what's
what and who's who, I'll drop it.

I wouldn't give donkey spit for the "dominant position of the industry".

>>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.

Sure, but which one of us is playing the role of Gerald Wienberg.

>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.

I don't think any other way. Please use the same approach when telling me
why I'm wrong.

>>... 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?

Again, you seem to arguing that if you take an undisciplined approach you
will land yourself in trouble.

Why should client code hold locks in the GUI while it is executing a
transaction in the database? Don't do it, you're asking for trouble that
you don't need.

If you're asking for a global convention, it's "Coupling is Bad: Don't
introduce dependencies that you don't need!"

There is a need to hold multiple locks within the GUI, so I've embedded a
protocol for using these locks into the way that the GUI operates.
(Incidentally, I've done the same for a database library, but I don't wish
to take over this discussion group.)

Only since you asked, here's a little more about my GUI library:
To enforce the tree protocol, it is important that widgets cannot traverse
up the GUI tree. An Apartment has a hard ceiling, unless some moron gave
the widget a pointer into an outer Apartment, then the widget will not be
able to naturally traverse up the GUI tree.
Apartments are place around a group of objects using the Decorator design
pattern. These decorators fit naturally into the GUI tree structure just as
any other container does. When the widget accesses deeper nested Apartments
of the GUI tree, it can't help but lock on these apartments in accordance
with the tree protocol. The one caveat to this is that if the widget makes
separate trips down the GUI tree, then there is still no deadlock; however,
it is possible that the transaction will not be serializable. I have found
that this is an easy caveat to deal with.

>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.

Which locks must the debugee and the debugger share?

>>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.

Well, you seem to be bashing me about the head with your
order-of-magnitude. I haven't spent any significant time thinking about
distributed environments. It's next on my list, but I've got things I need
to finish in the meantime. I expect that your asynchronous communication
paradigm is the way to go in a distributed environment. It has a sort of
natural symmetry to it. 

I am having a lot of difficulty accepting that a single computer should be
treated as a distributed environment. See my reply to Chip Morningstar's
post. I expect that your reply is going to be that you want a homogeneous
environment; however, this ignores the fundamental truth that your
execution space is not a homogeneous environment. Designs that ignore
fundamental truths make me nervous.

>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  

Thank you for the links. I greatly appreciate this.

>
>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.

I'll look into this.

ciao,
Tyler