Loose type checking in E

[Tyler Close]

[Forwarded with permission.  --MarkM]


At 12:50 PM 10/8/98 -0700, you wrote:
>At 06:36 PM 10/2/98 -0400, Tyler Close wrote:
>>Hi Mark,
>>
>>We met a couple of weeks ago at a Foresight meeting. I was there with Ping.
>>
>>I was just thinking about my gripe about no static type checking in E. It
>>occurs to me now that the runtime checks on method name / # parameters
>>enables parameratized programming of the kind that C++ templates allow,
>>without causing the source code explosion that C++ templates create.
>>
>>You've no doubt already thought of this, but it would be a good thing to
>>mention the next time some smart ass complains about no static type
>>checking. It certainly would've shut me up.
>
>While I would like to use this rationale, it doesn't quite work.  Other
>languages with parametric polymorphism (ie, like C++ templates) include
>Eiffel, ML, and the Pizza variant of Java.  All of these consider a
>parameterization of a parameterized type to be equivalent to an expansion
>with these type parameters filled in, but in the other languages, rarely
>does the implementation need to actually do any expansion.  Usually they
>can all share one implementation, with the parameterized type checking
>being only a static theory *about* what the run-time situation means.  C++
>painted itself into many corners (like argument-type-based overload
>resolution), some of which obligated it to usually expand parameterized
>types in the implementation.

Since E does not have static type checking, I was not suggesting that
compile time polymorphism was possible. However, with E's runtime checks,
it is still possible to write generic algorithms that expect their argument
objects to have methods with specific method name / # parameters signatures
without using inheritance based polymorphism. 

The use of iterators in the C++ STL is by far the most important feature in
the library which is enabled by templates. In E, you could create a
meta-type definition for iterators in much the same way as it is done in
the C++ STL. All you would need to do is document the expected names for
incrementing, decrementing, dereferecing, etc..., along with the runtime
bounds. You could then create a library of generic algorithms based on
these definitions.

This seems to me to be a very powerful advantage that was gained by doing
less work rather than more.

I do not have any experience with Eiffel, ML or Pizza; however, it has been
my experience that C++ compilers have very little success (none?) in
reusing code between different expansions of the same template.

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

>>I remember that one of the reasons for abandoning multi-threading was to
>>eliminate wall-banging; however, if you made thread creation a capability,
>>with a ThreadMaker object, wouldn't you still be able to guarantee
>>deterministic execution of untrusted code and thus eliminate wall-banging?
>
>Yes, but wall-banging is not the main reason for giving up multi-threading.
> The main reason is that -- despite the acceptance of multi-threading by
>the entire industry -- for general purpose programming, it is an unworkable
>concurrency control paradigm.  (The multi-threading paradigm can be the
>right thing for certain special cases, but it's ok with me if these cases
>are uncodable in E.)
>
>Correctness requires both that we maintain consistency and that we avoid
>deadlock.  Within the threading paradigm, "thread-safe" programming
>requires locking on many individual "thread-safe"
>abstractions/data-structures.  By the time we've put enough fine-grained
>locks in to preserve consistency, we can no longer document the composition
>rules needed to avoid deadlock.  A good example is Javasoft's attempts at a
>GUI library (the AWTs and Swing) vs the EC Habitats Beta.  
>
>Javasoft is firmly in the multi-threaded paradigm, and has tried through
>four generations to build a multi-threaded GUI library (Oak AWT, Java 1.0x
>AWT, Java 1.1x AWT, Swing).  Over time, these have gradually migrated away
>from actually *using* multi-threading and towards event-loops, but without
>ever giving up on multi-threading.  Even Swing's documentation admits that
>it suffers from *both* race condition and deadlock bugs, without providing
>adequate guidance for avoiding these bugs.  
>
>In contrast, the EC Habitats Beta, though put together sloppily and in a
>hurry, and only living through *one* customer release cycle, had
>essentially no race condition or deadlock bugs, despite taking on vastly
>harder concurrency problems than any faced by Javasoft (after all, it was a
>symmetric distributed system).  I attribute this to the
>asynchronously-coupled event-loop paradigm, which is really the Actor
>paradigm in different clothing.

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.

I fully agree with you that using many fine-grained locks is just too
complicated (not to mention ugly and inefficient). In my library, I have
used the tree protocol from database theory to create a sort of apartment
based threading model. Algorithms which operate on the GUI are given an
Object to lock on before accessing the GUI data structure. If the GUI is
multithreaded, then this Object will represent the apartment for the
shallowest node in the GUI tree that is used by the algorithm. All of the
methods of the objects in my GUI tree structure have been defined such that
they obey the tree protocol, locking on deeper nested apartments as necessary.

I have found that this works very well, and that it is quite simple to show
that deadlock will not occur.

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.

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

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

>
>
>>I really enjoyed the meeting and learning about E. The more I think about
>>it, the more slick it seems. 
>
>Thanks much!

Anyways, don't think any of what I've said means that I don't like E. I'm
pretty overwhelmed by the number of good ideas you've integrated into a
simple design.

>
>
>>I would very much appreciate being put on the
>>ad hoc mailing list you have for E.
>
>Will do.  May I forward our correspondence to the list?

Thank you and yes, of course.

ciao,
Tyler