Lecture Notes

1-3 インタプリタ

字句解析と構文解析が終わって木構造になった Lisp プログラムを interpret する方法を解説する。なお、これから作成する Lisp インタプリタは整数だけを扱える単純なものである。またガベージコレクション (GC: garbage collection) の機能もない。

木構造の操作

構文解析の結果得られる木構造のことを「構文木」と呼ぶ。Lisp の文法は単純なので、構文木は元のプログラム中の括弧の対応をそのまま反映したリスト構造である。

リスト構造を操作するための関数をいくつか用意した。(lisp.c)

int TestElementType(List* lst)

int GetIntegerElement(List* lst)

char* GetSymbolElement(List* lst)

List* GetListElement(List* lst)

List* GetSecond(List* lst)

List* GetThird(List* lst)

List* GetNth(List* lst, int n)

なお前回の関数群も lisp.c の中に定義してある。

環境 (Environment)

まず、

(define x 3) (+ x (+ x 2)) のような式に対応するリスト構造が与えられたとき、それを計算する関数 EvalList() を書こう。

int EvalList(Environment* env, List* expr)
{
    char* op = GetSymbolElement(expr);
    if (strcmp(op, "+") == 0)
        return EvalPlus(env, expr);
    else if (strcmp(op, "define") == 0)
        return EvalDefine(env, expr);
    else
        以下省略
}

この関数はまずリスト expr の先頭を調べて、+ なら EvalPlus() を呼んで加算を実行し、define なら EvalDefine() を呼んで変数を定義する。なお式の先頭は必ず名前であり、整数やリストではないと仮定している。

EvalList() の第一引数は環境(Environment)である。プログラムの実行中は、変数の値や関数の定義などをどこかに記録しておかなければならない。これを記録するためのデータ構造を一般に、環境と呼ぶ。環境に対する主要な操作は、名前と値のペアの登録と、名前から対応する値を探す操作である。

この講義では、非常に単純化して、環境を次のような構造体で表現する。


#define ENVIRONMENT_SIZE 64

struct _env {
    int         num;
    char*       symbols[ENVIRONMENT_SIZE];
    int         kinds[ENVIRONMENT_SIZE];   /* NUMBER or LIST */
    union {
        int     number;
        List*   list;
    } values[ENVIRONMENT_SIZE];
    struct _env* parent;
};

typedef struct _env Environment;

本来、環境は任意個数の名前を登録できなければならないが、単純化して、この実装では最大 64 個の名前しか登録できない。また、名前の検索を高速化するため、通常はハッシュ表などを用いるが、ここでは線形探索をすることとし、単純な配列を使っている。

環境に登録される名前には、さまざまな型の値が結び付けられる。この講義で作成する Lisp インタプリタは整数しか扱えないことにするが、環境には関数名も登録しなければならないので、結局、環境に登録される名前に結び付けられる値の型は、整数かリストのふたつとなる。これを区別するために、上の構造体では、kinds という配列を用意してある。例えば、整数を登録する関数は次のようになる。

void RecordInteger(Environment* env, char* symbol, int value)
{
    if (env->num >= ENVIRONMENT_SIZE) {
        fputs("Fatal error: environment overflows.\n", stderr);
        exit(1);
    }
    int i = env->num;
    env->symbols[i] = symbol;
    env->kinds[i] = NUMBER;
    env->values[i].number = value;
    ++env->num;
}

配列 symbols に登録される名前が、kinds に種類(NUMBER)が、values に値がそれぞれ代入される。配列 values は int でも List* でも代入できるように union 型になっている。

なお lisp.c の中にはりスト型の値を登録する関数も同様に定義してある。違いは配列 kinds に LIST を代入することと、配列 values[i].number ではなく values[i].list に値を代入することである。

void RecordList(Environment* env, char* symbol, List* value)

一方、環境から名前を探索するときは次の関数を使う。

int LookupNumberSymbol(Environment* env, char* symbol)

List* LookupListSymbol(Environment* env, char* symbol)

int LookupSymbol(Environment* env, char* symbol)

式の評価

