((schemeっぽい処理系)を書いてみた)

schemeっぽい処理系jellyfishを書いてみました．ここにおいています．ただ，あくまでもオレオレ実装なのでRnRSには対応していません． schemeは，処理系の自作としては定番のようですが，その割には解説した記事が少ないと感じます．ここでは簡単ですが，その実装方法などを書きたいと思います．

読者として想定しているのはbrainfuck処理系を書いてみて，もう少し高級?なオレオレ処理系(schemeに限らず)を書きたいなと思ってるそんな方々です．なんや簡単やんと思っていただけたら幸いです．

jellyfishではこんなプログラムが動いてくれます．簡単な組み込み関数(evalを含む)，高階関数は実装しています．

;
; quick sort
;
(define (part c y x)
    (if (null? y)
      '()
      (if (c (car y) x)
        (cons (car y) (part c (cdr y) x))
        (part c (cdr y) x))))

(define (quicksort x)
    (if (null? x)
      '()
      ((lambda (pivot)
        (append
          (quicksort (part < x pivot))
          (cons
            (car x)
            (quicksort (part > x pivot)))))
       (car x))))
;
; fizz buzz
;
(define check_fizzbuzz
  (lambda (x)
    (if (= (modulo x 15) 0)
      "FizzBuzz"
      (if (= (modulo x 5) 0)
        "Buzz"
        (if (= (modulo x 3) 0)
          "Fizz"
          x)))))

(define fizzbuzz
  (lambda (a b)
    (if (> a b)
      nil
      (begin
        (display (check_fizzbuzz a) " ")
        (fizzbuzz (+ a 1) b)))))

(define x '(fizzbuzz 1 50))
(display x " => ") (eval x) (newline)
(define x '(quicksort '(32 77 70 21 3 2 73)))
(display x " => " (eval x)) (newline)

まず，以下のようなことを考えてみます．

インタプリタか，コンパイラか
処理系を何言語で実装するか
構文(EBNFなどで書かれる)はどうするか
構文解析器はどうするか

jellyfishは，C言語で書かれた純粋なインタプリタ(中間コードは使わない，なんて言うんだろう) です． Ruby，Pythonなどスクリプト言語を使うとさらに簡単に処理系が書けますが，スクリプト言語の上で処理系動かすのもなーと思い， C言語でかきました．まあ何言語でもいいです．構文は以下のようにしました．構文解析器にはbison，字句解析器にはflexを使っています． bisonとflexは構文ルールを書いておけば自動で解析プログラム (C言語プログラム)を作ってくれます．

字句解析器は自分で実装できますが，構文解析器はLL文法と呼ばれるような簡単な構文でなければ既存の構文解析器に頼ったほうがよいです．

S式 = INTEGER | CHARACTER | SYMBOL | STRING | NIL | TRUE | FALSE | ( {S式} )

jellyfishでは，以下のような手順でschemeプログラムを動かしていきます．

字句解析(入力から括弧，整数，シンボルなどをトークンとして抜き出す)
↓
構文解析(トークンが構文を満たすかどうかチェックする)
↓
評価(eval()関数を実装して全部そこに投げる)

一つ一つ見ていくことにします．

字句解析

これはflexプログラム(lexer.l)の一部です．字句解析では，flexの構文ルールを以下のようにずらーと書いていきます．

[-]?[0-9]+   { sscanf(yytext, "%d", (int*)&yylval); return INTEGER; }
[(]          { paren_num ++; return LEFT_PAREN; }
[)]          { paren_num --; return RIGHT_PAREN; }
"\n"         { if(paren_num != 0) prompt_multi();}
"nil"        { return NIL; }
"#t"         { return TRUE; }
"#f"         { return FALSE; }

構文解析

