Accession Number : ADA324612

Title :   The Essence of Parallel ALGOL,

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

Personal Author(s) : Brookes, Stephen

PDF Url : ADA324612

Report Date : APR 1997

Pagination or Media Count : 45

Abstract : We consider a parallel Algol-like language, combining procedures with shared variable parallelism. Procedures permit encapsulation of common parallel programming idioms. Local variables provide a way to restrict interference between parallel commands. We provide a denotational semantics for this language, simultaneously adapting 'possible worlds' to the parallel setting and generalizing "transition traces" to the procedural setting. This semantics supports reasoning about safety and liveness properties of parallel programs, and validates a number of natural laws of program equivalence based on non-interference properties of local variables. The semantics also validates familiar laws of functional programming. We also provide a relationally parametric semantics, generalizing to permit reasoning about relation-preserving properties of programs, and adapting work of O'Ilearn and Tennent to the parallel setting. This semantics supports standard methods of reasoning about representational independence adapted to shared variable programs. The clean design of the programming language and its semantics supports the orthogonality of procedures and shared variable parallelism.

Descriptors :   *PARALLEL PROCESSING, *HIGH LEVEL LANGUAGES, PARAMETRIC ANALYSIS, REASONING, COMPUTER PROGRAMMING, PROGRAMMING LANGUAGES, SEMANTICS, VARIABLES, SHARING, STANDARDIZATION, ENCAPSULATION, TRANSITIONS, ORTHOGONALITY.

Subject Categories : Computer Programming and Software

Distribution Statement : APPROVED FOR PUBLIC RELEASE