JavaScriptでおもちゃのLispを作ろう(4) 〜評価器編〜

いよいよ評価器の実装を行います。Lispの評価器はeval()関数を実装することです。eval()関数はLisp自身で実装することができます。Lisp自身によるeval関数の実装はLispの古典であるLisp1.5マニュアルによると以下のようになります。

apply [fn;x;a] =
   [atom[fn]→[eq[fn;CAR]→caar[x];
               eq[fn;CDR]→car[x];
               eq[fn;CONS]→cons[car[x]; cadr[x]];
               eq[fn;ATOM]→atom[car[x]];
               eq[fn;EQ]→eq[car[x];cadr[x]];
               T→apply[eval[fn;a];x;a]];
    eq[car[fn];LAMBDA]→eval[caddr[fn];pairlis[cadr[fn];x;a]];
    eq[car[fn];LABEL]→apply[caddr[fn];x;cons[cons[cadr[fn];caddr[fn]];a]]]

eval[e;a] =
  [atom[e]→cdr[assoc[e;a]];
   atom[car[e]]→[eq[car;QUOTE]→cadr[e];
                  eq[car[e];COND]→evcon[cdr[e];a];
                  T→apply[car[e];evlis[cdr[e];a];a]];
   T→apply[car[e];evlis[cdr[el;a];a]]

このレベルのものをJavaScriptで実装するという単純な方針とします。a-listを使ったdeep bind方式の環境をそのまま実装したらさすがに遅いので、変数オブジェクトのプロパティに値をバインドして、古い値はスタックに退避しておくというshallow bind方式にします。また、applyもCAR,CDR,CONSなどの場合分けは無駄なので、全て組込み関数の処理としてevalの中でまとめて処理することにします。まず、変数スタックのコードは以下のようになります。getValue/setValueは第１回目に定義した関数です。

var valuestack = [];

/**
 * 変数と値のペアを表現するオブジェクト。
 */
function Env(symbol, value) {
  this.symbol = symbol;
  this.value = value;
}
/**
 * 変数とその値をvaluestackに退避する。
 */
function vpush(sym) {
  valuestack.push(new Env(sym, getValue(sym)));     
}
/**
 * valuestackに退避した変数と値をn個だけ戻して、現在の変数の値として
 セットする。
 */
function vpop(n) {
  while (n-- > 0) {
    var env = valuestack.pop();
    setValue(env.symbol, env.value);
  }
}

これらの関数を使ってlambda式評価の元となる変数束縛を実装します。いま、変数のリスト(a b c)と束縛すべき値のリスト(3 5 7)を与えたとき、a=3, b=5, c=7 にように変数に値をセットする関数lambdaBind()を以下のように定義します。実際にセットした変数の数を返します。

function lambdaBind(vars, args) {
  if (vars === NIL) {
    return 0;
  } else if (symbolp(vars)) {
    vpush(vars);
    setValue(vars, args);
    return 1;
  } else {
    var n = 0;
    var sym = vars;
    var arg = args;
    for (; !atom(sym); sym = cdr(sym), arg = cdr(arg)) {
      vpush(car(sym));
      setValue(car(sym), car(arg));
      n++;
    }
    if (sym !== NIL) {
      vpush(sym);
      setValue(sym, arg);
    }
    return n;
  }
}

ドット記法を使うことでオプション引数なども表現しています。例を以下に示します。

vars	args	結果
x	(1)	x=1
x	(1 2)	x=(1 2)
(x y)	(1 2)	x=1, y=2
(x . y)	(1 2)	x=1, y=(2)
(x y . z)	(1 2 3 4)	x=1, y=2, z=(3 4)

これを利用して、eval関数は以下のようになります。evalというJavaScriptと同じ名前にしていますが、後にクロージャ中で定義する関数にしますので、JavaScriptのevalとは衝突しません。

function eval(exp) {
  var rv;
  if (atom(exp)) {
    if (symbolp(exp)) {
      rv = getValue(exp);
      if (rv === undefined) {
        throw "unbound variable: " + exp;
      }
    } else {
      rv = exp;
    }
  } else if (listp(exp)) {
    var proc = eval(car(exp));
    var args = cdr(exp);
    if (procedurep(proc)) {
      if (!proc.lazy) {
        args = evlis(args);
      }
      var rv = apply(proc, args);
    } else if (car(proc) === LAMBDA) {
      args = evlis(args);
      var n = lambdaBind(cadr(proc), args);
      rv = progn(cddr(proc));
      vpop(n);
    }
  }
  return rv;
}

evlisは関数の引数のリストをそれぞれ評価してリストにする関数で、以下のようになります。Lispらしく再帰で書いた方がよいかも知れませんが、ここではループにします。

function evlis(args) {
  if (args === NIL) {
    return NIL;
  } else if (listp(args)) {
    var top = cons(eval(car(args)), NIL);
    var pp = top;
    for (var p = cdr(args); !atom(p); p = cdr(p)) {
      var v = cons(eval(car(p)), NIL);
      pp.cdr = v;
      pp = v;
    }
    return top;
  }
}

Lispの組込み関数はProcedureというオブジェクトにします。nameが関数名、funがJavaScriptの実装関数、lazyはtrueのとき引数を評価しないでそのまま関数に渡すことを示すフラグ。apply関数のProcedureを与えられた引数に適用するもの。

function Procedure(name, fun, lazy) {
  this.name = name;
  this.fun = fun;
  this.lazy = lazy;
}

Procedure.prototype.toString = function () {
  return "#<proc " + this.name + ">";
};

function apply(proc, args) {
  var fun = proc.fun;
  return fun.call(null, args);
}

以上で、組込み関数も制御構造も何もないピュアなLisp処理系ができました。簡単なテストをしてみましょう。

組込み関数consを定義して、

((lambda (x y) (cons y x)) 'a 'b)

を実行するには以下のようになります。

function test() {
  var sym = intern("cons");
  sym.value = new Procedure("cons", function (x) {
    return cons(car(x), cadr(x));
  });
  var s = "((lambda (x y) (cons y x)) 'a 'b)";
  var t = read(s);
  var u = eval(t);
  var pr = new Printer;
  pr.printExp(u);
}

test()関数の実行結果は期待通り

(b . a)

と出力されました。

今回はここまです。ピュアLispができても、このままでは使えません。次回は組込み関数をどんどん定義して多少なりとも実用的なレベルにします。