Scopeに対応する

# はじめに

以前の記事で[while文に対応](http://qiita.com/quwahara/items/36f6704ae9c756240068)しました。
今度は変数のScopeに対応したいと思います。

# Scope対応でやりたいこと

Scope対応でやりたいことを確認します。

例えば下のようなプログラムがあります。
変数`a`、`b`、`c`が`f()`関数の内と外で使われています。
関数の内と外ではScopeが変わるので、関数内で`var`で宣言されている`a`、`b`は、関数内でのみ有効です。
関数内での`println(a)`は`10`が出力され、外ではGlobal scopeで代入した値`1`が出力されます。
`b`も同じように内では`20`、外で`2`が出力されます。
`c`は関数内で宣言されておらず、内でも外でもGlobal scopeの変数になります。
`println(c)`は内でも外でも`30`が出力されます。

`var`宣言では変数の代入をできることにし、`,`(カンマ)で区切って複数の変数を同時に宣言できようにします。


```JS
a = 1
b = 2
c = 3
function f() {
  var a = 10, b
  b = 20
  c = 30
  println(a)
  println(b)
  println(c)
}
f()
println(a)
println(b)
println(c)
```

# 実装の仕方

実装の仕方について、構文解析(Parser)、インタプリタ(Interpreter)と順に考えていきます。

## 構文解析(Parser)の実装の仕方

Scopeの概念そのものは、関数の内か外かで表現されているので、
解析実装の視点から考えると、
関数定義が解析できていれば、Scopeの概念にも対応できています。

変数宣言の`var`は新しく導入されました。
キーワード`var`はトークンの並びの始めにくるので、
以前の記事で実装した[関数定義文の構文解析](http://qiita.com/quwahara/items/be71bac4b4359f5e6727#%E6%A7%8B%E6%96%87%E8%A7%A3%E6%9E%90parser%E3%81%AE%E5%AE%9F%E8%A3%85%E3%81%AE%E4%BB%95%E6%96%B9)と同じように実装します。

## インタプリタ(Interpreter)の実装の仕方

Scopeの概念を表すクラスを導入します。
ScopeクラスはScopeの階層構造を表せるように、親子関係を表現できるフィールド変数を用意します。

インタプリタの起動時には既定のGlobal scopeを作ります。
関数呼び出し時には、その関数内のScopeを作り、関数呼び出し元のScopeを関数内Scopeの親Scopeにします。
関数呼び出し後は関数内Scopeを破棄して、親Scopeにしていたものを現状のScopeに戻します。

# Javaで実装してみる

実装にうつります。
構文解析(Parser)、インタプリタ(Interpreter)について、
変更と追加をしたところを順にみていきます。

## Parser.java

Parser.javaの実装です。
トークンの意味に対して、どう動作するかの定義を追加します。
`var`が予約語となるので`// Update`のところへ加えました。

```Java:Parser.java
    public Parser() {
        degrees = new HashMap<>();
        degrees.put("(", 80);
        degrees.put("*", 60);
        degrees.put("/", 60);
        degrees.put("+", 50);
        degrees.put("-", 50);
        degrees.put("==", 40);
        degrees.put("!=", 40);
        degrees.put("<", 40);
        degrees.put("<=", 40);
        degrees.put(">", 40);
        degrees.put(">=", 40);
        degrees.put("&&", 30);
        degrees.put("||", 30);
        degrees.put("=", 10);
        factorKinds = Arrays.asList(new String[] { "digit", "ident" });
        binaryKinds = Arrays.asList(new String[] { "sign" });
        rightAssocs = Arrays.asList(new String[] { "=" });
        unaryOperators = Arrays.asList(new String[] { "+", "-", "!" });
        // Update
        reserved = Arrays.asList(new String[] { "function", "return", "if", "else", "while", "break", "var" });
    }
```

解析を行う部分の変更です。
`var`の解析を行う関数の呼び出しを`// Add`のところへ加えました。

```Java:Parser.java
    private Token lead(Token token) throws Exception {
        if (token.kind.equals("ident") && token.value.equals("function")) {
            return func(token);
        } else if (token.kind.equals("ident") && token.value.equals("return")) {
            token.kind = "ret";
            if (!token().kind.equals("eob")) {
                token.left = expression(0);
            }
            return token;
        } else if (token.kind.equals("ident") && token.value.equals("if")) {
            return if_(token);
        } else if (token.kind.equals("ident") && token.value.equals("while")) {
            return while_(token);
        } else if (token.kind.equals("ident") && token.value.equals("break")) {
            token.kind = "brk";
            return token;
            // Add
        } else if (token.kind.equals("ident") && token.value.equals("var")) {
            return var(token);
        } else if (factorKinds.contains(token.kind)) {
            return token;
        } else if (unaryOperators.contains(token.value)) {
            token.kind = "unary";
            token.left = expression(70);
            return token;
        } else if (token.kind.equals("paren") && token.value.equals("(")) {
            Token expr = expression(0);
            consume(")");
            return expr;
        } else {
            throw new Exception("The token cannot place there.");
        }
    }
```

解析を行う部分の変更です。
var宣言の解析を行うメソッド`var()`を追加しました。
var宣言の解析結果は引数のtokenにまとめられます。
`var()`メソッドでは次のパターンの解析を行います。

* `var`の後に変数名がある → `var a`
* さらに変数へ代入している → `var a = 0`
* `,`(カンマ)で複数の変数を宣言している → `var a = 0, b`

処理始めの`token.kind`への代入で、トークンの意味を`var`に決定します。
`token.block`は解析した結果を保持します。
`,`(カンマ)で複数の宣言ができるので、複数が保持できるリストになっている`token.block`に解析結果を保持します。
`var`の直後の解析を行います。
`var`は必ず変数名がくるはずなので`ident()`で変数名を要求します。
変数名のあとに代入があるときは`=`トークンがきます。
`=`トークンがきたときは、二項演算子と同じように解析して、その解析結果を`token.block`に保持します。
`=`トークンでないときは、`ident()`の結果をそのまま`token.block`に保持します。
その後`,`トークンがあれば、続けて同じように解析して、`token.block`に保持します。

```Java:Parser.java
    private Token var(Token token) throws Exception {
        token.kind = "var";
        token.block = new ArrayList<Token>();
        Token item;
        Token ident = ident();
        if (token().value.equals("=")) {
            Token operator = next();
            item = bind(ident, operator);
        } else {
            item = ident;
        }
        token.block.add(item);
        while (token().value.equals(",")) {
            next();
            ident = ident();
            if (token().value.equals("=")) {
                Token operator = next();
                item = bind(ident, operator);
            } else {
                item = ident;
            }
            token.block.add(item);
        }
        return token;
    }
```

## Interpreter.java

Interpreter.javaの実装です。

Scopeを表すクラスを導入しました。
`Interpreter`クラスにあったフィールド変数の`functions`と`variables`を移植しています。
Scopeの階層構造を表すために、親階層を表すフィールド変数`parent`を持っています。

```Java:Interpreter.java
    public static class Scope {

        public Scope parent;
        public Map<String, Func> functions;
        public Map<String, Variable> variables;

        public Scope() {
            functions = new HashMap<>();
            variables = new HashMap<>();
        }
    }
```

初期化の部分です。
導入したScopeクラスをフィールド変数にしています。
`global`と`local`のScopeを用意します。
`local`Scopeは関数内へ実行がうつるごとに、新しいScopeクラスのインスタンスを割り付けます。

```Java:Interpreter.java

    Scope global;
    Scope local;
    List<Token> body;

    public Interpreter init(List<Token> body) {
        global = new Scope();
        local = global;
        Func f = new Println();
        global.functions.put(f.name, f);
        this.body = body;
        return this;
    }
```


式を逐次実行するメソッド`body()`への変更です。

`// <-- Add`のところへvar宣言を処理するメソッドの呼び出しを追加しました。

```Java:Interpreter.java
    public Object body(List<Token> body, boolean[] ret, boolean[] brk) throws Exception {
        for (Token exprs : body) {
            if (exprs.kind.equals("if")) {
                Object val = if_(exprs, ret, brk);
                if (ret != null && ret[0]) {
                    return val;
                }
            } else if (exprs.kind.equals("ret")) {
                if (ret == null) {
                    throw new Exception("Can not return");
                }
                ret[0] = true;
                if (exprs.left == null) {
                    return null;
                } else {
                    return expression(exprs.left);
                }
            } else if (exprs.kind.equals("while")) {
                Object val = while_(exprs, ret);
                if (ret != null && ret[0]) {
                    return val;
                }
            } else if (exprs.kind.equals("brk")) {
                if (brk == null) {
                    throw new Exception("Can not break");
                }
                brk[0] = true;
                return null;
            } else if (exprs.kind.equals("var")) { // <-- Add
                var(exprs);
            } else {
                expression(exprs);
            }
        }
        return null;
    }
```

var宣言を処理する`var()`メソッドです。
`token.block`に複数の宣言が保持されているので順に処理します。
`token.block`の要素が変数名のトークンだったら、単純にLocal scopeへ変数を定義します。
要素が`=`トークンだったら、`item.left`の変数名トークンを使ってLocal scopeへ変数を定義します。
その後、`=`トークンを`expression(expr)`で実行します。

```Java:Interpreter.java
    public Object var(Token token) throws Exception {
        for (Token item : token.block) {
            String name;
            Token expr;
            if (item.kind.equals("ident")) {
                name = item.value;
                expr = null;
            } else if (item.kind.equals("sign") && item.value.equals("=")) {
                name = item.left.value;
                expr = item;
            } else {
                throw new Exception("var error");
            }
            if (!local.variables.containsKey(name)) {
                newVariable(name);
            }
            if (expr != null) {
                expression(expr);
            }
        }
        return null;
    }

    public Variable newVariable(String name) {
        Variable v = new Variable();
        v.name = name;
        v.value = 0;
        local.variables.put(name, v);
        return v;
    }
```

Scope導入による`ident()`メソッドの変更です。
while文で関数や変数が定義されていないか探索します。
Local scopeから、`parent`フィールド変数を使って、上位のScopeへさかのぼります。

```Java:Interpreter.java
    public Object ident(Token token) {
        String name = token.value;
        Scope scope = local;
        while (scope != null) {
            if (scope.functions.containsKey(name)) {
                return scope.functions.get(name);
            }
            if (scope.variables.containsKey(name)) {
                return scope.variables.get(name);
            }
            scope = scope.parent;
        }
        return newVariable(name);
    }
```

Scope導入による`func()`メソッドの変更です。
`// Update`以下が変更箇所です。
`context`を単なる`interpreter`の代入だったものから、
`interpreter`をクローンして代入するように変更しましたwhile文で関数や変数が定義されていないか探索します。
Local scopeから、`parent`フィールド変数を使って、上位のScopeへさかのぼります。

```Java:Interpreter.java
    public Object func(Token token) throws Exception {
        String name = token.ident.value;
        if (local.functions.containsKey(name)) {
            throw new Exception("Name was used");
        }
        if (local.variables.containsKey(name)) {
            throw new Exception("Name was used");
        }
        List<String> paramCheckList = new ArrayList<String>();
        for (Token p : token.params) {
            String param = p.value;
            if (paramCheckList.contains(param)) {
                throw new Exception("Parameter name was used");
            }
            paramCheckList.add(param);
        }
        DynamicFunc func = new DynamicFunc();
        // Update
        func.context = new Interpreter();
        func.context.global = global;
        func.context.local = local;
        func.context.body = body;
        func.name = name;
        func.params = token.params;
        func.block = token.block;
        local.functions.put(name, func);
        return null;
    }
```

Scope導入による`DynamicFunc`クラスの変更です。
関数呼び出しをする前に、現状のLocal Scopeを親Scopeとする、新しいScopeを生成します。
呼び出し後はLocal scopeを元のScopeに復帰します。
仮引数を新しいScopeに定義して、関数の処理blockを実行します。

```Java:Interpreter.java
    public static class DynamicFunc extends Func {

        public Interpreter context;
        public List<Token> params;
        public List<Token> block;

        @Override
        public Object invoke(List<Object> args) throws Exception {
            Scope parent = context.local;
            context.local = new Scope();
            context.local.parent = parent;
            for (int i = 0; i < params.size(); ++i) {
                Token param = params.get(i);
                Variable v = context.newVariable(param.value);
                if (i < args.size()) {
                    v.value = context.value(args.get(i));
                } else {
                    v.value = null;
                }
            }
            Object val;
            boolean[] ret = new boolean[1];
            val = context.body(block, ret, null);
            context.local = parent;
            return val;
        }
    }
```

以上の実装を使って下のプログラム

```JS
a = 1
b = 2
c = 3
function f() {
  var a = 10, b
  b = 20
  c = 30
  println(a)
  println(b)
  println(c)
}
f()
println(a)
println(b)
println(c)
```

を実行し、Scopeごとの変数`a`、`b`、`c`の値を標準出力へ出力します。

```Java:Interpreter.java
    public static void main(String[] args) throws Exception {
        String text = "";
        text += "a = 1";
        text += "b = 2";
        text += "c = 3";
        text += "function f() {";
        text += "  var a = 10, b";
        text += "  b = 20";
        text += "  c = 30";
        text += "  println(a)";
        text += "  println(b)";
        text += "  println(c)";
        text += "}";
        text += "f()";
        text += "println(a)";
        text += "println(b)";
        text += "println(c)";
        List<Token> tokens = new Lexer().init(text).tokenize();
        List<Token> blk = new Parser().init(tokens).block();
        new Interpreter().init(blk).run();
        // --> 10 
        // --> 20
        // --> 30
        // --> 1
        // --> 2
        // --> 30
    }
```

実装は以上です。
ありがとうございました。

# おわりに

ソースの全文はこちらで公開しています。

**Calc**
https://github.com/quwahara/Calc/tree/article-13-scope-r3/Calc/src/main/java

続きの記事があります。

**関数式に対応する**
http://qiita.com/quwahara/items/ae33ed944afc34cc5fac