Year 1990

Christian Queinnec. Reasonable Lisp. Technical Report LIX RR 90 01, 37-84, Laboratoire d'Informatique de l'École Polytechnique, January 1990.

Abstract:

This document is a trial to define a reasonable Lisp language. Its design spirit was to precisely describe a slightly extended kernel of currently used Lisps in order to provide answers to semantic questions such as evaluation order, evaluation time or evaluation environment. The main aspect of this work was to select an harmonious and efficient bunch among all interesting features that have been experimented for many years in many Lisp implementations. Many design decisions might have been far more ambitious, but we thought that it was preferable to live in a ``deterministic'' Lisp, whatever it may be, rather than in a poorly semantically defined Lisp with many trouble spots. On the other hand we tried to give a reasonable meaning to many fuzzy but useful constructs such as types, modules, macros, exceptions and threads. Care have also been taken to only design the ``run-time'' part of Lisp i.e., to clearly separate environmental features such as trace, *evalhook* or remove-method ...from execution primitives and to exclude the former features: programs must not use environmental features to be run. We put a great emphasis not to be encumbered by costly run-time data; symbols are, for instance, nearly eliminated from run-time. We also try not to reject interpretation nor the possibility of development of production environments. The form of the document is also an attempt of mixing formal semantics with description text. All essential linguistic features are described by a commented denotation. Other parts such as library functions or useful macros are not present, since they do not introduce semantical problems: they surely must be defined but the means to define them (Lisp itself) are already present in this document. This work is left to implementors or to users.

Christian Queinnec. A Framework for Data Aggregates. In Cointe et al. 13, pages 21-32.

Abstract:

The representation of data aggregates is fundamentally made of concatenation and/or repetition of smaller representations. These structurations may be arbitrarily composed to form complex aggregates of primitive representations such as characters, integers or pointers. Knowing its structuration allows the interpretation of a sequence of contiguous bits as an instance of a type represented by the given structuration. This paper presents a formalization of data representations, it identifies and analyses the features which describe primitive representations as well as representation structurers which allow to compose data representations. These features can be very naturally expressed in terms of objects, classes and methods. Our model makes structurations fully explicit: some computations can be performed on them. We will show how to derive a general data inspector and a garbage collector from them. We also present an extension of the subclass concept based on concatenation of representations. All these capabilities participate to the definition of a low level machinery for a powerful and generalized memory management.

Pierre Cointe, Philippe Gautron, and Christian Queinnec, editors. Actes des JFLA 90 - Journées Francophones des Langages Applicatifs, La Rochelle (France), January 1990. Revue Bigre+Globule 69.

Christian Queinnec. Struggle, The First Denotational Game. In EuroPal '90 - European Conference on Lisp and its Practical Applications, pages 351-361, Cambridge (UK), March 1990.

Abstract:

Games are often complex enough that new winning strategies cannot be devised without a clear and precise knowledge of the rules of the game. This situation makes games candidate to clear specifications and denotational semantics an interesting framework to specify games. This paper introduces a new game where two programs fight against each other by alteration of their code: program errors lead to death. Programs are written in a Scheme-like language with lambda, setq, prog2, if and quote special forms. Another unusual special form fork is offered which allows to run independent threads. Programs are interpreted in a very special way with continual references to the store which acts as the fighting arena. Data are restricted to functions (closures), symbols and dotted pairs. Primitives are only rplaca and rplacd. The two lattest primitives are the weapons that can alter the code structure of the opponent, conversely they can also be used to repair its own structure. Although very simple, these capabilities must be precisely defined since they are the rules of the game. To know, for instance, the number of steps taken by the execution of some construct as well as the semantics of threads is answered by the denotational semantics of the game. The paper is probably the first use of denotational semantics in the realm of games and as such may be viewed as an exercise in denotation. It also offers some insights on the meaning of the data = program equation inside interpreters. Eventually it follows the Lisp tradition and offer a world-wide arena for cleverness.

Christian Queinnec. A Subjective View of Lisp. Lisp Pointers, ACM SIGPLAN Special Interest Publication on Lisp, 3(1), January 1990.

Christian Queinnec and Julian Padget. A deterministic model for modules and macros. Bath Computing Group Technical Report 90-36, University of Bath, Bath (UK), 1990.

Abstract:

