INDEX to NOTES on Scheme and Implementing Scheme
Paul Wilson, University of Texas at Austin (wilson@cs.utexas.edu)

NOTE: most of these notes have been superseded by my book-in-progress
_An_Introduction_to_Scheme_and_its_Implementation_, available
as an html document via the web---it contains most of the same
material, in a much-improved presentation.

see http://www.cs.utexas.edu/users/oops/ for the new version.

---

 Copyright 1994 Paul R. Wilson

Until 1996, you may use these notes freely for noncommercial purposes, as
long as this notice is preserved in all copies.  After January 1, 1996,
you must obtain permission from the author to copy or redistribute.

-----

This directory contains files of notes (and code examples) about Scheme
and Scheme interpreters and compilers.

(You may also be interested in papers on garbage collection, persistence,
and memory hierarchies available via anonymous ftp from cs.utexas.edu
in the directory pub/garbage.  See the README file there.)

These are course notes, intended to supplement in-class lectures, but a lot
of this material can probably be absorbed by anybody who is motivated.
The explanations of most topics are detailed enough to be free-standing.

This material largely overlaps the material in Structure and Interpretation
of Computer Programs by Abelson and Sussman (with Sussman), but is pitched
toward people with some background in programming.


These notes are intended for use as a text in a programming languages
class, and as background reading for people trying to understand actual
Scheme compilers (e.g., our own RScheme compiler or the Scheme-48
compiler from the Scheme Underground).

These notes aren't necessarily in the right order or complete.  You get
what you pay for.  Eventually I may fill out the skimpy parts, make the
whole thing a little more organized, add advanced material, and call it
a book.  Until then, constructive suggestions are welcome, but don't
expect too much in the way of immediate rewrites.

Here are some file names, and descriptions, in (very approximately)
the order they should be read:

scheme.txt   talks about Scheme at an introductory level, up to writing
             a little evaluator for a tiny subset of scheme.  (For usage
             examples, you might look a the first several problems and
             solutions in prgex1.txt, below.)

prgex1.txt   Example problems in Scheme programming, with solutions
             and extensive comments.  Focuses on thinking recursively,
             and using tail recursion rather than iteration.  The first
             few problems should probably come sooner than this, and
             the last few should probably come later.

eval.txt     talks about basic issues in designing interpreters and a
             tiny bit about compilers.  This should really have more
             discussion of how the example interpreter (eval.scm, below)
             works, in detail.

eval.scm     is a simple interpreter for an interesting subset of Scheme,
             written in Scheme.  Its structure is helpful in understanding
             the meaning of Scheme expressions, as well as being helpful
             later in understanding how a compiler works.

indent.txt   is a little pedantry about proper naming and indenting of
             Scheme programs, which is important since there's not much
             syntax in the language.

scheme1b.txt talks about let, letrec, and lambda, including some programming
             examples of why they're so powerful, and introduces
             iteration with named let.

prgex2.txt   more examples of Scheme programming, with lots of notes.
             Stresses higher-order functions.

continua.txt describes continuations, Scheme's approximate equivalent
             of activation records (stack frames)

overview.scm starts with a quick review of important basic scheme topics,
             then talks about object oriented systems for a while, then
             talks about subproblems and reductions, and some advanced
             Scheme features like call-with-current-continuation.

             This file is a jumble of stuff that will eventually get moved
             elsewhere---the middle part will go with other notes on language
             design in general.

             If you don't want to take the digression about object orientation
             and type systems, you can skip to the stuff about tail recursion
             and continuations.

pairs.scm    is a simple example using the RScheme object system to define
             objects that are a lot like pairs.

queues.scm   is example code (with lots of comments) using the RScheme
             object system to implement queues.  (RScheme's object system
             is roughly a subset of Dylan's or TinyCLOS's or Meroon's.
             Eventually RScheme will have a very hip object system that
             really takes advantage of the hooks provided by the compiler.)

tasking.scm  is example code that shows how to implement simple
             cooperative multitasking in about a dozen lines of Scheme,
             using call/cc.  (Well, it's a few more than a dozen, but
             that's because I wanted it to be clear.  It also requires
             queues, like those implemented in queues.scm.)

drawing.txt  is more pedantry about visual presentation---how to draw
             data structures so that you can tell what they are.

scheme2.txt  reviews issues of binding and scoping in Scheme.  This is
             largely redundant with other stuff, but may be helpful if
             you need more examples, etc.

compiler.txt is about issues in compiling Scheme, and describes a
             fairly conventional scheme compiler.  Toward the end,
             it briefly covers some fairly advanced topics in generating
             good code for Scheme.

compiler.scm is the code for the skeleton of a fairly simple Scheme
             compiler.  It illustrates some of the major principles
             used by more serious Scheme compilers such as the RScheme
             compiler and the Scheme-48 compiler.  Eventually I intend
             to expand this to discuss advanced features of the RScheme
             compiler, such as simple closure analysis and register
             allocation, compiling to C, and compiling to threaded code.

macros.txt   discusses the use of macros, and how simple macro facilities
             can be implemented.  It also talks about scoping problems 
             with conventional macros, and briefly describes  (well, 
             mentions) modern macro systems that solve common problems.

meta.txt     Talks about metalevel programming and reflection.  (Some of
             this stuff motivated the design of RScheme, even though
             the relevant features of RScheme aren't implemented (as
             of 11/94).

rscheme.txt  describes the design of the RScheme compiler for an
             object-oriented extended Scheme.  It compiles to C using a
             different strategy than most Scheme-to-C compilers;  it is 
             compatible with copying garbage collection and pointer swizzling.

tagging.scm  talks about a space-efficient tag and header Scheme, and
             how it can support fast, general object-oriented dispatching.
             (This is likely to get implemented for RScheme, but as of
             11/94 it's just a proposal.)

dispatch.txt is some general notes on dynamic dispatching for object-oriented
             languages

rsmop.txt    documents design considerations for an RScheme object system
             and metaobject protocol.  (As of 11/94, none of this is
             implemented, and most of is not even designed in detail.)