Education Sampler 1992 [NeXTSTEP]/Education_1992_Sampler.iso/Programming/Source/winterp-1.13/doc/XlispImpl.doc

Text File | 1991-10-06 | 42.4 KB | 1,083 lines

********************************************************************************
* (c) Copyright 1990, by Jeff Prothero.
*
* Permission to use, copy, modify, distribute, and sell this software and its
* documentation for any purpose is hereby granted without fee, provided that
* the above copyright notice appear in all copies and that both that
* copyright notice and this permission notice appear in supporting
* documentation, and that the name of Jeff Prothero and the University of
* Washington not be used in advertising or publicity pertaining to
* distribution of the software and documentation without specific, written
* prior permission.  Jeff Prothero and the University of Washington make
* no representations about the suitability of this software and documentation
* for any purpose. It is provided "as is" without express or implied warranty.
*
* JEFF PROTHERO AND THE UNIVERSITY OF WASHINGTON DISCLAIM ALL WARRANTIES WITH
* REGARD TO THIS SOFTWARE AND DOCUMENTATION, INCLUDING ALL IMPLIED WARRANTIES OF
* MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL JEFF PROTHERO AND THE UNIVERSITY
* OF WASHINGTON BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIALDAMAGES OR
* ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN
* AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR
* IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE AND DOCUMENTATION.
********************************************************************************
* Document Version: $Header: XlispImpl.doc,v 1.3 91/10/06 07:04:38 mayer Exp $
********************************************************************************

------- Forwarded Messages

Forwarded: Fri, 16 Nov 90 16:08:00 PST
Forwarded: [e-mail]
Path: hplabsz!hplabs!ucbvax!bloom-beacon!mintaka!ogicse!milton!milton.u.washington.edu!jsp
From: [e-mail] (Jeff Prothero)
Newsgroups: comp.lang.lisp.x
Subject: xlisp 2.1/winterp internals (26K long)
Message-ID: <[e-mail]>
Date: 15 Nov 90 22:56:23 GMT
Sender: [e-mail]
Distribution: comp
Organization: Biological Structure, U of Wash, Seattle
Lines: 689

I've just finished reading the xlisp 2.1 source code for the first
time.  The tutorial and reference material included with the winterp
distribution are well done, but I would have liked an overview of the
interpreter internals.  Here's a first cut at such a document.
Comments welcome...

- ---------------------------cut here-------------------------------

90Nov13 [e-mail]

                   +---------------------+
                   | xlisp 2.1 internals |
                   +---------------------+


 Who should read this?
 ---------------------

Anyone poking through the C implementation of xlisp for the first
time.  This is intended to provide a rough roadmap of the global xlisp
structures and algorithms.  If you just want to write lisp code in
xlisp, you don't need to read this file -- go read xlisp.doc,
XlispOOP.doc, and XlispRef.doc, in about that order.  If you want to
tinker with the xlisp implementation code, you should *still* read
those three before reading this.  The following isn't intended to be
exhaustively precise -- that's what the source code is for!  It is
intended only to give you sufficient orientation give you a fighting
chance to understand the code the first time through, instead of the
third time.

At the bottom of the file you'll find an example of how to add new
primitive functions to xlisp.



 What is an LVAL?
 ----------------

An "LVAL" is the C type for a generic pointer to an xlisp
garbage-collectable something.  (Cons cell, object, string, closure,
symbol, vector, whatever.)  Virtually every variable in the
interpreter is an LVAL.  Cons cells contain two LVAL slots,
symbols contains four LVAL slots, etc.



 What is the obarry?
 ------------------

The obarray is the xlisp symbol table.  More precisely, it is is a
hashtable mapping ascii strings (symbol names) to symbols.  ("obarray"
is a misnomer, since it contains only xlisp SYMBOLs, and in particular
contains no xlisp OBJECTs.)  It is used when converting lisp
expressions from text to internal form. Since it is a root for the
garbage collector, it also serves to distinguish permanent
global-variable symbols from other symbols -- you can permanently
protect a symbol from the garbage collector by entering it into the
obarray.  This is called "interning" the symbol.  The obarray is
called "obarray" in C and "*OBARRAY*" in xlisp.



 The Interpreter Stacks
 ----------------------

xlisp uses two stacks, an "evaluation stack" and an "argument stack".
Both are roots for the garbage collector.  The evaluation stack is
largely private to the interpreter and protects internal values from
garbage collection, while the argument stack holds the conventional
user-visible stackframes.


The evaluation stack is an EDEPTH-long array of "LVAL" allocated by
xldmem.c:xlminit().  It grows zeroward.

xlstkbase points to the zero-near end of the evaluation stack.

xlstktop points to the zero-far end of the evaluation stack: the
occupied part of the stack lies between xlstack and xlstktop.  NOTE
that xlstktop is *NOT* the top of the stack in the conventional sense
of indicating the most recent entry on the stack: xlstktop is a static
bounds pointer which never changes once the stack is allocated.

