Path: utzoo!utgpu!news-server.csri.toronto.edu!rutgers!att!emory!hubcap!Steven From: zenith@ensmp.fr (Steven Ericsson-Zenith) Newsgroups: comp.parallel Subject: Linda "definition" :Zenith replies 2.5 Message-ID: <12487@hubcap.clemson.edu> Date: 6 Jan 91 18:06:27 GMT Sender: fpst@hubcap.clemson.edu Lines: 117 Approved: parallel@hubcap.clemson.edu 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