Lisp has some specialised capability for reflective operations, exemplified by its macro facility, structured name spaces, file compilation, file loading and dynamic code synthesis. There has been some progress in the last few years on the semantics of macros, but the other operations have been categorized as environmental issues. In this paper, we present a semantics for modules and will show that it substantially reduces the difficulty of defining precisely several features of usual Lisp systems such as macros, module compilation (file compilation), module loading (fasl loading) and dynamic evaluation. The module schema addresses the questions of name visibility and separate compilation. Macro-expansion is specified relative to where and how it takes place as part of operations on modules. We do not present a radical Lisp, but rather one that tries to stay within the commonly understood Lisp paradigm. We do not simply borrow from other languages -- the particular behaviour of Lisp precludes this. The semantics we have developed describes a Lisp with modules and macros enhancing portability and understandability.

Christian Queinnec. Filtrage et compilation. Revue Bigre+Globule, (70):25-36, September 1990. Actes des Journées Groplan AFCET, janvier 1990 (Nice, France).

Abstract:

Le filtrage est un important concept linguistique notamment dans le domaine des systèmes experts. C'est aussi un chapitre consacré figurant dans tous les livres célébrant Lisp. Le filtrage est largement utilisé dans les langages fonctionnels tels que ML ou Miranda^TM. Pourtant ces deux emplois sont différents puisque les langages fonctionnels mettent l'accent sur une discrimination fondée sur le type tandis que Lisp ou Plasma font usage de listes et de segments de listes au sein des filtres ou motifs. Le présent article présente un langage de filtrage ainsi que sa sémantique dénotationnelle. Ce langage, quoique réduit, est assez puissant pour exprimer les compositions booléennes de filtres, le filtrage par segments et la répétition non bornée de motifs. Un compilateur de ce langage est ensuite défini qui traduit ces filtres en un code fonctionnel. Nous présentons une esquisse des règles de typage des filtres. Ce travail, qui est assez indépendant du langage sous-jacent, rend le filtrage efficace et utile car il permet d'incorporer aux motifs une connaissance liée à la forme ou gestalt des données à traiter.

Christian Queinnec. Compilation of Non-Linear, Second Order Patterns on S-Expressions. In P Deransart and J Maluszynski, editors, Lecture Notes in Computer Science 456, pages 340-357, Linköping, August 1990. International Workshop PLILP '90 - Programming Language: Implementation and Logic Programming, Springer-Verlag.

Abstract:

Pattern matching is a key concept for rule-based expert systems. Simple pattern interpreters appear in nearly every book on Lisp. Pattern matching is also a useful tool for case analyses as provided by functional languages such as ML or Miranda^TM. These two uses are somewhat different since functional languages emphasize a discrimination based on types while Lisp, or Plasma, make use of S-expressions or segments of S-expressions within patterns. The paper presents an intermediate language for patterns and its denotational semantics. This reduced language is powerful enough to express boolean composition of patterns as well as segment handling and unbounded pattern repetition. A compiler is then defined which translates patterns into functional code. We discuss some compilation variant as well as the integration of the pattern sub-language into Lisp. These capabilities make pattern matching an useful and efficient tool for a wide class of applicative languages and allow to incorporate into patterns more knowledge about the form or gestalt of the data to be matched.

Christian Queinnec. PolyScheme : A Semantics for a Concurrent Scheme. In Workshop on High Performance and Parallel Computing in Lisp, Twickenham (UK), November 1990. European Conference on Lisp and its Practical Applications.

Abstract:

The Scheme language does not fully specify the semantics of combination: the evaluation order of the terms composing a combination is left indeterminate. We investigate in this paper a different semantics for Scheme where terms of combinations are evaluated concurrently. The resulting semantics models a language with concurrent threads sharing a common workspace. The semantics is given in terms of denotational semantics and uses resumptions as well as a choice operator: oneof which mimics a scheduler. An alternate definition for this operator lets appear the classical powerdomains. The main interest of this operator is to offer a formalization that can be read with an operational point of view while keeping a firm theoretical base. Scheme also offers first class continuations with indefinite extent; we examine some semantics for continuations with respect to concurrency. Each of these semantics is a natural extension of the sequential case of regular Scheme. Still they strongly differ in their observed behaviours. The resulting language, named PolyScheme, offers much of the features of current concurrent Lisp (or Scheme) dialects thanks to the sole extension of its combination semantics and without any explicit specialized construct dealing with concurrency.

Christian Queinnec. Le filtrage : une application de (et pour) Lisp. InterÉditions, Paris (France), 1990. [Cover page]

Pierre Cointe, Philippe Gautron, and Christian Queinnec, editors. Actes des JFLA 90 - Journées Francophones des Langages Applicatifs, La Rochelle (France), January 1990. Revue Bigre+Globule 69.