Lisper, Björn (1995) Computing in Unpredictable Environments: Semantics, Reduction Strategies, and Program Transformations. [SICS Report]
We study systems where deterministic computations take place in environments which may behave nondeterministically. We give a simple formalization by unions of abstract reduction systems, on which various semantics can be based in a straightforward manner. We then prove that under a simple condition on the reduction systems, the following holds: reduction strategies which are cofinal for the deterministic reduction system will implement the semantics for the combined system, provided the environment behaves in a "fair" manner, and certain program transformations, such as folding and unfolding, will preserve the semantics. An application is evaluation strategies and program transformations for concurrent languages.
|Item Type:||SICS Report|
|Uncontrolled Keywords:||formal semantics, program transformations, nondeterminism, reduction systems, recursive program schemes|
|Deposited By:||Vicki Carleson|
|Deposited On:||22 Oct 2007|
|Last Modified:||18 Nov 2009 16:00|
Repository Staff Only: item control page