xlstack starts at the zero-far end of the evaluation stack.  *xlstack
is the most recent LVAL on the stack.  The garbage collector MARKs
everything reachable from the evaluation stack (among other things),
so we frequently push things on this stack while C code is
manipulating them. (Via xlsave(), xlprotect(), xlsave1(), xlprot1().)


The argument stack is an ADEPTH-long array of "LVAL".  It also grows
zeroward.  The evaluator pushes arguments on the argument stack at the
start of a function call (form evaluation).  Built-in functions
usually eat them directly off the stack.  For user-lisp functions
xleval.c:evfun() pops them off the stack and binds them to the
appropriate symbols before beginning execution of the function body
proper.

xlargstkbase is the zero-near end of argument stack.

xlargstktop is the zero-far end of argument stack.  Like xlstktop,
xlargstktop is a static bounds pointer which never changes after
the stack is allocated.

*xlsp ("sp"=="stack pointer") is the most recent item on the argument stack.

xlfp ("fp"=="frame pointer") is the base of the current stackframe.



  What is a context?
  ------------------

An xlisp "context" is something like a checkpoint, recording a
particular point buried in the execution history so that we can
abort/return back to it.  Contexts are used to implement call/return,
catch/throw, signals, gotos, and breaks.  xlcontext points to the
chain of active contexts, the top one being the second-newest active
context.  (The newest -- that is, current -- active context is
implemented by the variables xlstack xlenv xlfenv xldenv xlcontext
xlargv xlargc xlfp xlsp.)  Context records are written by
xljump.c:xlbegin() and read by xljump.c:xljump().  Context records are
C structures on the C program stack; They are not in the dynamic
memory pool or on the lisp execution or argument stacks.



  What is an environment?
  -----------------------

An environment is basically a store of symbol-value pairs, used to
resolve variable references by the lisp program.  xlisp maintains
three environments, in the global variables xlenv, xlfenv and xldenv.

xlenv and xlfenv are conceptually a single environment, although they
are implemented separately.  They are linked-list stacks which are
pushed when we enter a function and popped when we exit it.  We also
switch xlenv+xlfenf environments entirely when we begin executing a
new closure (user-fn written in lisp).

The xlenv environment is the most heavily used environment.  It is
used to resolve everyday data references to local variables.  It
consists of a list of frames (and objects).  Each frame is a list of
sym-val pairs.  In the case of an object, we check all the instance
and class variables of the object, then do the same for its
superclass, until we run out of superclasses.

The xlfenv environment is maintained strictly parallel to xlenv, but
is used to find function values instead of variable values.  The
separation may be partly for lookup speed and partly for historical
reasons.

When we send a message, we set xlenv to the value it had when the
message CLOSURE was built, then push on (obj msg-class), where
msg-class is the [super]class defining the method.  (We also set
xlfenv to the value xlfenv had when the method was built.)  This makes
the object instance variables part of the environment, and saves the
information needed to correctly resolve references to class variables,
and to implement SEND-SUPER.

The xldenv environment tracks the old values of global variables which
we have changed but intend to restore later to their original values,
particularly when we bind and unbind s_evalhook and s_applyhook
(*EVALHOOK* and *APPLYHOOK*).  (This is mostly to support the debug
facilities.)  It is a simple list of sym-val pairs,
treated as a stack.

These environments are manipulated in C via the xlisp.h macros
xlframe(e), xlbind(s,v), xlfbind(s,v), xlpbind(s,v,e), xldbind(s,v),
xlunbind(e).



  How are xlisp entities stored and identified?
  ---------------------------------------------

Conceptually, xlisp manages memory as a single array of fixed-size
objects.  Keeping all objects the same size simplifies memory
management enormously, since any object can be allocated anywhere, and
complex compacting schemes aren't needed.  Every LVAL pointer points
somewhere in this array.  Every xlisp object has the basic format
(xldmem.h:typdef struct node)

 struct node {
     char n_type;
     char n_flags;
     LVAL car;
     LVAL cdr;
 }

where n_type is one of:

 FREE     A node on the freelist.
 SUBR     A function implemented in C. (Needs evalutated arguments.)
 FSUBR    A special function implemented in C. (Needs unevaluated arguments).
 CONS     A regular lisp cons cell.
 SYMBOL   A symbol.
 FIXNUM   An integer.
 FLONUM   A floating-point number.
 STRING   A string.
 OBJECT   Any object, including class objects.
 STREAM   An input or output file.
 VECTOR      A variable-size array of LVALs.
 CLOSURE  Result of DEFUN or LAMBDA -- a function written in lisp.
 CHAR      An ascii character.
 USTREAM  An internal stream.
 STRUCT      A structure.

Messages may be sent only to nodes with n_type == OBJECT.

Obviously, several of the above types won't fit in a fixed-size
two-slot node.  The escape is to have them malloc() some memory
and have one of the slots point to it -- VECTOR is the archetype.  For
example, see xldmem.c:newvector().  To some extent, this malloc()
hack simply exports the memory- fragmentation problem to the C
malloc()/free() routines.  However, it helps keep xlisp simple, and it
has the happy side-effect of unpinning the body of the vector, so that
vectors can easily be expanded and contracted.

