インタプリタ(1) 式、変数、関数

これから、tiny-Cのインタープリタを作ってみることにする。 まず、式の実行から考えてみよう。 変数を考えなければ、大体は式の評価でつくったインタープリタと同じである。 その後に、言語の重要な機能である関数について考えてみることにする。

説明するプログラムは、以下にある。

変数の扱い

変数の値を格納しておくためには、シンボル構造体のvalのフィールドにいれ ておく。シンボル構造体は以下のようになっていた。
AST.h 
typedef struct symbol {
    char *name;
    int val;   /* ← これを用いる */
    AST *func_params;
    AST *func_body;
} Symbol;
式を実行する関数は、以下のようになる。
interp_expr.c 
int executeExpr(AST *p)
{
    if(p == NULL) return 0;
    switch(p->op){
    case NUM:
	return p->val;
    case SYM:
	return getValue(getSymbol(p));
    case EQ_OP:
	return setValue(getSymbol(p->left),executeExpr(p->right));
    case PLUS_OP:
	return executeExpr(p->left) + executeExpr(p->right);
    case MINUS_OP:
	return executeExpr(p->left) - executeExpr(p->right);
    case MUL_OP:
	return executeExpr(p->left) * executeExpr(p->right);
    case LT_OP:
	return executeExpr(p->left) < executeExpr(p->right);
    case GT_OP:
	return executeExpr(p->left) > executeExpr(p->right);

        /* 残りは省略 */
    }
}
  1. まず、ASTが数値NUMであれば、その値(p->val)を返す。
  2. ASTが2項演算子(PLUS_OP,MINUS_OPなど)であれば、 左右のASTをexecuteExprを再帰的に呼び出して、実行し、その結果を演算子に したがって、計算してその結果を返す。
  3. シンボルの場合は、変数と解釈する。 変数の値は、最初に説明したとおり、 シンボル構造体のvalのところにはいっているので、これを返す。それを行う 関数がgetValueである。
  4. 変数の代入（EQ_OP）では右の式の値を求めて、それを左の変数のシン ボルのvalにセットすればよい。それを行う関数がsetValueである。
  5. また、ASTがない(NULL)場合には、0を返す。
いろいろなところで、executeExprを再帰的に呼び出していることに注意しょ う。

getValueは変数シンボルのvalの値をかえし、setValueはそのvalに値をセット する。したがって、以下のようになるはずである。 

int getValue(Symbol *var)
{
    return var->val;
}

int setValue(Symbol *var,int val)
{
    var->val = val;
    return val;
}
単なる式を評価するだけならば、以上のコードで十分であるが、実際はもうす こし仕掛けが必要となる。それは関数のパラメータ引数や局所変数があるから である。

関数の定義：構文解析部とのインタフェース

さて、関数がどのように処理されるかの説明をすることにしょう。 まず、構文解析部において、関数の定義が処理されると、defineFunctionが呼 び出される。これは、インタプリタでは、以下のように定義されている。

interp.c 
void defineFunction(Symbol *fsym,AST *params,AST *body)
{
    fsym->func_params = params;
    fsym->func_body = body;
}
関数名のシンボルのfunc_paramsにパラメータのシンボルのリスト、func_body に関数本体のASTをいれておく。これらは、関数呼び出しを実行する時に参照 する。次に関数呼び出しを考える。

ちなみに、変数宣言に対するインタフェースは、declareVariableである。
interp_expr.c 
void declareVariable(Symbol *vsym,AST *init_value)
{
    if(init_value != NULL){
	vsym->val = executeExpr(init_value);
    }
}
インタプリタでは、プログラム中に変数が現れた時点で、シンボルが作られる ために、変数宣言で特になにもする必要はない。ただし、初期化の式が与えら れた時には、その式の値をもとめ、シンボルのvalにセットしておく。

環境(environment) ：変数と値の結合(bind)

例えば、tiny-Cの次の関数を考える。 

foo(x,y) { return x + y; }
プログラム中で、foo(1,2)を実行し、関数呼び出しをした場合には、関数本体 を実行している間はxの値は1、yの値は2になっていなくてはならない。 このために、関数の実行をはじめに1,2をx,yにいれておくことが考えられるが、 注意しなくてはならないのはパラメータは局所変数なので、 関数の実行を終了したときには、xとyの値は元にももどしておかなくはならな い。これは単なる代入と異なり、このように動的に変数と値を対応させること を結合(bind)するという。 このためのデータ 構造として、結合した変数と値のペアを記録しておくデータ構造を用意する。 どの変数がどのような値と結合されているかという状態のことを 環境(environment)という。

