JavaScriptでLispインタープリターを作ろう(8) ～ローカルスコープの導入～

前回の記事で関数を記述する機能が導入できた。しかしながら、現状のインタープリターにはローカルスコープが無く、変数が関数内に閉じていないために課題も残った。今回は、上記の課題を解決するためにローカルスコープを導入する。

ローカルスコープとは

ローカルスコープを実現する前に、JavaScriptを例にローカルスコープの性質をおさらいしておこう。

var a = 1;
var b = 2;
function sample(c) {
  var b = 1; // シャドーイング
  return a + b + c;
}
console.log(sample(3)); // -> 5が出力される
console.log(b);         // -> 2が出力される

ここではsample関数を作成している。sample関数の中では、sample関数の外で定義されたグローバル変数aを参照している。

また、グローバル変数bについてはsample関数内で新規変数bを作成しているため、いわゆる「シャドーイング」が発生し、b = 2という変数のバインディングがsample関数内では隠され、b = 1というバインディングだけが見えるようになっている。

また、仮引数cには実引数3が渡され、関数内部だけで参照可能である。

sample(3)の計算は1 + 1 + 3の結果なので5となる。また、sample関数内でシャドーイングされていた変数bは、関数の外ではシャドーイングされなくなり、変数bの値は2となる。

この例を用いてLispインタープリターをどのように変更するかを考えていくと、次のことが言える。

• 変数aや変数bはグローバル変数領域に入っているので、今のインタープリターで言うglobalEnv相当のHashMapで管理するのが自然である。
• 変数cはsample関数内部に閉じた変数領域に入っているので、今のインタープリターで言うglobalEnvとは別の、sample関数に閉じたHashMapで管理する必要がある。ここでは便宜上そのHashMapをenv1と呼ぶ。
• sample関数の中で新規に定義された変数bは、上記のenv1で管理するのが自然である。また、シャドーイングの発生状況からして、globalEnvではb = 2というバインディングを保持し、env1ではb = 1というバインディングを保持する必要がある。
• sample関数の中では主にenv1を見て変数の値を読み取るはずだが、env1に存在しない変数aのようなものは、より外側のHashMap（ここではglobalEnv）を探しに行くような挙動が必要になる。

JavaScriptのローカルスコープの仕様を元にローカルスコープの実現に必要そうな性質を洗い出してみると、上記のようになる。これを図示すると以下のようになる。

こう見てみると、今まで利用してきたglobalEnvという変数の入れ物をどのように変更すればよいかが浮かび上がってくる。

ローカルスコープを実現するためのデータの入れ物

ここまでの考察の結果、ローカルスコープを実現するためのデータの入れ物として必要な要件は、以下のようになる。

• globalEnvや関数ローカルの領域は、それぞれ別のHashMapとする。
• それぞれのHashMapは、より上位の階層のHashMapを知っている。別の言葉で言うと、「親」を知っている。
• 最上位の「親」はglobalEnvである。
• 変数のバインディングを解決する際には、現在のHashMapからバインディングを探し、そこにバインディングが無ければより上位の階層のHashMapへバインディングを探しに行く。そして最上位の親であるglobalEnvまでさかのぼって探しに行く。

これを図示すると以下のようになる。実のところ、これはJavaScriptで言う「スコープチェーン」の概念と合致したものでもある。

以下がこのようなデータ構造の実装である。以降、このデータ構造をenvオブジェクトと呼ぶことにする。

var Env = function(binding, outerEnv) {
  return {
    binding: binding,
    outerEnv: outerEnv,
    findEnv: function(key) {
      return (key in this.binding
              || this.outerEnv === undefined)
        ? this
        : this.outerEnv.findEnv(key);
    }
  };
};

この新しいEnv関数は、envオブジェクトをリターンする。

Env関数に渡す引数は2つある。1つ目のbinding引数には、envオブジェクトでバインディングを保持するHashMapを渡す。もう1つのouterEnv引数には、このenvオブジェクトの親となるべきスコープを渡す。

Env関数が戻すenvオブジェクトは2つのフィールドと1つのメソッドを保持している。

bindingフィールドには、変数名とその値の結びつきを保持するHashMapが入る。

outerEnvフィールドは、より上位のenvオブジェクトへの参照である。ただし、globalEnvの場合はundefinedになる。

findEnvメソッドでは、引数で与えられた変数名がどのenvオブジェクトに入っているかを探し、そのenvオブジェクトを返却する。もしどのenvオブジェクトにもその変数名が保持されていなかった場合、globalEnvが返却される。

このEnv関数の挙動を試した例を以下に載せる。

この例では、以下の様なenvのツリーを構築して、操作している。

たとえばenv1で変数aを探した場合、env1自身がそのバインディングを持つため、findEnvメソッドはenv1オブジェクトを返却する。そのため、変数aの値としては1が取得できる。