The garbage collector has special-case code for each of the above node
types, so it can find all LVAL slots and recycle any malloc()ed ram
when a node is garbage-collected.

Xlisp pre-allocates nodes for all ascii characters, and for small
integers.  These nodes are never garbage-collected.

As a practical matter, allocating all nodes in a single array is not
very sensible.  Instead, nodes are allocated as needed, in segments of
one or two thousand nodes, and the segments linked by a pointer chain
rooted at xldmem.c:segs.



  How are vectors implemented?
  ----------------------------

An xlisp vector is a generic array of LVAL slots.  Vectors are also
the canonical illustration of xlisp's escape mechanism for node types
which need more than two LVAL slots (the maximum possible in the
fixed-size nodes in the dynamic memory pool).  The node CAR/CDR slots
for a vector hold a size field plus a pointer to a malloc()ed ram
chunk, which is automatically free()ed when the vector is
garbage-collected.

xldmem.h defines macros for reading and writing vector fields and
slots: getsize(), getelement() and setelement().  It also defines
macros for accessing each of the other types of xlisp nodes.



  How are strings implemented?
  ----------------------------

Strings work much like vectors: The node has a pointer to a malloc()ed
ram chunk which is automatically free()ed when the string gets
garbage-collected.



 How are symbols implemented?
 ----------------------------

A symbol is a generic user-visible lisp variable, with separate slots
for print name, value, function, and property list.  Any or all of
these slots (including name) may be NIL.  You create a symbol in C by
calling "xlmakesym(name)" or "xlenter(name)" (to make a symbol and
enter it in the obarray). You create a symbol in xlisp by using the
single-quote operator: "'name", or by calling "(gensym)", or
indirectly in various ways.  Most of the symbol-specific code in the
interpreter is in xlsym.c.

Physically, a symbol is implemented like a four-slot vector.

Random musing: Abstractly, the LISP symbols plus cons cells (etc)
constitute a single directed graph, and the symbols mark spots where
normal recursive evaluation should stop.  Normal lisp programming
practice is to have a symbol in every cycle in the graph, so that
recursive traversal can be done without MARK bits.



  How are closures implemented?
  -----------------------------