以下に環境のためのデータ構造Environmentを示す。

interp.h 
typedef struct env {
    Symbol *var;
    int val;
} Environment;

Environment Env[MAX_ENV];
int evnp = 0;
Envは変数と値のペアの配列で、パラメータの変数に値が結合されるごとにこ の配列に記録しておく。この配列をどこまで使っているかを示すために、envp という変数を使う。

変数の値を探す時には、この表を最近に結合された順に探 し、この表で見つかった場合にはその値を使い、ない時にはシンボル構造体 にある値を使えばよい。関数の実行が終わったら、envpの値を元に戻せば結合 はなくなる。代入で、変数の値を変える場合もこの表にある場合には、その値 を変更しなくてはならない。したがって、setValue, getValueは以下のように なる。

interp.c 
int setValue(Symbol *var,int val)
{
    int i;
    for(i = envp-1; i >= 0; i--){
	if(Env[i].var == var){
	    Env[i].val = val;
	    return val;
	}
    }
    var->val = val;
    return val;
}

int getValue(Symbol *var)
{
    int i;
    for(i = envp-1; i >= 0; i--){
	if(Env[i].var == var) return Env[i].val;
    }
    return var->val;
}

関数呼び出し

executeExprの省略している部分は、関数呼び出しの部分である。式のなかで、 foo(x+1,2)のような式がある場合にこの部分が実行される。

interp_expr.c 
int executeExpr(AST *p)
{
    if(p == NULL) return 0;
    switch(p->op){
     
    /* 上に示した演算式、代入の実行 */

    case CALL_OP:
	return executeCallFunc(getSymbol(p->left),p->right);
    case PRINTLN_OP:
	printFunc(p->left);
	return 0;

    /* あと、配列についての式の実行は後で説明する */

    }
}
関数の呼び出しをするする関数がexecuteCallFuncである。この関数は、一番 目の引数が呼び出す関数のシンボル、第二引数が引数のASTのリストである。

では、executeCallFuncを見てみよう。一部省略しているところがあるが、引 数に書かれた式を実行 して、その値をパラメータにbindして、関数の中の文を実行する。

interp.c 
int executeCallFunc(Symbol *f,AST *args)
{
    int nargs;
    int val;
    AST *params;
    
    nargs = 0;
    for(params = f->func_params; params != NULL; 
	params = getNext(params)){
	Env[envp+nargs].var = getSymbol(getFirst(params));
	Env[envp+nargs].val = executeExpr(getNth(args,nargs));
	nargs++;
    }
    envp += nargs;
    /* 省略しているところあり */
    executeStatement(f->func_body);
    /* 省略しているところあり */
    envp -= nargs;
}
  1. 関数名のシンボルから、パラメータの並びを取り出す。パラメータの並 びは、シンボルのASTのリストである。
  2. それぞれのパラメータのリストと引数のリストから、 パラメータとそれに対応する式をとりだし、式を実行して、その値とパラメー タを結合する。ここでは、Envにセットするだけで、envpは変えない。
  3. 引数の評価が終わったら、結合したところまで、envpを移動させる。こ れによって、パラメータの変数の値はenvにある値になる。
  5. 関数から本体のASTを取り出し、executeStatementで実行する。なお、 executeStatementは後で説明する。
  6. おわったら、envpの値を元にもどし、結合を解く。
関数が再帰的に呼び出される場合にも、最近の結合されたものから探す（つま り、Envを逆順に探す）ことにより、最も最近に結合された値を参照できるこ とになる。

ちなみに、システム関数であるprintlnの処理は、以下のようになる。
interp_expr.c 
static void printFunc(AST *args)
{
    printf((char *)executeExpr(getNth(args,0)),
	   executeExpr(getNth(args,1)));
    printf("\n");
}
第１引数は文字列のアドレス、第２引数はその値である。これをprintfで呼び 出す。

動的結合と静的結合

