Ludovic Court�s <ludo@gnu.org> wrote:
+---------------
| Mike Aizatsky <mike.aizatsky@gmail.com> writes:
| > I wonder what's the state of the art for binary representation of
| > scheme objects?
| 
| GNU Guile's manual contains an appendix on this topic:
| 
|   http://www.gnu.org/software/guile/manual/html_node/Data-Representation.html
| 
| Roughly, it uses a hierarchy of types.  "Immediate" data types are types
| that can fit into a single `void *' (e.g., booleans, characters, small
| integers, etc.); said `void *' holds a "type tag" of a few bits, along
| with the actual value.  "Non-immediate" data types (e.g., pairs,
| strings, etc.) use the non-type-tag bits to hold a pointer to the actual
| data structure (because of this, pairs/cells are 8-octet aligned, which
| leaves 3 bits for the type tag).
+---------------

An even more extensive survey of type representation, which should
be read by any aspiring Scheme/Lisp implementor, can be found here:

    ftp://ftp.cs.indiana.edu/pub/scheme-repository/doc/pubs/typeinfo.ps.gz
    David Gudeman, "Representing Type Information in Dynamically Typed
    Languages", University of Arizona at Tucson, Technical Report TR 93-27
    (1993). [The .gz is ~104 KB]

From the abstract:

    This report is a discussion of various techniques for representing
    type information in dynamically typed languages, as implemented on
    general-purpose machines (and costs are discussed in terms of modern
    RISC machines). It is intended to make readily available a large body
    of knowledge that currently has to be absorbed piecemeal from the
    literature or re-invented by each language implementor. This discussion
    covers not only tagging schemes but other forms of representation
    as well, although the discussion is strictly limited to the
    representation of type information.  ...

That, plus the Wilson paper mentioned in a parallel reply:

    ftp://ftp.cs.utexas.edu/pub/garbage/bigsurv.ps
    Paul R. Wilson, "Uniprocessor Garbage Collection Techniques",
    University of Texas (1994).

While somewhat dated, it remains a very useful introduction to the
aspiring Scheme/Lisp implementor who will need to integrate the needs
of GC into his/her implementation.


-Rob

-----
Rob Warnock			<rpw3@rpw3.org>
627 26th Avenue			<URL:http://rpw3.org/>
San Mateo, CA 94403		(650)572-2607