We develop am abstract model of memory management in distributed systems. The model is low-level enough so that we can express communication, allocation and garbage collection, but otherwise hides many of the lower-level details of an actual implementation.Recently, such formal models have been developed for memory management in a functional, sequential setting [10]. The models are rewriting systems whose terms are programs. Programs have both the "code" (control string) and the "store" syntactically apparent. Evaluation is expressed as conditional rewriting and includes store operations. Garbage collection becomes a rewriting relation that removes part of the store without affecting the behavior of the program.Distribution adds another dimension to an already complex problem. By using techniques developed for communicating and concurrent systems [9], we extend their work to a distributed environment. Sending and receiving messages is also made apparent at the syntactic level. A very general garbage collection rule based on reachability is introduced and proved correct. Now proving correct a specific collection strategy is reduced to showing that the relation between programs defined by the strategy is a sub-relation of the general relation. Any actual implementation which is capable of providing the transitions (including their atomicity constraints) specified by the strategy is therefore correct.This model allows us to specify and prove correct in a compact manner two garbage collectors; the first one does a simple garbage collection local to a node. The second garbage collector uses migration of data in order to be able to reclaim inter-node cyclic garbage.

This paper presents an application of partial evaluation (program specialization) techniques to concurrent programs. The language chosen for this investigation is a very simple CSP-like language. A standard binding-time analysis for imperative languages is extended in order to deal with the basic concurrent constructs (synchronous communication and nondeterministic choice). Based on the binding-time annotations, a specialization transformation is defined and proved correct. In order to maintain a simple and clear presentation, the specialization algorithm addresses only the data transfer component of the communication; partial evaluation, the way it is defined here, always generates residual synchronizations. However, a simple approximate analysis for detecting and removing redundant synchronizations from the residual program (i.e. synchronizations whose removal does not increase the nondeterminism of a program) can be performed. The paper also addresses pragmatic concerns such as improving the binding-time analysis, controlling loop unrolling and the consequences of lifting nondeterminism from run-time to specialization-time. Finally, the power of the newly developed technique is shown in several examples.

This paper describes a method for finding the least fixed points of higher-order functions over finite domains using symbolic manipulation. Fixed point finding is an essential component in the calculation of abstract semantics of functional programs, providing the foundation for program analyses based on abstract interpretation. Previous methods for fixed point finding have primarily used semantic approaches, which often must traverse large portions of the semantic domain even for simple programs. This paper provides the theoretical framework for a syntax-based analysis that is potentially very fast. The proposed syntactic method is based on an augmented simply typed lambda calculus where the symbolic representation of each function produced in the fixed point iteration is transformed to a syntactic normal form. Normal forms resulting from successive iterations are then compared syntactically to determine their ordering in the semantic domain, and to decide whether a fixed point has been reached. We show the method to be sound, complete and compositional. Examples are presented to show how this method can be used to perform strictness analysis for higher-order functions over non-flat domains. Our method is compositional in the sense that the strictness property of an expression can be easily calculated from those of its sub-expressions. This is contrary to most strictness analysers, where the strictness property of an expression has to be computed anew whenever one of its subexpressions changes. We also compare our approach with recent developments in strictness analysis.

In reference counting schemes for automatically reclaiming storage, each time a reference to a heap-allocated object is created or destroyed, the reference count of the object needs to be updated. This may involve expensive inter-processor message exchanges in distributed environments. This overhead can be reduced by analyzing the lifetimes of references to avoid unnecessary updatings. We present a compile-time analysis for higher-order functional languages that determines whether the lifetime of a reference exceeds the lifetime of the environment in which the reference was created. Using this statically inferred information, a method for optimizing reference counting schemes is described. Our method can be applied to reference counting schemes in both uniprocessor and multiprocessor environments.

This paper presents a method for statically inferring a range of information including strictness, evaluation-order, and evaluation-status information in a higher-order polymorphically-typed lazy functional language. This method is based on a compile-time analysis called order-of-demand analysis, which provides safe information about the order in which the values of bound variables are demanded. The time complexity of the analysis is substantially less than that of other approaches such as path analysis [5] and compositional analysis [7] and comparable to that of strictness analysis.

Higher order functional programs constantly allocate objects dynamically. These objects are typically cons cells, closures, and records and are generally allocated in the heap and reclaimed later by some garbage collection process. This paper describes a compile time analysis, called escape analysis, for determining the lifetime of dynamically created objects in higher order functional programs, and describes optimizations that can be performed, based on the analysis, to improve storage allocation and reclamation of such objects. In particular, our analysis can be applied to programs manipulating lists, in which case optimizations can be performed to allow cons cells in spines of lists to be either reclaimed immediately or reused without incurring any garbage collection overhead. In a previous paper on escape analysis [10], we had left open the problem of performing escape analysis on lists.

In reference counting schemes for automatically reclaiming storage, each time a reference to an object is created or destroyed, the reference count of the object needs to be updated.This may involve expensive inter-processor message exchanges in distributed environments.This overhead can be reduced by analyzing the lifetimes of references to avoid unnecessary updatings.This paper describes a technique for reducing the runtime reference counting overhead through compile-time optimization.We present a compile-time analysis called re~erence escape analysis for higher-order functional languages that determines whether the lifetime of a reference ezceeds the lifetime of the environment in which the reference was created.Using this statically inferred information, a method for optimizing reference counting schemes is described.Our method can be applied to reference counting schemes in both uniprocessor and multiprocessor environments.

With the emergence of a number of strongly typed kmguages with very dynamic storage allocation, efficient methods of storage reclamation have become especially important, Even though no type tags are required for type checking programs written in these languages, current implementations douse tags to support run time garbage collection, This often inflicts a high time and space overhead on program execution. Since the early days of LISP (and Algo168 later on), there have been schemes for performing tag-free garbage collection, In this paper, we describe an improvement of existing methods that leads to more effective storage rechunation in the absence of tags. Garbage collection has also traditionally been viewed as being independent of the particular program being executed. This means that results of compile-time analyses which could increase the effectiveness of garbage collection cannot be incorporated easily into the garbage collection process. This paper describes a method for performing garbage collection 1) in the absence of tagged data, and 2) using compile-time information. This method relies on compiler-generated garbage collection routines specific to the program bekg executed and incurs no time overhead during execution other then the cost of the garbage collection process itself. We describe tag-free garbage collection methods for monomorphically typed and polymorphically typed languages, and suggest how they might be extended to support parallel languages.

This paper describes generational reference counting, a new distributed storage reclamation scheme for loosely-coupled multiprocessors. It has a significantly lower communication overhead than distributed versions of conventional reference counting. Although generational reference counting has greater computational and space requirements than ordinary reference counting, it may provide a significant saving in overall execution time on machines in which message passing is expensive.

A general strategy for automatically decomposing and dynamically distributing a functional program is discussed. The strategy is suitable for parallel execution on multiprocessor architectures with no shared memory. It borrows ideas from data flow and reduction machine research on the one hand, and from conventional compiler technology for sequential machines on the other. One of the more troublesome issues in such a system is choosing the right granularity for the parallel tasks. As a solution, the authors describe a program transformation technique based on serial combinators that offers in some sense just the right granularity for this style of computing, and that can be fine-tuned for particular multiprocessor architectures. Simulation demonstrates the success of this approach.