Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!usc!hacgate!eos!roger
From: roger@eos.eos.scg.hac.com (Roger Sheldon (Loral))
Newsgroups: comp.lang.c++
Subject: Re: Implementing LISP in C++ (type discrimination)
Message-ID: <14342@hacgate.UUCP>
Date: 11 Apr 91 20:20:13 GMT
References: <1991Mar8.024331.14235@searchtech.com> <27D7F621.2F5@tct.uucp> <17238@cadillac.CAD.MCC.COM> <1991Mar12.221015.22144@aero.org>
Sender: news@hacgate.UUCP
Reply-To: roger@eos.UUCP (Roger Sheldon (Loral))
Organization: Hughes Aircraft Co., El Segundo, CA
Lines: 98

In article <1991Mar12.221015.22144@aero.org> jordan@aero.org (Larry M. Jordan) writes:
>I'm endeavoring to implement an interpreter/compiler for a LISP-like language
>in C++.  

Larry,
I've been working on Lisp in C++ also.  I've discovered a garbage collection
technique which you and others may find useful.  Here's a summary
of the technique.

The class hierarchy is similar to yours:

                        Base -------------- Object
       |-----------------|---------------|
      Cons             Symbol         Integer
       |           |-----|-----|
      Null  Static_symbol    Function

(The relationship of the Object class will be explained below.)
Garbage collection is accomplished via a combination of reference maintenance
and temporary objects.  Reference maintenance is done with a
few member functions:

Base *Base::Ref()       { refs++; return this; }
void Base::Deref()      { if (--refs == 0) delete this; }
void Cons::Deref() {                 // hides inhereted Base::Deref()
    Base *a = this;
    while (a != nil.value && --a->refs==0) {
        a->Car().Deref();            // delete car obj (clobber if last ref)
        Base *save = & a->Cdr();
        delete a;                    // may be deleting *this* !
        a = save;
    }
}

The Cons::Deref() method is a variation of the deref() method found in
Gnu's libg++ parameterized List class. (Thanks FSF) That's pretty much it 
for reference maintenance.  The Null and Static_symbol classes override the 
inherited Deref() method with no ops so there's no need to worry about 
refs and derefs to nil and t.

Now, the temporary objects work with the reference maintenance as follows.
The Object class is defined as: 

class Object { 
    Base *value;
public:
    Object() 			{ value = nil.value; }
    Object(Object &a) 	{ value = a.value->Ref(); }
    Object(Base &a) 	{ value = a.Ref(); }
    ~Object() 			{ value->Deref(); }
    operator=(Object &a){ 
        Base *save=value; 
        value = a.value->Ref();
        save->Deref();
    }
    ...
};

User code manipulates Lisp objects only through the Object class.  Specifically,
all user functions must use the same signature:
	Object foo(Object &a, Object &b <possibly more args>);
The main point is that Lisp objects are always returned through copied objects.
This allows user code to be written without the need to do reference 
maintenance -- the Object class takes care of reference maintenance 
automatically.  Here's an example of some user code:

Object shove_pl(Object &variable, Object &item, Object &alist) {
    if (!alist)
        return list(list(variable, list(item)));
    else if (variable == caar(alist))
        return cons(list(variable, append(cadar(alist), list(item))),
                    cdr(alist));
    else
        return cons(car(alist), shove_pl(variable, item, cdr(alist)));
    }

This is a translation of the Common Lisp shove_pl function found in
Winston's Lisp book:

(defun shove-pl (variable item a-list)
  (cond ((null a-list) (list (list variable (list item))))
        ((equal variable (caar a-list))
         (cons (list variable (append (cadar a-list) (list item)))
               (cdr a-list)))
        (t (cons (car a-list) (shove-pl variable item (cdr a-list))))))

OK, so this approach allows you to write elegant code.  But how
expensive is this garbage collection technique (which I'm calling
"Immediate" garbage collection since objects are clobbered immediately
after the last reference to it is removed) ?
I'm not going to get into a big discussion on performance.  I will
say that I've converted user functions to do their own reference maintenance 
(they deal with Base *'s rather than Objects) and the performance
improvement has ranged from 0 to 3 times.

Feel free to call me at 301 805-0463.

Roger Sheldon