7,482 papers · page 297 of 375
Concurrent ML (CML) is an extension of Standard ML of New Jersey with concurrent features similar to those of process algebra. In this papes we build upon John Reppy's reduction semantics for CML by constructing a compositional operational semantics for a fragment of CML, based o…
This paper describes the distributed memory implementation of a shared memory parallel functional language. The language is Id, an implicitly parallel, mostly functional language that is currently evolving into a dialect of Haskell. The target is a distributed memory machine, bec…
System kernel Fun is an abstract version of the system Fun defined by Cardelli's and Wegner's seminal paper [CW85], and is strictly related to system F≤. Extensions of these two systems are currently the basis of most proposals for strong type systems for object-oriented language…
In this paper we present a construction smoothly integrating pattern matching with abstract data types. We review some previous proposals [19, 23, 20, 6, 1] and their drawbacks, and show how our proposal can solve them. In particular we pay attention to equational reasoning about…
Projet PARA
An extension of the simply-typed lambda calculus is presented which contains both well-structured inductive and coinductive types, and which also identifies a class of types for which general recursion is possible. The motivations for this work are certain natural constructions i…
... this paper, we propose an algorithm which can automatically turn all practical recursive definitions into structural hylomorphisms making program fusion be easily applied.
Virtually every compiler performs transformations on the program it is compiling in an attempt to improve efficiency. Despite their importance, however, there have been few systematic attempts to categorise such transformations and measure their impact.In this paper we describe a…
We investigate the computational efficiency of the sharing graphs of Lamping [Lam90], Gonthier, Abadi, and Lévy [GAL92], and Asperti [Asp94], designed to effect so-called optimal evaluation, with the goal of reconciling optimality, efficiency, and the clarification of reasonable …
A context in the λ-calculus is a term with some holes. Hole filling differs from β-substitution in that name capture is intended. This seemingly simple feature transcends static scope and lies at the heart of modular and object-oriented programming. Still, the name capture featur…
We present the formal semantics of future in a Scheme-like language which has both side-effects and first-class continuations. Correctness is established by proving that programs annotated by future have the same observable behaviour as their non-annotated counterparts, even thou…
Traditional techniques for designing and analyzing amortized data structures in an imperative setting are of limited use in a functional setting because they apply only to single-threaded data structures, yet functional data structures can be non-single-threaded. In earlier work,…
This paper studies type inference for a functional, ML-style language with subtyping, and focuses on the issue of simplifying inferred constraint sets. We propose a powerful notion of entailment between constraint sets, as well as an algorithm to check it, which we prove to be so…
Nowadays the Net is one of the most obvious driving forces. Yet, to consider it as one global store through which values and code may be shared is still immature. This paper suggests first-class environments as a means to achieve that goal in a multi-user Scheme framework. We pro…
The context for this paper is functional computation by graph reduction. Our overall aim is more efficient use of memory. The specific topic is the detection of dormant cells in the live graph --- those retained in heap memory though not actually playing a useful role in computat…
A number of compilers exploit the following strategy: translate a term to continuation-passing style (CPS) and optimize the resulting term using a sequence of reductions. Recent work suggests that an alternative strategy is superior: optimize directly in an extended source calcul…
In this paper we present a new program analysis method which we call Storage Use Analysis. This analysis deduces how objects are used by the program and allows the optimization of their allocation. This analysis can be applied to both statically typed languages (e.g. ML) and late…
We have designed and implemented a program-generator generator (PGG) for an untyped higher-order functional programming language. The program generators perform continuation-based multi-level offline specialization and thus combine the most powerful and general offline partial ev…
Our purpose is to promote a second-class mechanism --- the synchronization barrier --- to a first-class value. We introduce the synchron, a novel synchronization mechanism that enables the coordination of a dynamically varying set of concurrent threads that share access to a firs…
Identifying some pointers as invisible threads, for the purposes of storage management, is a generalization from several widely used programming conventions, like threaded trees. The necessary invariant is that nodes that are accessible (without threads) emit threads only to othe…