インタプリタ(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);
/* 残りは省略 */
}
}
|
- まず、ASTが数値NUMであれば、その値(p->val)を返す。
- ASTが2項演算子(PLUS_OP,MINUS_OPなど)であれば、
左右のASTをexecuteExprを再帰的に呼び出して、実行し、その結果を演算子に
したがって、計算してその結果を返す。
- シンボルの場合は、変数と解釈する。
変数の値は、最初に説明したとおり、
シンボル構造体のvalのところにはいっているので、これを返す。それを行う
関数がgetValueである。
- 変数の代入(EQ_OP)では右の式の値を求めて、それを左の変数のシン
ボルのvalにセットすればよい。それを行う関数がsetValueである。
- また、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;
}
|
- 関数名のシンボルから、パラメータの並びを取り出す。パラメータの並
びは、シンボルのASTのリストである。
- それぞれのパラメータのリストと引数のリストから、
パラメータとそれに対応する式をとりだし、式を実行して、その値とパラメー
タを結合する。ここでは、Envにセットするだけで、envpは変えない。
- 引数の評価が終わったら、結合したところまで、envpを移動させる。こ
れによって、パラメータの変数の値はenvにある値になる。
-
- 関数から本体のASTを取り出し、executeStatementで実行する。なお、
executeStatementは後で説明する。
- おわったら、envpの値を元にもどし、結合を解く。
関数が再帰的に呼び出される場合にも、最近の結合されたものから探す(つま
り、Envを逆順に探す)ことにより、最も最近に結合された値を参照できるこ
とになる。
ちなみに、システム関数であるprintlnの処理は、以下のようになる。
interp_expr.c
static void printFunc(AST *args)
{
printf((char *)executeExpr(getNth(args,0)),
executeExpr(getNth(args,1)));
printf("\n");
}
|
第1引数は文字列のアドレス、第2引数はその値である。これを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");
}
}
|
- 配列の要素の参照は、GET_ARRAY_OPのASTになっている。左は配列名であ
るが、これをexecuteExprで実行すると配列のアドレスが返される。これを引
数にして、getArrayを呼び出している。
- SET_ARRAYでは、左に配列と要素のインデックスの式のリストが入っているこ
とに注意。これらをexecuteExprで実行して、setArrayを呼び出す。
- これ以外のコードが式として処理されることはないはずなので、errorと
する。
次に、文の実行について解説することにする。