2,199 papers · page 88 of 110
We present a static analysis method for determining aliasing and lifetime of dynamically allocated data in lexically scoped, higher-order, strict and polymorphic languages with first class continuations. The goal is validate program transformations that introduce imperative const…
In this paper, we introduce a new formal system, $\Lambda CCL$, based on Curien's Categorical Combinators [Cur86a]. We show that $\Lambda CCL$ has properties that make it especially suitable for analysis and implementation of a wide range of $\lambda$-reduction schemes using shar…
This paper describes a type system for Smalltalk that is type-safe, that allows most Smalltalk programs to be type-checked, and that can be used as the basis of an optimizing compiler.
The programming language Scheme contains the control construct call/cc that allows access to the current continuation (the current control context). This, in effect, provides Scheme with first-class labels and jumps. We show that the well-known formulae-as-types correspondence, w…
The purpose of this paper is to discuss the relationship between the interpretations of non-deterministic programs using the upper (total correctness) powerdomain on the one hand and the lower (partial correctness) powerdomain on the other. It is shown that there is a close seman…
In earlier work, we used a typed function calculus, XML, with dependent types to analyze several aspects of the Standard ML type system. In this paper, we introduce a refinement of XML with a clear compile-time/run-time phase distinction, and a direct compile-time type checking a…
The notion of Cartesian closure on a set of unifiers has been used to define approximations of the least models of logic programs. Such approximations, often called types, are not known to be recursive. In this paper, we use Cartesian closure to define a similar, but more accurat…
We propose a new kind of programming language, with the following features:a simple graph rewriting semantics,a complete symmetry between constructors and destructors,a type discipline for deterministic and deadlock-free (microscopic) parallelism.Interaction nets generalize Girar…
We present an algorithm for lambda expression reduction that avoids any copying that could later cause duplication of work. It is optimal in the sense defined by Lévy. The basis of the algorithm is a graphical representation of the kinds of commonality that can arise from substit…
A well known but incorrect piece of functional programming folklore is that ML expressions can be efficiently typed in polynomial time. In probing the truth of that folklore, various researchers, including Wand, Buneman, Kanellakis, and Mitchell, constructed simple counterexample…
Our exhaustive and incremental hybrid data flow analysis algorithms, based on iteration and elimination techniques, are designed for incremental update of a wide variety of monotone data flow problems in response to source program changes. Unlike previous incremental iterative me…
This paper discusses the phenomenon of method specialization in object-oriented programming languages. A typed function calculus of objects and classes is presented, featuring method specialization when methods are added or redefined. The soundness of the typing rules (without su…
In this paper we study concurrent, asynchronous processes and functions on them which can be programmed using the (full) unfair or the fair merge operations. The main result is a normal form theorem for these (relatively) “computable process functions” which implies that although…
We present a polynomial time algorithm for constructing a minimum completion time schedule of instructions from a basic block on RISC machines such as the Sun SPARC, the IBM 801, the Berkeley RISC machine, and the HP Precision Architecture. Our algorithm can be used as a heuristi…
Article Free Access Share on Parallelism in logic programs Author: Raghu Ramakrishnan Computer Sciences Department, University of Wisconsin-Madison, WI Computer Sciences Department, University of Wisconsin-Madison, WIView Profile Authors Info & Claims POPL '90: Proceedings of the…
Indexing Prolog clauses is an important optimization step that reduces the number of clauses on which unification will be performed and can avoid the pushing of a choice point. It is quite desirable to increase the number of functors used in indexing as this can considerably redu…
We present a functional language featuring a form of dynamic overloading akin to message passing in object oriented languages. We give a dynamic semantics describing a non-deterministic evaluation, as well as a type discipline (static semantics) supporting type inference. The typ…
In this paper we investigate generalizations of Kahn's principle to nondeterministic dataflow networks. Specifically, we show that for the class of "oraclizable" networks a semantic model in which networks are represented by certain sets of continuous functions is fully abstract …
This paper presents a new and very rich class of (con-current) programming languages, based on the notion of comput.ing with parhal information, and the con-commitant notions of consistency and entailment. ’ In this framework, computation emerges from the inter-action of concurre…
Use of strictness analysis in parallel evaluation and optimization of lazy functional languages is well known. The first formal treatment of strictness analysis appeared in Mycroft's seminal work which however dealt only with flat domains. Unlike flat domains, strictness analysis…