From: Scott McLoughlin
Subject: Structure inheritance, #2
Date:
Message-ID: <0iZwqc2w165w@sytex.com>
Howdy,
It seems some misunderstood my original post regarding
structure inheritance, so here goes again...
We are _implementing_ a Lisp (used to be a heavily
enhanced Scheme, now a CL subset) packaged as a Windows .DLL and
.VBX for embedding in non-Lisp applications (extension language,
whatever).
We need to implement structure inheritance (yes, need for
various reasons) and are looking for tips/literature pointers on
how to do efficient but safe slot access in the presense of
structure inheritance. The scheme will have to allow for
dynamic "subclassing" so schemes that rely on static analysis
of a programs source prior to "seal off" won't be that
helpful.
We have some literature available on CLOS, OakLisp and
other object oriented Lisp extensions. While they excite
the imagination, we really would like info directly pertaining
to the limited case of structure inheritance where common usage
patterns will probably be _NO_ structure inheritance.
P.S. -- Outside of a university environment, Lisp literature
is hard to come by. In DC, we can access the Library of Congress,
thank goodness. I can imaging a market for a big compendium of
Lisp implementation oriented papers.
=============================================
Scott McLoughlin
Conscious Computing
=============================================
I assume that your main question is about how to do efficient structure type
tests, since it is easy to tack subclass slots on the end of the superclass
slots.
In CMU CL, there are two mechanisms:
-- A general test mechanism, and
-- Compiler support for using knowledge about the subclasses of "frozen"
classes.
The general mechanism is somewhat non-obvious, and the idea was from a
Modula 3 implementation. A simplified version of the test would be as follows:
1] Each structure type is represented by a vector of its supertype and its
supertype's supertype, etc. This vector is ordered most general to least
general (subtypes at higher indices.)
2] Instances are tagged with this type descriptor.
3] A type test looks like:
(defun structure-typep (structure type-desc)
(let ((obj-type (structure-type-descriptor object))
(idepth (length type-desc)))
(if (eq obj-type type-desc)
t
(and (> (length obj-type) idepth)
(eq (svref obj-type idepth) type-desc)))))
Note that "idepth" is actually a compile-time constant if the type is also a
constant. In practice, the type descriptor is itself a structure holding the
supertypes vector. You can look at the CMU CL sources for other ideas.
If many structures have no super- or sub-types, then you would definitely win
big if you allowed that to be statically declared, since a type test is just an
EQ test then.
Rob
Is the structure inheritance single-inheritance, as it is in common lisp?
If so, slots have fixed positions which can be compiled in. Subclasses
simply get new slot positions.
If you allow users to redefine classes, so slot position may change, you
can use a global slot coloring approach which requires an extra level of
indirection. See OOPSLA '92 i think, or email me separately if you'd like
more information.
k
--
Ken Anderson
Internet: ·········@bbn.com
BBN ST Work Phone: 617-873-3160
10 Moulton St. Home Phone: 617-643-0157
Mail Stop 6/4a FAX: 617-873-2794
Cambridge MA 02138
USA