The Datafile PD-CD 3/PDCD_3.iso/utilities/utilss/siod/!Siod/Docs/siod_doc

Text File | 1993-03-01 | 22KB | 633 lines

 *                   COPYRIGHT (c) 1988-1992 BY                             *
 *        PARADIGM ASSOCIATES INCORPORATED, CAMBRIDGE, MASSACHUSETTS.       *
 *        See the source file SLIB.C for more information.                  *

Documentation for Release 2.9 21-MAR-92, George Carrette

[Release Notes:]

1.4 This release is functionally the same as release 1.3 but has been
remodularized in response to people who have been encorporating SIOD
as an interpreted extension language in other systems.

1.5 Added the -g flag to enable mark-and-sweep garbage collection.
    The default is stop-and-copy.

2.0 Set_Repl_Hooks, catch & throw.

2.1 Additions to SIOD.SCM: Backquote, cond.

2.2 User Type extension. Read-Macros. (From C-programmer level).

2.3 save-forms. load with argument t, comment character, faster intern.
    -o flag gives obarray size. default 100.

2.4 speed up arithmetic and the evaluator. fixes to siod.scm. no_interrupt
    around calls to C I/O. gen_readr.

2.5 numeric arrays in siod.c

2.6 remodularize .h files, procedure prototypes. gc, eval, print hooks
    now table-driven.

2.7 hash tables, fasload.

2.8 bug fixes.

2.9 added trace.c, fseek, ftell, some fixes.

[e-mail], [e-mail]
George Carrette


Paradigm Associates Inc          Phone: [phone]
29 Putnam Ave, Suite 6
Cambridge, MA 02138

[Files:]

 siod.h    Declarations
 siodp.h   private declarations.
 slib.c    scheme library.
 sliba.c   array library.
 siod.c    a main program.
 trace.c   an optional trace package.
 siod.scm  Some scheme code
 pratt.scm A pratt-parser in scheme.


[Motivation:]

The most obvious thing one should notice is that this lisp implementation
is extremely small. For example, the resulting binary executable file
on a VAX/VMS system with /notraceback/nodebug is 17 kilo-bytes.

Small enough to understand, the source file slib.c is 30 kilo-bytes.

Small enough to include in the smallest applications which require
command interpreters or extension languages.

We also want to be able to run code from the book "Structure and
Interpretation of Computer Programs."

Techniques used will be familiar to most lisp implementors.  Having
objects be all the same size, and having only two statically allocated
spaces simplifies and speeds up both consing and gc considerably.  the
MSUBR hack allows for a modular implementation of tail recursion,
an extension of the FSUBR that is, as far as I know, original.
The optional mark and sweep garbage collector may be selected at runtime.

Error handling is rather crude. A topic taken with machine fault,
exception handling, tracing, debugging, and state recovery which we
could cover in detail, but is clearly beyond the scope of this
implementation. Suffice it to say that if you have a good symbolic
debugger you can set a break point at "err" and observe in detail all
the arguments and local variables of the procedures in question, since
there is no casting of data types. For example, if X is an offending
or interesting object then examining X->type will give you the type,
and X->storage_as.cons will show the car and the cdr.

[Invocation:]

siod [-hXXXXX] [-iXXXXX] [-gX] [-oXXXXX] [-nXXXXX] [-sXXXXX]
 -h where XXXXX is an integer, to specify the heap size, in obj cells,
 -i where XXXXX is a filename to load before going into the repl loop.
 -g where X = 1 for stop-and-copy GC, X = 0 for mark-and-sweep.
 -o where XXXXX is the size of the symbol hash table to use, default 100.
 -n where XXXXX is the number of preconsed/interned non-negative numbers.
 -s where XXXXX is the number of bytes of machine recursion stack.

  Example:
   siod -isiod.scm -h100000

[Garbage Collection:]

There are two storage management techniques which may be chosen at runtime
by specifying the -g argument flag.

 -g1 (the default) is stop-and-copy. This is the simplest and most
     portable implementation. GC is only done at toplevel.
 -g0 is mark-and-sweep. GC is done at any time, required or requested.
     However, the implementation is not as portable.

Discussion of stop-and-copy follows:

As one can see from the source, garbage collection is really quite an easy
thing. The procedure gc_relocate is about 25 lines of code, and
scan_newspace is about 15.

The real tricks in handling garbage collection are (in a copying gc):
 (1) keeping track of locations containing objects
 (2) parsing the heap (in the space scanning)

The procedure gc_protect is called once (e.g. at startup) on each
"global" location which will contain a lisp object.

That leaves the stack. Now, if we had chosen not to use the argument
and return-value passing mechanism provided by the C-language
implementation, (also known as the "machine stack" and "machine
procedure calling mechanism) this lisp would be larger, slower, and
rather more difficult to read and understand. Furthermore it would be
considerably more painful to *add* functionality in the way of SUBR's
to the implementation.

Aside from writing a very machine and compiler specific assembling language
routine for each C-language implementation, embodying assumptions about
the placement choices for arguments and local values, etc, we
are left with the following limitation: "YOU CAN GC ONLY AT TOP-LEVEL"

However, this fits in perfectly with the programming style imposed in
many user interface implementations including the MIT X-Windows Toolkit.
In the X Toolkit, a callback or work procedure is not supposed to spend
much time implementing the action. Therefore it cannot have allocated
much storage, and the callback trampoline mechanism can post a work
procedure to call the garbage collector when needed.

Our simple object format makes parsing the heap rather trivial.
In more complex situations one ends up requiring object headers or markers
of some kind to keep track of the actual storage lengths of objects
and what components of objects are lisp pointers.

Because of the usefulness of strings, they were added by default into
SIOD 2.6. The implementation requires a hook that calls the C library
memory free procedure when an object is in oldspace and never
got relocated to newspace. Obviously this slows down the mark-and-sweep
GC, and removes one of the usual advantages it has over mark-and-sweep.

Discussion of mark-and-sweep follows:

In a mark-and-sweep GC the objects are not relocated. Instead
one only has to LOOK at objects which are referenced by the argument
frames and local variables of the underlying (in this case C-coded)
implementation procedures. If a pointer "LOOKS" like it is a valid
lisp object (see the procedure mark_locations_array) then it may be marked,
and the objects it points to may be marked, as being in-use storage which
is not linked into the freelist in the gc_sweep phase.

Another advantage of the mark_and_sweep storage management technique is
that only one heap is required.

This main disadvantages are:
(1) start-up cost to initially link freelist.
    (can be avoided by more general but slower NEWCELL code).
(2) does not COMPACT or LOCALIZE the use of storage. This is poor engineering
    practice in a virtual memory environment.
(2) the entire heap must be looked at, not just the parts with useful storage.

In general, mark-and-sweep is slower in that it has to look at more
memory locations for a given heap size, however the heap size can
be smaller for a given problem being solved. More complex analysis
is required when READ-ONLY, STATIC, storage spaces are considered.
Additionally the most sophisticated stop-and-copy storage management
techniques take into account considerations of object usage temporality.

The technique assumes that all machine registers the GC needs to
look at will be saved by a setjmp call into the save_regs_gc_mark data.

[Compilation:]

This code (version 2.7) has been compiled and run under the following:
- SUN-IV,      GCC (GNU C)
- VAX/VMS,     VAXC
- MacIntosh,   THINK C 5.0

Earlier versions were compiled and run on the AMIGA, Encore, and 4.3BSD.
There are reports that the code will also compile and run under MS-DOS.

On all unix machines use (with floating-point flags as needed)

  %cc -O -c siod.c
  %cc -O -c slib.c
  %