Optimal Derivations in Weak Lambda-calculi and in Orthogonal Terms Rewriting Systems
We introduce the new framework of Labeled
2,199 papers · page 87 of 110
An Extension of Standard ML Modules with Subtyping and Inheritance
We describe a general module language integrating abstract data types, specifications and object-oriented concepts. The framework is based on the Standard ML module system, with three main extensions: subtyping, a form of object derived from ML structures, and inheritance primiti…
How to Make Destructive Updates Less Destructive
We present a safe embedding of mutable data structures in functional languages. With safety we mean that confluence and (in some sense) referential transparency are maintained. We develop a static criterion based on abstract interpretation which checks that any side-effect which …
Dependence Flow Graphs: An Algebraic Approach to Program Dependencies
The topic of intermediate languages for optimizing and parallelizing compilers has received muchattention lately. In this paper, we argue that any good representation of a program must havetwo crucial properties: first, it must be a data structure that can be rapidly traversed to…
Program Optimization and Parallelization Using Idioms
Programs in languages such as FORTRAN, Pascal, and which our method indeed outperforms existing analysis techniques.
Modeling Concurrency with Geometry
The phenomena of branching time and true or noninterleaving concurrency find their respective homes in automata and schedules.But these two models of computation are formally equivalent via Birkhoff duality, an equivalence we expound on here in tutorial detail.So why should these…
A Dynamic Extent Control Operator for Partial Continuations
A partial continuation is a prefix of the computation that remains to be done.We propose in this paper a new operator which precisely controls which prefix is to be abstracted into a partial continuation.This operator is strongly related to the notion of dynamic extent which we d…
Fully Abstract Translations between Functional Languages
Article Fully abstract translations between functional languages Share on Author: Jon G. Riecke MIT Laboratory for Computer Science MIT Laboratory for Computer ScienceView Profile Authors Info & Claims POPL '91: Proceedings of the 18th ACM SIGPLAN-SIGACT symposium on Principles o…
Semantic Foundations of Concurrent Constraint Programming
Concurrent constraint programming [Sar89 ,SR90] is a simple and powerful model of concurrent computation based on the notions of store-as-constraint and process as information combinators in the language, can be used for proving liveness properties of programs, and is fully abstr…
On the Power and Limitation of Strictness Analysis Based on Abstract Interpretation
Strictness analysis based on abstract interpretation is an important technique for optimization of lazy functional languages.It is well known that all strictness analysis methods are incomplete, i.e., fail to report some strictness properties.In this paper, we provide the first p…
Modeling Continuations without Continuations
Article Free Access Share on Models of continuations without continuations Authors: Dorai Sitaram Department of Computer Science, Rice University, Houston, TX Department of Computer Science, Rice University, Houston, TXView Profile , Matthias Felleisen Department of Computer Scie…
Incremental Compilation via Partial Evaluation
Article A theory of incremental computation and its application Share on Authors: R. S. Sundaresh Yale University, Department of Computer Science, Box 2158 Yale Station, New Haven, CT Yale University, Department of Computer Science, Box 2158 Yale Station, New Haven, CTView Profil…
Explicit Substitutions
The λσ-calculus is a refinement of the λ-calculus where substitutions are manipulated explicitly. The λσ-calculus provides a setting for studying the theory of substitutions, with pleasant mathematical properties. It is also a useful bridge between the classical λ-calculus and co…
Program Transformation in the Presence of Errors
Language designers and implementors have avoided specifying and preserving the meaning of programs that produce errors. This is apparently because being forced to preserve error behavior severely limits the scope of program optimization, even for correct programs. However, preser…
Implicative Formulae in the "Proofs as Computations" Analogy
In [As87] a correspondence between the subset of Linear Logic [Gi86] involving the conjunctive tensor product only and Place/Transition Petri Nets [Rei85] is established. In this correspondence, formulae are regarded as distributed states and provable sequents are computations in…
Fairness and Hyperfairness in Multi-Party Interactions
In this paper, a new fairness notion is proposed for languages with multi-party interactions as the sole interprocess synchronization and communication primitive. The main advantage of this fairness notion is the elimination of starvation occurring solely due to race conditions (…
The Chemical Abstract Machine
We introduce a new kind of abstract machine based on the chemical metaphor used in the Γ language of Banâtre & al. States of a machine are chemical solutions where floating molecules can interact according to reaction rules. Solutions can be stratified by encapsulating subsolutio…
A Relationship Between Abstract Interpretation and Projection Analysis
Abstract interpretation and projection analysis are two techniques for finding out information about lazy functional programs. Two typical uses of these techniques are speeding up sequential implementations, and the introduction of parallelism into parallel implementations.
Inheritance Is Not Subtyping
In typed object-oriented languages the subtype relation is typically based on the inheritance hierarchy. This approach, however, leads either to insecure type-systems or to restrictions on inheritance that make it less flexible than untyped Smalltalk inheritance. We present a new…
Combining Generational and Conservative Garbage Collection: Framework and Implementations
Two key ideas in garbage collection are generational collection and conservative pointer-finding. Generational collection and conservative pointer-finding are hard to use together, because generational collection is usually expressed in terms of copying objects, while conservativ…