SODA

Computing in Unpredictable Environments: Semantics, Reduction Strategies, and Program Transformations

Lisper, Björn (1995) Computing in Unpredictable Environments: Semantics, Reduction Strategies, and Program Transformations. [SICS Report]

[img]Postscript
80Kb

Abstract

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
ID Code:2147
Deposited By:Vicki Carleson
Deposited On:22 Oct 2007
Last Modified:18 Nov 2009 16:00

Repository Staff Only: item control page