ちょっと変わったLisp入門：Gaucheでメタプログラミング（1）（3/5 ページ）
Lisp処理系を作ってみよう！
Lispの説明では、「シンボル」など、ほかの言語にはないものが登場します。Lispの本を読むと、ほかの言語では使われないような用語や概念が登場し、Lispを理解しにくくしています。
そこで、ここでは簡単なLisp処理系をC言語で作りながら、Lispを理解しましょう。実はLispの処理系は、性能や堅牢さを考えなければ案外と簡単なのです。Lispの不可思議な部分も処理系の動きが分かれば、理解しやすくなると思います。
セルの管理
まず、定数や広域変数を行います。
#define NIL ((cell)0)
#define CAR(e) ((cons_t *)e)->car_e
#define CDR(e) ((cons_t *)e)->cdr_e
typedef void *cell;
typedef struct {
cell car_e;
cell cdr_e;
} cons_t;
static cons_t cons_cell[CONS_MAX];
static int cons_pt = 0;
typedef struct {
char name[SYMBOL_NAME_MAX + 1];
} symbol_t;
static symbol_t symbol[SYMBOL_MAX];
static int symbol_pt = 0;
セルはcar／cdr部分からなる構造体で、CAR／CDRマクロはcar／cdr部分の値を取り出すマクロです。シンボルはセルとは別の変数で管理しています。
このLisp処理系ではメモリ管理は手を抜いて、セル用の固定長の配列、シンボル用の固定長の配列で管理しています。
cell cons(cell car_a, cell cdr_a) {
if (cons_pt >= CONS_MAX) gc();
cell new_cons = &cons_cell[cons_pt];
cons_pt++;
CAR(new_cons) = car_a;
CDR(new_cons) = cdr_a;
return new_cons;
Lispでは新しいセルが必要になった場合は、cons関数を呼び出し新しいセルを用意し、car／cdrの値を入れて戻します。セル用の配列を使い切った場合はGCを呼び出すようになっていますが、このLisp処理系は実装されていません。
出力部分
セル内のS式を出力する部分は、出力される値「e」がnil、数値やシンボルならば、その値を表示します。セルの場合は、「(」を出力し、car部分を再帰的にprint_eで出力し、cdrがnilなら終わり、cdrが数値やシンボルなら「.」を表示し、cdr部を表示します。cdrがセルへのポインタならたぐって繰り返します。
#define SYMBOL_NAME(e) (((symbol_t *)e)->name)
void print_e(cell e) {
if (e == NIL) {
printf("nil");
} else if (IS_INT(e)) {
printf("%d", CELL2INT(e));
} else if (IS_SYMBOL(e)) {
printf("%s", SYMBOL_NAME(e));
} else if (IS_CONS(e)) {
printf("(");
while (1) {
print_e(CAR(e));
e = CDR(e);
if (e == NIL) break;
if (IS_INT(e) || IS_SYMBOL(e)) {
printf(".");
print_e(e);
break;
}
printf(" ");
}
printf(")");
} else {
printf("lisp処理系がへん？");
}
}
動作がピンとこない方は、前ページの(a b)や(+ (* a b) (* c d))のセルの図を見ながら、print_eの動きを追ってみるとよいと思います。このように、特定な条件の場合を処理し、あとはcar部分を再帰して、cdr部分をループ／再帰で処理するのはLispでは定石です。
入力部分
キー入力した文字列をS式として解釈し、リスト構造を作ります。
入力は出力の逆の処理で、入力文字列が数値なら数値として、シンボルならシンボルとして処理します。「()」の中はやはりcar部分は再帰的に、cdr部分はループで処理を行います。ここで、使っている関数は以下のような処理を行います。
- get_token()は入力文字列が数値ならtoken->kindに「N」を、シンボルなら「S」をセットし数値や名前を設定し戻ります。Lispで特殊な意味を持つ文字「( . )」ならその文字を token->kindにセットして戻ります。また空白などは適宜無視します
- concat2(list,e)関数はlistの最後にeを連結します（listの最後のセルのcdrの値にeを書き込みます）
- make_symbol(s)関数はシンボル（文字列）sがすでに読み込まれていれば、同じシンボルへのポインタを戻し、新規のシンボルならシンボル用の配列に追加し、シンボルへのポインタを戻します
cell read_next(token_t *token) {
cell car_e, cdr_e, e;
cell list = NIL;
if (token->kind != '(') {
if (token->kind == 'N') return INT2CELL(token->number);
// symbol
return make_symbol(token->name);
}
while (1) {
token = get_token();
if (token->kind == ')') return list;
car_e = read_next(token);
if (token->kind == '.') {
// (a.b)
token = get_token();
cdr_e = read_next(token);
token = get_token();
if (token->kind != ')') throw_error(") required after '%s'", sprint_e(cdr_e));
return cons(car_e, cdr_e);
}
// (a b)
list = concat2(list, cons(car_e, NIL));
}
}
cell read_e() {
cell e;
e = read_next(get_token());
return e;
}
メイン
Lispの処理系はREPL（Read Eval Print Loop）と呼ばれるインタラクティブな実行環境を持っています。これはRubyのirbコマンドや、Pythonのpythonコマンドに引数を指定しなかった場合、Perlのperlsh（CPANからインストールできます）と同じようなものです。
% ./lisp lisp> (+ 2 3) 5 lisp> (list 1 2 3) (1 2 3) lisp>
メインのコードは下のようにRead Eval Print Loopそのものです。
int main(int argc, char *argv[]) {
init();
while (1) {
print_e(eval(read_e(), NIL));
}
}
Copyright © ITmedia, Inc. All Rights Reserved.
ITmediaはアイティメディア株式会社の登録商標です。