Christian Queinnec - Lisp in Small Pieces

Lisp in Small Pieces

Christian Queinnec
Ecole Polytechnique

Translated by Kathleen Callaway

PUBLISHED BY THE PRESS SYNDICATE OF THE UNIVERSITY OF CAMBRIDGE
The Pitt Building, Trumpington Street, Cambridge, United Kingdom

CAMBRIDGE UNIVERSITY PRESS
The Edinburgh Building, Cambridge CB2 2RU, UK
40 West 20th Street, New York NY 100114211, USA
477 Williamstown Road, Port Melbourne, VIC 3207, Australia
Ruiz de Alarcn 13, 28014 Madrid, Spain
Dock House, The Waterfront, Cape Town 8001, South Africa

http://www.cambridge.org
Information on this title: www.cambridge.org/9780521562478

Christian Queinnec 1994
English Edition, Cambridge University Press 1996

This book is in copyright. Subject to statutory exception
and to the provisions of relevant collective licensing agreements,
no reproduction of any part may take place without
the written permission of Cambridge University Press.

First published in French as Les Langages Lisp by Interditions 1994

First published in English 1996
First paperback edition 2003

Translated by
Kathleen Callaway, 9 alle des Bois du Stade, 33700 Merignac, France

A catalogue record for this book is available from the British Library

ISBN 0 521 56247 3 hardback
ISBN 0 521 54566 8 paperback

E VEN though the literature about Lisp is abundant and already accessible to the reading public, nevertheless, this book still fills a need. The logical substratum where Lisp and Scheme are founded demand that modern users must read programs that use (and even abuse) advanced technology, that is, higher-order functions, objects, continuations, and so forth. Tomorrows concepts will be built on these bases, so not knowing them blocks your path to the future.

To explain these entities, their origin, their variations, this book will go into great detail. Folklore tells us that even if a Lisp user knows the value of every construction in use, he or she generally does not know its cost. This work also intends to fill that mythical hole with an in-depth study of the semantics and implementation of various features of Lisp, made more solid by more than thirty years of history.

Lisp is an enjoyable language in which numerous fundamental and non-trivial problems can be studied simply. Along with ML, which is strongly typed and suffers few side effects, Lisp is the most representative of the applicative languages. The concepts that illustrate this class of languages absolutely must be mastered by students and computer scientists of today and tomorrow. Based on the idea of function, an idea that has matured over several centuries of mathematical research, applicative languages are omnipresent in computing; they appear in various forms, such as the composition of UN*X byte streams, the extension language for the EMACS editor, as well as other scripting languages. If you fail to recognize these models, you will misunderstand how to combine their primitive elements and thus limit yourself to writing programs painfully, word by word, without a real architecture.

This book is for a wide, if specialized audience:

• to graduate students and advanced undergraduates who are studying the implementation of languages, whether applicative or not, whether interpreted, compiled, or both.
• to programmers in Lisp or Scheme who want to understand more clearly the costs and nuances of constructions theyre using so they can enlarge their expertise and produce more efficient, more portable programs.
• to the lovers of applicative languages everywhere; in this book, theyll find many reasons for satisfying reflection on their favorite language.

This book was developed in courses offered in two areas: in the graduate research program (DEA ITCP: Diplme dtudes Approfondies en Informatique Thorique, Calcul et Programmation) at the University of Pierre and Marie Curie of Paris VI; some chapters are also taught at the cole Polytechnique.

A book like this would normally follow an introductory course about an applicative language, such as Lisp, Scheme, or ML, since such a course typically ends with a description of the language itself. The aim of this book is to cover, in the widest possible scope, the semantics and implementation of interpreters and compilers for applicative languages. In practical terms, it presents no less than twelve interpreters and two compilers (one into byte-code and the other into the C programming language) without neglecting an object-oriented system (one derived from the popular MEROON). In contrast to many books that omit some of the essential phenomena in the family of Lisp dialects, this one treats such important topics as reflection, introspection, dynamic evaluation, and, of course, macros.

This book was inspired partly by two earlier works: Anatomy of Lisp [], which gave all the necessary code without hiding any details on how an operating system works and thereby gained the readers complete confidence.

In the same spirit, we want to produce a precise (rather than concise) book where the central theme is the semantics of applicative languages generally and of Scheme in particular. By surveying many implementations that explore widely divergent aspects, well explain in complete detail how any such system is built. Most of the schisms that split the community of applicative languages will be analyzed, taken apart, implemented, and compared, revealing all the implementation details. Well tell all so that you, the reader, will never be stumped for lack of information, and standing on such solid ground, youll be able to experiment with these concepts yourself.

Incidentally, all the programs in this book can be picked up, intact, electronically (details on ).

This book is organized into two parts. The first takes off from the implementation of a naive Lisp interpreter and progresses toward the semantics of Scheme. The line of development in this part is motivated by our need to be more specific, so we successively refine and redefine a series of name spaces (Lisp1, Lisp2, and so forth), the idea of continuations (and multiple associated control forms), assignment, and writing in data structures. As we slowly augment the language that were defining, well see that we inevitably pare back its defining language so that it is reduced to a kind of -calculus. We then convert the description weve gotten this way into its denotational equivalent.

Figure 1 Approximate signatures of interpreters and compilers

More than six years of teaching experience convinced us that this approach of making the language more and more precise not only initiates the reader gradually into authentic language-research, but it is also a good introduction to denotational semantics, a topic that we really cant afford to leap over.

The second part of the book goes in the other direction. Starting from denotational semantics and searching for efficiency, well broach the topic of fast interpretation (by pretreating static parts), and then well implement that preconditioning (by precompilation) for a byte-code compiler. This part clearly separates program preparation from program execution and thus handles a number of topics: dynamic evaluation ( eval ); reflective aspects (first class environments, auto-interpretable interpretation, reflective tower of interpreters); and the semantics of macros. Then we introduce a second compiler, one compiling to the C programming language.