特集記事

JavaScriptでつくるSchemeインタプリタの基礎の基礎

JavaScriptによるSchemeの実装

zick[著]

2006/12/12 00:00

ポスト

入出力

入力の変換

　文字列である入力をインタプリタ内部形式に変換するルールは意外と簡単です。まず、入力された文字列をトークンに切り分け、順番に返す関数を用意します。トークンの区切りは、空白、「(」「)」「'」「.」です。

　次に、変換のために次の2つの関数を作ります。

InputToLObject
InputToList

　InputToLObjectは次の役割を持ちます。

トークンを1つ読み出す
トークンが数字なら数値オブジェクト（Num）を生成してそれを返す
トークンが「(」以外ならシンボル（Symbol）を生成してそれを返す
トークンが「(」なら、InputToListに続きの文字列を渡す

　InputToListは次の役割を持ちます。

対応する「)」が出てくるまでトークンを読み出し、InputToLObjectに渡し、その戻り値をコンスにつなぐ
対応する「)」が見つかれば、戻り値をつないできたリストを返す

　この2つがお互いを再帰的に呼び合うことにより、意外と簡単に文字列である入力が、コンスからなるリストに変換されます。'hogeを(quote hoge)に変換する処理や、「.」への対応も少し工夫すれば記述できます。

出力への変換

　プログラムを実行した結果はインタプリタの内部形式なので、これを出力する前にいったん文字列に変換する必要があります。しかし、これは入力を変換する処理の逆を行うだけなので、比較的楽に記述できるかと思います。

式の評価

評価の規則

　Schemeでは、プログラムのことを「式」、プログラムを実行することを「式を評価する」と言います。この式の評価器こそがインタプリタの根幹であり、最も重要な部分です。

　式の評価は次の3つの規則からなります。

式が数値ならそれ自身を返す
式がシンボルなら環境から対応する値を取り出して返す
式がコンスなら、CAR部を関数、CDR部を引数のリストとして関数呼び出しを行う

　1つ目の規則は、単に数値が入力されても特に操作をしないというものです。3つ目の規則は、冒頭で挙げた関数呼び出しの規則です。2つ目の規則において「環境」という言葉が出てきましたが、これは次項で説明します。

環境の設計

　環境とは「変数とその値の対応表」です。ここではリストを用いて、次のように表します。

((変数名1 . 値1) (変数名2 . 値2) (変数名3 . 値3))

　変数名にはシンボルを用いますが、値の型は問いません。大域環境（グローバル変数の値の対応表）は、最初は次のように定義しておくと良いでしょう。

