Document Type

Article

Date

1995

Embargo Period

1-19-2012

Keywords

Algol-like languages, functional languages, imperative languages, programming languages, interference control

Language

English

Disciplines

Programming Languages and Compilers

Description/Abstract

In "Syntactic Control of Interference" (POPL, 1978), J. C. Reynolds proposes three design principles intended to constrain the scope of imperative state effects in Algol-like languages. The resulting linguistic framework seems to be a very satisfactory way of combining functional and imperative concepts, having the desirable attributes of both purely functional languages (such as pcf) and simple imperative languages (such as the language of while programs). However, Reynolds points out that the "obvious" syntax for interference control has the unfortunate property that fi-reductions do not always preserve typings. Reynolds has subsequently presented a solution to this problem (ICALP, 1989), but it is fairly complicated and requires intersection types in the type system. Here, we present a much simpler solution which does not require intersection types. We first describe a new type system inspired in part by linear logic and verify that reductions preserve typings. We then define a class of "bireflective" models, which provide a categorical analysis of structure underlying the new typing rules; a companion paper "Bireflectivity," in this volume, exposes wider ramifications of this structure. Finally, we describe a concrete model for an illustrative programming language based on the new type system; this improves on earlier such efforts in that states are not assumed to be structured using locations.

Creative Commons License

Creative Commons Attribution 3.0 License
This work is licensed under a Creative Commons Attribution 3.0 License.

Share

COinS
 
 

To view the content in your browser, please download Adobe Reader or, alternately,
you may Download the file to your hard drive.

NOTE: The latest versions of Adobe Reader do not support viewing PDF files within Firefox on Mac OS and if you are using a modern (Intel) Mac, there is no official plugin for viewing PDF files within the browser window.