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
二つの値のペア
と特殊形式
のみからなるとする。
データの表現
LISPのリストは以下のようなコンスセルで表現される。
しかしこのままでは各要素がアトムなのかペアなのか判定できない。そこで隣接する二つのアドレス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
の返り値で、文字コードをそのまま出力している。