zenith@ensmp.fr (Steven Ericsson-Zenith) (01/07/91)
As I mentioned in part 1 of my reply there is a Research Report at Yale
by James Narem. The report is entitled:
"An Informal Operational Semantics of C-Linda V2.3.5:"
James E. Narem Jr. (email: narem-james@cs.yale.edu)
Jim is the moderator of the Linda Users mailing list. I mentioned our
recent discussion to him. He said:
"Actually we've been through this before on linda-users. All the same
stuff comes around again and again. I just saw that someone asked the
obvious question about the predicate operations yet again."
I've just reposted a reply from Jerry Leichter to the later. I an
earlier reply to similar issues on that list Jim had said (quoted with
permission)
"... I thought I might muddy the waters a bit with an absurdly
pragmatic view of eval as seen in Carriero's C-Linda. Basically, it
comes down to a simple "if it hurts, don't do it." Note that C-Linda
is an evolving language. This summary may not represent the current
state of the system."
Jim then quotes from his report (I've shortened this further):
"... The current C-Linda implementation by Carriero uses one process
per {\em eval} and each field is evaluated left to right within the
tuple. This can cause deadlocks if code for different fields
communicate using blocking operations.
... There are four basic types of process creation used in {\em eval}
implementations; a given C-Linda implementation may use more than one.
The simplest is creation using the Unix\footnote{Unix is a registered
trademark of AT\&T} fork library call. An {\em eval} gets a new
process context created by fork which inherits a copy of the global
state at the time of the fork. At process exit, the global state is
discarded. This provides great isolation between {\em eval}ed
processes while allowing significant initial state to be passed to the
new process. Process creation may also be done by one of the many
threads packages available. Basically a thread allows multiple
concurrent execution paths, each with a private stack. Both globals
and the heap are shared. This allows significant data communication
between processes not using the C-Linda operations and provides very
little interprocess protection. {\em Eval}ed processes may be
executed by evaluators --- tasks, usually with separate process
contexts, that pick up requests to perform {\em eval}s and execute
them. In this case, the global state is unpredictable since the
process state is dependent on the history of {\em eval}s performed by
a specific evaluator. Lastly, processes may be created on processors
that share no state with the creating process; often this involves
creating an evaluator on a remote machine in a distributed system. In
this case, the initial global state is created by the native C runtime
system. No sharing occurs between processes and interprocess
protection is quite strict. Again, existing implementations may use a
combination of these methods. These observations should be used to
find {\em eval} related program errors; their effect on program
behavior should not be relied upon even if it results in more
efficient code."
He further states:
"There are three very distinct observable semantics for eval in the
carriero derived C-Lindas at Yale. And since C has unrestricted
pointers, it is not possible to check a program for conformance with
the language definition. It is simply not possible to debug a large
program without knowing the observable semantics of eval. That is
plainly obvious to anyone who has written a large linda program ..."
Yes, yes, I know this is implementation and not definition - but this
has been how Gelernter has attempted to define Linda; by the provision
of a definitive implementation. In fact, Jerry Leichter has just sent me
a copy of his reply to a question (I guess from the Linda Users list),
which he suggests I post in this group, it is a reply to
["snykanen@cs.Helsinki.FI"] who asks about the semantics of inp and rdp.
It makes very much the same observation:
"You asked whether the code:
out("tuple"); x = inp("tuple");
is guaranteed to set x to 1 (assuming, for the sake of simplicity,
that tuple space is initially empty and that there are no other
processes acting on it). The answer is, "probably".
A better answer is: Forget about inp and rdp. They were a mistake
that never belonged in the language; they happened to be trivial to
add to a shared- memory implementation, so snuck in. But they cause a
lot of problems in a distributed setting, confuse the semantics of the
language, encourage the writing of buggy code, and ultimately add
nothing to the expressiness of Linda.
For arguments justifying these assertions, and a lot of discussion of
Linda semantics, see my dissertation, "Shared Tuple Memories, Shared
Memories, Buses and LAN's - Linda Implementations Across the Spectrum
of Connectivity", available from the Yale Department of Computer
Science as TR-714 (July 1989).
(You'll probably get an answer from someone at Yale citing some recent
paper in which a semantics which justifies the conclusion that x = 1
is cited. Don't take this to mean you should have been able to
somehow guess that for yourself. Linda went along for years with an
early 1960's-style "definition" with "obvious" semantics that no one
ever bothered to write down - until, of course, what became "obvious"
was that different readers (and different implementors) where finding
different "obvious" interpretations.)"
And frankly, is it any surprise?
Steven
--
Steven Ericsson Zenith * email: zenith@ensmp.fr * fax: (1).64.69.47.09
| | voice: (1).64.69.48.52
Ecole Nationale Superieure des Mines de Paris
35 Rue Saint-Honore 77305 Fontainebleau Cedex France
"All see beauty as beauty only because they see ugliness" LaoTzu