1,205 papers · page 35 of 61
In the article “On the Conversion of Indirect to Direct Recursion”( ACM Lett. Program. Lang. 2, 1-4. pp. 151-164), a method was introduced to convert indirect to direct recursion. It was claimed that for any call graph, there is a mutual-recursion elimination sequence if and only…
A relation between recursive object types, called matching , has been proposed as a generalization of subtyping. Unlike subtyping, matching does not support subsumption, but it does support inheritance of binary methods. We argue that matching is a good idea, but that it should n…
This article formally defines Eiffel dynamic binding in presence of renaming and redefinition. Message passing, inheritance, and polymorphism are expressed in an operational style using natural semantics. From the formal specification, we derive an algorithm to determine the appr…
This article presents and illustrates a practical approach to the dataflow analysis of constraint logic programming languages using abstract interpretation. It is first argued that, from the framework point of view, it suffices to propose relatively simple extensions of tradition…
Attribute grammars are a useful formalism for the specification of computations on structured terms. The classical definition of attribute grammars, however, has no way of treating conditionals nonstrictly. Consequently, the natural way of expressing many otherwise well-behaved c…
Several new attribute grammar dialects have recently been developed, all with the common goal of allowing large, complex language translators to be specified through a modular composition of smaller attribute grammars. We refer to the class of dialects as hierarchical attribute g…
Partial-evaluation folklore has it that massaging one's source programs can make them specialize better. In Jones, Gomard, and Sestoft's recent textbook, a whole chapter is dedicated to listing such “binding-time improvements”: nonstandard use of continuation-passing style, eta-e…
The efficiency of resolution-based logic programming languages, such as Prolog, depends critically on selecting and executing sets of applicable clause heads to resolve against subgoals. Traditional approaches to this problem have focused on using indexing to determine the smalle…
In task-parallel programs, diversee activities can take place concurrently, and communication and synchronization patterns are complex and not easily predictable. Previous work has identifiedcompositionalityas an important design principle for task-parallel programs. In this arti…
An important function of any register allocator is to target registers so as to eliminate copy instructions. Graph-coloring register allocation is an elegant approach to this problem. If the source and destination of a move instruction do not interfere, then their nodes can be co…
The notion of dependence captures that most important properties of a program for efficient execution on parallel computers. The dependence structure of a program defines that necessary constraints of the order of execution of the program components and provides sufficient inform…
This article defines a set of type inference rules for resolving overloading introduced by type classes, as used in the functional programming language Haskell. Programs including type classes are transformed into ones which may be typed by standard Hindley-Milner inference rules…
There are a number of schemes for handling arithmetic exceptions that can be used to improve the speed (or alternatively the reliability) of numeric code. Overflow and underflow are the most troublesome exceptions, and depending on the context in which the exception can occur, th…
Dynamically dispatched calls often limit the performance of object-oriented programs, since opject-oriented programming encourages factoring code into small, reusable units, thereby increasing the frequency of these expensive operations. Frequent calls not only slow down executio…
We consider parallel programs with shared memory and interleaving semantics, for which we show how to construct for unidirectional bitvector problems optimal analysis algorithms that are as efficient as their purely sequential counterparts and that can easily be implemented. Wher…
DSP architectures typically provide indirect addressing modes with autoincrement and decrement. In addition, indexing mode is generally not available, and there are usually few, if any, general-purpose registers. Hence, it is necessary to use address registers and perform address…
In the past decade, processor speed has become significantly faster than memory speed. Small, fast cache memories are designed to overcome this discrepancy, but they are only effective when programs exhibit data locality . In the this article, we present compiler optimizations to…
Probabilistic predicates generalize standard predicates over a state space; with probabilistic predicate transformers one thus reasons about imperative programs in terms of probabilistic pre- and postconditions. Probabilistic healthiness conditions generalize the standard ones, c…
Sather extends the notion of an iterator in a powerful new way. We argue that iteration abstractions belong in class interfaces on an equal footing with routines. Sather iterators were derived from CLU iterators but are much more flexible and better suited for object-oriented pro…
A constrained type consists of both a standard type and a constraint set. Such types enable efficient type inference for object-oriented languages with polymorphism and subtyping, as demonstrated by Eifrig, Smith, and Trifonov. Until now, it has been unclear how expressive constr…