Subject: Re: List diagrams -- Siebel and Touretzky draw them differently
From: (Rob Warnock)
Date: Wed, 21 May 2008 03:25:13 -0500
Newsgroups: comp.lang.lisp
Message-ID: <>
Duane Rettig  <> wrote:
| Rainer Joswig <> writes:
| > Duane Rettig <> wrote:
| >> Some lisps actually encode a cons cell with more than
| >> two natural words.
| >
| > Any reason for that?
| I don't know.  Presumably header information for gc maintenance.

Or for sometimes just for the simplicity of not having to deal
with decoding lowtag types everywhere type discrimination is done.

| Perhaps someone with such a lisp can comment.

SIOD Scheme is one such. *All* SIOD objects are a single C struct
type which contains a GC mar, a type field, and a union of all
of the possible subtypes [actually, the first two words of them].
Edited slightly:

    struct obj
    {short gc_mark;
     short type;
     union {struct {struct obj * car;
		    struct obj * cdr;} cons;
	    struct {double data;} flonum;
	    struct {char *pname;
		    struct obj * vcell;} symbol;
	    struct {char *name;
		    struct obj * (*f)(void);} subr0;
	    struct {char *name;
		    struct obj * (*f)(struct obj *);} subr1;
	    struct {char *name;
		    struct obj * (*f)(struct obj *, struct obj *);} subr2;
	    ...[and so on for subr3, subr4, subr5]...
	    ...[other types]...
	    struct {struct obj *env;
		    struct obj *code;} closure;
	    struct {long dim;
		    long *data;} long_array;
	    ...[and so on for other specialized array types]...
	    struct {long dim;
		    struct obj **data;} lisp_array;
	    struct {FILE *f;
		    char *name;} c_file;}

So in SIOD a cons is 3 machine words! [(car p) =~= p->]

Another example is MzScheme. [Caveat: I don't know what the current code
looks like; this is valid for MzScheme-103 and earlier.] MzScheme uses
only one lowtag bit, distinguishing only between fixnums [low bit set]
and word-aligned pointers [low bit clear]. All heap objects start with
a short type field, then a short "hash key extension" field, then either
a union of several other types or a dedicated struct definition [edited
slightly for brevity]:

    typedef struct Scheme_Object
      Scheme_Type type; /* Anything that starts with a type field
			   can be a Scheme_Object */
      short keyex;
	  struct { char *string_val; int tag_val; } str_val;
	  struct { void *ptr1, *ptr2; } two_ptr_val;
	  struct { int int1; int int2; } two_int_val;
	  struct { void *ptr; int pint; } ptr_int_val;
	  struct { void *ptr; long pint; } ptr_long_val;
	  struct { struct Scheme_Object *car, *cdr; } pair_val;
	  struct { struct Scheme_Env *env;
		   struct Scheme_Object *code; } closure_val;
	  struct { short len; short *vec; } svector_val;
	} u;
    } Scheme_Object;
    /* A floating-point number: */
    typedef struct {
      Scheme_Type type;
      double double_val;
    } Scheme_Double;
    typedef struct Scheme_Symbol {
      Scheme_Type type;
      int len;
      char s[4]; /* Really, a number of chars to match `len' */
    } Scheme_Symbol;

So here again a cons is three machine words. [(car p) == p->]


Rob Warnock			<>
627 26th Avenue			<URL:>
San Mateo, CA 94403		(650)572-2607