3. Computation Model CCM
A computation model called the chemical casting model (CCM) is described in this section. This model defines the microscopic behavior of computation. Its name is derived from an analogy to chemical systems.[*3.1]
The system components in CCM are shown in Figure 2. We assert that the systems we are going to treat are discrete both in space and time. The reason why they are discrete in space is that the model to be defined is a model of self-organizing symbols; symbols that humans handle are discrete, as has been pointed out in linguistics and semiotics since Saussure [Sau 49].
Figure 2. The elements of CCM
The set of data to which the rules apply is called the working memory. A unit of data in the working memory is called an atom. An atom has an internal state and may be connected to other atoms by links. Links are similar to chemical bindings, but the difference is that links (may) have directions and may have labels (link names). A set of atoms connected by links can be called a molecule.[*3.2] Any discrete data structure such as a list, tree, graph, or network can be represented using atoms and links.
Reaction rules change the state of the working memory. Thus, they define the operators. The reaction rules are written as production rules, such as chemical reaction formulae or as rules in production systems. Production rules are used for the following reasons:
- The production system is a suitable model for bottom-up computation.
What we need is a model that uses bottom-up or emergent computation. Computation in forward-chaining production systems, such as the one in OPS5 [For 81], works in a bottom-up manner. Thus, a refined production system would be a good model.
- The analogy to chemical reaction systems is useful.
We need strong analogies for self-organizing computational systems, because we are just starting research on them. The theory of self-organization [Pri 77] was developed in certain chemical reaction systems, so the analogy would give us many suggestions.
- A production system is suitable for writing incomplete programs.
A production system is a good way of describing an incomplete system. In the case of a procedural language, incomplete programs usually violate the syntax or semantics and, thus, are nonsense. On the contrary, certain incomplete programs can be interpreted in a meaningful way in a production system.
The syntax of reaction rules is similar to rules in normal production systems. The reaction rules are also similar to reaction formulae in chemical reactions. The syntax of reaction rules is as follows:
LHS --> RHS.
The left-hand side (LHS) and the right-hand side (RHS) are sequences of patterns. Each pattern matches an atom. An atom is used for matching only once in a rule application. This means that no atom matches two or more patterns on the left-hand side of a rule at once. Not only single atoms but atoms in a molecule can be matched here. The rule can be applied when there is a set of atoms that matches the LHS patterns. If the rule is applied, the matched atoms vanish and new atoms that match the RHS patterns are generated. For example, Figure 3 shows a toy rule that removes oxygen and hydrogen molecules and makes water molecules.
Figure 3. An example of a reaction rule
A pair consisting of a reaction rule and a set of atoms that can match the patterns in the rule is called an instance. An instance is said to be reacted if its rule is applied with its set of atoms. The instance is an implementation-independent concept, and is different from both the concept of an instance in conventional production systems[*3.3] and that in object-oriented systems,
A rule may be reversible. LHS and RHS can be exchanged in a reversible rule. A reversible rule is written using a bi-directional arrow: LHS <--> RHS.
Although we did not mention this above, another important condition must hold to react an instance. This is called the instance order condition. This condition is computed using local order degrees (LODs), an evaluation function.[*3.4] The existence of LODs is the most characteristic feature of CCM among production-system-based models of computation. The value of an LOD is usually an integer or a real number. LODs are defined in one of the following two forms.
- Self order degree o(e): defined for an atom e.
- Mutual order degree o(e1, e2): defined for a pair of atoms <e1, e2 >.
The sum of the LODs of the atoms matching at least one of the patterns in the rule is called the instance order degree (IOD). The instance is reacted only when the IOD is not decreased by the reaction.[*3.5] If the LOD is defined as a self order degree, the IOD is defined by the sum of the LODs of the matched atoms. The IOD before the reaction is computed and the IOD after the activation is estimated, then they are compared. The instance is activated only if the latter is larger. If the LOD is defined as a mutual order degree, the IOD is defined by the sum of the LODs of all the pairs of matched atoms. The comparison method is the same as for the self order degree.
In CCM, instances are reacted successively when possible. If there is no instance whose IOD is increased by the reaction, the system temporarily terminates. However, the system begins to work again when data in the working memory is modified or data is added and can react an instance.
The behavior of the system might not be determined uniquely by the instance order condition. This means that more than one instance can be reacted at the same time. The order of reaction is not predetermined in CCM. They may be reacted in any order, or they may be reacted in parallel, if they do not rewrite the same atom. Different orders of computation may cause different results. However, both results will be as expected, regardless of the order of computation.[*3.6] However, if two instances contain the same atom, they may not be reacted in parallel. Thus, if a set of rules is well-defined, an ordered state indirectly induced by the LODs will be organized nondeterministically and in a self-organizing manner.
The system interpreter selects the instance whose instance order condition is to be tested and which may be reacted. Although instances are selected autonomously, the user or software can control the selection macroscopically by specifying a strategy. Strategies for the selection are called scheduling strategies in CCM, because instances can be regarded as microscopic processes. Scheduling strategies are related to conflict resolution strategies in conventional production systems. The strategies can be classified as sequential strategies and parallel strategies. Four types of sequential strategies are proposed by Kanada [Kan 92a]. The following two are particularly important.
- Mathematical random strategies (MR strategies): Scheduling strategies that select instances using pseudo-random numbers or some other mathematical method of generating randomness (or noise) are called mathematical random strategies.
- Systematic strategies (S strategies): Scheduling strategies that select instances in systematic methods are called systematic strategies. Although they do not select instances randomly, they do not refer to the logic of the system, i.e., selection is made autonomously. Thus the system can still be regarded as nondeterministic.
S strategies are less computation intensive. However, they may cause limit cycles (loops). MR strategies do not cause limit cycles, even if the user pays no attention to them. This is a major merit, and thus MR strategies are regarded as the standard strategies in CCM. Parallel strategies will make CCM-based computation appears more like chemical reactions. However, these are beyond the scope of this paper.
Go to: Next section, Parent node
(C) Copyright 1994 by Yasusi Kanada and IEEE
Y. Kanada