Accession Number : ADA310837

Title :   Controlling Effects.

Descriptive Note : Doctoral thesis,

Corporate Author : CARNEGIE-MELLON UNIV PITTSBURGH PA DEPT OF COMPUTER SCIENCE

Personal Author(s) : Filinski, Andrezej

PDF Url : ADA310837

Report Date : MAY 1996

Pagination or Media Count : 145

Abstract : Many computational effects, such as exceptions, state, or nondeterminism, can be conveniently specified in terms of monads. We investigate a technique for uniformly adding arbitrary such effects to ML-like languages, without requiring any structural changes to the programs themselves. Instead, we use monadic reflection, a new language construct for explicitly converting back and forth between representations of effects as behavior and as data. Using monadic reflection to characterize concisely all effects expressible with a given monad, we can give a precise meaning to the notion of simulating one effect by another, more general one. We isolate a simple condition allowing such a simulation, and in particular show that any monadic effect can be simulated by a continuation monad. In other words, under relatively mild assumptions on the base language (allowing formation of a suitably large answer type), control becomes a universal effect. Concluding the development, we show that this universal effect can itself be explicitly implemented in terms of only standard first-class continuations (call/cc) and a piece of global state. This means that we can specify an effect such as nondeterminism abstractly, in terms of result lists, then directly obtain from this description a nondeterministic-choice operator performing imperatively-implemented backtracking. We include a full realization of the general construction in Standard ML of New Jersey, and give several programming examples.

Descriptors :   *HIGH LEVEL LANGUAGES, *CONTROL SEQUENCES, ALGORITHMS, SOFTWARE ENGINEERING, COMPUTATIONS, DATA MANAGEMENT, SEMANTICS, EFFICIENCY, THESES, INPUT OUTPUT PROCESSING, CONCURRENT ENGINEERING, CONTROL THEORY, COMPUTER PROGRAM VERIFICATION, SYNTAX, FIELDS(COMPUTER PROGRAMS), STRUCTURED PROGRAMMING.

Subject Categories : Computer Programming and Software

Distribution Statement : APPROVED FOR PUBLIC RELEASE