特集記事

JavaScriptでつくるSchemeインタプリタの基礎の基礎

JavaScriptによるSchemeの実装

2006/12/12 00:00

ポスト

関数定義

Scheme側の関数

　さて、これで自由に組み込み関数を作れるようになったので、今度はScheme側で関数を作れるようにしましょう。Schemeで記述され、引数が固定個であり、呼び出し前に引数が評価される関数をEXPRと言います。今度はこれを定義／呼び出しできるようにします。

注意

　Schemeで記述し、引数が可変長で、呼び出し前に引数を評価しない関数をFEXPRと呼びます。
　これは、実引数のリストと共に、呼び出し元の環境を送ることにより、FSUBRと同じ役割を持たせるものですが、ここでの説明は省きます。また、SUBR/FSUBR同様、EXPR/FEXPRも本来Schemeの用語ではありません。本物のSchemeはFEXPRに相当するものをマクロを使って実現します。

begin

　EXPRを実行するための足がかりとして、beginというFSUBRをつくります。beginは引数として、複数の式からなるリスト、beginを呼び出した環境を受け取ります。そして、式を順番に評価し、最後の式の評価の結果を返します。これ自身は単純な関数ですが、EXPRを動かす上では重要な役割を果たします。

beginの定義

function LF_begin(s, env) {
  var ret = nil;
  while (s != nil) {
    ret = Eval(CAR(s), env);
    s = CDR(s);
  }
  return ret;
}

AddBindToEnv(globalEnv, CreateSymbol("begin"), CreateSUBR(LF_begin));

EXPRオブジェクト

　SUBR/FSUBR同様に、EXPRもオブジェクトとして扱います。

EXPRの定義

var TAG_EXPR = 5;

function EXPR(f, a, e) {
  this.tag = TAG_EXPR;
  this.forms = f;
  this.args = a;
  this.env = e;
}

　formsは定義する関数の式のリスト、argsは仮引数のリスト、envは関数が定義されたときの環境です。定義は省略しますが、例によってCreateEXPRという関数を作っておきます。

lambda

　EXPRを定義するために lambdaというFSUBRをつくります。lambdaは引数として、定義する関数の式のリスト、仮引数のリスト（args）、lambdaを呼び出した環境を受け取ります。そして、それを元にCreateEXPRを呼び出し、得られたEXPRオブジェクトを返します。一見、環境は必要がないように思えますがこれが実は後で重要な役目を果たします。

EXPRの呼び出し

　引数のことを無視すれば、EXPRオブジェクトのformsを取り出し、beginの引数として送れば、EXPRが呼び出せそうです。さて、その引数ですが、Evlisで実引数を評価したリストを得た後に、EXPRオブジェクトのargsを取り出し、両方のリストから要素を1つずつ取り出し、対を作ったものをリストにします。

例 : ((lambda (x y z) (+ x (* y z))) 1 2 3)

仮引数 (x y z)
実引数 (1 2 3)
生成物 ((x . 1) (y. 2) (z . 3))

　そして、このリストの後ろにEXPRオブジェクトのenvを取り出したものをつなげ、それをnew_envとします。最後にbegin(forms, new_env)を呼び出して、その値を返せばEXPRの呼び出しは終わりです（ただし、実際には環境リストの先頭にダミーデータを付加します）。

Applyの改良

