Next: 3 リスプデータの内部表現
Up: 2 Lispインタプリタの構造
Previous: 2.4 print
組込みの手続きがインタプリタで処理される仕組みを見るために，
組込み手続きとして定義されている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の５行目のlistには引数のリストが入ります．
6行目で引数がそれ以外にないかを確認します．
for文でvalにリストを作っています．
4行目と９行目は，非常に重要なものです．
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日