Year 1989

Greg Nuyens and Christian Queinnec. Identifier Semantics: a Matter of References. Technical Report LIX RR 89 02, 67-80, Laboratoire d'Informatique de l'École Polytechnique, May 1989.

Abstract:

We present a clear semantics for identifier use. Using precise terminology, this semantics accounts for: the creation, use, modification and visibility of bindings, as well as the mention of identifiers. It covers current practice in Lisp-like languages, while incorporating features usually found outside Lisp. This semantics is shown to be viable for both Lisp$_1$ (unified function and value cell Lisp) and Lisp$_2$. A syntactic device is included which allows concise expression without sacrificing generality. The ensemble has been demonstrated in a meta-circular version, while a production version for the next release of Le-Lisp is in progress. The associated denotational semantics will figure in an annex of the full paper.

Christian Queinnec, Barbara Beaudoing, and Jean-Pierre Queille. Mark DURING Sweep rather than Mark THEN Sweep. In PARLE '89 - Parallel Architectures and Languages Europe. Lecture Notes in Computer Science 365, Springer-Verlag, June 1989.

Abstract:

Garbage Collection frees the programmer from the burden of explicitly deallocating unused data. This facility induces a considerable overhead but also causes some delays that may affect real-time applications. Guaranteed throughput (with at most short and predictable delays) is needed in many applications such as plane or plant control and requires at least a worst case analysis to identify the performances of the whole system. Traditional GC are made of two phases: the marker which identifies all useful data, followed by the sweeper which reclaims all useless data. On-the-fly GC schemes were introduced to permit an application and a collector to run concurrently. That concurrency may lessen the GC penalty incurred by the application. We present here a new algorithm where the application, the marker and the sweeper are concurrent. The benefit is to tightly adjust collection rate to application consumption and have an allocation time bounded by a small constant. Moreover our algorithm does not waste memory and appears to be well suited for embedded systems. This ``mark DURING sweep'' algorithm is completely presented. An interesting single-processor and incremental realisation is also analysed and followed by some implementation variations.

Christian Queinnec. Lisp - Almost a whole Truth. Technical Report LIX/RR/89/03, 79-106, Laboratoire d'Informatique de l'École Polytechnique, December 1989.

Abstract:

Lisp is well known for its metacircular definitions. They differ by their intent (what they want to prove), their means (what linguistic features are allowed for the definition) and by their scope (what linguistic features are described). This paper provides a new metacircular definition for a complete Lisp system including traditionally neglected features such as cons, read, print and error. The programming style adopted for this interpreter is inspired both by denotational semantics and its continuation passing style (to explain continuation handling) and by the object oriented paradigm as highlighted by type-driven generic functions. The resulting interpreter lessens the number of primitives it uses to only eight: car, cdr, rplaca, rplacd, eq, read-char, write-char and end, while still providing Scheme-like essential capabilities (less arithmetic). The overall size is near 500 lines of fully encapsulated code that, if efficiency is not the main requirement, can be easily turned into a stand alone program.

Christian Queinnec. Validation Suite Generation. Revue Bigre+Globule, (65):134-144, July 1989.

Abstract:

To validate big systems is a very complex task which has not been solved yet. Many researchers have addressed the more restricted problem of language validation but still did not succeed. One reason is the lack of a semantical definition of the language to be validated, the other reason is that such a semantics is often considered as a theoretical object unable to provide more than meanings to programs. To validate a Lisp-like system is still a large problem due to the number of its essential constructs (special forms and other unusual features like eval or multiple values) and to the size of its run-time support of which the garbage collector is the main and most complex part. However -- since Scheme has only a few features and may be considered as an efficient $lambda$-calculus, -- since $lambda$-calculus is the support of Denotational Semantics and denotational semantics for Scheme has already been published and eventually -- since the equation ``program $=$ data'' holds in Scheme, it seems therefore possible to make use of the denotational semantics of Scheme to generate validation suites. The paper will present this technique, its implementation (via streams) and some experimental results.

Christian Queinnec and Nitsan Séniak. Puzzling with current puzzles. Lisp Pointers, ACM SIGPLAN Special Interest Publication on Lisp, 2(3), January 1989.

A Pasquier, P Estève, O Roubine, C Queinnec, and V Delacour. FLTR3: Object Oriented Extensions to a Strongly Typed Real-Time Language. In TOOLS '89 -- Technology of Object-Oriented Languages and Systems, pages 115-122, Paris (France), November 1989.

A Pasquier, P Estève, O Roubine, C Queinnec, and V Delacour. FLTR3 : Extensions à objets pour un langage temps réel fortement typé. Génie Logiciel, (17):58-67, December 1989.