$Id: README,v 1.15 2006/12/11 21:50:33 queinnec Exp $

(((((((((((((((((((((((((((((((( L i S P ))))))))))))))))))))))))))))))))
 This file is part of the files that accompany the book:
     LISP Implantation Semantique Programmation (InterEditions, France)
 By Christian Queinnec <[email protected]>
 Newest version may be retrieved from:
      http://www-spi.lip6.fr:~queinnec/Books/LiSP-2ndEdition.tgz
(((((((((((((((((((((((((((((((( L i S P ))))))))))))))))))))))))))))))))

                           Programs of
                       Lisp in Small Pieces

                <[email protected]>


These are the source files that accompany the second French edition of
the book "Principes d'implantation de Scheme et Lisp" by Christian
Queinnec. These are roughly the same programs that were bundled with
the English edition and no effort was made to make them run with
modern Scheme systems.

Although probably not bug-free, these programs are made available as
they are. No warranty is made about these programs or their
performance. They are distributed in the hope that they will be useful
and help readers to experiment with the concepts of the associated
book.  Use and copying of this software and preparation of derivative
works based upon this software are permitted, so long as the following
conditions are met:
      o credit to the author is acknowledged according to current
        academic practices
      o no fees or compensation are charged for use, copies, or
        access to this software
      o this copyright notice is included intact.

Remember that these programs were used to build a pedagogical book. In
many places, the algorithms are not optimal and rather naive. Better
algorithms may be found in other places but are there to show
variants.  These programs contain a lot of material (more than 13
different interpreters or compilers) written with many different
styles (naive, object-oriented, continuation-passing, closure-passing,
byte-code compilation, compilation towards C, etc). The intention is
to show again and again the various facets of the semantics of
Lisp-like languages.

____________________________________________________________________________
*** SKETCH OF THE TABLE OF CONTENTS

Chapter 1: The basic interpreter (eval expression environment).

Chapter 2: Name spaces and Recursion
        Some new interpreters introducing lexical and/or dynamic binding,
        single or multiple namespaces, various brands of global environments.

Chapter 3: Escape, Continuation
        A bunch of control operators (catch/throw, block/return-from,
        unwind-protect, call/cc) all explained through an interpreter
        (eval exp env continuation) written in OO style.

Chapter 4: Side-effect
        Assignment, data mutation and equality explained through another
        interpreter (eval exp env cont memory) written with lambdas only.

Chapter 5: Denotational Semantics
        A simple currying of the previous interpreter which now appears as
        ((eval exp) env cont mem). Numerous variants such as dynamic
        binding, global environments.

Chapter 6: Fast interpretation
        Precompile expressions to speed up interpretation. Introduce
        runtime representations of environment and continuations through
        various interpreters such as
                ((eval exp lexical.env) runtime.env continuation),
                ((eval exp lexical.env) runtime.env) and finally
                ((eval exp lexical.env)).

Chapter 7: ByteCode compilation
        Compile expressions into byte-code instructions; invent registers,
        PC, stack and the like with still another compiler/interpreter
                (bytecode-run (bytecode-compile exp lexical.env))

Chapter 8: Eval and other reflective features.
        A whole chapter on eval, its implementation and cost, in all the
        previous interpreters/compilers. Also introduce first class
        environments and a complete reflective interpreter.

Chapter 9: Macros
        Everything you want to know on macros, macroexpansion, hygien etc.
        in relation with (separate) compilation and interpretation.

Chapter 10: Compilation towards C
        Another complete compiler from Scheme to C and its runtime in C.

Chapter 11: An Object System (Meroonet)
        The innards of an Object system (based on Meroon) in Scheme.

  There are also corrected exercices, a bibliography and an index.

____________________________________________________________________________
*** INSTALLATION

