1,205 papers · page 47 of 61
Attribute grammars are a formal notation for expressing the static semantics of programming languages—those properties that can be derived from inspection of the program text. Attribute grammars have become popular as a mechanism for generating language-based programming environm…
Designing data types in isolation is fundamentally different from designing them for integration into communities of data types, especially when inheritance is a fundamental issue. Moreover, we can distinguish between the design of families—integrated types that are variations of…
Interactive screen editors repeatedly determine terminal command sequences to update a screen row. Computing an optimal command sequence differs from the traditional sequence comparison problem in that there is a cost for moving the cursor over unedited characters and the cost of…
Dijsktra's calculus of guarded commands can be generalized and simplified by dropping the law of the excluded miracle. This paper gives a self-contained account of the generalized calculus from first principles through the semantics of recursion. The treatment of recursion uses t…
A denotational semantics is presented for the language Pro.og. Metapredicates are not considered. Conventional control sequencing is assumed for Prolog's execution. The semantics is nonstandard, and goal continuations are used to explicate the sequencing.
Several related notions of the productivity are presented for functional languages with lazy evaluation. The notion of productivity captures the idea of computability, of progress of infinite-list programs. If an infinite-list program is productive , then every element of the lis…
Abstract: Drechsler and Stadel presented a solution to a problem with Morel and Renvoise's “Global Optimization by Suppression of Partial Redundancies.” We cite some earlier generalizations of Morel and Renvoise's algorithm that solve the same problem, and we comment on their app…
Register allocation is an important optimization in many compilers, but with per-procedure register allocation, it is often not possible to make good use of a large register set. Procedure calls limit the improvement from global register allocation, since they force variables all…
A systematic representation of objects grouped into types by constructions similar to the composition of sets in mathematics is proposed. The representation is by lambda expressions, which supports the representation of objects from function spaces. The representation is related …
Atomic actions (or transactions) are useful for coping with concurrency and failures. One way of ensuring atomicity of actions is to implement applications in terms ofatomic data types: abstract data types whose objects ensure serializability and recoverability of actions using t…
SR is a language for programming distributed systems ranging from operating systems to application programs. On the basis of our experience with the initial version, the language has evolved considerably. In this paper we describe the current version of SR and give an overview of…
Action systems provide a method to program distributed systems that emphasizes the overall behavior of the system. System behavior is described in terms of the possible interactions (actions) that the processes can engage in, rather than in terms of the sequential code that the p…
A popular but “not-quite” correct technique for computing LALR(1) look-ahead sets has been formalized by DeRemer and Pennello and dubbed NQLALR(l). They also claim that the class of SLR(l) grammars is a subset of the class of NQLALR(1) grammars. We prove here that no such relatio…
A language model is presented for the specification of User Interface Management Systems. The model, called the Abstract Interaction Tool (AIT) model, offers a tree-like hierarchy of interaction objects. Each object represents a subtree and can be considered as an abstract input …
Systems semantics extends the denotational semantics of programming languages to a semantics for the description of arbitrary systems, including objects that are not computations in any sense. By defining different meaning functions, the same formal description may be used to den…
A technique for generating parsers which is an extension to LR techniques and is based on parsing table splitting, is presented. Then this technique is slightly extended to support incremental syntax analysis. Given a context-free grammar and a set “ IC ” of nonterminals devised …
It is extremely difficult to characterize the possible behaviors of a distributed software system through informal reasoning. Developers of distributed systems require tools that support formal reasoning about properties of the behaviors of their systems. These tools should be ap…
Morel and Renvoise have previously described a method for global optimization and code motion by suppression of partial redundancies [l]. Morel and Renvoise use data flow analysis to determine expression computations that should be inserted at the end of certain basic blocks and …
The problem of computing the maximum of n inputs on an asynchronous parallel computer is considered. In general, the inputs may arrive staggered in time, the number of processors available to the maximization algorithm may vary during its execution, and the number of inputs, n , …
The theory of abstract data types is generalized to the case of nondeterministic operations (set-valuedfunctions). Since the nondeterminism of operations may be coupled, signatures are extended so that operations can have results in Cartesian products. Input/output behavior is us…