1,205 papers · page 38 of 61
We explore the use of UNITY logic in specifying and verifying fairness properties of UNITY and UNITY-like programs whose semantics can be modeled by weakly fair transition systems. For such programs, strong fairness properties in the form of “if p holds infinitely often then q al…
Program slicing is a program analysis technique that has been studied in the context of several different applications in the construction, optimization, maintenance, testing, and debugging of programs. Algorithms are available for constructing slices for a particular execution o…
The current algebraic models for nondeterminism focus on the notion of possibility rather than necessity and consequently equate (nondeterministic) terms that one would intuitively not consider equal. Furthermore, existing models for nondeterminism depart radically from the stand…
We describe a new technique for optimizing first-order functional programs. Programs are represented as graph grammars, and optimization proceeds by counterexample: when a graph generated by the grammar is found to contain an unnecessary computation, the optimizer attempts to ref…
Although the circularity test problem for attribute grammars (AGs) has been proven to be intrinsically exponential, to date, a worst case for the existing circularity test algorithms has yet to be presented. This note presents a worst-case AG in which the number of incomparable d…
Traditional methods for specifying and reasoning about concurrent systems work for real-time systems. Using TLA (the temporal logic of actions), we illustrate how they work with the examples of a queue and of a mutual-exclusion protocol. In general, two problems must be addressed…
This article presents a solution to the first-come, first-enabled ℓ-exclusion problem of Fischer et al. [1979]. Unlike their solution, this solution does not use powerful read-modify-write synchronization primitives and requires only bounded shared memory. Use of the concurrent t…
LIFE is a programming language proposing to integrate logic programming, functional programming, and object-oriented programming. It replaces first-order terms with ψ-terms, data structures that allow computing with partial information. These are approximation structures denoting…
If a compiler for language L is implemented in L , then it should be able to compile itself. But for systems used interactively commands are compiled and immediately executed, and these commands may invoke the compiler; so there is the question of how ever to cross-compile for an…
In most PROLOG implementations, for efficiency occur-check is omitted from the unification algorithm. This paper provides natural syntactic conditions that allow the occur-check to be safely omitted. The established results apply to most well-known PROLOG programs, including thos…
Two independently derived denotational semantics for Prolog are contrasted, Arbab and Berry's for the full language and Nicholson and Foo's for a databaseless language. Using the ideas suggested by the former, the latter can be easily extended to include the database operations.
This paper presents an optimized general-purpose algorithm for polyvariant, static analyses of higher-order applicative programs. A polyvariant analysis is a very accurate form of analysis that produces many more abstract descriptions for a program than does a conventional analys…
The ability to count events in a program's execution is required by many program analysis applications. We represent an instrumentation method for efficiently counting events in a program's execution, with support for on-line queries of the event count. Event counting differs fro…
This paper describes algorithms for inserting monitoring code to profile and trace programs. These algorithms greatly reduce the cost of measuring programs with respect to the commonly used technique of placing code in each basic block. Program profiling counts the number of time…
The execution of a program on a processor is viewed as a representation of that program going through a sequence of states. Each state change is manifested by the execution of a single instruction. Models that depend on this perspective are presented. The first is a static model …
LR parsing techniques have long been studied as being efficient and powerful methods for processing context-free languages. A linear-time algorithm for recognizing languages representable by LR(k) grammars has long been known. Recognizing substrings of a context-free language is …
Strictness optimizations in the implementation of lazy functional languages are not always valid. In nonoptimized graph reduction, evaluation always takes place at the request of case analysis or a primitive operation. Hence, the result of a reduction is always a data value and n…
We present a language-independent semantic model of the process of combining changes to programs. This model extends the domains used in denotational semantics (complete partial orders) to Boolean algebras, and represents incompatible modifications as well as compatible extension…
The functional programming style is increasingly popular in the research world, but functional languages still execute slowly relative to imperative languages. This is largely because the power and flexibility of functional languages restrict the amount of information readily ava…
In this article, we discuss two programming language features that have value for expressibility and efficiency: nonstrictness and nondeterminism. Our work arose while assessing ways to enhance a currently successful language, SISAL [McGraw et al. 1985]. The questions of how best…