The Datafile PD-CD 3/PDCD_3.iso/languages/siod_v2/siod_doc

Text File | 1992-06-24 | 18KB | 522 lines

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

Documentation for Release 2.4 27-APR-90, 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.

[e-mail]
George Carrette


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

[Files:]

 siod.h    Declarations
 slib.c    scheme library.
 siod.c    a main program.
 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]
 -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.

  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.


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.

[Compilation:]

The code has been compiled and run by the author on Sun III and IV,
Encore Multimax, 4.3BSD VAX, VAX/VMS, AMIGA 500 using the Lattice C
compiler, MacIntosh using THINK C version 4.0

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

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

on VAX/VMS:

  $ cc siod
  $ cc slib
  $ link siod,slib,sys$input:/opt
  sys$library:vaxcrtl/share
  $ siod == "$" + F$ENV("DEFAULT") + "SIOD"

on AMIGA 500, ignore warning messages about return value mismatches,
  %lc siod.c
  %lc slib.c
  %blink lib:c.o,siod.o,slib.o to siod lib lib:lcm.lib,lib:lc.lib,lib:amiga.lib

in THINK C.
  The siod project must include siod.c,slib.c,siod_m.c, Mactraps, ansi, unix.


[System:]

The interrupts called SIGINT and SIGFPE by the C runtime system are
handled by invoking the lisp error procedure. SIGINT is usually caused
by the CONTROL-C character and SIGFPE by floating point overflow or underflow.

[Syntax:]

The only special characters are the parenthesis and single quote.
Everything else, besides whitespace of course, will make up a regular token.
These tokens are either symbols or numbers depending on what they look like.
Dotted-list notation is not supported on input, only on output.

[Special forms:]

The CAR of a list is evaluated first, if the value is a SUBR of type 9 or 10
then it is a special form.

(