((dummy . dummy) (nil . nli) (#t . #t) (#f . #f))

　dummyは環境の先頭を表すためにおいているシンボルです。この値を用いることはありません。nilは既に述べたとおりで、#tと#fは、真／偽を表すのに使用するシンボルです。これらのシンボルは、評価した際にそのままの値が返るように定義しています。この大域環境を、評価器に、入力された式と共に送ります。

評価器の実装

　では、上記の設計を元に評価器を実際に作ってみます。

Evalの実装

function Eval(s, env) {
  if (s.tag == TAG_NUM)
    return s;
  if (s.tag == TAG_SYMBOL)
    return CDR(Assoc(s, env)); /* 環境から値を取り出す */
  if (s.tag == TAG_CONS)
    return Apply(Eval(CAR(s), env), CDR(s), env);
}

function Assoc(key, lst) {
  ret = nil;
  while (lst != nil) {
    if (key == CAR(CAR(lst)))
      return CAR(lst);
    lst = CDR(lst)
  }
  return nil;
}

function Apply(fn, args, env) {
  /* 関数呼び出しを行う（後述） */
}

　上の定義から分かるように、(fn arg1)という式を評価しようとすると、fnを評価したものが関数、(arg1)というリストが引数となります。このように、引数はリストとして渡されるということに注意してください。

　次はApplyを実装して関数の呼び出しをできるようにします。

組み込み関数

組み込み関数の設計

　組み込み関数は大きく分けて2つあります。carのように引数を評価するものと、quoteのように引数を評価しないものです。前者をSUBRと呼び、後者をFSUBRと呼びます。引数を評価する／しないといってもピンとこないと思うので、(car '(a b c))という式を見てください。これはいったん(car (quote (a b c))) という式に変換されます。carは引数を評価するので、関数carが呼ばれる前に((quote (a b c)))のすべての要素（と言っても(quote (a b c))1つですが）が評価されます。

　一方、quoteは引数を評価しないので、関数quoteに((a b c))というリストが直接渡されます。quoteは第1引数である(a b c)をそのまま返します。そして、関数carには((quote (a b c)))の第1要素をquoteの戻り値に置換した((a b c))というリストが引数として渡されます。

注意

　Schemeでは本当は、SUBR、FSUBRという言葉は用いられません（FSUBRのように引数を評価しないものは関数と言わず、別の呼び方をします）。これは、古いLispで使われていた言葉ですが、この考え方のほうが簡単にインタプリタを作れるので、SUBR、FSUBRという言葉を使いました。

　SUBR/FSUBRをオブジェクトとして扱えるように次のように定義します。

SUBR/FSUBRの定義1

var TAG_SUBR = 3;
var TAG_FSUBR = 4;

function SUBR(fn) {
  this.tag = TAG_SUBR;
  this.func = fn;
}

function FSUBR(fn) {
  this.tag = TAG_SUBR;
  this.func = fn;
}

　これも、CreateSUBRとCreateFSUBRという関数を作っておきます。ただし、SUBRに格納する関数は1引数の関数、FSUBRに格納する関数は2引数の関数とします。SUBRは引数のリストを受け取り処理をするだけですが、FSUBRは特定の引数を評価することがあるため、評価に必要な環境を受け取る必要があります。

　では、実際に使ってみましょう。

SUBR/FSUBRの定義2

function LF_car(args) {
  var arg1 = CAR(args); /* 第1引数を取得 */
  return CAR(arg1);
}

function LF_quote(args, env) {
  var arg1 = CAR(args); /* 第1引数を取得 */
  return arg1;
}

/* 大域環境に要素を追加 */
AddBindToEnv(globalEnv, CreateSymbol("car"), CreateSUBR(LF_car));
AddBindToEnv(globalEnv, CreateSymbol("quote"), CreateFSUBR(LF_quote));

　AddBindToEnvにより2つの引数を受け取り、それにより対リストを作り、環境に加える関数として実装します。これにより、carというシンボルとその処理をするSUBR型のオブジェクトと、quoteというシンボルとその処理をするFSUBR型のオブジェクトが作られました。後は、関数呼び出しを行うApplyを実装するだけです。

Applyの実装

Apply/Evlis

function Apply(fn, args, env) {
  if (fn.tag == TAG_SUBR) /* SUBRは引数を評価 */
    args = Evlis(args, env);

  if (fn.tag == TAG_SUBR)
    return fn.func(args);
  if (fn.tag == TAG_FSUBR) {
    return fn.func(args, env);
  return nil; /* Error! */
}
function Evlis(args, env) {
  var p = args, tmp;
  var ret = CreateCons();
  var current = ret;
  while (p != nil) {
    tmp = CreateCons();
    SetCAR(tmp, Eval(CAR(p), env));
    SetCDR(current, tmp);
    current = tmp;
    p = CDR(p);
  }
  SetCDR(current, nil);
  return CDR(ret);
}

　Evlisは与えられたリストのすべての要素を評価して、それをリストにしたものを返します。それさえ分かれば、案外あっさりと終わってしまうものです。これで、入力、実行、出力ができたので、組み込み関数さえ増やせば、最低限のインタプリタとしては一応完成です。

用意すべき組み込み関数

　最低限必要な関数はcar、cdr、cons、eq?、atom?の5つです。

　carは引数のCAR部を取り出し、cdrは引数のCDR部を取り出します。consは新たなコンスを作り、CAR部に第1引数、CDR部に第2引数を代入して返します。eq?は第1引数と第2引数が同一のオブジェクトである場合に#tを、そうでなければ#fを返します。数値の場合は、異なるオブジェクトでも、保持する値で比較します。atom?は引数がコンスであれば#fを、そうでなければ#tを返します。以下がこれらの定義になります。

基本的な組み込み関数

var sharp_t = CreateSymbol("#t");
var sharp_f = CreateSymbol("#f");
function LF_car(s) {
  var x = CAR(s);
  if (x == nil)
    return nil;
  return CAR(x);
}
function LF_cdr(s) {
  var x = CAR(s);
  if (x == nil)
    return nil;
  return CDR(x);
}
function LF_cons(s) {
  var x = CAR(s);
  var y = CAR(CDR(s));
  var ret = CreateCons();
  SetCAR(ret, x);
  SetCDR(ret, y);
  return ret;
}
function LF_eq(s) {
  var x = CAR(s);
  var y = CAR(CDR(s));
  if (x.tag == TAG_NUM && y.tag == TAG_NUM && GetNum(x) == GetNum(y))
    return sharp_t;
  if (x == y)
    return sharp_t;
  return sharp_f;
}
function LF_atom(s) {
  var x = CAR(s);
  if (x.tag != TAG_CONS)
    return sharp_t;
  return sharp_f;
}