Lambda-Flow: A Parallel Functional Synchronous Dataflow Language
No abstract available.
1,066 papers · page 53 of 54
Analysis and Caching of Dependencies
We address the problem of dependency analysis and caching in the context of the λ-calculus. The dependencies of a λ-term are (roughly) the parts of the λ-term that contribute to the result of evaluating it. We introduce a mechanism for keeping track of dependencies, and discuss h…
A Provable Time and Space Efficient Implementation of NESL
In this paper we prove time and space bounds for the implementation of the programming language NESL on various parallel machine models. NESL is a sugared typed λ-calculus with a set of array primitives and an explicit parallel map over arrays. Our results extend previous work on…
Synchronous Kahn Networks
Synchronous data-flow is a programming paradigm which has been successfully applied in reactive systems. In this context, it can be characterized as some class of static bounded memory data-flow networks. In particular, these networks are not recursively defined, and obey some ki…
A Probabilistic Approach to the Problem of Automatic Selection of Data Representations
The designs and implementations of efficient aggregate data structures have been important issues in functional programming. It is not clear how to select a good representation for an aggregate when access patterns to the aggregate are highly variant, or even unpredictable. Previ…
Mixin Modules
Mixin modules are proposed as a new construct for module languages, allowing recursive definitions to span module boundaries. Mixin modules are proposed specifically for the Standard ML language. Several applications are described, including the resolution of cycles in module imp…
A Theory of Weak Bisimulation for Core CML
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…
pHluid: The Design of a Parallel Functional Language Implementation on Workstations
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…
Complexity of Kernel Fun Subtype Checking
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…
A New Look to Pattern Matching in Abstract Data Types
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…
Functional Back-Ends within the Lambda-Sigma Calculus
Projet PARA
Inductive, Coinductive, and Pointed Types
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…
Deriving Structural Hylomorphisms From Recursive Definitions
... this paper, we propose an algorithm which can automatically turn all practical recursive definitions into structural hylomorphisms making program fusion be easily applied.
Let-floating: Moving Bindings to Give Faster Programs
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…
Optimality and Inefficiency: What Isn't a Cost Model of the Lambda Calculus?
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 …
Enriching the Lambda Calculus with Contexts: Toward a Theory of Incremental Program Construction
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…
The Semantics of Scheme with Future
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…
The Role of Lazy Evaluation in Amortized Data Structures
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,…
Simplifying Subtyping Constraints
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…
Sharing Code through First-class Environments
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…