These files were tested with a Scheme interpreter augmented with
        a test-suite driver (tester.scm),
        the define-syntax and define-abbreviation macros (using
                Dybvig's syntax-case package),
        and an object system: Meroonet (meroonet.scm).

Bigloo, Scheme->C, Gambit, Elk or SCM can be used. The first three are
better since a specialized interpreter may be built that contains a
compiled Meroonet and compiled hygienic macros. To obtain such an
interpreter you'll have to examine the Makefile of the distribution,
mainly setup the SCHEME variable then, run `make' to regenerate this
interpreter that will appear in the o/${HOSTTYPE} directory.

Of course, on Mac, you cannot rebuild things so easily. With MacGambit
you must load or compile the gambit/book.scm file.

____________________________________________________________________________
*** CONVENTIONS

Source files are named after the chapter to which they belong. The
name of the file is built as chap<number><letters>.scm where <number>
is the number of the chapter and <letters> differentiate variants or
parts. For many of these files, there exist specific test suites with
a similar name but with a .tst extension. These files have some
dependencies that are visible in the Imakefile that shows how to load
them and test them. Most of these files have an associated test entry
in the Imakefile named test.chap<number><letters>. Test suites may
usually be run with a Scheme function named test-{scheme,chap}<number>
while interpreters may be started with a scheme<number> function.

Examples:

You want to use the OO-style interpreter of chapter 3.  Scan Makefile
for "test.chap3", you will find a line saying that chap3f contains
such an interpreter. To try this interpreter, you have to load files
src/chap3f.scm, src/chap3g.scm and src/chap3h.scm. Then, given that
tests are started with test-scheme3f, the interpreter is started with
(scheme3f). This can be confirmed by looking at the end of file
chap3f.scm. And you're done!

You now want to use the Bytecode compiler. Scan Makefile or the rest
of this file to find an occurence of `bytecode', this yields chap7d.
Look now for the `test.chap7d' entry in Makefile to discover that you
have to load files src/chap6d.scm and src/chap7d.scm. Look at the end
of src/chap7d how to run this new system: (scheme7d) is the answer.

If you want to load the compiler from Scheme towards C, then look in
the index below. You'll find that this compiler is defined in
chap10e.scm then look in the Imakefile file for the test.chap10e
entry. You'll find there that you have to load chap10a, chap10c,
chap10g, chap10e, chap10h, chap10f to obtain it. Then looking at these
files, you'll figure out how to run the compiler (Hint: look at the
show-C-expression function from the chap10f.scm file). Of course, more
documentation is given in the associated book!


____________________________________________________________________________
*** REMARKS

Bug descriptions, use reports, comments or suggestions are welcome
whether on these programs or on the book.

Send them to:                    or to:
  Christian Queinnec                     Christian Queinnec
  <[email protected]>  <[email protected]>
  Laboratoire d'Informatique de l'X      INRIA -- Rocquencourt
  Ecole Polytechnique                    Domaine de Voluceau, BP 105
  91128 Palaiseau                        78153 Le Chesnay Cedex
  France                                 France

These programs will be probably improved or revised, the latest version
might be found on:
        ftp.inria.fr:INRIA/Projects/icsla/Books/LiSP*.tar.gz
New informations can also be gleaned from
        file://ftp.inria.fr/INRIA/Projects/icsla

                        Have fun!


____________________________________________________________________________
*** INDEX

Here are the files and a brief description of their content

README file:
        This very file you are reading.

ChangeLog file:
        This file describes the changes made on these sources.

Makefile file:
        Used to regenerate intepreters with compiled Meroonet and syntax-case.
Used to load and test the various source files.

o/ directory:
        This directory will contain relocatable or executable programs
that depend on your computer. More precisely, it will contain
subdirectories for each type of machine you use. These subdirectories
are named after the HOSTTYPE shell variable usually set-up by tcsh.
I personnally use news_mips, sun4, vax and so on for HOSTTYPE.

si/ directory:
        This directory contains the files that were byte-compiled
(with the .scm extension) as well as their compiled form (with
extension .so or .out) as produced by the byte-code compiler of chapter 7.

tmp.si/ directory:
        This is a copy of the si/ directory for use by tests which may write
and alter its content.

perl/ directory:
        This directory contains little Perl script to inspect results of tests.
It is used in the Makefile for the grand.test entry. It takes hours to run
it so you probably do not need it.

bigloo/ directory:
        This directory contains the source files that are necessary to
regenerate a compiled interpreter suitable to run the programs of the
book. It will contain (in compiled form) a test-suite driver, the
syntax-case package of Hieb and Dybvig as well as Meroonet (an
object-oriented layer). It also contains format.scm from Ken Dickey,
pp.scm from Marc Feeley.

You can regenerate this interpreter by running:
        make o/${HOSTTYPE}/book.bigloo

scheme2c/ directory:
        This directory contains the source files that are necessary to
regenerate a compiled interpreter suitable to run the programs of the
book. It will contain (in compiled form) a test-suite driver, the
syntax-case package of Hieb and Dybvig as well as Meroonet (an
object-oriented layer).

You can regenerate this interpreter by running:
        make o/${HOSTTYPE}/book.sci

scm/ directory:
        This directory contains the source files that are necessary to
run SCM with all the bells and whistles needed to run the programs of
the book. It contains the syntax-case package of Hieb and Dybvig and
property list routines from Ozan Yigit.

meroonet/ directory:
        This directory contains the original distribution of Meroonet
(that can be obtained from the Scheme Repository) as well as some of the
variants suggested in exercises in chapter 11 of the book.

src/ directory:
        It is detailed chapter by chapter.

--------------- Naive interpretation
chap1.scm       a small Scheme interpreter written in a naive way.
                signature: (eval e env)
chap1.tst       tests
chap1a.scm      variants on (begin) and explicit left->right evaluation order.
chap1b.scm      naive dynamic binding
chap1c.scm      shallow binding
chap1d.scm      solutions to exercices.

--------------- Multiple namespaces
chap2a.scm      a small (naive) Lisp2 interpreter
                signature: (eval e env fenv)
chap2a.tst      tests
chap2b.scm      addition of flet, function, funcall ...
chap2b.tst      tests
chap2c.scm      dynamic variables with dynamic-let, dynamic, dynamic-set!
                signature: (eval e env fenv denv)
chap2c.tst      tests
chap2d.scm      various excerpts from chapter2 (a cyclic printer, various
                fixpoints combinators)
chap2e.scm      addition of Common-Lispy dynamic variables
chap2e.tst      tests
chap2f.scm      dynamic-variables without special forms
chap2f.tst      tests
chap2g.scm      Scheme (chap1.scm) + let,letrec,label
chap2g.tst      tests
chap2h.scm      Scheme (chap1.scm) innovation like (number e) or ((f1 f2) e)
chap2h.tst      tests

--------------- Continuations
chap3a.scm      excerpts from chapter 3
chap3a.tst      tests
chap3b.scm      other excerpts
chap3c.scm      other excerpts
chap3d.scm      other excerpts
chap3e.scm      other excerpts
chap3f.scm      An interpreter with explicit continuation (in OO style)
                signature: (eval e env k)
chap3f.tst      tests for block, catch, unwind-protect
chap3g.scm      block and catch additions to chap3f.scm
chap3h.scm      addition of unwind-protect
chap3i.scm      other excerpts
chap3j.scm      variants for chap3f.scm

--------------- Assignment and side effects
chap4.scm       excerpts from chapter 4
chap4.tst       tests
chap4a.scm      Scheme++ interpreter entirely coded with closures.
                signature: (eval e r s k)
chap4a.tst      tests

--------------- Denotational Semantics
chap5a.scm      Denotational interpreter for Scheme
                signature: ((eval e) r s k)
chap5b.scm      lambda calculus denotation
chap5b.tst      tests
chap5c.scm      denotational intepreter for Scheme and dynamic variables
chap5c.tst      tests
chap5d.scm      another denotational intepreter for Scheme
chap5e.scm      another one preserving an unspecified evaluation order
chap5e.tst      tests
chap5f.scm      delay, memo-delay and CPS
chap5g.scm      a denotational interpreter with explicit global environment
chap5g.tst      tests
chap5h.scm      exercice

--------------- Fast interpretation
chap6a.scm      fast interpreter
                signature: ((meaning e r) sr k)
chap6b.scm      automatic creation of global variable
chap6b.tst      tests
chap6c.scm      fast interpreter with a *env* register
                signature: ((meaning e r) k)
chap6d.scm      fast interpreter with generated combinators
                signature: ((meaning e r))
chap6dd.scm     Variant of chap6d.scm preallocation of activation frames
chap6dd.tst     tests
chap6e.scm      compiler to byte tree                                         *
                signature: (byte-eval (meaning e r))                          *
chap6f.scm      compiler to C (a first attempt different from chap10)         *
chap6g.scm      Variant with an explicit meaning for define
chap6g.tst      tests
chap6h.scm      Variant of chap6d on niladic functions

c/rt.h          header file for the C compiler                                *
c/rt.c          runtime library                                               *
Files marked with a star are not explained in the book, they are superseded
by chapter 10.

--------------- Compilation to bytecode (uses the fast interpreter as front-end)
chap7a.scm      Variant of chap6d with a *val* register
chap7b.scm      Explicit *stack* now
chap7c.scm      Activation frame is now in *val*
chap7d.scm      Byte-code compiler
chap7d.tst      tests
chap7e.scm      Addition of dynamic variables, error handler, bind-exit
chap7f.scm      Instruction set for the bytecode interpreter
chap7g.scm      Separate compilation stuff
chap7h.scm      Dynamic variables and error handlers with specific registers
chap7i.scm      Dynamic variables with shallow binding

--------------- Evaluation
chap8.tst       tests
chap8a.scm      eval as a special form above chap1.scm
chap8a.tst      tests
chap8b.scm      eval as a special form above chap4a.scm
chap8c.scm      eval as a special form above chap6.scmx
chap8d.scm      Patch to the byte-compiler taking care of tail position.
chap8e.scm      eval as a function in chap1.scm
chap8f.scm      eval as a function in the bytecode compiler
chap8g.scm      variant of chap1.scm
chap8h.scm      first-class environment (export) above byte-compiler
chap8h.tst      tests
chap8i.scm      first-class environment (import) above byte-compiler
chap8i.tst      tests
chap8j.scm      reflective byte-compiler (monitor, the-environment)
chap8j.tst      tests
chap8k.scm      Reflective interpreter

--------------- Macros
chap9a.scm      excerpts from chapter 9
chap9a.tst      tests
chap9b.scm      solution to exercices
chap9c.scm      objectification and low-level hygienic macroexpander
chap9c.tst      tests
chap9d.scm      quick and dirty evaluator for objectified programs
chap9e.scm      convert Programs back to Scheme aspect
chap9z.scm      other excerpts from chapter 9

Complex macro stuff may be found in the source files defining the
book.bigloo and book.sci executables that simultaneously use two
different macro systems. Meroon sources are another example.

--------------- Compilation to C
chap10a.scm     objectification of a program
chap10b.scm     interpreter for objectified programs
chap10c.scm     program transformations (free variables, lifting)
chap10d.scm     test procedures for chap10c.scm
chap10e.scm     C generation
chap10e.tst     tests
chap10ex.scm    running example to be compiled to C
chap10f.scm     test procedures for chap10e.scm
chap10g.scm     Program transformation (let variables coalescion)
chap10h.scm     Initial environment definition
chap10i.scm     Variants of chap10e.scm
chap10j.scm     Initialization analysis
chap10j.tst     tests
chap10k.scm     CPS transformation
chap10k.tst     test
chap10l.scm     test procedures for chap10k.scm

c/scheme.h      header file for C generated code
c/scheme.c      runtime in C
c/schemelib.c   initial environment for the runtime (direct style)
c/schemeklib.c  initial environment for the runtime (CPS style)

--------------- Object technology
meroonet.scm    the object system
oo-tests.scm    tests

--------------- Miscellaneous
tester.scm      test suite driver
scheme.tst      tests for regular Scheme
Imakefile       A makefile that shows how to test these previous files

*** END