Path: utzoo!news-server.csri.toronto.edu!rutgers!usc!aero-c!jordan
From: jordan@aero.org (Larry M. Jordan)
Newsgroups: comp.lang.c++
Subject: Implementing LISP in C++ (type discrimination)
Message-ID: <1991Mar12.221015.22144@aero.org>
Date: 12 Mar 91 22:10:15 GMT
References: <1991Mar8.024331.14235@searchtech.com> <27D7F621.2F5@tct.uucp> <17238@cadillac.CAD.MCC.COM>
Sender: news@aero.org
Organization: The Aerospace Corporation, El Segundo, CA
Lines: 50

I'm endeavoring to implement an interpreter/compiler for a LISP-like language
in C++.  The question I wish to have answered is "Can I implement a
type-less lang. like LISP in C++ without resorting at some point to
actually asking an object for its type?" I just don't see how not to.
Also, I'm implementing a simple mark/sweep garbage collector which takes 
liberties with Cons cell pointers to avoid recursion.  I don't see a 
reasonable way to do this without asking objects during the mark phase
'are you a Cons?'. (Of course, I will need to implement the predicate 
functions like 'null, consp, listp, etc.').   I'd also like some
remarks on the 'reasonableness' of the implementation scheme I've 
chosen (to be described next paragraph).

Techniques I've seen in the past for implementing LISP objects in
languages like C or Modula-2 define an enumeration type and create
a discriminated union using the enum as a type 'tag' or discriminant.
XLISP and XSCHEME are implemented this way and it seems perfectly
reasonable.  I've taken a different approach since I'm using C++.
I'm implementing LISP objects as C++ classes--Cons, Vector, Fixnum, 
Closure, Environment...--derived from a common base class Node.  Most
methods are virtual and defined in class Node with a call to an error 
routine.  It is each derived class's responsiblity to redefine the
methods which are meaningfull--i.e.  the Cons class redefines
'car() and cdr()':

  class Cons : Node {
    Node *theCar;
    Node *theCdr;
    virtual Node *car() { return theCar; }
    virtual Node *cdr() { return theCdr; }
    virtual void setCar(Node *n) { theCar = n; }
    virtual void setCdr(Node *n) { theCdr = n; }
    ...
  };

Consequently, there are a large number of virtual methods in the base
class Node--20+ and growing.  At first I thought there would be a lot
of space dedicated to large vft's--sizeof(char*) * 
NumberOfVirtualMethodsInBase for each LISP object
derived from Node!  I was concerned about using vast amounts of memory
for vft's.  But then I considered what the alternative would be--
using code space to check the type of the object I'm about to 
reference as a 'Cons' object (which would be an operation that
would widely distributed throughout the system) rather that just 
envoke the method.  I get the error checking at the expense of a
calling a virtual method.  I'm convinced that this experiment is 
worthwhile to continue.

Thanks in advance.

--Larry