Year 1992

Bernard Lang, Christian Queinnec, and José Piquer. Garbage collecting the world. In POPL '92 - Nineteenth Annual ACM symposium on Principles of Programming Languages, pages 39-50, Albuquerque (New Mexico, USA), January 1992.

Abstract:

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 present in this paper a new distributed GC algorithm which (i) is fault-tolerant, (ii) is largely independent of how a processor garbage collects its own data space, (iii) does not need centralized control nor global stop-the-world synchronization, (iv) allows for multiple concurrent active GCs, (v) does not require to migrate objects from processor to processor and (vi) eventually reclaims all inaccessible objects including distributed cycles. These results are mainly obtained through the concept of a group of processors (or processes). Processors of a same group cooperate together to a GC inside this group; this GC is conservative with respect to the outside of the group. A processor contributes to the global GC of all groups to which it belongs. Garbage collection on small groups reclaims quickly locally distributed garbage clusters, while garbage collection on large groups ultimately reclaims widely distributed garbage clusters, albeit more slowly. Groups can be reorganized dynamically, in particular to tolerate failures of some member processors. These properties make the algorithm usable on very large and evolving networks of processors. Other than distributed symbolic computations, possible applications include for example distributed file or database systems.

Christian Queinnec, editor. Actes des JFLA 92 - Journées Francophones des Langages Applicatifs, Perros-Guirec (France), February 1992. Revue Bigre+Globule 76/77.

Christian Queinnec. Compiling syntactically recursive programs. Lisp Pointers, ACM SIGPLAN Special Interest Publication on Lisp, 5(4):2-10, October-December 1992.

Abstract:

The representation of Lisp programs is based on S-expressions. Side-effects on S-expressions allied to macros allow to easily build syntactically recursive programs i.e., programs, the representation of which contains cycles. Usual compilers are defeated by these programs since they only expect regular programs i.e., programs with finite DAG-like representation. The paper proposes a program transformation that translates possibly syntactically recursive programs into equivalent regular programs. This result lessens the gap between Lisp interpreters and compilers and, in particular, allows the dynamic evaluation facility i.e., the eval function, to be fully compiler-based.

Christian Queinnec and Jean-Marie Geffroy. Partial evaluation applied to symbolic pattern matching with intelligent backtrack. In M Billaud, P Castéran, MM Corsini, K Musumbu, and A Rauzy, editors, WSA '92--Workshop on Static Analysis, number 81-82 in Revue Bigre+Globule, pages 109-117, Bordeaux (France), September 1992.

Abstract:

We present in this paper a general pattern matching algorithm which leads to a very clever pattern compiler thanks to partial evaluation. We examine some target code produced for classical patterns, and show how techniques such as Kuth-Morris-Pratt or Boyer-Moore (in the domain of string or tree matching) are automatically re-discovered by our compiler.

Christian Queinnec. A concurrent and distributed extension to scheme. In D. Etiemble and J-C. Syre, editors, PARLE '92 - Parallel Architectures and Languages Europe, pages 431-446, Paris (France), June 1992. Lecture Notes in Computer Science 605, Springer-Verlag.

Abstract:

The Lisp family of languages has traditionally been a privileged domain where linguistic experiments were done, this paper presents a new dialect offering concurrency and distribution. This dialect, nicknamed CD-Scheme, has been designed above Scheme with as few as possible features to allow a great expressiveness but still to retain the original consistency and simplicity of Scheme. We explicitly show how common parallel constructs can be written in regular CD-Scheme. A denotational semantics is also presented that expresses the detailed meaning of assignment, data mutation, continuations in presence of concurrency and distribution. This semantics offers a basis to understand new proposals of concurrent or distributed features and may be used to justify compiler optimizations or implementation techniques. The proposed set of features of CD-Scheme can be also used to extend languages other than Scheme.

Christian Queinnec. Value transforming style. In M Billaud, P Castéran, MM Corsini, K Musumbu, and A Rauzy, editors, WSA '92--Workshop on Static Analysis, number 81-82 in Revue Bigre+Globule, pages 20-28, Bordeaux (France), September 1992.

Abstract:

A new program transformation is presented that allows to remove control operators related to partial continuations. The basis for the transformation is to adopt an improved representation for continuations that makes frames apparent. Various examples of control operators with or without dynamic extent stress are presented.

Christian Queinnec. Value transforming style. Research Report LIX RR 92/07, Laboratoire d'Informatique de l'École Polytechnique, 91128 Palaiseau Cedex, France, May 1992.

Christian Queinnec. Continuation sensitive compilation. Research Report LIX RR 92/14, Laboratoire d'Informatique de l'École Polytechnique, 91128 Palaiseau Cedex, France, November 1992.

Abstract:

This paper presents a compilation technique for Scheme-like languages where functions may look at their continuation before pushing frames onto it. This allows for some optimizations when the frame to be pushed and the frame on top of the continuation can be combined into a single and simplified frame. Among possible simplifications are: intermediate data structure elimination and removal of redundant calculations. Functions can therefore be compiled with respect to their near future and reorganize it when appropriate. The compilation technique is based on an improved CPS-like transformation that makes continuation (i.e., stack) frames explicit. Shape of continuations is approximated to determine which frames would gain by being combined together then partial evaluation is used to determine the behavior of combined frames. Our main results cover local deforestation-like effect as well as iterative compilation of associatively wrapped recursions.

José M Piquer and Christian Queinnec. Transpive: A distributed lisp system. La lettre du Transputer, Laboratoire d'Informatique de Besançon, (16):55-68, December 1992.