minilispのevalを解説する

ruiさんのminilispの評価器のところを勝手に解説します。
対象読者はタイムインターメディアの社内勉強会のメンバーですが誰かの役に立つかもしれないと思い公開します。

https://github.com/rui314/minilisp/blob/nogc/minilisp.c#L352 からがevaluatorです。

static Obj *eval(Obj *env, Obj *obj);

evalを構成する関数の中でevalを使うためにプロトタイプ宣言しておきます。

static void add_variable(Obj *env, Obj *sym, Obj *val) {
    env->vars = acons(sym, val, env->vars);
}

envは環境フレームで、上位の環境(up)と、自分自身が持っている変数(vars)との組になっています。
add_variableはvarsに変数を追加します。varsはalistになっています。
変数の追加は単に今までのvarsにaconsした結果を新しいvarsにするだけです。

// Returns a newly created environment frame.
static Obj *push_env(Obj *env, Obj *vars, Obj *values) {
    if (list_length(vars) != list_length(values))
        error("Cannot apply function: number of argument does not match");
    Obj *map = Nil;
    for (Obj *p = vars, *q = values; p != Nil; p = p->cdr, q = q->cdr) {
        Obj *sym = p->car;
        Obj *val = q->car;
        map = acons(sym, val, map);
    }
    return make_env(map, env);
}

これは環境フレームを作る関数ですが、関数呼び出し処理の一部です。ちょっとここで環境フレームとスコープについての解説。

環境フレームが作られる時というのはつまりスコープが作られる時ということになります。馴染みのあるschemeの例だとlambdaとlet系の構文がスコープを作っています。letは意味的には

(let ((x a)
      (y b))
  body...)
;;↓
((lambda (x y) body...) a b)

のように解釈できます。xとyが定義される環境は関数が実際に呼び出されて、関数のbody部分に来たときに新しく発生しているわけです。つまり、lambdaこそがスコープを作る構文ということになります。

これを踏まえて、push_envが何をしているか見ていきます。まず引数のvarsというのは関数のパラメータで(xとy)、valuesは実引数です(aとb)。最初のエラーチェックは関数適用ができるかどうかの引数の個数チェックです。
次のfor文はvarsとvaluesをzipしてalistを作っています(変数map)。
最後に上位環境とこのmapを使って、新しい環境を作れば、めでたく関数本体を実行するときに使う環境が完成です。

続く