3. Transition rules

Q: How do you program the evolution of an evolving algebra?

A: The basic language of transition rules is very modest and even minimal in some justifiable sense. Think about static algebras as states of evolving algebras. What is a simplest atomic change of a static algebra?

Q: To change one function at one place, I guess. There are, however, other atomic changes: Adding an element to the superuniverse, removing an element from the superuniverse, adding a new basic function, removing a new basic function.

A: Adding elements to the superuniverse can be avoided with the help of Reserve. To extend a universe U, place a Reserve element a in U; technically, set U to true and Reserve to false at a . To remove an element a from U, set U(a) = false.

Q: I see. And what about adding and removing basic functions.

A: I do not believe that this is ever necessary if your EA properly formalizes the given algorithm.

Q: Suppose the algorithm is given by a program which declares new functions from time to time. This isn't unusual, right?

A: Right. But the new functions can be treated as data. For example, you may have a whole universe F of, say, unary operations on some universe U. To deal with this situation, you may have a binary basic function Apply. If f F and u U then Apply(f,u) will be the result of applying f to u.

Q: What if my program declares functions of a priori unbounded arities? Better yet, it may declare a function that takes an arbitrary number of arguments.

A: Use the usual tricks. A function with arbitrarily many arguments can be viewed as a unary function of lists, for example.

Q: Thus, your basic language allows no extension or contraction of either the signature or the superuniverse.

A: That is right. Commands of the basic language will be called transition rules or simply rules. The only primitive transition rule is a local function update of the form

f() := 

where f is (the name of) a basic function, r is the arity of f and every is a closed term. Is the meaning clear?

Q: I think so. You evaluate all terms . If is the value of then you reset f() to .

A: That is right. For brevity, let me call local function updates simply updates. A slightly more complicated rule is a guarded update

if b then u endif

where b (the guard) is any term and u is any update. If b evaluates to true on the given static algebra then perform u; otherwise do nothing. Let me stress that all evaluations are done in the given static algebra.

Q: I think you can get rid of guarded updates. Introduce a logical constant, say, Cond(x,y,z) interpreted in any static algebra as follows: If x is true then the result is y; otherwise the result is z. Then a guarded update above has exactly the same effect as the unguarded update

f() := Cond(b, , f())

A: You are right. With Cond, a guarded update is equivalent to (i.e. has exactly the same effect on any static algebra as) some unguarded update. Unfortunately, the use of Cond makes rules more difficult to read.

Q: By the way, Cond corresponds naturally to a command like this:

if b then  else  endif

A: This command, which is a legal rule as well, is equivalent to a set of two regular conditional updates:

if b then  endif
if b<>true then  endif

A set of guarded updates, written usually as a list, is executed in parallel, so that the order is immaterial. All guarded updates on the list are performed simultaneously. For example, the rule

a := f(a)  
b := f(a)  
 

sets a and b to the same value. Imagine a demon who evaluates all relevant terms in a given state and then makes the necessary changes; the result is a new state.

Q: But different guarded updates may contradict each other. For example, you may have

a := true 
b := false 
 

where a and b evaluate to the same value. Better yet, you may have

a := true 
a := false 

What is the meaning then?

A: The computation halts. The basic EA machine is deterministic. There is an extension of the basic model with explicit nondeterminism; see Subsection 4.1 in [Gu4].

Q: Why did you choose to interpret a list of rules as a set rather than a sequence? The sequence approach is more usual, it is clear, it avoids nicely the problems of contradicting updates and lends itself more naturally to the use of macros.

A: I admit that the sequence interpretation may work better in many situations though the use of guards allows one to ensure the desired sequence of actions in the set approach as well and the set interpretation has its own advantages. First, it permits a certain concurrency; this is convenient and helps to achieve a better simulation of the given algorithm. Second, the set interpretation allows a natural transition to asynchronous distributed computing, but let us stick to sequential computing for the time being.

Q: Is it difficult to define basic transition rules in full generality?

A: No. Here is the definition.

• Any local function update is a rule.
• If k is a natural number, are terms and are sets of rules then

  if  then  
  elseif  then   
    .
    .
  elseif  then   
  else   
  endif
  

  as well as

  if  then  
  elseif  then   
    .
    .
  elseif  then   
  endif
  

  is a rule.

Q: And what is a program?

A: A program is a set of rules. Recall that we deal with sequential algorithms; only a bounded amount of work is done at each step.

Q: Is the definition of sequential EAs complete?

A: No, not yet. Let us see an example.