ちょっと変わった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));
  }
}