一方、env2で変数aを探した場合、env2自身にはそのようなバインディングが無いため、さかのぼってglobalEnvを参照し、そこで変数aのバインディングを見付ける。そのため、変数aの値は0となる。

変数の階層構造を導入したLispインタープリター

Lispインタープリターに、変数の階層構造をサポートするEnv関数を導入すると次のようになる。

envはソースコードの多くの箇所に登場するため、上記のコードは沢山の変更点を含んでいる。変更点をかいつまんで説明すると、以下のようになる。

• 関数呼び出しの際には、関数呼び出しのたびに新しいローカル変数領域であるnewEnvを作成するようにした。これにより、関数呼び出しのたびにローカルスコープが作成される。また、このローカルスコープの親のenvは、関数の呼び出し元のenvではなく、関数が定義された際のenvとなっている事が重要である。親のenvとして、関数の呼び出し元のenvを利用した場合、これは「ダイナミックスコープ」と呼ばれるスコープ解決方法となる。一方、関数が定義された際のenvを親とする場合は「レキシカルスコープ」（もしくは静的スコープ）と呼ばれる。ほとんどのプログラマーにとって、レキシカルスコープの方が馴染みの深いスタイルである。ダイナミックスコープを採用している代表的な言語にはEmacs Lispがある。
• 変数の定義や代入を行うdefやset!の処理内容が新しくなっている。defの挙動としては、常に「現在の」ローカルスコープに変数を定義している。一方で、set!は該当の変数がどのenvに存在するかを探し、該当のenvの変数を書き換えようとする。もし該当の変数が無ければ、globalEnvに新規変数を作成する。
• 変数の解決を行う処理が変更になり、findEnvメソッドを用いた方法へと書き換えられている。
• globalEnvの初期化方法が変わり、Env関数を用いたものとなっている。

実行例1：シャドーイング

前出の以下のJavaScriptコードと同等の操作を、このLispインタープリターで試してみる。

var a = 1;
var b = 2;
function sample(c) {
  var b = 1; // シャドーイング
  return a + b + c;
}
console.log(sample(3)); // -> 5が出力される
console.log(b);         // -> 2が出力される

このLispインタープリターで記述すると以下の通りとなる。

evaluate(['do',
           ['def', 'a', 1],
           ['def', 'b', 2],
           ['def', 'sample',
             ['fn', ['c'],
               ['def', 'b', 1], // シャドーイング
               ['+', ['+', 'a', 'b'], 'c']]],
           ['console.log', ['sample', 3]], // -> 5が出力される
           ['console.log', 'b']], // -> 2が出力される
         globalEnv);

ソースコードとしては、ほとんど1対1に対応するので理解して頂けると思う。この実行結果は、きちんとJavaScript版と同じ結果となる。

実行例2：クロージャー（閉包）

今回導入したローカルスコープは、レキシカルスコープであったため、驚くべきことにクロージャー（閉包）も同時に導入された状態になった。

たとえば以下の様なJavaScriptにおけるクロージャーの利用例と同等のコードは、このインタープリターでも実行可能だ。

var newseq = function(n) {
  return function() {
    n = 1 + n;
    return n;
  };
};
var seq1 = newseq(0);
console.log(seq1()); // -> 1が出力される
console.log(seq1()); // -> 2が出力される
console.log(seq1()); // -> 3が出力される

これを、このLispインタープリター向けに書き直すと以下の通りとなる。

evaluate(['do',
           ['def', 'newseq',
             ['fn', ['n'],
               ['fn', [],
                 ['set!', 'n', ['+', 1, 'n']],
                 'n']]],
           ['def', 'seq1', ['newseq', 0]],
           ['console.log', ['seq1']],  // -> 1が出力される
           ['console.log', ['seq1']],  // -> 2が出力される
           ['console.log', ['seq1']]], // -> 3が出力される
         globalEnv);

以上でローカルスコープの導入は完了だ。ローカルスコープの概念をあらためて紐解いたことに加えて、ローカルスコープの導入そのものが大きな変更を伴うものだったため、長文のエントリーとなってしまった。しかし、ローカルスコープを導入したことにより、プログラミング言語として必要な基本機能は揃ったと言えるだろう。是非このミニ言語で何が出来るか、色々試してみて欲しい。

さて、ようやく機能的には通常のプログラミング言語が持つレベルに近づいてきたこのLispインタープリターだが、今までソースコードをJavaScriptの配列を用いて記述してきた。このままでは、あまり大手を振って「これはプログラミング言語だ」とは言えないだろう。次回はこのLispインタープリターにパーサーを導入し、通常のプログラミング言語と同じように、文字列でソースコードを記述可能にする。