エンタープライズギークス (Enterprise Geeks)

企業システムの企画・開発に携わる技術者集団のブログです。開発言語やフレームワークなどアプリケーション開発に関する各種情報を発信しています。ウルシステムズのエンジニア有志が運営しています。

JavaScriptでLispインタープリターを作ろう(2) ~四則演算インタープリター編~

前回の記事では、JavaScriptで記述した小さな四則演算インタープリターの実装を紹介した。今回は、この四則演算インタープリターがどのように作られているかを解説する。

四則演算インタープリターの動かし方

まずはこの四則演算インタープリターの動かし方を紹介しよう。まずは非常に簡単な1 + 2の計算だ。1 + 2の計算は、四則演算インタープリターでは以下のように計算する。

>> evaluate(['+', 1, 2], globalEnv);
3

1 + 2は、四則演算インタープリターでは['+', 1, 2]といった配列で表記する。['+', 1, 2]という表記は、+という名前の関数に対し、引数として12の2つの引数を渡して実行することを意味する。より一般的に書くと、配列の第一要素は実行する関数であり、リストの第二要素以降はその関数に渡す引数である。Lispではリスト(ここでは配列で代用しているが)は関数呼び出しとみなし、このように記述するのである。

なお、足し算を行う関数名がplusaddsumではなく、+であることに違和感を持つ方も居るだろう。多くのプログラミング言語では、関数名としてアンダースコアなどの少数の記号が使えるだけで、+-*などの記号を関数名に用いる事は少ない。しかし、Lispでは関数名に様々な記号を用いる事が一般的である。

より複雑な(1 + 2) * (8 - 3)の計算もしてみよう。(1 + 2) * (8 - 3)の計算は、四則演算インタープリターでは以下のように計算する。

>> evaluate(['*', ['+', 1, 2], ['-', 8, 3]], globalEnv);
15

(1 + 2) * (8 - 3)は、四則演算インタープリターでは['*', ['+', 1, 2], ['-', 8, 3]]といった配列で表記する。(1 + 2) * (8 - 3)のように、計算順序を強制するための丸括弧がある場合であっても、四則演算インタープリターの表記方法では特別な事を考えることはない。

使い方を説明したところでインタープリターの実装内容を説明していこう。
四則演算インタープリターの実装は、大きな2つの構成要素から成り立っている。
1つはevaluate関数であり、もう1つはグローバル変数領域(globalEnv)である。

evaluate関数

四則演算インタープリターの中核となる仕組みは、たった10行のevalueate関数である。

var evaluate = function(x, env) {
  if (Array.isArray(x)) {
    var exps = x.map(function(exp) {return evaluate(exp, env);});
    var proc = exps.shift();
    return proc.apply(null, exps);
  } else {
    var y = env[x];
    return y !== undefined ? y : x;
  }
};

evaluate関数の処理内容を日本語で記述すると、以下の様になる。

if (引数のxが配列) {
  配列のすべての要素を再度evaluateで評価(処理)する
  配列の先頭要素は関数として扱うためprocという名前を付ける
  return procに配列の残りの要素を引数として渡して実行
} else {
  xをキーにglobalEnvを検索して結果をyとして受け取る
  return もしyがあればyを返却し、無ければ元のxを返却
}

処理中での大きな関心事の1つは、evaluate関数の引数xが配列か否かである。引数xが配列であれば、関数呼び出しと認識し、その関数を実行しようとする。一方、もし引数xが配列でなければ、evaluate関数に渡される変数領域(env)を探し、xが指し示す名前(変数名や関数名)に該当するもの(値や関数)があればそれを返すという挙動をする。

JavaScriptmap関数になじみの無い方は、

var exps = x.map(function(exp) {return evaluate(exp, env);});

の部分が分かりにくいかもしれない。
mapは、変換する関数を引数として受け取り、集合データを別の集合データに変換する関数である。Lispを初めとする多くの関数型言語で、標準機能としてサポートされている。map関数を使わずに記述すると以下のようになる。

// var exps = x.map(function(exp) {return evaluate(exp, env);}); を、
// map関数を使わずに書き直すと以下のようになる。
var exps = [];
for (var i = 0; i < x.length; i++) {
  exps.push(evaluate(x[i], env));
}

なお、このevaluate関数は、インタープリターであれば大抵存在するeval関数と同じ位置づけの存在である。この四則演算インタープリターの場合でもevalという名前の関数としたかったが、JavaScriptにも当然eval関数が既に存在し、関数名が重なってしまうため、evaluateという名前にして名前の衝突を回避している。

グローバル変数領域、globalEnv

四則演算インタープリターのもう1つの大きな構成要素は、グローバル変数領域(globalEnv)である。グローバル変数領域(globalEnv)そのものは、以下に示す通り、キーに対して値が保持される単なるハッシュマップである。ここでのキーは、インタープリター中では「関数名」や「変数名」である。また、値は関数名の場合には「関数オブジェクト」を表し、変数名の場合には「実際の値」を表す。

var globalEnv = {
  '+': function(a, b) {return a + b;},
  '-': function(a, b) {return a - b;},
  '*': function(a, b) {return a * b;},
  '/': function(a, b) {return a / b;},
  'mod': function(a, b) {return a % b;}
};

一般的にインタープリターには大抵グローバル変数領域があり、その領域には、あらかじめプログラム中のどこでも使用可能なグローバル変数や関数が用意されている。四則演算インタープリターの場合、globalEnvに用意したのは以下の5つの関数である。

