純LISPインタプリタを作る

C言語で純LISPインタプリタを作りました。 github.com

純LISP

純LISPはLISPの方言で、ごく少数の基本的な関数やプリミティブからなる。コンパイラとかは作ったことなかったけど、純LISPなら記述が少なくて済むだろうなと思って作ってみた。

LISPには二種類のデータ型アトムとペアがある。ペアは二つのデータのペア。アトムはペアでないもの。真偽値はt,nilがtrue,falseに対応する。AとBのペアを(A . B)と表す。またリスト(A B C)を(A . (B . (C . nil)))という風に入れ子にしたペアの略記とみなす。純LISPの要素は人によって異なるが、今回は以下の関数

• atom 値がアトムのときt
• eq 二つの値が等しいときt
• car ペアの左側
• cdr ペアの右側
• cons 二つの値のペア

と特殊形式

• cond 条件分岐
• quote 評価しない式を明示
• lambda ラムダ式
• define グローバル変数の宣言

のみからなるとする。

データの表現

LISPのリストは以下のようなコンスセルで表現される。

リスト`(A B C)`

しかしこのままでは各要素がアトムなのかペアなのか判定できない。そこで隣接する二つのアドレスp, p + 1を用いてデータを表現し、pで表すことにした。アトムの場合はpにその値を格納し、p + 1に0を格納する。ペアの場合はpにcarのアドレス、p + 1にcdrのアドレスを格納した。C言語ではメモリ0番地に値を書き込むことは基本的にできないらしいので、多分これで識別できそう。アドレスはlongなのでポインタの型はlong*で統一した。例えば((A B) C)は となる。ただしtには1,0をnilには0,0をそれぞれ格納する。つまりt = 1,nil = 0。またnilと空リスト()も等しい。（実際はどう割り当てるのが良いんだろう）

構文解析(parse.c)

まず全体をexprに渡す。空白と改行は無視して、(が来たらparentheses、それ以外の文字が来たらnumberやsymbolに渡す。)が来て括弧の収支が合ったら終了。parenthesesでは括弧の収支が合うまでexprで読む。

long* parentheses(){
    long *begin = calloc(2, sizeof(long));
    long *p, *q; p = begin;
    int cnt = parentheses_count - 1;
    while(true){
        *p = (long)expr();
        if(eq(p, nil) == t){
            return begin;
        }else{
            q = calloc(2, sizeof(long));
            *(p + 1) = (long)q;
            p = q;
        }
        if(cnt == parentheses_count) return begin;
    }
}

long* expr(){
    char c;
    while(!feof(fp)){
        c = fgetc(fp);
        if(c == EOF) return nil;
        if(c == ' ') continue;
        if(c == '\n'){
            line_number++;
            continue;
        }
        if(c == '('){
            parentheses_count++;
            return parentheses();
        }else if(c == ')'){
            parentheses_count--;
            if(parentheses_count < 0){
                printf("error %d : parnetheses don't correspond.\n", line_number);
            }
            return (long*)0;
        }
        else if('0' <= c && c <= '9') return number(c - '0');
        else return symbol(c);
    }
}

評価(eval.c)

読み込んだ結果をevalに渡す。evalの中身を順番に見ていく。 まず文字列がt,nilに一致したらそれを返す。

    if(equal(p, "t")) return t;
    else if(equal(p, "nil")) return nil;

次に宣言された変数名に等しければその値を返す。varが変数名の配列、valueが値の配列となっている。

    for(int i = var_count - 1; i >= 0; i--){
        if(eq(p, var[i]) == t) return value[i];
    }

それ以外の場合は最初の要素が関数や特殊形式なので、関数名tokenと引数argsに分ける。

    long* token = car(p);
    long* args = cdr(p);

基本関数の評価。

    if(equal(token, "atom")) return atom(eval(car(args)));
    else if(equal(token, "eq")) return eq(eval(car(args)), eval(car(cdr(args))));
    else if(equal(token, "car")) return car(eval(car(args)));
    else if(equal(token, "cdr")) return cdr(eval(car(args)));
    else if(equal(token, "cons")) return cons(eval(car(args)), eval(car(cdr(args))));