上で説明した環境の作り方は、コンパイラで実行するCなどの言語とはちょっ と違った振舞を示すことがある。例えば、 

var x;

addx(y) {   return x + y; }

addxy(x,y) {  return addx(y); }
ここで、x = 10; として、addx(2) を呼び出してみると、その値は12になる。 なぜなら、addxの中のxは大域変数のxを参照するからである。 しかし、x = 10; としても、addxy(2,3)を実行すると、その値は5となる。 
main()
{ 
    x = 10;
    println("%d",addx(2)); /* ここは、12 */
    println("%d",addxy(2,3)); /* ここは 5 */
}
addxy(2,3)が5になるわけは、addxyでは、x に2が結合され、そこでaddxが呼 び出されるとその中のxは、この束縛されたxが参照されてしまうからである。 つまり、どのような順番で呼び出されるかに依存してしまう。この ような実現の方法を動的結合(dynamic binding)と呼ぶ（動的束縛と呼ぶこと もある）。それに対して、addxがどのような順番でよびだされても、プログラ ム中にかかれた参照範囲できまった大域変数のxを参照する方式を静的束縛と いう。コンパイラでは静的束縛になるのが普通である。

配列と文字列の処理

最後に配列の処理を完成させて、executeExprを完成させることにしよう。

構文解析部で変数宣言が入力されると、declareArrayが呼び出される。
interp_expr.c 
void declareArray(Symbol *a, AST *size)
{
    a->val = (int)malloc(sizeof(int)*executeExpr(size));
}
tiny Cのインタープリタでは配列はシンボルのvalの部分に、配列のアドレス をいれることによって実現している。declareArrayでは、size部分の式を実行 してサイズを求め、そのサイズ分のintegerの領域をmallocで確保し、その配 列をvalにセットする。このインタプリタは、32bitマシンで実行することを仮 定しているので、intとポインタのサイズは同じであるので、キャストするこ とによって、intの変数に無理矢理代入している。

なお、文字列についても、文字列のアドレスを値として、同じような処理をしている。 printlnの処理を参照のこと。

次に、その配列の要素について、参照と代入する関数getArrayとsetArrayを示 す。

interp_expr.c 
int getArray(int a, int index)
{
    int *ap;
    ap = (int *)a;
    return ap[index];
}

int setArray(int a,int index,int value)
{
    int *ap;
    ap = (int *)a;
    ap[index] = value;
    return value;
}
intの値をキャストしてintへのポインタにして、その要素にアクセスしている ことに注意しよう。

これで、いままで説明した部分をあわせて、executeExprを完成させる。

interp_expr.c 
int executeExpr(AST *p)
{
    if(p == NULL) return 0;
    switch(p->op){
    case NUM:
	return p->val;
    case SYM:
	return getValue(getSymbol(p));
    case EQ_OP:
	return setValue(getSymbol(p->left),executeExpr(p->right));
    case PLUS_OP:
	return executeExpr(p->left) + executeExpr(p->right);
    case MINUS_OP:
	return executeExpr(p->left) - executeExpr(p->right);
    case MUL_OP:
	return executeExpr(p->left) * executeExpr(p->right);
    case LT_OP:
	return executeExpr(p->left) < executeExpr(p->right);
    case GT_OP:
	return executeExpr(p->left) > executeExpr(p->right);
    case GET_ARRAY_OP:
	return getArray(executeExpr(p->left),executeExpr(p->right));
    case SET_ARRAY_OP:
	return setArray(executeExpr(getNth(p->left,0)),
			executeExpr(getNth(p->left,1)),
			executeExpr(p->right));
    case CALL_OP:
	return executeCallFunc(getSymbol(p->left),p->right);
    case PRINTLN_OP:
	printFunc(p->left);
	return 0;
    default:
	error("unknown operater/statement");
    }
}
  1. 配列の要素の参照は、GET_ARRAY_OPのASTになっている。左は配列名であ るが、これをexecuteExprで実行すると配列のアドレスが返される。これを引 数にして、getArrayを呼び出している。
  2. SET_ARRAYでは、左に配列と要素のインデックスの式のリストが入っているこ とに注意。これらをexecuteExprで実行して、setArrayを呼び出す。
  3. これ以外のコードが式として処理されることはないはずなので、errorと する。

次に、文の実行について解説することにする。