Next: Flow graphs and semantics Up: Foundational models and abstract Previous: The tile model
Computing systems have two parts: a computational part and a descriptive part. The descriptive part specifies the environment in which the computational part is to execute, and it may be nondeterministic (e.g. asynchrony in a system with communicating processes). The computational part is most often deterministic and can be implemented in various ways, which gives opportunities for optimisations.
Traditional program transformations, like fold/unfold-transformations, are however not always correct in the presence of nondeterminism. Yet, there is a need to perform optimising transformations on programs containing an environmental part, especially if the language concepts are very high level (and thus expensive to implement). The motivation for this work is to provide a theory to support the design and implementation of languages where the computational part can be optimised as freely as possible while preserving the (possibly nondeterministic) semantics for the full system. The results are general, but the intended target is recursive languages with process constructs.
If the computational and descriptive parts (both described as rewrite
rules) commute, it is however possible to prove the validity of
unfold/fold program tranformations. This earlier work within Confer-1
has been completed during this year [Lisp98]. These
results hold under the classical condition of ``restricted
folding-unfolding'' [Cou90], which is quite
restrictive with respect to the formation of new recursive
definitions. We have made some initial investigations towards
extending the results to the particular formation of new recursive
definitions that typically occur during program specialization.
Computing in unpredictable environments: Semantics, reduction strategies, and program transformations.
Theoretical Comput. Sci., 190(1):61-85, Jan. 1998.