Xref: utzoo comp.lang.scheme:2121 comp.lang.lisp:4590 comp.lang.smalltalk:2725
Path: utzoo!news-server.csri.toronto.edu!rutgers!uwm.edu!wuarchive!tripos!rick
From: rick@tripos.com (Rick Moll)
Newsgroups: comp.lang.scheme,comp.lang.lisp,comp.lang.smalltalk
Subject: implementing an interpreter
Message-ID: <1991Mar8.153120.19836@tripos.com>
Date: 8 Mar 91 15:31:20 GMT
Distribution: comp
Organization: Tripos Associates, Inc.
Lines: 33

I have been thinking a lot about data-structures for implementing 
a Scheme interpreter, and have the following question:

There appears to be two fundamentally different approaches to the 
design of language interpreters.

1) Make all pointers to objects have a type tag.  This is typical 
in lisp and scheme.

2) Make all pointers to objects be in index into an object table 
that contains the type information.  The object's data may be in 
the object table for small objects, or point to a data-structure 
elsewhere for large object types.  This is typical in SmallTalk.

The first approach allows low cost access to the type info.  But 
is more costly to do a compaction after a garbage collection.

The second approach is more costly to access the type, but allows 
compaction with only one pointer being changed since all objects 
point to other objects only indirectly through the object table.

I'm looking for information about this issue.  Has anyone studied 
the tradeoffs involved here for traditional architecture machines 
(68030, 386, etc)?

Thanks in advance for your help,

    Rick Moll
    503 McLain Lane
    Kirkwood, MO 63122
    314/822-4263

    uunet!tripos!rick