2,199 papers · page 85 of 110
Our research is concerned with compiler-independent, tag-free garbage collection for the C++ programming language. We have previously presented a copying collector based on root registration. This paper presents a mark-and-sweep garbage collector that ameliorates shortcomings of …
Attribute grammars have been used for many language-oriented tasks, including the formal description of semantics and the implementation of compilation tasks from simple type checking through code generation. Despite their successful use, attribute grammars have some disadvantage…
This paper introduces Composable Attribute Grammars (CAGs), a formalism that extends classical attribute grammars to allow for the modular composition of translation specifications and of translators. CAGs bring to complex translator writing systems the same benefits of modularit…
We present a functional interpretation of classical linear logic based on the concept of linear continuations. Unlike their non-linear counterparts, such continuations lead to a model of control that does not inherently impose any particular evaluation strategy. Instead, such add…
Lamping discovered an optimal graph-reduction implementation of the λ-calculus. Simultaneously, Girard invented the geometry of interaction, a mathematical foundation for operational semantics. In this paper, we connect and explain the geometry of interaction and Lamping's graphs…
The notion of dominators is generalized to include multiple-vertex dominators in addition to single-vertex dominators. A multiple-vertex dominator of a vertex is a group of vertices that collectively dominate the vertex. Existing algorithms compute immediate single-vertex dominat…
Althoughthere is considerable experience in using languages that combine the functional and logic program-
Compiler generation is often emphasized as being the most important application of partial evaluation. But most of the larger practical applications have, to the best of our knowledge, been outside this field. Expecially, no one has generated compilers for languages other than sm…
We present a taxonomy of languages for multiparty interaction, which covers all proposals of which we are aware. Based on this taxonomy, we present a comprehensive analysis of the computational complexity of the multiparty interaction implementation problem, the problem of schedu…
Distributed symbolic computations involve the existence of remote references allowing an object, local to a processor, to designate another object located on another processor. To reclaim inaccessible objects is the non trivial task of a distributed Garbage Collector (GC). We pre…
This paper presents a program transformation that allows languages with polymorphic typing (e.g. ML) to be implemented with unboxed, multi-word data representations. The transformation introduces coercions between various representations, based on a typing derivation. A prototype…
We study the complexity of type inference for programming languages with subtypes. There are three language variations that effect the problem: (i) basic functions may have polymorphic or more limited types, (ii) the subtype hierarchy may be fixed or vary as a result of subtype d…
A polymorphic function is parametric if it has uniform behavior for all type parameters. This property is useful when writing, reasoning about, and compiling functional programs.
In the context of abstract interpretation we study the number of times a functional need to be unfolded in order to give the least fixed point. For the cases of the total or monotone functions we obtain an exponential bound and in the case of strict and additive (or distributive)…
Article Free Access Share on Partial evaluation of high-level imperative programming languages with applications in hard real-time systems Authors: Vivek Nirkhe View Profile , William Pugh View Profile Authors Info & Claims POPL '92: Proceedings of the 19th ACM SIGPLAN-SIGACT sym…
Polymorphic record calculi have recently attracted much attention as a typed foundation for object-oriented programming. This is based on the fact that a function that selects a field l of a record can be given a polymorphic type that enables it to be applied to various records c…
F≤ is a typed λ-calculus with subtyping and bounded second-order polymorphism. First proposed by Cardelli and Wegner, it has been widely studied as a core calculus for type systems with subtyping.
We show that any functional language with record extension possesses record concatenation for free. We exhibit a translation from the latter into the former. We obtain a type system for a language with record concatenation by composing the translation with type-checking in a lang…
Jade is a language designed to support coarse-grain parallelism on both shared and distributed address-space machines. Jade is data-oriented: a Jade programmer simply augments a sequential imperative program with declarations specifying how the program accesses data. A Jade imple…
Under the Damas-Milner type discipline for functional languages, every expression has principal type, if it elaborates at all. In the type discipline for ML Modules, a signature expression has a principal signature, if it elaborates at all. However, while functions can be higher-…