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]

3.1 Working Memory and Data

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.

3.2 Reaction Rules

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 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.

3.3 Local Order Degrees

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. 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.

3.4 Scheduling Strategies

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.

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