連載
» 2008年10月31日 00時00分 公開

ちょっと変わった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.

RSSについて

アイティメディアIDについて

メールマガジン登録

@ITのメールマガジンは、 もちろん、すべて無料です。ぜひメールマガジンをご購読ください。