EBNFに従い，bisonプログラム(parser.y)を書いていきます．こんな感じです． $$はその構文の返値になります．例えば，nilとか真偽値の場合はそれをそのまま返し， INTEGERなどではinteger2sexp()を呼んでその結果を返しています．括弧でくくられた場合は，cons()で繋いでS式でリスト構造を作っていきます． _noevalがついているのは，元々解析直後にすぐeval()を呼んでいたのでその名残ですね． jellyfish(schemeでも)では関数だけでなく特殊形式があるのでそうはいきません．

input :
        | input exp_noeval
          {
            struct s_exp *e = eval($2);
            if(interactive){
              write_sexp(e);
              putc('\n',stdout);
              prompt();
            }
            sexp_free(e,1);
          }
exp_noeval : INTEGER { $$ = integer2sexp($1);}
        | CHARACTER  { $$ = character2sexp($1);}
        | SYMBOL     { $$ = symbol2sexp($1);}
        | STRING     { $$ = string2sexp($1);}
        | NIL        { $$ = nil;}
        | TRUE       { $$ = sexp_t;}
        | FALSE      { $$ = sexp_f;}
        | QUOTE exp_noeval
          {
               struct s_exp *car = symbol2sexp($1);
               struct s_exp *cdr = cons($2, nil);
               $$ = cons(car,cdr);
          }
        | LEFT_PAREN members_noeval
          {
               $$ = $2;
          }
members_noeval : RIGHT_PAREN { $$ = nil; }
        | exp_noeval members_noeval
          {
            $$ = cons($1,$2);
          }

eval()

オレオレ処理系ではあとはeval()を作れば終わりです．こんな感じで，整数などなどの場合は評価値はそのままで，シンボルの場合はシンボルテーブルから引っ張ってきます．それ以外は特殊形式か，組み込み関数か，クロージャの呼び出しなのでそれぞれの処理に投げます．組み込み関数・特殊形式の呼び出しjf_apply_special(),jf_apply_builtin() の中身は想像の通り，単純に評価して新しいS式を返しているだけです．ユーザ定義の関数を実行するjf_apply_clojure()の中身も気になると思いますが，こっちはシンボルテーブルに引数を追加し，クロージャの本体を評価します．

struct s_exp *
eval(struct s_exp *e)
{
        struct s_exp *car, *cdr, *q, *p;

        if(is_singleton(e))
                return e;

        switch(e->type){
                case S_EXP_INTEGER:
                case S_EXP_CHARACTER:
                case S_EXP_STRING:
                case S_EXP_BUILTIN:
                case S_EXP_SPECIAL:
                case S_EXP_CLOJURE:
                        return e;
                case S_EXP_SYMBOL:
                        q = st_find(global_table, e->u.obj);
                        p = sexp_copy(q);
                        sexp_free(e,1);
                        return p;
        }

        car = e->u.pair.car;
        cdr = e->u.pair.cdr;
        sexp_free(e,0);

        q = eval(car);
        car = q;

        switch(car->type){
                case S_EXP_SPECIAL:        return jf_apply_special(car,cdr);
                case S_EXP_CLOJURE:        return jf_apply_clojure(car,cdr);
                case S_EXP_BUILTIN:        return jf_apply_builtin(car,cdr);
        }

        return nil;
}

bisonのサンプルプログラム(電卓?)を見てscheme処理系作れそうから始まり，大学のアルゴリズムの課題を自作処理系で動かせればステキというくだらんモチベーションだったので，だいたい成功ですが，反省点もあります．

仕様書も読まずに書いてしまったので互換性がない => まあいっか
メモリ管理を考えずに実装してしまった． => 後々valgrindチェックを通しました
lisp自体よりも処理系を書いていた時間が長く，lispわかってない => land of lisp買ってこよう

今後はマクロを実装したり，VM型に切り替えたりしようかなと企んでいます．

ぐだぐた書いてみましたが，自作scheme処理系を作りたい方は，前置記法な電卓作って，if文作って… としていれば何となくそれっぽいのは作れると思います．これが一番近道かもしれない．

字句解析#

構文解析#

eval()#

字句解析

構文解析

eval()