さて準備が整ったので、加算を実行する関数 EvalPlus() を書こう。なお Lisp では、プログラムを実行することをプログラム(ないしは式)を評価(evaluate)するという。

int EvalList(Environment* env, List* expr)
{
    char* op = GetSymbolElement(expr);
    if (strcmp(op, "+") == 0)
        return EvalPlus(env, expr);
    else if (strcmp(op, "define") == 0)
        return EvalDefine(env, expr);
    else
        以下省略
}

EvalPlus() の仕事は、2つのオペランド(operand)の値を計算して、それらを足しあわせた値を返すことである。

int EvalPlus(Environment* env, List* expr)
{
    int x = EvalOperand(env, GetSecond(expr));
    int y = EvalOperand(env, GetThird(expr));
    return x + y;
}

式は (+ x 3) のような形をしているので、オペランドを得るにはそれぞれ GetSecond(), GetThird() を呼べばよい。

オペランドは、整数値、変数、別な式の３つの可能性があるので、オペランドを評価する関数 EvalOperand() はまずオペランドの型を調べて、それぞれの型に合わせて計算を実行する。

int EvalOperand(Environment* env, List* expr)
{
    switch (TestElementType(expr)) {
    case NUMBER :
        return GetIntegerElement(expr);
    case SYMBOL :
        return LookupNumberSymbol(env, GetSymbolElement(expr));
    case LIST :
        return EvalList(env, GetListElement(expr));
    default :
        fputs("Fatal error: invalid list\n", stderr);
        exit(1);
    }
}

オペランドが数字の場合は、その値を GetIntegerElement() で取り出す。リストの場合は、EvalList() を再帰的に呼び出す。もしオペランドが変数名ならば、環境 env を調べてその変数の値を得る。

変数の定義

変数を定義する define 式は次のような形をしている。

(define x (+ 3 1))

この define 式は初期値 4 の変数 x を定義する。このような式を評価する関数 EvalDefine() は、２番目の変数名を取り出し、３番目の式を EvalOperand() で評価する。

int EvalDefine(Environment* env, List* expr)
{
    char* symbol = GetSymbolElement(GetSecond(expr));
    int value = EvalOperand(env, GetThird(expr));
    RecordInteger(env, symbol, value);
    return value;
}

main 関数

以上のプログラムで式を評価することが可能になる。標準入力から Lisp プログラムを読み込んで評価、結果を表示する main 関数は次のようになる。

main()
{
    List* prog;
    Environment env;

    InitializeEnvironment(&env, NULL);
    for(;;) {
        prog = Read();
        if (prog == NULL)
            break;
        else
            printf("%d\n", EvalList(&env, prog));
    }
}

InitializeEnvironment() は環境 env を初期化するための関数である。

関数の定義

いやしくも Lisp のインタプリタを名乗るのなら、少なくとも関数が使えなければならないだろう。defun という命令を実装して、

(defun add (x y) (+ x y)) を実行すると関数 add が定義されるようにしよう。引数は x と y で、関数本体は (+ x y) である。

defun を実装する関数 EvalDefun() は EvalDefine() とほぼ同様である。違いは名前に結び付く値が整数ではなく、リストである点である。上の例の場合、環境に名前 add と値 ((x y) (+ x y)) のペアを登録すればよい。なお Lisp では defun も何らかの値を返すのが普通である。任意の値でよいが、ここでは defun は 1 を返すことにする。

関数の評価と環境の入れ子

評価する式の先頭の名前が、組み込みの演算子でも命令でもなければ、それは defun で定義された関数であると考えられる。したがって関数呼び出し(Lisp の用語では関数適応: apply)も扱えるようにした EvalList() は次のようになる。

int EvalList(Environment* env, List* expr)
{
    char* op = GetSymbolElement(expr);
    if (strcmp(op, "+") == 0)
        return EvalPlus(env, expr);
    else if (strcmp(op, "define") == 0)
        return EvalDefine(env, expr);
    else if (strcmp(op, "defun") == 0)
        return EvalDefun(env, expr);
    else
        return EvalFunction(env, op, expr);
}

