From: mjg@ktbush.ogo.dec.com (Michael J. Grier)
Subject: Re: reentrant code
Reply-To: mjg@ktbush.ogo.dec.com (Michael J. Grier)
Organization: Digital Equipment Corporation
Date: Sun, 27 Dec 1992 20:51:34 GMT


In article <1992Dec22.050426.17583@linus.mitre.org>, crawford@boole.mitre.org (Randy Crawford) writes:
|>As Mr. Grier put it:
|>> Consider a module which implements an abstraction of a queue
|>> or other searching structure, which provides a service for iteration on the
|>> data structure.  If you specify the service such that the caller provides
|>> a function to execute for each element in the structure, there is again
|>> a need for reentrancy controls of some fashion.
|>
|>Here, reentrancy is necessary only if there are one or more data shared among 
|>these search callbacks to which they might write asynchronously, interfering 
|>with each other's state.  In that case, I still see this as a concurrency 
|>problem (and certainly a reentrancy problem too).  
|>
|>To better define my terms, I think that reentrancy exists to serve concurrency,
|>and as such, you cannot have reentrancy without concurrency, but you can have 
|>concurrency without reentrancy when no shared data is vulnerable.  
|>
|>To pick a nit.

   I've put a fair amount of thought into this issue, and while you might be
able to convince me that in some abstract sense recursion and concurrency
are different specializations of a common principle, while I lack a formal
proper definition for concurrency, I would classify the two as separate
concepts.  I believe this is/was my major point personally.

   It's a working/engineering style definition rather than a pure theoretical
view, but a definition of concurrency which includes recursion is, IMHO,
in any practical sense, useless or confusing.  (Not useless per se., so much as
that if I was explaining a module in a formal inspection with my peers, and
controls which are of the nature I described earlier -- where a recursive
reentrancy into a data structure could naively cause destructive behaviour --
and I started describing the facets as "concurrency controls" rather than
"recursive reentrancy controls", confusion would reign.)

   In a functional (i.e. no destructive assignments) world, the two could
probably be merged successfully, as parallelism and recursion could both
be "implementation details".  In my very real world of thousands of lines of
C and other languages, where the cost of "reentrancy controls" is often
orders of magnitude lower in cost than "concurrency controls", the difference
is very important.  (My current project is layered, and uses a threading
programming model, so both recursion within a thread and multiple threads
coexisting peacefully are concerns.  I'll think more about it, but there is
such a real world difference between recursion and the pseudo-concurrency
granted us by threads that merging the two concepts in a day-to-day world
is inconceivable.)

------------------------------------------------------------------------
I'm saying this, not Digital.  Don't hold them responsibile for it!

Michael J. Grier                           Digital Equipment Corporation
(508) 496-8417                             mjg@ktbush.dec.com
Stow, Mass, USA                            Mailstop OGO1-1/E16