A closure, the return value from a lambda, is a regular coded-in-lisp
fn.  Physically, it it implemented like an eleven-slot vector, with the
node n_type field hacked to contain CLOSURE instead of VECTOR. The
vector slots contain:

 name   symbol -- 1st arg of DEFUN.  NIL for LAMBDA closures.
 type   (s_lambda or s_macro). Must be s_lambda to be executable.
 args   List of "required" formal arguments (as symbols)
 oargs  List of "optional" args, each like: (name (default specified-p))
 rest   Name of "&rest" formal arg, else NIL.
 kargs  keyword args, each like: ((':foo 'bar default specified-p))
 aargs  &aux vars, each like: (('arg default))
 body   actual code (as lisp list) for fn.
 env    value of xlenv when the closure was built.  NIL for macros.
 fenv   value of xlfend when the closure was built. NIL for macros.
 lambda The original formal args list in the DEFUN or LAMBDA.

The lambda field is for printout purposes.  The remaining fields store
a predigested version of the formal args list.  This is a limited form
of compilation: by processing the args list at closure-creation time,
we reduce the work needed during calls to the closure.



  How are objects implemented?
  ----------------------------

An object is implemented like a vector, with the size determined by
the number of instance variables.  The first slot in the vector points
to the class of the object; the remaining slots hold the instance
variables for the object.  An object needs enough slots to hold all
the instance variables defined by its class, *plus* all the instance
variables defined by all of its superclasses.



  How are classes implemented?
  ----------------------------

A class is a specific kind of object, hence has a class pointer plus
instance variables.  All classes have the following instance variables:

 MESSAGES   A list of (interned-symbol method-closure) pairs.
 IVARS        Instance variable names: A list of interned symbols.
 CVARS      Class variable names:    A list of interned symbols.
 CVALS      Class variable values:   A vector of values.
 SUPERCLASS A pointer to the superclass.
 IVARCNT    Number of class instance variables, as a fixnum.
 IVARTOTAL  Total number of instance variables, as a fixnum.

IVARCNT is the count of the number of instance variables defined by
our class.  IVARTOTAL is the total number of instance variables in an
object of this class -- IVARCNT for this class plus the IVARCNTs from
all of our superclasses.




  How is the class hierarchy laid out?
  ------------------------------------

The fundamental objects are the OBJECT and CLASS class objects.  (Both
are instances of class CLASS, and since CLASSes are a particular kind
of OBJECT, both are also objects, with n_type==OBJECT.  Bear with me!)

OBJECT is the root of the class hierarchy: everything you can send a
message to is of type OBJECT.  (Vectors, chars, integers and so forth
stand outside the object hierarchy -- you can't send messages to them.
I'm not sure why Dave did it this way.) OBJECT defines the messages:

 :isnew -- Does nothing
 :class -- Returns contents of class-pointer slot.
 :show  -- Prints names of obj, obj->class and instance vars.

A CLASS is a specialized type of OBJECT (with instance variables like
MESSAGES which generic OBJECTs lack), class CLASS hence has class
OBJECT as its superclass.  The CLASS object defines the messages:

 :new     -- Create new object with self.IVARTOTAL LVAR slots, plus
            one for the class pointer. Point class slot to self.
            Set new.n_type char to OBJECT.
 :isnew     -- Fill in IVARS, CVARS, CVALS, SUPERCLASS, IVARCNT and
            IVARTOTAL, using parameters from :new call.  (The
            :isnew msg inherits the :new msg parameters because
            the  :isnew msg is generated automatically after
            each :new   msg, courtesy of a special hack in
            xlobj.c:sendmsg().)
 :answer -- Add a (msg closure) pair to self.MESSAGES.



Here's a figure to summarize the above, with a generic object thrown
in for good measure.  Note that all instances of CLASS will have a
SUPERCLASS pointer, but no normal object will.  Note also that the
messages known to an object are those which can be reached by
following exactly one Class Ptr and then zero or more Superclass Ptrs.
For example, the generic object can respond to :ISNEW, :CLASS and
:SHOW, but not to :NEW or :ANSWER.  (The functions implementing the
given messages are shown in parentheses.)

                    NIL
                     ^
                     |
                     |Superclass Ptr
                     |
                Msg+--------+
 :isnew (xlobj.c:obisnew) <----|  class |Class Ptr
 :class (xlobj.c:obclass) <----| OBJECT |------------+
 :show    (xlobj.c:objshow) <----|        |            |
                   +--------+            |
       +---------+                ^  ^               |
       | generic |Class Ptr       |  |               |
       | object  |----------------+  |Superclass Ptr |
       +---------+             |               |
                Msg+--------+            |
 :isnew    (xlobj.c:clnew)      <----| class  |Class Ptr   |
 :new    (xlobj.c:clisnew) <----| CLASS  |--------+   |
 :answer(xlobj.c:clanswer)<----|        |        |   |
                   +--------+        |   |
                  ^  ^           |   |
                  |  |           |   |
                  |  +-----------+   |
                  +------------------+


Thus, class CLASS inherits the :CLASS and :SHOW messages from class
OBJECT, overrides the default :ISNEW message, and provides new the
messages :NEW and :ANSWER.

New classes are created by (send CLASS :NEW ...) messages.  Their
Class Ptr will point to CLASS.  By default, they will have OBJECT as
their superclass, but this can be overridden by the second optional
argument to :NEW.

The above basic structure is set up by xlobj.c:xloinit().



  How do we look up the value of a variable?
  ------------------------------------------

When we're cruising along evaluating an expression and encounter a
symbol, the symbol might refer to a global variable, an instance
variable, or a class variable in any of our superclasses.  Figuring
out which means digging throught the environment.  The canonical place
this happens is in xleval.c:xleval(), which simply passes the buck to
xlsym.c:xlgetvalue(), which in turn passes the buck to
xlxsym.c:xlxgetvalue(), where the fun of scanning down xlenv begins.
The xlenv environment looks something like

     Backbone    Environment frame contents
     --------    --------------------------
xlenv --> frame      ((sym val) (sym val) (sym val) ... )
      frame      ...
      object     (obj msg-class)
      frame      ...
      object     ...
      frame      ...
      ...

The "frame" lines are due to everyday nested constructs like LET
expressions, while the "object" lines represent an object environment
entered via a message send.  xlxgetvalue scans the enviroment left to
right, and then top to bottom.  It scans down the regular environment
frames itself, and calls xlobj.c:xlobjgetvalue() to search the object
environment frames.

xlobjgetvalue() first searches for the symbol in the msg-class, then
in all the successive superclasses of msg-class.  In each class, it
first checks the list of instance-variable names in the IVARS slot,
then the list of class-variables name in the CVARS slot.



  How are function calls implemented?
  -----------------------------------

xleval.c contains the central expression-evaluation code.
xleval.c:xleval() is the standard top-level entrypoint.  The two
central functions are xleval.c:xlevform() and xleval.c:evfun().
xlevform() can evaluate four kinds of expression nodes:

SUBR: A normal primitive fn coded in C.  We call evpushargs() to
evaluate and push the arguments, then call the primitive.

FSUBR: A special primitive fn coded in C, which (like IF) wants its
arguments unevaluated.  We call pushargs() (instead of evpushargs())
and then the C fn.

CLOSURE: A preprocessed written-in-lisp fn from a DEFUN or LAMBDA.  We
call evpushargs() and then evfun().

CONS: We issue an error if it isn't a LAMBDA, otherwise we call
xleval.c:xlclose() to build a CLOSURE from the LAMBDA, and fall into
the CLOSURE code.

The common thread in all the above cases is that we call evpushargs()
or pushargs() to push all the arguments on the evaluation stack,
leaving the number and location of the arguments in the global
variables xlargc and xlargv.  The primitive C functions consume
their arguments directly from the argument stack.

xleval.c:evfun() evaluates a CLOSURE by:

(1) Switching xlenv and xlfenv to the values they had when
the CLOSURE was built. (These values are recorded in the CLOSURE.)

(2) Binding the arguments to the environment.  This involves scanning
through the section of the argument stack indicated by xlargc/xlargv,
using information from the CLOSURE to resolve keyword arguments
correctly and assign appropriate default values to optional arguments,
among other things.

(3) Evaluating the body of the function via xleval.c:xleval().

(4) Cleaning up and restoring the original environment.



  How are message-sends implemented?
  ----------------------------------

We scan the MESSAGES list in the CLASS object of the recipient,
looking for a (message-symbol method) pair that matches our message
symbol.  If necessary, we scan the MESSAGES lists of the recipients
superclasses too.  (xlobj.c:sendmsg().)  Once we find it, we basically
do a normal function evaluation. (xlobjl.c:evmethod().)  Two oddities:
We need to replace the message-symbol by the recipient on the argument
stack to make things look normal, and we need to push an 'object'
stack entry on the xlenv environment so we remember which class is
handling the message.



  How is garbage collection implemented?
  --------------------------------------

The dynamic memory pool managed by xlisp consists of a chain of memory
*segments* rooted at global C variable "segs".  Each segment contains
an array of "struct node"s plus a pointer to the next segment.  Each
node contains a n_type field and a MARK bit, which is zero except
during garbage collection.

Xlisp uses a simple, classical mark-and-sweep garbage collector.  When
it runs out of memory (fnodes==NIL), it does a recursive traversal
setting the MARK flag on all nodes reachable from the obarray, the
three environments xlenv/xlfenv/xldenv, and the evaluation and
argument stacks.  (A "switch" on the n_type field tells us how to find
all the LVAL slots in the node (plus associated storage), and a
pointer-reversal trick lets us avoid using too much stack space during
the traversal.)  sweep() then adds all un-MARKed LVALs to fnodes, and
clears the MARK bit on the remaining nodes.  If this fails to produce
enough free nodes, a new segment is malloc()ed.

The code to do this stuff is mostly in xldmem.c.



 How do I add a new primitive fn to xlisp?
 -----------------------------------------

Add a line to the end of xlftab.c:funtab[].  This table contains a
list of triples:

The first element of each triple is the function name as it will
appear to the programmer. Make it all upper case.

The second element is S (for SUBR) if (like most fns) your function
wants its arguments pre-evaluated, else F (for FSUBR).

The third element is the name of the C function to call.

Remember that your arguments arrive on the xlisp argument rather
than via the usual C parameter mechanism.

CAUTION: Try to keep your files separate from generic xlisp files, and
to minimize the number of changes you make in the generic xlisp files.
This way, you'll have an easier time re-installing your changes when
new versions of xlisp come out.  It's a good idea to put a marker
(like a comment with your initials) on each line you change or insert
in the generic xlisp fileset.  For example, if you are going to add
many primitive functions to your xlisp, use an #include file rather
than putting them all in xlftab.c.

CAUTION: Remember that you usually need to protect the LVAL variables
in your function from the garbage-collector.  It never hurts to do
this, and often produces obscure bugs if you dont.  Generic code for
a new primitive fn:

/* xlsamplefun - do useless stuff. */
/* Called like (samplefun '(a c b) 1 2.0) */
LVAL xlsamplefun()
{
    /* Variables to hold the arguments: */
    LVAL    list_arg, integer_arg, float_arg;

    /* Get the arguments, with appropriate errors */
    /* if any are of the wrong type.  Look in     */
    /* xlisp.h for macros to read other types of  */
    /* arguments.  Look in xlmath.c for examples  */
    /* of functions which can handle an argument  */
    /* which may be either int or float:          */
    list_arg    = xlgalist()  ;  /* "XLisp Get A LIST"   */
    integer_arg = xlgafixnum();  /* "XLisp Get A FIXNUM" */
    float_arg   = xlgaflonum();  /* "XLisp Get A FLONUM" */

    /* Issue an error message if there are any extra arguments: */
    xllastarg();



    /* Call a separate C function to do the actual  */
    /* work.  This way, the main function can       */
    /* be called from both xlisp code and C code.   */
    /* By convention, the name of the xlisp wrapper */
    /* starts with "xl", and the native C function  */
    /* has the same name minus the "xl" prefix:     */
    return samplefun( list_arg, integer_arg, float_arg );
}
LVAL samplefun( list_arg, integer_arg, float_arg )
LVAL            list_arg, integer_arg, float_arg;
{
    FIXTYPE val_of_integer_arg;
    FLOTYPE val_of_float_arg;

    /* Variables which will point to LISP objects: */
    LVAL result;

    LVAL list_ptr;
    LVAL float_ptr;
    LVAL int_ptr;

    /* Protect our internal pointers by */
    /* pushing them on the evaluation   */
    /* stack so the garbage collector   */
    /* can't recycle them in the middle */
    /* of the routine:                  */
    xlstkcheck(3);    /* Make sure following xlsave */
                      /* calls won't overrun stack. */
    xlsave(list_ptr); /* Use xlsave1() if you don't */
    xlsave(float_ptr);/* do an xlstkcheck().        */
    xlsave(int_ptr);

    /* Create an internal list structure, protected */
    /* against garbage collection until we exit fn: */
    list_ptr = cons(list_arg,list_arg);

    /* Get the actual values of our fixnum and flonum: */
    val_of_integer_arg = getfixnum( integer_arg );
    val_of_float_arg   = getflonum( float_arg   );


    /*******************************************/
    /* You can have any amount of intermediate */
    /* computations at this point in the fn... */
    /*******************************************/


    /* Make new numeric values to return: */
    integer_ptr = cvflonum( val_of_integer_arg * 3   );
    float_ptr   = cvflonum( val_of_float_arg   * 3.0 );

    /* Cons it all together to produce a return value: */
    result = cons(
        list_ptr,
        cons(
            integer_ptr,
            cons(
                float_ptr,
                NIL
            )
        )
    );

    /* Restore the stack, cancelling the xlsave()s: */
    xlpopn(3); /* Use xlpop() for a single argument.*/

    return result;
}




 Minor Observations:
 -------------------

xlapply, xlevform and sendmsg will issue an error if they encounter a
s_macro CLOSURE.  This is presumably because all macros are expanded
by xleval.c:xlclose when it builds a closure.

Neither xlapply nor sendmsg will handle FSUBRs.  This is presumably
a minor bug, left due to the difficulty of keeping arguments
unevaluated to that point. ?


 Minor Mysteries:
 ----------------

Why doesn't xlevform trace FSUBRs?  Is this a speed hack?

Why do both xlobj.c:xloinit() and xlobj.c:obsymvols() initialize the
"object" and "class" variables?
- --

- - Jeff   (S)

------- Message 2

Path: hplabsz!hplabs!ucbvax!ucdavis!csus.edu!wuarchive!zaphod.mps.ohio-state.edu!uakari.primate.wisc.edu!dali.cs.montana.edu!milton!uw-beaver!zephyr.ens.tek.com!tekchips!tekgvs!toma
From: [e-mail] (Tom Almy)
Newsgroups: comp.lang.lisp.x
Subject: Re: xlisp 2.1/winterp internals (26K long)
Message-ID: <[e-mail]>
Date: 16 Nov 90 21:13:29 GMT
References: <[e-mail]>
Reply-To: [e-mail] (Tom Almy)
Distribution: comp
Organization: Tektronix, Inc., Beaverton,  OR.
Lines: 206

>I've just finished reading the xlisp 2.1 source code for the first
>time.  The tutorial and reference material included with the winterp
>distribution are well done, but I would have liked an overview of the
>interpreter internals.  Here's a first cut at such a document.
>Comments welcome...

I have spend many hours going over the listings, fixing bugs, and making
extensions. I wish I had this when I started. But I do have a few comments.


>xlenv and xlfenf are conceptually a single environment, although they
>are implemented separately. [...]

>The xlfenv environment is maintained strictly parallel to xlenv, but
>is used to find function values instead of variable values.  The
>separation may be partly for lookup speed and partly for historical
>reasons.

They have to be maintained separately because let lexically binds values and
flet, labels, and macrolet lexically bind only functions.
For instance consider:
(defun x () x)
(setq x 10)
(let ((x 3)) (print x) (print (x)))

will print 3 and 10.

while

(flet ((x () (+ 1 x))) (print x) (print (x)))

will print 10 and 11.

and

(let ((x 3)) (flet ((x () (+ 1 x))) (print x) (print (x))))

will print 3 and 4.

You couldn't do this with a combined binding list.


>The xldenv environment tracks the old values of global variables which
>we have changed but intend to restore later to their original values,
>particularly when we bind and unbind s_evalhook and s_applyhook
>(*EVALHOOK* and *APPLYHOOK*).  (This is mostly to support the debug
>facilities.)  It is a simple list of sym-val pairs,
>treated as a stack.

xldenv tracks the dynamic binding (as opposed to lexical binding). A "flaw"
in xlisp is that there is no mechanism for declaring special variables
(which would be always dynamically bound). You can dynamically bind
variables with PROGV. If my memory serves, only PROGV, EVALHOOK and
(as I implemented it) APPLYHOOK dynamically bind variables.  For instance,
consider the following variation of the LET example above:

(defun x () x)
(setq x 10)
(progv '(x) '(3) (print x) (print (x)))

will print 3 and 3. (When execution falls out of progv, the global x is
rebound to 10).


This is the best way to override global variable settings in an application,
since the variables will be restored automatically on termination.


>Obviously, several of the above types won't fit in a fixed-size
>two-slot node.  The escape is to have them malloc() some memory
>and have one of the slots point to it -- VECTOR is the archetype.  For
>example, see xldmem.c:newvector().  To some extent, this malloc()
>hack simply exports the memory- fragmentation problem to the C
>malloc()/free() routines.  However, it helps keep xlisp simple, and it
>has the happy side-effect of unpinning the body of the vector, so that
>vectors can easily be expanded and contracted.

XSCHEME which relies more heavily on arrays, maintains a pool of storage
to allocate arrays and strings, for which it does garbage collection
and (I believe) compaction as well. At any rate, my modified xlisp can
optionally use the xcheme approach which has decided advantages in
programs that use many arrays and strings since the memory does not
get fragmented. Enough said.


>Xlisp pre-allocates nodes for all ascii characters, and for small
>integers.  These nodes are never garbage-collected.

This also speeds up READ, and vastly reduces the number of nodes since
all identical characters and small integers are unique. The range of
small integers treated in this way is compilation settable.


>As a practical matter, allocating all nodes in a single array is not
>very sensible.  Instead, nodes are allocated as needed, in segments of
>one or two thousand nodes, and the segments linked by a pointer chain
>rooted at xldmem.c:segs.

The size of the segment is settable using the ALLOC function.

>You create a symbol in xlisp by using the
>single-quote operator: "'name", or by calling "(gensym)", or
>indirectly in various ways.

I would say that 'name is an indirect way to create a symbol. The direct
ways are using MAKE-SYMBOL (for uninterned symbols) or INTERN (for interned
symbols), or as you mentioned GENSYM (also uninterned). You can make READ
create an uninterned symbol by preceeding it with #:, otherwise all symbols
read by READ are interned.

In addition, when you make a symbol that starts with the colon character,
the symbol is given itself as the value, otherwise the new symbol has no
value.


>OBJECT is the root of the class hierarchy: everything you can send a
>message to is of type OBJECT.  (Vectors, chars, integers and so forth
>stand outside the object hierarchy -- you can't send messages to them.
>I'm not sure why Dave did it this way.)

Probably because the object facility is an extension of lisp. You can
create classes of these things. There is also efficiency considerations.
The only object oriented programming language I know of where everything
is an object is Smalltalk, but if you look at the implementation, it does
cheat at the low level to speed things up.

> :isnew -- Does nothing

It does return the object!


>FSUBR: A special primitive fn coded in C, which (like IF) wants its
>arguments unevaluated.

These are the "special forms"

>We scan the MESSAGES list in the CLASS object of the recipient,
>looking for a (message-symbol method) pair that matches our message
>symbol.  If necessary, we scan the MESSAGES lists of the recipients
>superclasses too.  (xlobj.c:sendmsg().)  Once we find it, we basically
>do a normal function evaluation. (xlobjl.c:evmethod().)  Two oddities:
>We need to replace the message-symbol by the recipient on the argument
>stack to make things look normal, and we need to push an 'object'
>stack entry on the xlenv environment so we remember which class is
>handling the message.


The first "oddity" has an important side effect, when :answer was
used to build the method closure, an additional argument, "self", was
added so that the method could access itself with the symbol self.
This argument stack fix supplies the needed argument.

The reason for the second "oddity" is that the method's class is
needed for SEND-SUPER. When one uses SEND-SUPER, the message lookup
begins in the superclass of the method rather than the class of the
object (as with SEND).

>    xlstkcheck(3);    /* Make sure following xlsave */
>                      /* calls won't overrun stack. */
>    xlsave(list_ptr); /* Use xlsave1() if you don't */
>    xlsave(float_ptr);/* do an xlstkcheck().        */
>    xlsave(int_ptr);

xlsave also set the variable to nil. If you don't need to do that you
can use xlprot instead of xlsave, or xlprot1 instead of xlsave1

>xlapply, xlevform and sendmsg will issue an error if they encounter a
>s_macro CLOSURE.  This is presumably because all macros are expanded
>by xleval.c:xlclose when it builds a closure.

You are not allowed to use APPLY or FUNCALL with macros in Common
Lisp. There is no way provided to declare macro methods, nor do they
make much sense (at least in my mind).

>Neither xlapply nor sendmsg will handle FSUBRs.  This is presumably
>a minor bug, left due to the difficulty of keeping arguments
>unevaluated to that point. ?

You are not allowed to use APPLY or FUNCALL with special forms. There is
no way to declare methods using SUBRs or FSUBRs (the existing SUBR
methods are initialized at load time).

>
> Minor Mysteries:
> ----------------

>Why doesn't xlevform trace FSUBRs?  Is this a speed hack?
Good question. Probably not a speed hack. You can't trace macros either.

>Why do both xlobj.c:xloinit() and xlobj.c:obsymvols() initialize the
>"object" and "class" variables?

xloinit creates the classes class and object, as well as the symbols, but
sets the C variables class and object to point to the class and object.

obsymbols just set the C variables by looking up the symbols. It is needed
because when you restore a workspace you don't create new objects but still
need to know where the existing objects are (they might be in a different
location in the saved workspace). Notice that obsymbols is called by xlsymbols
which is called both when initializing a new workspace or restoring an old
workspace.


Tom Almy
[e-mail]
Standard Disclaimers Apply

------- Message 3

Path: hplabsz!hplabs!sdd.hp.com!wuarchive!emory!att!cbnewsc!lgm
From: [e-mail] (lawrence.g.mayka)
Newsgroups: comp.lang.lisp.x
Subject: Re: xlisp 2.1/winterp internals (26K long)
Summary: CLOS treats everything as an object
Message-ID: <[e-mail]>
Date: 17 Nov 90 15:58:36 GMT
References: <[e-mail]> <[e-mail]>
Organization: AT&T Bell Laboratories
Lines: 20

In article <[e-mail]>, [e-mail] (Tom Almy) writes:
> The only object oriented programming language I know of where everything
> is an object is Smalltalk, but if you look at the implementation, it does
> cheat at the low level to speed things up.

Correction: the Common Lisp Object System (CLOS) indeed considers
every entity to be an object - i.e, an instance of some class on which
methods can specialize.  Thus, one can specialize a method for
integers, or symbols, or sequences.  It is also true, however, that
CLOS classes differ in their inheritance behavior according to
metaclass (STANDARD-CLASS, STRUCTURE-CLASS, or BUILT-IN-CLASS); and it
is also true that functionality may reside not only in methods but
also in (unspecializable) functions and macros.


    Lawrence G. Mayka
    AT&T Bell Laboratories
    [e-mail]

Standard disclaimer.

------- Message 4

Path: hplabsz!hplabs!sdd.hp.com!zaphod.mps.ohio-state.edu!van-bc!ubc-cs!uw-beaver!zephyr.ens.tek.com!tekchips!tekgvs!toma
From: [e-mail] (Tom Almy)
Newsgroups: comp.lang.lisp.x
Subject: Re: xlisp 2.1/winterp internals (26K long)
Message-ID: <[e-mail]>
Date: 17 Nov 90 17:47:38 GMT
References: <[e-mail]> <[e-mail]>
Reply-To: [e-mail] (Tom Almy)
Distribution: comp
Organization: Tektronix, Inc., Beaverton,  OR.
Lines: 22

I hate to followup to my own posting, but:

1. I appologise for all the CR characters at the end of each line.
2. I realized I made a mistake.
The original posting:
>>xlapply, xlevform and sendmsg will issue an error if they encounter a
>>s_macro CLOSURE.  This is presumably because all macros are expanded
>>by xleval.c:xlclose when it builds a closure.

>>Neither xlapply nor sendmsg will handle FSUBRs.  This is presumably
>>a minor bug, left due to the difficulty of keeping arguments
>>unevaluated to that point. ?

Corrected reply:
Common Lisp does not allow APPLYing a macro or special form (FSUBR).
This is based on the evaluation model.
Since SEND is a subr, all of its arguments are already evaluated so it
is already too late to have macro or fsubr methods.

Tom Almy
[e-mail]
Standard Disclaimers Apply

------- Message 5

Path: hplabsz!hplabs!sdd.hp.com!uakari.primate.wisc.edu!dali.cs.montana.edu!milton!milton.u.washington.edu!jsp
From: [e-mail]. (Jeff Prothero)
Newsgroups: comp.lang.lisp.x
Subject: Re: xlisp 2.1/winterp internals (26K long)
Message-ID: <[e-mail].>
Date: 17 Nov 90 19:13:11 GMT
References: <[e-mail]>
    <[e-mail]>
Sender: [e-mail]
Distribution: comp
Organization: Biological Structure, U of Wash, Seattle
Lines: 42
In-reply-to: [e-mail]'s message of 16 Nov 90 21:13:29 GMT

In article <[e-mail]> [e-mail] (Tom Almy) writes:

>[lots of good clarifications of stuff I was fuzzy on]

Thanks!  I'm going to merge your comments into internals.doc
(with a global acknowledgement) if you don't object...

>[good examples of lexical binding of fns vs variables]
>You couldn't do this with a combined binding list.

Um.  Clearly, the lexical binding mechanism needs to distiguish
between binding of functions and variables.  Maybe I'm a little slow,
but it is still not obvious to me that you need separate xlenv and
xlfenv base pointers.  For example, I don't see simultaneous pushing
of one stack and popping of the other.

>>Vectors, chars, integers and so forth
>>stand outside the object hierarchy -- you can't send messages to them.
>>I'm not sure why Dave did it this way.

>Probably because the object facility is an extension of lisp. You can
>create classes of these things. There is also efficiency considerations.
>The only object oriented programming language I know of where everything
>is an object is Smalltalk, but if you look at the implementation, it does
>cheat at the low level to speed things up.

Doing CAR and CDR via messages (say), would clearly have a big
efficiency impact (barring very smart compilation).  But defining a
CLASS string and supporting messages to strings (say), doesn't present
any serious (to me) efficiency issues.  It means that xlobj.c:xsend(),
instead of using xlgaobject(), needs to check for n_type != OBJECT,
and if so, get the apppropriate class object by using n_type to index
into a C array.  Added cost to a normal xlisp message-send: about two
machine instructions.  The win would be that you could safely send
(say) a :SHOW message to any LVAL, instead of needing special-case
checking in the xlisp code. No?


- --
     [e-mail] (Jeff Prothero)
     [e-mail] (If above bounces.)
     Biological Structure Graphics Lab, U Washington

------- End of Forwarded Messages