関数呼び出しを実行するのが EvalFunction() である。EvalFunction() の実装の要点は、どのようにして局所変数を実現するかである。例えば関数 add の場合、関数本体(+ x y) を評価する際には、局所変数 x と y に実引数の値が結びつけられていなければならない。そこで、

List *function, *args, *body;

expr = GetSecond(expr);                     /* 実引数列を得る */
function = LookupListSymbol(env, op);       /* 関数定義を探す */
args = GetListElement(function);            /* 仮引数を得る */
body = GetListElement(GetSecond(function)); /* 関数本体を得る */
while (args != NULL) {
    char* symbol = GetSymbolElement(args);
    int value = EvalOperand(env, expr);
    RecordInteger(env, symbol, value);      /* 環境に登録 */
    args = GetSecond(args);                 /* 次の引数 */
    expr = GetSecond(expr);
}

このようにすると、実引数をひとつづつ EvalOperand() で評価して、結果を仮引数の名前で環境に登録することができる。この後、

return EvalList(env, body);

とすれば、うまく関数本体を評価することができる。

以上のような実装で、一見うまくいきそうだが、実はこれでは局所変数を実現したことにならない。局所変数 x と y が有効なのは、関数 add の本体を評価している間だけで、評価後は環境から取り除かなければならない。さらに問題なのは、もし、

(define x 3)
(define y 4)
(add 5 7)

と評価した後は、環境から局所変数 x (=5) と y (=7) を取り除くだけでなく、元々 define で定義していた変数 x (=3) と y (=4) を元に戻さなければならない。

この問題をうまく解決するには、関数呼び出しを実行するたびに、新しい環境をつくり、その環境の下で関数本体を評価し、呼び出しが終了したら元の古い環境で評価を続けるようにすればよい。局所変数は、すべて新しく作った環境に登録することになる。

しかし、まったく新しい環境を作ったのでは、それまでに登録した関数などが探せなくなってしまう。そこで新しい環境を作る際には、まずそれまでの古い環境の内容を全てコピーしなくてはならない。

ところが環境の内容をいちいちコピーするのは効率が悪いので、一般には、入れ子になった環境を使って、同等の効果を実現する。新しく作る環境に、元の古い環境へリンクを持たせ、名前を検索する際に、新しい環境の中で見つからなければ、古い環境を検索するようにするのである。こうするとコピーしたのと同等の効果を得ることができる。

lisp.c の中で実装されている環境は、すでに環境の入れ子を作れるようになっている。環境をあらわす構造体の要素 parent は、元の環境を指すポインタである。入れ子になった環境を作るには、

Environment new_env;
InitializeEnvironment(&new_env, env);

とすればよい。new_env が新しく作られた環境で、env が古い環境である。main() 関数の中で、環境を用意したときは、元になる環境がないので、InitializeEnvironment() の第２引数は NULL であった。

課題3

lisp.c、lisp.h、 read.c や eval.c を参考に Lisp のインタプリタを完成させよ。字句解析、構文解析のプログラムは課題2で作成したものを用いよ。次のLisp プログラムが動けばよい。

(define x 3) ; 変数 x を宣言
(define y 4) ; 変数 y を宣言
(defun f (y z) (+ (+ x y) z)) ; 関数 f を宣言
(f 5 1)      ; 関数 f の呼び出し
(+ x y)      ; x + y の計算

変数 x は大域変数、z は関数 f の局所変数である。変数 y は大域変数と局所変数の両方が宣言されている。環境の実装が正しければ、関数 f の内部では局所変数 y が、関数の外では大域変数 y が有効になるはずである。

なおプログラムのコンパイルは次のようにする。yylex.c は課題2で作成した字句解析器である。

gcc lisp.c read.c eval.c yylex.c

つぎに - や * など他の演算子も追加し、また if 文が使えるようにせよ。

if 文は例えば

(if (- x 3) (+ x 1) (- x 1))
(if x y z)

のような形をとる。条件式の値が 0 以外なら then 式を、そうでなければ else 式を評価する。

目次へ戻る

Email: chiba@is.tsukuba.ac.jp