The Chemical Reaction Model

 < Day Day Up > 



Gamma

A distributed system involves entities in distributed sites that communicate with each other through communication links. The complexity of designing such a system is an issue under research. The designer of the system cannot afford the burden of decomposing a program into a large number of individual tasks. Therefore, the Gamma language was proposed (Banatre & Le Metayer, 1990; Le Metayer, 1994) to create the kind of high-level architectural design in which parallelism is left implicit.

A Gamma program is composed of a set of rules governing the interactions among underlying program units, termed “reactions,” which are analogous to chemical reactions. The underlying data structure is modeled by a multiset. No global control is imposed on the way multiset elements are selected to ignite the reaction. The execution of the program proceeds until no more reactions can take place, and the multiset at that point represents the result of the computation.

A “multiset” is a set, except that its elements may have multiple occurrences. The computation sequence of a Gamma program is the transformation from the original multiset to the final one. We refer to the elements in the multiset as “tuples.”

Therefore, the Gamma language involves two different kinds of terms: the programs and the multisets. The multiset is the only data structure, and the programs are described as collections of pairs (Reaction Condition, Action). For example, the following is a Gamma program computing the maximum element of a nonempty set:

max M = x: M, y: M x: M x y

The reaction condition x y specifies a property to be satisfied by the selected elements x and y. These elements are replaced in the set by the value x, known as the ‘’context of the action.’’ Nothing is said about the order of evaluation of the comparisons. If several disjoint pairs of elements satisfy the conditions, the comparisons and replacements can be performed in parallel. An intuitive way of describing the meaning of a Gamma program is the chemical-reaction metaphor: the set can be seen as a chemical solution, and the computation terminates when a stable state is reached or when no elements of the set satisfy the reaction condition. Of course, in some cases, the programs may not terminate, and the reaction will take place forever.

We adopted a syntax of Gamma similar to that for higher-order Gamma (Le Metayer, 1994). In this syntax, a program is expressed as a configuration, in the form of [P, E], which is made of a program P and a record E of named multisets. The record component of the configuration can be seen as the environment of the program. Each component of the environment is a typed multiset. The program extracts elements from these multisets and produces new elements.

For example, the following program:

x: M, pivot: Pivot x: R , pivot: Pivot x pivot

extracts an element x of multiset M and the pivot of the multiset Pivot, and once the condition x pivot is evaluated as “true,” x is removed from M and inserted into R , and the pivot remains in the Pivot.

Programs can be composed by using the sequential operator and the parallel operator +. Conf.Var returns the value of the field Var in the configuration Conf (when Conf has reached a stable state). The operational semantics of Gamma (Hankin et al., 1993a, 1993b) mean that the environment returned by a parallel composition P1 + P2 must be stable for both P1 and P2. When a sequential composition P1 P2 is concerned, the initial environment for P1 must be a stable environment for P2, and the final environment is returned by P1.

For instance, the following program compares the elements of a multiset of integers M with a pivot p and dispatches the elements into R and R>.

click to expand

Higher-Order Gamma

Higher-order Gamma (Le Metayer, 1994) is an extension of the Gamma formalism unifying the program and data syntactic categories, or unifying the multiset and (R, A) pair into a single notion of configuration. A configuration is made of a program and a record of named multisets. As a result, active programs can be inserted into multisets, and reactions can take place simultaneously at different levels. This extension greatly strengthens the expressivity of Gamma language. Various operators for combining Gamma programs can be defined naturally in higher-order Gamma, including the sequential and the parallel composition. Thus, these operators do not need to be introduced as primitives in the language.

The syntax of the higher-order Gamma language is defined as follows:

click to expand

The following is an informal description of the semantic rules. (The formal semantics of higher-order Gamma can be found in Le Metayer (1994).)

Rule 1: (Reaction) [P, E] [P, E’ ], where E’ = E Q e e’ . e is the multiset of the elements of E that satisfy the condition of one of the reaction rules of P, and e’ is the multiset of the elements produced by the action of that reaction rule. and Q denote multiset union and difference, respectively.

Rule 2: (Inertness) [P, E] [F, E] if no action contained in P can take place in environment E, and E is inert (i.e., no actions take place in the configurations inside E).

Rule 3: (Concurrency) {X} M {X’ } M if X X’ . Individual elements can evolve independently in a multiset.

Rule 4: (Hierarchy) [P, E] [P, E’ ] if E E’ . Because actions take place in different levels concurrently, the environment (E) of a configuration can evolve while P is being executed.

Rule 5: (Sequentiality) [P o Q, E] [P o Q’ , E2 ] if [Q, E] [Q, E’ ]. P and Q are executed sequentially. Especially, [P o Q, E] [P, E’ ] if [Q, E] [F, E’ ].

Rule 6: (Parallelism) [P + Q, E] [P + Q’ , E’ ] if [Q, E] [Q, E’ ] and

[P + Q, E] [P’ + Q, E’ ] if [P, E] [P’ , E’ ]. In addition, [P + Q, E] [F, E] if [P, E] [F, E], and [Q, E] [F, E].

Rule 7: (Extraction) [F, (V1 = M1, …, Vk = Mk)].Vi = Mi. This operator is usually used to present the results of the program.

As an example, suppose P1 and P2 are Gamma programs; the following is a higher-order Gamma program iteratively executing P1 and P2:

Iter M = [Q, E1 = {[P1, M]}, E2 = F, R = {M}].R,

where Q = Q1 + Q2 + Q3.

Q1 = [M]: E1, M’ : R [P2, M]: E2, F: R M M’

Q2 = [M]: E1, M’ : R [P2, M]: E2, M: R M = M’

Q3 = [M]: E2, M’ : R [P1, M]: E1, M: R M M’

A number of simplifications are made when no ambiguity arises (Le Metayer, 1994). First, the condition part of a simple program is omitted when the condition is true. As well:

[Prog, (Var1 = Multexp1, …, Varn = Multexpn)]

can be written as

[Prog, Var1 = Multexp1, …, Varn = Multexpn]

or

[Prog, Multexp1, …, Multexpn]

and

[Var1 = Multexp1, …, Varn = Multexpn]

stands for

[ , (Var1 = Multexp1, …, Varn = Multexpn)]

Finally, we call a “simple program” a transition rule in the following sections.



 < Day Day Up > 



Designing Distributed Environments with Intelligent Software Agents
Designing Distributed Learning Environments with Intelligent Software Agents
ISBN: 1591405009
EAN: 2147483647
Year: 2003
Pages: 121

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net