特殊形式の評価。quoteについては引数をそのまま返す。lambdaは引数の組と処理の内容を返す。defineはvar,valueに変数を登録する。

    if(equal(token, "cond")){
        while(eq(args, nil) == nil){
            long* condition = car(car(args));
            long* expression = car(cdr(car(args)));
            if(eval(condition) == t) return eval(expression);
            args = cdr(args);
        }
        return nil;
    }
    else if(equal(token, "quote")){
        return car(args);
    }
    else if(equal(token, "lambda")){
        return args;
    }
    else if(equal(token, "define")){
        var[var_count] = car(args);
        value[var_count] = eval(car(cdr(args)));
        var_count++;
        return value[var_count - 1];
    }

最後にラムダ式の展開。tokenがそれ以前に登録したラムダ式の名前に一致するとき、引数を評価してvar,valueに加えた上で、ラムダ式の内容をevalで評価する（defineで定義した変数とラムダ式の引数は分けた方が良いかもしれない）。再帰呼び出しする場合は引数の名前を複数登録することになるが、evalの冒頭で新しい順に変数名を照合しているので問題ない。

        for(int i = var_count - 1; i >= 0; i--){
            if(eq(token, var[i]) == t){
                token = value[i];
                break;
            }
        }
        long* params = car(token);
        int n = 0;
        while(eq(params, nil) == nil){
            var[var_count] = car(params);
            value[var_count] = eval(car(args));
            var_count++;
            n++;
            params = cdr(params);
            args = cdr(args);
        }
        long* ret = eval(car(cdr(token)));
        for(int i = 0; i < n; i++){
            var_count--;
            var[var_count] = 0;
            value[var_count] = 0;
        }
        return ret;

テスト

バグってるかもしれないけど。sample.lisp

(quote 1)
(quote (1 2 3 4))
(atom (quote 1))
(atom (cons (quote 1) (quote 1)))
(eq (cons (quote 2) (quote 3)) (cons (quote 2) (quote 3)))
(car (cons (cons (quote 1) (quote 2)) (quote 3)))
(cdr (cons (cons (quote 1) (quote 2)) (quote 3)))
(cond
    ((eq (quote 1) (quote 1)) (quote 2))
    ((quote t) (quote 3))
)

(define inc (lambda (x) (cons (quote 1) x)))
(inc (quote (1 1)))

(define append
    (lambda (x y)
        (cond
            ((eq x nil) y)
            (t (cons (car x) (append (cdr x) y)))
        )
    )
)
(append (quote (1 2 3)) (quote (4 5 6 7)))

(define f (lambda (x) (cons x (quote 2))))
(define g (lambda (f x) (f x)))
(g f (quote 3))

に対して実行すると

> .\lisp sample.lisp
1
1 2 3 4 0
1
0
1
1 2
3
2
((120 0) 0) ((99 111 110 115 0) ((113 117 111 116 101 0) 1 0) (120 0) 0) 0
1 1 1 0
((120 0) (121 0) 0) ((99 111 110 100 0) (((101 113 0) (120 0) (110 105 108 0) 0) (121 0) 0) ((116 0) ((99 111 110 115 0) ((99 97 114 0) (120 0) 0) ((97 112 112 101 110 100 0) ((99 100 114 0) (120 0) 0) (121 0) 0) 0) 0) 0) 0
1 2 3 4 5 6 7 0
((120 0) 0) ((99 111 110 115 0) (120 0) ((113 117 111 116 101 0) 2 0) 0) 0       
((102 0) (120 0) 0) ((102 0) (120 0) 0) 0
3 2

となる。リスト末尾のnil(0)が表示されてる。ごちゃごちゃしてるのはdefineとかlambdaの返り値で、文字コードをそのまま出力している。

関連文献

簡易LISP処理系の実装例【各言語版まとめ】

簡易LISP処理系の実装例（C言語版）