ちょっと変わったLisp入門：Gaucheでメタプログラミング（1）（4/5 ページ）

Lispの一種であるScheme。いくつかある処理系の中でも気軽にスクリプトを書けるGaucheでLispの世界を体験してみよう（編集部）

[吉田裕美，有限会社イーワイオフィス]

Lisp処理系における変数について

　CやJavaでは、変数はメモリまたはスタック上の番地を表すものです。Lispでも処理系が頑張れば大部分の場合は、C言語のようにメモリまたはスタック上の番地にできます。しかし、Lispでは変数名を表すシンボル自身を動的に作れるので、実行時に何らかの管理が必要な場合があります。また、この連載でも後で取り上げるクロージャの実現にも工夫が必要です。

　Lispでは変数名に使われるシンボルと値は、「一時的に結び付いている」というニュアンスで「束縛」されるという言葉をよく使います。

　このLisp処理系では、性能は考えず変数の管理を簡単にするためにalist(association list)で実装します。

• alistは((キー . 値) (キー.値) ...)のようにキーと値のペアのリストです。ここではキーはシンボル、値は変数値です
• 変数の値は、キーをalistの先頭から探していき、最初にマッチしたキーに対応する値を変数（シンボル）の値とします
• 関数呼び出し時には「(仮引数 . 実引数の値)」をalistの先頭に追加します
• 関数から戻ったらalistは呼び出し前の状態に戻ります（先頭に追加した部分は外されます）
• alistは環境（env）としてインタプリタ内部を渡り歩きます

　次のような、aの値をn個連結したリストを戻す関数を実行する際の、変数管理（alist）の様子を見てみましょう。

(define (nlist a n l)
  (if (= n 0)
      l
      (nlist a (- n 1) (cons a l)))))

	呼び出し／戻り	alistの値
	開始前	()
	(nlist 111 2 nil) が呼び出される	((a.111)(n.2)(l.nil))
	(nlist 111 1 (111)) が呼び出される	((a.111)(n.1)(l.(111))(a.111)(n.2)(l.nil))
	(nlist 111 0 (111 111)) が呼び出される	((a.111)(n.0)(l.(111 111))(a.111)(n.2)(l.nil))(a.111)(n.2)(l.nil))
	(111 111) が戻る	((a.111)(n.1)(l.(111))(a.111)(n.2)(l.nil))
	(111 111) が戻る	((a.111)(n.2)(l.nil))
	終了 (111 111) が戻る	()

Lisp処理系における関数について

　これまで、Lispの関数について、あまり厳密に説明しませんでしたが、次のようなものがあります。

・関数

　Lisp処理系内にC言語で作られ、引数は呼び出し前に評価（計算）されます。

例：
+、list

・スペシャルフォーム

　Lisp処理系内にC言語で作られ、引数は評価せずに処理に渡され、処理内で必要に応じて評価されます。

例：
ifは最初の式の値が真の場合は2番目の引数のみ評価し、3番目の引数は評価しない。
偽の場合は3番目の式のみ評価し、2番目の引数は評価しない。

・Lambda式

　Lispで作られた関数、引数は呼び出し前に評価されます。このLispではdefineで定義した関数は関数名のシンボルに「(lambda (仮引数) 定義)」という値で定義されます。

・マクロ

　Lispでマクロとして定義された関数で、スペシャルフォームと同様なことができます。詳細は後で説明します。このLispではdefine-marcoで定義した関数は関数名のシンボルに「(macro (仮引数) 定義)」という値で定義されます。

式の評価（eval）

　式の評価（計算）は、eval関数で行います、evalの引数eが、

• 数値ならその値を戻す
• シンボルなら変数なので、env(alist)から対応する値を戻す。値がない場合はエラー
• リストなら(car e)の値を関数、(cdr e)を引数とし、次で説明するapplyで評価してもらう

となります。

　引数envは変数で説明したalistです、またassoc()はalistから、指定されたシンボルの値を探してくる関数です。

cell eval(cell e, cell env) {
  cell v;
  if (e == NIL || IS_INT(e)) return e;
  if (IS_SYMBOL(e)) {
    v = assoc(e, env);
    if (v != NIL) return CDR(v);
    throw_error("Undefined symbol '%s'", SYMBOL_NAME(e));
  }
  return apply(CAR(e), CDR(e), env);
}

関数の評価（apply）

　evalは式の評価のみで、関数の評価はapplyで行います。ここではまずLispで作られた関数の評価を説明します。

　例えば、引数に3を足す関数(define (add3 n) (+ n 3))は、add3シンボルに(lambda (n) (+ n 3))という値が定義されます。(add3 4)という式はeval関数からapply(add3, (4), ())のように呼び出されます。

　applyでは、

1. add3の値をeval()を呼んで評価、(lambda (n) (+ n 3))が戻る
2. 1の最初の要素(car)がlambdaなのでLambda式と分かる
3. 1の2番目の値(cdrのcar)は仮引数のリスト
4. 1の3番目の値(cdrのcdrのcar)は関数定義
5. 実引数をeval_listで評価した値をparlis関数で仮引数とペアにして、環境alistの先頭に追加
6. 関数定義と5でできた環境をevalに渡して関数定義を評価するeval((lambda (n) (+ n 3)), ((n.4)) )というイメージでevalを呼び出す

という処理が行われます。

　このように、applyとevalはお互いに呼び出し合いながら計算が進んでいきます。eval_list関数は引数のリストの要素を1つ1つevalで評価したリストを戻します。

cell apply(cell func, cell args, cell env) {
  cell fbody = eval(func, env);
  cell ftype = CAR(fbody);
  if (ftype == lambda_sym) {
    cell params = CAR(CDR(fbody));
    cell e = CAR(CDR(CDR(fbody)));
    return eval(e,
                concat2(pairlis(params,eval_list(args,env)),
                        env));
  }
}
 
cell eval_list(cell list, cell env) {
  cell values = NIL;
  while (list != NIL) {
    values = concat2(values,
                     cons(eval(CAR(list), env), NIL));
    list = CDR(list);
  }
  return values;
}

　また、C言語で書かれた関数の場合は、applyの最後のreturn文がC言語の関数呼び出しになります。例えば、引数が2つの関数の場合は以下のようになります。

    return (*func_pt)(eval(CAR(args), env), eval(CAR(CDR(args)), env));