[comp.lang.prolog] CP, Linda and Multiple Producers.

mitsolid@acf5.NYU.EDU (Thanasis Mitsolides) (05/05/89)

I believe that the ability for one language to simulate features
	of another easily, is very important and a good indicator
	of the language's relative power.

At the same time I believe that 
	it is important that the implementation should be reasonably efficient.

A simulation of Linda's features in CP, appeared in this group
	which was inefficient.
	In fact the complexity of executing n Linda operations seems
	to be n*n.

It seems to me that an efficient implementation of Linda on any
	concurrent logic programming language would require
	a "linda monitor" but also lots of "merge" invocations.
	Thus, making that Linda Implementation almost impractical.

I believe that one of the problems that CLP languages must face
	in the future is the ability to handle
	multiple producers (of a stream of messages),
	in a simple, efficient and fair way (direct messages to objects?),
	avoiding the ever needed (often unfair) explicit merge invocations
	and the inefficient n*n solution (above).

That should extend the (practical) expressiveness of CLP languages.

Please correct me if I am wrong.

Thanasis

udi@wisdom.weizmann.ac.IL (Udi Shapiro) (05/10/89)

        A simulation of Linda's features in CP, appeared in this group
        which was inefficient.
        In fact the complexity of executing n Linda operations seems
        to be n*n.

This was the simplest possible program.  Adding an argument to 'out'
that returns the tail of the Tuple Space incomplete list
and garbage collecting deleted tuples by 'in' would make
a single producer and single consumer communicate  via a Tuple Space
in constant time per operation.  In general the overhead will be linear in
the number of producers/consumers, rather than the number of tuples
they consume or produce.

Using binary search trees can reduce to overhead of any operation to
be logarithmic in the number of operations (or active tuples, if rebalancing
after tuple delection takes place).  Using hash tables an algorithm similar
to (what I think) Linda uses for non-shared memory machines would result.

        It seems to me that an efficient implementation of Linda on any
        concurrent logic programming language would require
        a "linda monitor" but also lots of "merge" invocations.
        Thus, making that Linda Implementation almost impractical.

See my previous answer.

        I believe that one of the problems that CLP languages must face
        in the future is the ability to handle
        multiple producers (of a stream of messages),
        in a simple, efficient and fair way (direct messages to objects?),
        avoiding the ever needed (often unfair) explicit merge invocations
        and the inefficient n*n solution (above).

Fair constant time mergers are known for some time (see the Concurernt
Prolog book), and are used everyone in the Logix system and in applications.

Udi