1,205 papers · page 48 of 61
This paper illustrates the use of Ada's abstraction facilities—notably, operator overloading and type parameterization—to define an oft-requested feature: a way to attribute units of measure to variables and values. The definition given allows the programmer to specify units of m…
We propose a method for detecting the generation of garbage cells by analyzing a source text written in a functional programming language which uses ordinary linked lists to implement list-type values. For a subexpression such as F ( G ( . . . )) in a program where the function v…
A simple calculus (the Director String Calculus-DSC) for expressing abstractions is introduced, which captures the essence of the “long reach” combinators introduced by Turner. We present abstraction rules that preserve the applicative structure of the original lambda term, and t…
A new formalism is given for read-modify-write (RMW) synchronization operations. This formalism is used to extend the memory reference combining mechanism introduced in the NYU Ultracomputer, to arbitrary RMW operations. A formal correctness proof of this combining mechanism is g…
When explicit control predicates rather than dummy variables are used, the Owicki-Gries method for proving safety properties of concurrent programs can be strengthened, making it easier to construct the required program annotations.
Many syntactic error repair strategies examine several additional symbols of input to guide the choice of a repair; a problem is determining how many symbols to examine. The goal of gathering all relevant information is discussed and shown to be impractical; instead we can gather…
There has been a great deal of research done on the evaluation of the complexity of particular algorithms; little effort, however, has been devoted to the mechanization of this evaluation. The ACE (Automatic Complexity Evaluator) system is able to analyze reasonably large program…
Abstract data type declarations appear in typed programming languages like Ada, Alphard, CLU and ML. This form of declaration binds a list of identifiers to a type with associated operations, a composite “value” we call a data algebra . We use a second-order typed lambda calculus…
Dijkstra's programming language is extended by specification statements , which specify parts of a program “yet to be developed.” A weakest precondition semantics is given for these statements so that the extended language has a meaning as precise as the original. The goal is to …
Program transformations are proposed as a means of providing fair parallelism semantics for parallel programs with shared variables. The transformations are developed in two steps. First, abstract schedulers that implement the various fairness policies are introduced. These sched…
A technique is described for software specification and verification of concurrent, distributed systems. The complete specification of a program is given in terms of a hierarchical structure of module specifications. Module external specifications are abstract; module internal sp…
An incremental update algorithm modifies the solution of a problem that has been changed, rather than re-solving the entire problem. ACINCF and ACINCB are incremental update algorithms for forward and backward data-flow analysis, respectively, based on our equations model of Alle…
Tichy's Smart Recompilation method can be made smarter by permitting benign type inconsistencies between separately compiled modules. This enhanced method helps the programmer to make far-reaching changes in small, manageable steps.
In this paper we consider an optimization problem that arises in the execution of parallel programs on shared-memory multiple-instruction-stream, multiple-data-stream (MIMD) computers. A program on such machines consists of many sequential program segments, each executed by a sin…
Schwanke and Kaiser's extension of smart recompilation is an intriguing idea. Their mechanism aims at delaying recompilation work by permitting “harmless” compilation inconsistencies to remain after changes. Full consistency can be reestablished at a later time, after the change …
Software systems represent a hierarchy of modules. Client modules contain sets of procedures that extend the capabilities of imported modules. This concept of extension is here applied to data types. Extended types are related to their ancestor in terms of a hierarchy. Variables …
The recent success of vector computers such as the Cray-1 and array processors such as those manufactured by Floating Point Systems has increased interest in making vector operations available to the FORTRAN programmer. The FORTRAN standards committee is currently considering a s…
A new programming language construct, called DOupon, subsumes Dijkstra's selective (IF) and iterative (DO) constructs. DOupon has a predicate transformer approximately equivalent in complexity to that for DO. In addition, it simplifies a wide variety of algorithms, in form as wel…
John Backus introduced the Functional Programming (FP) system, the variable-free applicative system having reduction semantics. Backus has also introduced a unique expansion technique for reasoning about a class of recursive FP programs. As a natural outgrowth of this expansion t…