Path: utzoo!news-server.csri.toronto.edu!rutgers!mcnc!decwrl!elroy.jpl.nasa.gov!aero-c!jordan
From: jordan@aero.org (Larry M. Jordan)
Newsgroups: comp.lang.c++
Subject: Re: Implementing LISP in C++ (type discrimination)
Message-ID: <1991Mar13.214542.13779@aero.org>
Date: 13 Mar 91 21:45:42 GMT
References: <17238@cadillac.CAD.MCC.COM> <1991Mar12.221015.22144@aero.org> <1991Mar13.145107.19724@linus.mitre.org>
Sender: news@aero.org
Organization: The Aerospace Corporation, El Segundo, CA
Lines: 57

Newsgroups: comp.lang.c++
Subject: Re: Implementing LISP in C++ (type discrimination)
Summary: 
Expires: 
References: <17238@cadillac.CAD.MCC.COM> <1991Mar12.221015.22144@aero.org> <1991Mar13.145107.19724@linus.mitre.org>
Sender: 
Followup-To: 
Distribution: 
Organization: The Aerospace Corporation, El Segundo, CA
Keywords: 

Doug,

Could you elaborate on the marking technique via 'GCmarkPhase'.  I
just don't see what you are driving at.  What I'm currently planning
to do is this:

  [1] for each LISP object class (I realize there is only one vtab per
      class) I have overloaded 'new' and 'delete'.  Each class
      'manages' its own object space. (i.e. when a new Cons cell is 
      'allocated', the method Cons::new() will fetch and return a Cons
      cell from Cons::FreeList.  If none are available, the
      garbage collector will be called.  It (gc) will need to
      mark all objects in use, won't it?   See [2].  Then sweep.  If
      Cons::FreeList is still empty, then the Cons object
      space manager will allocate a new chuck of Cons's
      and return one of these.

  [2] during the mark phase, each LISP object class will be asked to
      mark all its internal objects which are in use. (i.e. the Symbol
      class maintains the Obarray.  The Interpreter maintains the 
      evaluation stack, registers, etc.).
      
  [3] each LISP object class will be asked (after marking) to
      sweep, collecting objects into free lists.

'sweep' will be a static member in each class.  There will be a static
'mark' as well, but this will call a generic mark function 'void mark(Node*)'
which knows how to traverse LISP structures, as I indicated before
in a non recursive way, saving backpointer when chasing car's and
cdr's and restoring pointers when unwinding.  Writing such a generic
mark function seems to require doing a case analysis, doesn't it?

I have envisioned two methods one for marking during descent--
'int markAndDecend(?)' which marks and does the pointer reversal--
and a second on ascent--'int ascend(?)' which will restore pointers
up to a point where descending can continue or the marking phase is
complete.  These are two more virtual functions I will need to add
to the base class 'Node'! (The number continues to grow).  But, more
importantly, there are a lot of calls to virtual methods during
the marking phase.  How can this be as efficient as an up front
case analysis?!  I am concerned about the overhead.  Is the technique 
you've intimated substantially different?  Maybe more sophisticated
storage reclamation techniques are called for?!

--Larry