Linda

Linda is a programming language from David Gelernter at Yale for parallel programming. The main idea is decoupling communication from effective presence of communicating Actors by defining a global tuple space where Actors may publish tuples. Tuples are persistently retained in the space, and are freely accessible by all the Actors, which have primitives to read and extract tuples from the space by pattern-matching.

The idea seems nice, but it's basically a very very particular case of what the pi calculus in its asynchronous variant allows. The original Linda semantics has been proved underspecified in [1] by Busi, Gorrieri and Zavattaro at University of Bologna, as it is not clearly stated whether the emitting Actor may continue before the tuple becomes visible to other Actors, or not. The difference is meaningful since the first semantics (named unordered) is not Turing-complete, while the second (named ordered) is.

Many implementations are available of the Linda paradigm, named "generative communication". The most relevant are IBM's TSpaces and Sun's JavaSpaces, in Java. The latter is also integrated in Jini. These also introduce reactive operations, whose semantics has been investigated at University of Bologna. Many extensions have been proposed to overcome the limits of having a global shared dataspace, like KLAIM and Lime. These introduce multiple tuple spaces and primitives for distributed tuple access (KLAIM) and transient sharing (Lime).

    Bibliography

  1. Nadia Busi, Roberto Gorrieri, Gianluigi Zavattaro,On the Expressiveness of Linda Coordination Primitives (.ps), Information and Computation, 156(1/2):90-121, Academic Press, 2000