A Unified Treatment of Flow Analysis in Higher-Order Languages
We describe a framework for flow analysis in higher-order languages. It is both a synthesis and extension of earlier work in this area, most notably [20, 22]
7,482 papers · page 307 of 375
Structuring Depth-First Search Algorithms in Haskell
Depth-first search is the key to a wide variety of graph algorithms. In this paper we express depth-first search in a lazy functional language, obtaining a linear-time implementation. Unlike traditional imperative presentations, we use the structuring methods of functional langua…
Applicative Functors and Fully Transparent Higher-Order Modules
we present a variety of the Standard ML module system where parameterized abstract types (i.e. functors returning generative types) map provably equal arguments to compatible abstract types, instead of generating distinct types at each applications as in Standard ML. This extensi…
Monad Transformers and Modular Interpreters
We show how a set of building blocks can be used to construct programming language interpreters, and present implementations of such building blocks capable of supporting many commonly known features, including simple expressions, three different function call mechanisms (call-by…
The Geometry of Interaction Machine
We investigate implementation techniques arising directly from Girard's Geometry of Interaction semantics for Linear Logic, specifically for a simple functional programming language (PCF). This gives rise to a very simple, compact, compilation schema and run-time system. We analy…
A Type System Equivalent to Flow Analysis
Flow-based safety analysis of higher-order languages has been studied by Shivers, and Palsberg and Schwartzbach. Open until now is the problem of finding a type system that accepts exactly the same programs as safety analysis.
Obtaining Sequential Efficiency for Concurrent Object-Oriented Languages
Concurrent object-oriented programming (COOP) languages focus the abstraction and encapsulation power of abstract data types on the problem of concurrency control. In particular, pure fine-grained concurrent object-oriented languages (as opposed to hybrid or data parallel) provid…
Optimizing an ANSI C Interpreter with Superoperators
This paper introduces superoperators, an optimization technique for bytecoded interpreters. Superoperators are virtual machine operations automatically synthesized from smaller operations to avoid costly per-operation overheads. Superoperators decrease executable size and can dou…
Precise Interprocedural Dataflow Analysis via Graph Reachability
The paper shows how a large class of interprocedural dataflow-analysis problems can be solved precisely in polynomial time by transforming them into a special kind of graph-reachability problem. The only restrictions are that the set of dataflow facts must be a finite set, and th…
Using Functor Categories to Generate Intermediate Code
In the early 80's Oles and Reynolds devised a semantic model of Algol-like languages using a category of functors from a category of store shapes to the category of predomains. Here we will show how a variant of this idea can be used to define the translation of an Algol-like lan…
Isolating Side Effects in Sequential Languages
It is well known that adding side effects to functional languages changes the operational equivalences of the language. We develop a new language construct, encap, that forces imperative pieces of code to behave purely functionally, i.e., without any visible side effects. The coe…
Total Correctness by Local Improvement in Program Transformation
The goal of program transformation is to improve efficiency while preserving meaning. One of the best known transformation techniques is Burstall and Darlington's unfold-fold method. Unfortunately the unfold-fold method itself guarantees neither improvement in efficiency nor tota…
Time and Space Profiling for Non-Strict Higher-Order Functional Languages
We present the first profiler for a compiled, non-strict, higher-order, purely functional language capable of measuring time as well as space usage. Our profiler is implemented in a production-quality optimising compiler for Haskell, has low overheads, and can successfully profil…
Default Timed Concurrent Constraint Programming
We extend the model of [SJG94b] to express strong time-outs (and pre-emption): if an event A does not happen through time t, cause event B to happen at time t. Such constructs arise naturally in practice (e.g. in modeling transistors) and are supported in languages such as ESTERE…
Separation Constraint Partitioning - A New Algorithm for Partitioning Non-strict Programs into Sequential Threads
In this paper we present substantially improved thread partitioning algorithms for modern implicitly parallel languages. We present a new block partitioning algorithm, separation constraint partitioning, which is both more powerful and more flexible than previous algorithms. Our …
A Linear Time Algorithm for Placing phi-nodes
Dataflow analysis framework based on Static Single Assignment (SSA) form and Sparse Evaluation Graphs (SEGs) demand fast computation of program points where data flow information must be merged, the so-called φ-nodes. In this paper, we present a surprisingly simple algorithm for …
Structural Decidable Extensions of Bounded Quantification
We show how the subtype relation of the well-known system order theory of several successor functions (W)SnS.
Sifting Out the Gold
Integrated, dynamically-typed object-oriented programming environments offer many advantages, but have trouble producing small, self-contained applications. Recent advances in type inference have made it possible to build an application extractor for Self. The extractor was able …
Optimizing Multi-Method Dispatch Using Compressed Dispatch Tables
Optimizing method dispatch is a central issue in object-oriented language implementation. The dispatch table scheme, used for example by C++, is the only implementation of method dispatch that offers constant time performance. This property is the main asset of dispatch tables an…
Objects and Databases (Panel)
No abstract available.