Michael Roper <michael_roper@hotmail.com> 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).


-Rob

[*] 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"
<URL:ftp://ftp.cs.indiana.edu/pub/scheme-repository/doc/pubs/typeinfo.ps.gz>

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