function Apply(fn, args, env) {
  if (fn.tag == TAG_SUBR || fn.tag == TAG_EXPR)
    args = Evlis(args, env);

  if (fn.tag == TAG_SUBR)
    return fn.func(args);
  if (fn.tag == TAG_FSUBR)
    return fn.func(args, env);
  if (fn.tag == TAG_EXPR) {
    var new_env = CreateEXPREnv(args, fn);
    return LF_begin(fn.forms, new_env);
  return nil;
}

function CreateEXPREnv(args, fn) {
  var ret = CreateNewEnv(); /* ((dummy . dummy)) というリストを生成 */
  var p = fn.args;
  var q = args;
  while (p != nil) {
    AddBindToEnv(ret, CAR(p), CAR(q));
    p = CDR(p);
    q = CDR(q);
  }
  Nconc(ret, fn.env); /* lambdaの呼び出しもとの環境を後ろにつなぐ */
  return ret;
}

　環境から値を探すときは先頭から探すので、もし、大域環境などでx, y, zといった仮引数と同じ名前の変数が定義されていても、引数の値のほうが先に見つかり、こちらの値が使われます。

　これでScheme側で関数を定義できるようになりました。

環境の操作

　今のままではScheme側で環境を操作することはできません。そこで、defineとset!というFSUBRを作ります。defineはFSUBRで、引数としてシンボルと任意の値を受け取り、それを対にしたものを現在の環境リストの先頭（正確にはダミーの後ろ）に付け加えます。第1引数であるシンボルは評価しませんが、第2引数は評価することを忘れないようにしましょう。

　set!もdefineと同様にシンボルと任意の引数を受け取りますが、set!は既に環境にある変数と値の対応を書き換えます。

define/set!の定義

function LF_define(s, env) {
  var name = CAR(s);
  var val = CAR(CDR(s));
  var bind;
  val = Eval(val, env);
  bind = CreateCons();
  SetCAR(bind, name);
  SetCDR(bind, val);
  AddBindToEnv(env, name, val);
  return name;
}

function LF_set(s, env) {
  var name = CAR(s);
  var val = CAR(CDR(s));
  var bind = Assoc(name, env);
  if (bind == nil) /* 変数が見つからなければ新たに作る */
    return LF_define(s, env);
  val = Eval(val, env);
  SetCDR(bind, val);
  return name;
}

条件分岐

　やはり、まともなプログラムを書く上で、条件分岐は必須です。Schemeでの条件分岐は次のように書きます。

条件分岐の例

(cond (条件1 式1)
      (条件2 式2)
      (else  式m))

　condは条件nを評価し、結果が#f以外の場合、式nを評価してその値を返します。elseは必ずしも必要ではありません。式は条件が満たされたときのみ評価する必要があるのでcondはFSUBRとして定義します。

condの定義

function LF_cond(s, env) {
  while (s != nil) {
    if (Eval(CAR(CAR(s)), env) != sharp_f)
      return LF_begin(CDR(CAR(s)), env);
    s = CDR(s);
  }
  return nil;
}
AddBindToEnv(CreateSymbol("cond"), CreateFSUBR(LF_cond));
AddBindToEnv(CreateSymbol("else"), sharp_t); 
                                        /* else を評価すると必ず #t */

サンプル

階乗

　ここまでに作成したインタプリタを使って階乗を求める関数を書いてみます。

階乗の例

(define factorial
  (lambda (n)
    (cond ((eq? n 0) 1)
          (else (* n (factorial (- n 1)))))))

　特徴は再帰的に関数が定義されているということです。この定義の後に(factorial 10)を評価すると、上記の定義から、factorial(10) * factorial(9) * ... * factorial(0)が計算され、結果としてnの階乗が求まります。

クロージャ

　関数を返す関数というものを定義してみます。

クロージャの例

(define make-adder
  (lambda (n)
    (lambda (x)
      (set! n (+ n x))
      n)))

　(make-adder 0)を評価すると、n=0を示す環境を保持した「仮引数xを持つ関数」が返されます。この戻り値の関数を呼び出すとnの値が毎回更新されていきます。これが、EXPRオブジェクトに環境へのポインタを持たせた効果です。

make-adderの使用例

(define a0 (make-adder 0))
(define a1 (make-adder 10))
(a0 9)  ;結果⇒9
(a1 21) ;結果⇒31
(a0 70) ;結果⇒79

まとめ

　ここで作ったインタプリタで実装しているのはSchemeのほんの一部分だけです。もともと関数型に近いJavaScriptで書いたため、非常に楽をしましたが、C言語などでデータ構造に気を使ったり、ガベージコレクションを自分で書いてみるのも楽しいでしょう。興味がある方は下記の参考文献などを元に、自分のインタプリタを作ってみてはいかがでしょうか。