next up previous
Next: 3 リスプデータの内部表現 Up: 2 Lispインタプリタの構造 Previous: 2.4 print

2.5 手続きの定義

組込みの手続きがインタプリタで処理される仕組みを見るために, 組込み手続きとして定義されているreverseを取り上げてみます. reverseは,
> (reverse '(a b c))
(C B A)
というように引数に与えられたリストデータを受けとり 要素を逆順にしたリストデータを返します. このLisp関数reverseの実行は上のxreveseというC言語で 書かれた関数が行なっています. 組込み関数は,一覧表として,xlftab.cにおいて,funtabに登録されています. この表は,以下のFUNDEFタイプを要素にもつ配列となっています.

typedef struct {
    char *fd_name;        /* function name */
    int fd_type;        /* function type */
    LVAL (*fd_subr)();        /* function entry point */
} FUNDEF;
このfuntabの77番目のところに,以下のように,

{"REVERSE", S, xreverse}, /*  77 */
と定義されています. このxreverseがREVERSEに対応するCの関数です. Sは,SUBRであることを意味します.
1: LVAL xreverse()
2: {
3:     LVAL list,val;
4:     xlsave1(val);
5:     list = xlgalist();
6:     xllastarg();
7:     for (val = NIL; consp(list); list = cdr(list))
8:      val = cons(car(list),val);
9:     xlpop();
10:    return (val);
11: }
xreverseの5行目のlistには引数のリストが入ります. 6行目で引数がそれ以外にないかを確認します. for文でvalにリストを作っています. 4行目と9行目は,非常に重要なものです. xreverseの定義のvalにはreverseの結果であるリストデータが 順次consにより付け加えられていきます.consという のはメモリ領域からcar部とcdr部をもつセルをひとつ とり出してきますが,このconsの途中でメモリ領域が 足りなくなった場合に,Lisp処理系は自動的に メモリ領域の整理を行ないます.その整理というのは, 使われている領域とそうでない領域を判別し, 使われていない領域のみを再び使えるようにかきあつめる という処理です.この処理のことをガーベッジコレクション(Garbage Collection:GC) といいます. GCは,大域変数の値として 代入されているものや,関数を実行する際に渡された引数, 関数を実行している最中に使っているスタック,などから たどれるデータを使用中のデータとみなし,それ以外は ごみとみなします. 今,xreverseを実行している中でconsが呼ばれているために, そのGCが起こると,それまでvalに蓄えておいたものが ごみとみなされるおそれがあります. そこで,4行目のxlsave1によりスタックにvalを保存して おくと,GCが起こってもごみと扱われなくなります. そして,valが完成したらばスタックをもとに戻す ためにxlpopし,return値としてvalを返します. スタックに退避する部分の処理は,以下のようにマクロで定義されています. これはxlisp.hというファイルの中に定義されています.

#define xlsave1(n)
{if (xlstack <= xlstkbase) xlstkoverflow();\
                  *--xlstack = &n; n = NIL;}
#define xlpop()         {++xlstack;}
reverseの中では,cons手続きによってリストを作っています. consの本体は,xldmem.cにあります.


/* cons - construct a new cons node */
LVAL cons(x,y)
  LVAL x,y;
{
  LVAL nnode;
  
  /* get a free node */
  if ((nnode = fnodes) == NIL) {
    xlstkcheck(2);
    xlprotect(x);
    xlprotect(y);
    findmem();
    if ((nnode = fnodes) == NIL)
      xlabort("insufficient node space");
    xlpop();
    xlpop();
  }
  
  /* unlink the node from the free list */
  fnodes = cdr(nnode);
  --nfree;
  
  /* initialize the new node */
  nnode->n_type = CONS;
  rplaca(nnode,x);
  rplacd(nnode,y);
  
  /* return the new node */
  return (nnode);
}
このconsの中で,findmemを実行して,フリーリスト(fnodes) を更新し,その先頭のノードのcarとcdr部にx,yを代入して, そのノードを返します.フリーリストは,

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