Subject: Re: Implementation of vectors
From: (Rob Warnock)
Date: 2000/05/27
Newsgroups: comp.lang.scheme
Message-ID: <8gocj8$fknpn$>
Michael Roper <> wrote:
| Can someone please tell me how vectors are typically implemented
| in Scheme systems?

Like pairs, only bigger?  ;-}  ;-}

No, seriously, like pairs, only bigger. That is, a typical[*] representation
for objects (ignoring "immediates" and "fixnums") is with a pointer to some
heap-allocated storage. The first word (or sometimes, the *preceding* word)
pointed to may contain some type (and sometimes length) info, then succeeding
words contain "the stuff". Thus, in C terms, a pair might be:

	struct Pair {
	    SCM_Header hdr;
	    Object car;
	    Object cdr;

Then, using the usual hack for variable-length structs in C,
a vector might be:

	struct Vector {
	    SCM_Header hdr;
	    int length;
	    Object data[1];	/* XXX Hack! Might be longer than 1... */

But it varies. Sometimes the data part is allocated "out-of-line"
from the header, and then you have something like this:

	struct Vector {
	    SCM_Header hdr;
	    int length;
	    Object *data;	/* pointer to separately allocated data */

It varies, depending on the needs of the implementation. For example,
if you need to interface with a lot of existing C code, the out-of-line
method allows a garbage-collectable header to point to non-collectable
static C data, but costs an extra indirection to access. And sometimes,
as in Common Lisp "adjustable" vectors, there's both a "max-length" and
"actual-length" field, and vectors can be grown and shrunk after being
created (if necessary, re-allocating and copying the out-of-line part).


[*] There are *many* different reasonable choices of representation
for Lisp & Scheme objects that an implementation could use. For a good
survey of them, see:

Gudeman, "Representing Type Information in Dynamically Typed Languages"

Rob Warnock, 41L-955
Applied Networking
Silicon Graphics, Inc.		Phone: 650-933-1673
1600 Amphitheatre Pkwy.		PP-ASEL-IA
Mountain View, CA  94043