In general runs may be affected by the environment. Suppose that the
environment manifests itself via some basic functions ,
called external functions. A typical external function is the
input provided by the user.
Think about an external function as a (dynamic) oracle. The ealgebra provides the arguments and the oracle gives the result. The oracle need not be consistent and may give different results for the same argument at different times. The seeming inconsistency may be quite natural. For example, the argument may specify an input channel. The next time around, another input can come via the same channel.
However, the oracle should be consistent during the execution of any one step of the program. In an implementation, this may be achieved by not reiterating the same question during a one-step execution. Ask the question once and, if necessary, save the result and reuse it.
The computation steps of a program are supposed to be atomic at an appropriate level of abstraction. A computation step is hardly atomic if during that step the ealgebra queries an oracle and then, depending on the result, submits another query to the same or a different oracle. Thus it seems reasonable to forbid nesting of external functions. Indeed, the need to nest external functions has not arisen in applications so far. But we withhold final judgement and wait for more experimentation.
Call non-external basic functions internal. If S is an
appropriate state for a program P , let be the reduct of S to the
internal vocabulary.