関数名 引数 処理内容
+ 2つの数値 a + b
- 2つの数値 a - b
* 2つの数値 a * b
/ 2つの数値 a / b
mod 2つの数値 a % b

これらglobalEnvに用意したの5つの関数のうち、たとえば+関数の実体をevaluate関数で引きたい場合、以下のように実行する。

evaluate('+', globalEnv);

この結果は

function (a, b) {return a + b;}

となる。なぜこうなるかを順を追って説明する。

  1. evaluate('+', globalEnv);が実行されるとevaluate関数の第一引数x'+'という文字列が渡される。また、evaluate関数の第二引数envにはglobalEnvが渡される。
  2. evaluate関数の引数xには'+'という文字列が入るので、if文のArray.isArray(x)の判定結果はfalseになる。
  3. var y = env[x]が実行される。右辺を評価する際には、env(実体はglobalEnv)というハッシュマップに、'+'というキーで何か入っているか調べる。この場合、キー'+'には値function(a, b) {return a + b;}が入っているため、function(a, b) {return a + b;}yに入る。
  4. yはundefinedではないので、function(a, b) {return a + b;}が返却される。

このような挙動は、'+'以外のキーに対しても、以下のように同様に機能する。なお、以下の実行例はChromeブラウザーJavaScriptコンソール上での確認例だ。

>> evaluate('+', globalEnv);
function (a, b) {return a + b;}
>> evaluate('-', globalEnv);
function (a, b) {return a - b;}
>> evaluate('*', globalEnv);
function (a, b) {return a * b;}
>> evaluate('/', globalEnv);
function (a, b) {return a / b;}
>> evaluate('mod', globalEnv);
function (a, b) {return a % b;}

ちなみに円周率をグローバル変数領域(globalEnv)に用意したければ、以下のように円周率'PI'の定義を追加するだけだ。

var globalEnv = {
  '+': function(a, b) {return a + b;},
  '-': function(a, b) {return a - b;},
  '*': function(a, b) {return a * b;},
  '/': function(a, b) {return a / b;},
  'mod': function(a, b) {return a % b;},
  'PI': 3.14159 // 円周率
};

globalEnv'PI'が定義されれば、以下のようにその値を参照することが可能になる。

>> evaluate('PI', globalEnv);
3.14159

1 + 2の計算

四則演算インタープリターの大きな2つの構成要素である、evaluate関数とグローバル変数領域(globalEnv)についての解説が終わったので、これからは実際の計算がどのように進行するかを説明する。

まずは非常に簡単な1 + 2の計算だ。前述のとおり、1 + 2の計算は、四則演算インタープリターでは以下のように計算する。

>> evaluate(['+', 1, 2], globalEnv);
3

この計算を、evaluate関数内部の処理ステップごとに記述すると、以下のようになる。

  1. evaluate(['+', 1, 2], globalEnv);が実行されるとevaluate関数の第一引数x['+', 1, 2]という配列が渡される。また、evaluate関数の第二引数envにはglobalEnvが渡される。
  2. 引数xには['+', 1, 2]という配列が入るので、if文のArray.isArray(x)の判定はtrueである。
  3. evaluate('+')evaluate(1)evaluate(2)が実行され、それぞれfunction(a, b) {return a + b;}12になる。
  4. var proc = exps.shift();が実行され、procにはfunction(a, b) {return a + b;}が保持される。
  5. proc.apply(null, exps)が実行され、実質的には(function(a, b) {return a + b;})(1, 2)が実行され、答えの3が得られる。

(1 + 2) * (8 - 3) の計算

それではより複雑な(1 + 2) * (8 - 3)の計算もしてみよう。(1 + 2) * (8 - 3)の計算を四則演算インタープリターで実行するには以下のようにする。

>> evaluate(['*', ['+', 1, 2], ['-', 8, 3]], globalEnv);
15

この計算の処理の流れを簡単に書き下すと以下のようになる。機械的にevaluate関数の処理を追いかけて行けば、このようになる事がわかって頂けると思う。

  1. ['*', ['+', 1, 2], ['-', 8, 3]]
  2. [function(a, b) {return a * b;}, ['+', 1, 2], ['-', 8, 3]]
  3. [function(a, b) {return a * b;}, [function(a, b) {return a + b;}, 1, 2], ['-', 8, 3]]
  4. [function(a, b) {return a * b;}, 3, ['-', 8, 3]]
  5. [function(a, b) {return a * b;}, 3, [function(a, b) {return a - b;}, 8, 3]]
  6. [function(a, b) {return a * b;}, 3, 5]
  7. 15

まとめ

今回は四則演算インタープリターの大きな2つの構成要素である、evaluate関数とグローバル変数領域(globalEnv)について解説し、四則演算インタープリターの動作の仕方も順を追って説明した。

プログラマーにとって、evaluate関数やグローバル変数領域(globalEnv)などはとても身近なものである一方で、今までブラックボックスとして捉えていた方も多いのではないだろうか。また、「インタープリターはソースコード逐次解釈しながら実行する」という概念は理解していても、これがどう実装されるのかをご存知ない方も多いのではないだろうか。

この四則演算インタープリターは、非常に小さいながら、これらの概念がすべて含まれている。そのため、この四則演算インタープリターさえ分かってしまえば、本格的なLispインタープリターに至る最初の大きな山は超えたと言って差し支えない。本格的なLispインタープリターに育てる作業は、この四則演算インタープリターに様々な要素を追加していく作業となる。

[近棟 稔]