Next: 4 Xlispの組込み関数の定義 Up: ソフトウェア特論講義資料 C言語によるLisp処理系 Previous: 2.5 手続きの定義

3 リスプデータの内部表現

xlispにおいては，整数やコンス以外もデータとして扱うことができます．xlispの中で使えるデータをどのように表現しているかの様子を見てみるために以下の構造体を示します．xldmem.hに定義されています．データに関して，C言語の中で扱うデータint, floatなどと，Lispの世界での整数，浮動少数点データなどを相互に変換する関数やマクロを用意します．


/* new node access macros */
#define ntype(x)        ((x)->n_type)
/* cons access macros */
#define car(x)                ((x)->n_car)
#define cdr(x)                ((x)->n_cdr)
#define rplaca(x,y)        ((x)->n_car = (y))
#define rplacd(x,y)        ((x)->n_cdr = (y))

typedef struct node {
    char n_type;  /* type of node */
    char n_flags; /* flag bits */
    union ninfo { /* value */

        /* subr/fsubr node */
        struct xsubr {
                /* function pointer */
            struct node *(*xs_subr)();
                /* offset into funtab */
            int xs_offset;
        } n_xsubr;

        /* cons node */
        struct xcons {
                /* the car pointer */
            struct node *xc_car;
                /* the cdr pointer */
            struct node *xc_cdr;
        } n_xcons;

        /* fixnum node */
        struct xfixnum {
                /* fixnum value */
            FIXTYPE xf_fixnum;
        } n_xfixnum;

        /* flonum node */
        struct xflonum {
                /* flonum value */
            FLOTYPE xf_flonum;
        } n_xflonum;

        /* character node */
        struct xchar {
                /* character code */
            int xc_chcode;
        } n_xchar;

        /* string node */
        struct xstring {
                /* string length */
            int xs_length;
                /* string pointer */
            unsigned char *xs_string;
        } n_xstring;

        /* stream node */
        struct xstream {
                /* the file pointer */
            FILE *xs_fp;
                /* lookahead character */
            int xs_savech;
        } n_xstream;

        /* vector/object/symbol/structure node */
        struct xvector {
                /* vector size */
            int xv_size;
                /* vector data */
            struct node **xv_data;
        } n_xvector;
    } n_info;
} *LVAL;

このように，リスプデータはノード構造体ですべてを管理しています．このノード構造体へのポインタタイプが LVALです．上に出てきたcvfixnumの定義を見てみます．


/* cvfixnum - convert an integer to a fixnum node */
LVAL cvfixnum(n)
  FIXTYPE n;
{
    LVAL val;
    if (n >= SFIXMIN && n <= SFIXMAX)
        return (&fixseg->sg_nodes[(int)n-SFIXMIN]);
    val = newnode(FIXNUM);
    val->n_fixnum = n;
    return (val);
}

というようになっています．これは，整数値がSFIXNUM(-128)から SFIXMAX(255)の間にあればノード構造体を必要としませんが，それ以外の数であれば必要とするということを示しています．ノード構造体を作る関数newnodeは以下のようになっています．


LVAL newnode(type)
  int type;
{
    LVAL nnode;
    if ((nnode = fnodes) == NIL) {
        findmem();
        if ((nnode = fnodes) == NIL)
            xlabort("insufficient node space");
    }
    /* unlink the node from the free list */
    fnodes = cdr(nnode);
    nfree -= 1L;
    /* initialize the new node */
    nnode->n_type = type;
    rplacd(nnode,NIL);
    /* return the new node */
    return (nnode);
}

このnewnodeの中でメモリ領域からノード構造体の領域を新しくとってくる関数がfindmemです．


LOCAL findmem()
{
    gc();
    if (nfree < (long)anodes)
        addseg();
}

/* addseg - add a segment to the available memory */
LOCAL int addseg()
{
  SEGMENT *newseg;
  LVAL p;
  int n;
  
  /* allocate the new segment */
  if (anodes == 0 ||
      (newseg = newsegment(anodes)) == NULL)
    return (FALSE);
  
  /* add each new node to the free list */
  p = &newseg->sg_nodes[0];
  for (n = anodes; --n >= 0; ++p) {
    rplacd(p,fnodes);
    fnodes = p;
  }
  
  /* return successfully */
  return (TRUE);
}

SEGMENT *newsegment(n)
     int n;
{
  SEGMENT *newseg;
  
  /* allocate the new segment */
  if ((newseg = 
       (SEGMENT *)calloc(1,segsize(n))) == NULL)
    return (NULL);
  
  /* initialize the new segment */
  newseg->sg_size = n;
  newseg->sg_next = NULL;
  if (segs)
    lastseg->sg_next = newseg;
  else
    segs = newseg;
  lastseg = newseg;
  
  /* update the statistics */
  total += (long)segsize(n);
  nnodes += (long)n;
  nfree += (long)n;
  ++nsegs;
  
  /* return the new segment */
  return (newseg);
}

このように，findmemの中でガーベッジコレクションのgcを行なっています．

generated through LaTeX2HTML. M.Inaba 平成18年5月6日