連載
» 2008年10月31日 00時00分 公開

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

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

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));

Copyright © ITmedia, Inc. All Rights Reserved.

RSSについて

アイティメディアIDについて

メールマガジン登録

@ITのメールマガジンは、 もちろん、すべて無料です。ぜひメールマガジンをご購読ください。