5. Static, dynamic and external functions

Q: You speak about basic functions like a programmer; a function has a name and may change. In mathematics, a function is a particular mapping. If you set sin(1) to 1/2 then the result isn't the sin function anymore.

A: You are right. Basic functions are the current interpretations of the corresponding function names. In every state of an EA, basic functions are particular mappings, but the same function name may be interpreted differently in different states. Actually, it is convenient to distinguish between static and dynamic basic functions. The distinction is syntactical: Dynamic functions appear in function updates as subjects for updating. Static functions do not change during the evolution of the algebra whereas dynamic functions may change. In the stack machine example, for instance, the only dynamic functions are S, F, Arg1 and Arg2.

Q: I see a problem with evolving algebras. They are completely isolated. How do you deal with input, output, interrupts and other interactions of the given algorithm with the outside world? Do you want to pretend that all reactions of the outside world are written in files ahead of time?

A: Let us examine the problem. In an attempt to formalize the given algorithm as an evolving algebra, we may discover that some basic functions depend on the outside world; let f be one of them. In the case that the algorithm is given by a program, f may reflect, for example, whatever the user types at the keyboard or some activity of the operating system. I presume that f is not a subject of updating by our transition rules; in other words, f is syntactically static. Nevertheless f may have different values in different states. One way to deal with this situation is to add another argument to f which will allow us to distinguish between different evaluations. For example, we may pretend, as you said, that f reads from a file and use the position in the file as a new argument. The pretense creates the illusion that the program of an evolving algebra is the only means to change its state. This illusion may be awkward to maintain and we use the following more radical way to deal with the problem.

The basic functions of an evolving algebra A are partitioned into internal static functions (in short, static functions), internal dynamic functions (in short, dynamic functions), and external functions. External functions cannot be changed by rules of A, but they may be different in different states of A. From the point of view of A, , an external function is an oracle, an unpredictable black box that is used but not controlled by A.

Q: Let me see if I understand you. I imagine again the demon responsible for the evolution of A, the one who executes the rules. In the case of an internal function f , the demon knows exactly how to compute f . For example, he may have a fixed algorithm for computing the default version of f and a complete table to account for the deviation from the default. In the case of an external function f , the demon has an unpredictable magic box for evaluating f . Whenever he needs to evaluate f , he enters the appropriate number of arguments and miraculously gets the result.

A: That is right. From the point of view of the demon, an external function is a nondeterministic function.

Q: I guess one can have rules like

Output := t

too, right?

too, right?

A: Sure. Nothing dramatic happens in the given algebra when this rule is fired; syntactically your Output is just another distinguished element. But of course such rules are extremely important for communication. You may have several communication channels (and distinguished elements like Output-on-channel-5) and even a whole universe of channels (and a basic output function with an argument that is a channel). You may have a net of evolving algebras, but for the time being let us concentrate on a single evolving algebra (possibly communicating with the outside world).

Q: I have a question related to the types of basic functions. Formally, all r-ary basic functions are of the same type: In each state, they map the r-th power of the superuniverse to the superuniverse. It is clear, however, that you really think in terms of multiple universes and try to specify the type of basic functions in terms of universes.

A: This is very true. Essentially, we deal with many-sorted algebras though it is convenient, technically speaking, to have the superuniverse around.

Q: The case of a static function seems clear; here typing, i.e. prescribing a type, is a part of the initial state description. But what is the meaning of typing a dynamic function? Is it a declaration of intent?

A: It is an integrity constraint. Integrity constraints are statements (in indicative rather than imperative mood) that should be satisfied in any state during the evolution of a given EA. Often integrity constraints are implicit, but they can be stated explicitly. In the stack machine example, for instance, we have the following integrity constraints: Arg1 and Arg2 are data (i.e. belong to Data), F is a list, and S is a stack. It is easy to see that these four statements indeed hold in every state of the EA.

Q: Are there other kinds of integrity constraints?

A: Yes, usually we expect external functions to have values of certain types.

Q: What happens if an integrity constraint is violated?

A: The ideal machine breaks down.

Q: Do you suppose that integrity constraints constitute a part of the description of the EA?

A: This is not necessary. The effect of integrity constraints in question can be achieved by additional rules. In practice, however, an integrity constraint may be a convenient way to avoid writing boring transition rules. For example, stating a constraint that an external function f produces values of certain type allows one to avoid writing rules for what to do if f produces a value of a wrong type.