一般に、関数の返り値はひとつしかありません。複数の値を返す場合、Lisp ではリストに格納して返すのがふつうです。この場合、返す側は必要なデータをリストに格納し、受け取る側はリストからデータを取り出す処理が必要になります。ところが、Common Lisp の 多値 (Multiple Values) という機能を使うと、複数の値を簡単にやり取りすることができます。
複数の値を受け取るには、マクロ multiple-value-bind を使うと簡単です。
multiple-value-bind (&rest vars) values-form &rest form
multiple-value-bind は、多値を返す関数 values-form を評価し、その結果を vars で定義した変数にセットします。変数はレキシカル変数として設定されるので、multiple-value-bind を実行している間だけ有効です。簡単な例を示しましょう。Common Lisp には、整数でない値を整数に変換する関数 floor, ceiling, truncate, round が定義されています。これらの関数は 2 つの値（多値）を返します。
(truncate 10 3)
=> 3
(multiple-value-bind
(q r)
(truncate 10 3)
(format nil "商 ~D, 余り ~D" q r))
=> "商 3, 余り 1"
関数 truncate は割り算を行って商と余りを返します。ふつうに truncate を呼び出すと商を返すだけですが、multiple-value-bind を使うと、商のほかに余りも受け取ることができます。q と r は truncate が返す値を受け取る変数です。次に、truncate を評価して結果を変数にセットします。あとは、残りの form を順番に評価していきます。multiple-value-bind は最後に評価した form の値を返します。
もしも、返される値よりも変数の個数が多い場合、残りの変数には nil がセットされます。逆に、返される値が変数よりも多い場合、余分な値は捨てられます。次の例を見てください。
(multiple-value-bind (q)
(truncate 10 3)
(list q))
=> (3)
(multiple-value-bind (q r s)
(truncate 10 3)
(list q r s))
=> (3 1 nil)
最初の例では、変数 q しか定義されていないので、q には商がセットされますが余りは捨てられます。次の例では、変数 s が定義されていますが、truncate は 2 つの値しか返さないので、s には nil がセットされます。
次は、複数の値を返す方法を説明します。これはとても簡単で、関数 values を使うだけです。
values &rest args
引数 args を値として順番に帰します。簡単な例を示しましょう。
(defun foo (x y z) (values x y))
(multiple-value-bind (a b c)
(foo 1 2 3)
(list a b c))
=> (1 2 nil)
foo は 3 つ受け取る引数から最初の 2 つを返します。これは (values x y) とすればいいですね。実際に試してみると、multiple-value-bind で 2 つの値を受け取ることができます。
このように、多値の操作は multiple-value-bind と values を使って簡単に行うことができます。このほかにも、便利な関数やマクロがあるので紹介しましょう。
values-list list multiple-value-list form
(multiple-value-list (truncate 10 3)) => (3 1)
関数 values-list は list の要素を多値として返します。逆に、マクロ multiple-value-list は form を評価して、多値をリストに格納して返します。
multiple-value-call function &rest form
特殊形式 multiple-value-call は、form を評価した結果をすべて集めて、それらを引数として function に渡して評価します。次の例を見てください。
(multiple-value-call #'+ (truncate 10 3) (truncate 14 3)) => (+ 3 1 4 2) => 10
最初の truncate は 3 と 1 を返し、次は 4 と 2 を返します。したがって、関数 + には 3, 1, 4, 2 が引数として与えられ、その結果が 10 となるのです。function に #'list を与えれば、multiple-value-list と同様の働きをします。
multiple-value-prog1 form &rest forms
prog1 の多値バージョンです。複数の form を順番に評価しますが、最初に評価した form の結果（多値）を返します。
multiple-value-setq var-list form
multiple-value-bind の setq バージョンです。ようするに、var-list で指定した変数に値を代入するだけで、これらの変数はレキシカル変数として設定されるわけではありません。let などで定義したレキシカル変数や、スペシャル変数へ値を代入するときに使うと便利でしょう。
今回は構造体の具体的な使用例として、二分探索木という探索アルゴリズムを Lisp で実装してみましょう。
あるデータの中から特定のデータを探す場合、データ数が少なければ力任せに探索しても何とかなりますが、データ数が多くなると探索に時間がかかるようになります。このような場合、あらかじめデータを整理整頓しておくことで、特定のデータを高速に見つけることができるようになります。この代表的なアルゴリズムがハッシュ法と二分探索木です。
Common Lisp にはハッシュ表が用意されているので、二分探索木を使う機会は少ないでしょう。ですが、二分探索木にはハッシュにはない特徴があります。格納されたデータをある順番で出力すると、それはソートした結果と同じになるのです。また、データの中から最大値や最小値を簡単に見つけることができます。データを見つけることだけならばハッシュの方が高速なのですが、データの大小関係が絡む処理には、二分探索木の方が適しているのです。
木構造の場合、リストのセルに相当するデータ構造を節(node)と呼び、複数の節を連結することで木構造を表します。木構造の詳しい説明は拙作のページ ちょっと寄り道「木構造と二分木」 をお読みください。たとえば、二分木の節は次のように表すことができます。
List 1 : 節の定義
; 節
(defstruct Node
value ; データ
left ; 左の子
right) ; 右の子
スロット value にデータを格納し、left は左側の子、right は右側の子を格納します。スロット left からデータを取り出せば、左側の節へ移動することができ、right からデータを取り出せば、右側の節へ移動することができます。子がない場合、left と right には nil をセットすることにします。
次に、二分木のルートを格納する構造体を定義します。
List 2 : ルートの定義
; ルート
(defstruct Tree
root ; ルート
compare) ; 比較関数
構造体 Tree は、二分木の根 root と比較関数を格納します。実際の二分木は Node を使って実現します。二分木を操作する場合、データの比較関数が必要になります。たとえば、数値を格納するのであれば、数値の比較関数を使って操作関数を作ればいいのですが、それでは数値専用の二分木になってしまいますね。
オブジェクト指向の場合、比較関数をメソッドとして定義すれば、データ型によって比較関数を自動的に選択することができます。このため、二分探索木のプログラムを変更しなくても、あらゆるデータ（オブジェクト）に対応することができます。しかしながら、構造体ではそのようなことはできません。
そこで、make-Tree でルートを生成するときに、使用する比較関数をキーワード :compare でセットしてもらうことにします。データを比較するときは、スロット compare に格納されている比較関数を使うように、プログラムを作るわけです。比較関数は次に示す仕様を満たすものとします。
引数 obj1 obj2
OUTPUT : obj1 < obj2 --> -1
obj1 = obj2 --> 0
obj1 > obj2 --> 1
比較関数は 2 つの引数 obj1 と obj2 を比較し、-1, 0, 1 のいずれかの値を返します。これは Perl の演算子 <=> と同じ仕様です。たとえば、数値を格納する場合は、次のような定義になるでしょう。
List 3 : 数値の比較関数
(defun num-comp (n1 n2)
(cond ((= n1 n2) 0)
((> n1 n2) 1)
(t -1)))
それでは、二分木の中からデータを探索する search-tree を作ります。これは簡単です。プログラムは次のようになります。
List 4 : データの探索
(defun search-tree (root value)
(check-tree-p root)
(let ((node (Tree-root root))
(func (Tree-compare root)))
(while node
(case (funcall func value (Node-value node))
( 0 (return t))
( 1 (setq node (Node-right node)))
(-1 (setq node (Node-left node)))))))
再帰を使ってもいいのですが、繰り返しでも簡単にプログラムできます。最初に、データ型のチェックを行っています。次に、ルートと比較関数を取り出し、二分木をたどってデータを探索します。このプログラムでは、cond ではなくマクロ case を使っています。
(case キーとなるＳ式
( キーリスト１ Ｓ式A1 Ｓ式A2 ... )
( キーリスト２ Ｓ式B1 Ｓ式B2 ... )
・・・・・
( キーリストＭ Ｓ式M1 Ｓ式M2 ... )
( t Ｓ式T1 Ｓ式T2 ... ))
case は最初にキーとなる S 式を受け取り、そのあと cond と同様に複数の節が続きます。cond には節の先頭に条件部がありましたが、case の場合はキーリストというものがあります。まず、キーとなる S 式を評価します。次に、この評価結果とキーリストに格納された要素を比較します。このとき、キーリスト本体や要素は評価されないことに注意してください。もし、等しい要素を見つけた場合は、その節の S 式を順番に実行します。キーリストの要素がひとつしかない場合は、要素だけ書いてもかまいません。
データ型のチェックは簡単です。
List 5 : データ型のチェック
(defun check-tree-p (data)
(unless (Tree-p data)
(error "引数には Tree を指定してください"))
(unless (Tree-compare data)
(error "比較関数を指定してください")))
データを Tree-p でチェックし、比較関数が指定されていなければエラーとします。
次はデータを挿入する insert-tree です。
List 6 : データの挿入
(defun insert-tree (root value)
(check-tree-p root)
(setf (Tree-root root)
(insert-tree-sub (Tree-root root) value (Tree-compare root))))
実際にデータを挿入する関数は insert-tree-sub が担当します。
List 7 : 挿入関数の本体
(defun insert-tree-sub (node value func)
(if (null node)
(setq node (make-Node :value value))
(case (funcall func value (Node-value node))
( 1 (setf (Node-right node)
(insert-tree-sub (Node-right node) value func)))
(-1 (setf (Node-left node)
(insert-tree-sub (Node-left node) value func)))))
; 返り値は node だよ
node)
insert-tree-sub は再帰関数で、データを挿入した新しい部分木を返します。これでデータが挿入されます。よくわからないという方は、拙作のプログラミング入門講座を参照してください。
最後に、データを表示する関数 print-tree を作ります。
List 8 : データの出力 (defun print-tree (root) (check-tree-p root) (print-tree-sub (Tree-root root)))
実際の仕事は print-tree-sub で行います。
ところで、木のすべての節を規則的な順序で回ることを巡回 (traverse) といいます。この中で重要なのが次の方法です。
二分木の場合、通りがけ順でデータを出力すると、ソートした出力結果を得ることができます。print-tree-sub は次のようになります。
List 9 : 通りがけで出力
(defun print-tree-sub (node)
(when node
(print-tree-sub (Node-left node))
(print (Node-value node))
(print-tree-sub (Node-right node))))
print-tree-sub も再帰を使えば簡単ですね。
それでは、実行してみましょう。
(setq *r* (make-Tree :compare #'num-comp)) => #S(Tree root nil compare #<lexical-closure: ・・省略・・>) (dotimes (x 10) (insert-tree *r* (random 1000))) (print-tree *r*) 11 192 337 449 535 623 626 630 743 757 nil
正常に動作していますね。このように、二分探索木を通りがけで出力すると、その結果はソートされるのです。
ところで、このプログラムはマクロを多用しているので、バイトコンパイルしてから実行した方が良いでしょう。また、実際に使うのであれば、パッケージ (package) としてまとめておいたほうがよいでしょう。M.Hiroi は Common Lisp のパッケージを使ったことがほとんどありません。勉強しないといけませんね。
プログラムを作っていると、ほかのプログラムで作った関数が利用できるのではないか、といった場面に出あうことがあります。このような場合、自分で作成した関数をライブラリとしてまとめておくと、簡単に再利用することができて便利です。
ライブラリの作成で問題になるのが「名前の衝突」です。複数のライブラリを使うときに、同じ名前の関数や変数が存在すると、そのライブラリは正常に動作しないでしょう。このような名前の衝突を避けるために、Common Lisp ではパッケージ (package) を使います。次の例を見てください。
; ファイル bar.l (defpackage "bar") (in-package "bar") (defvar aaa 10) (defvar bbb 20) (defun test () (print "package bar"))
このファイルをロードしてから、*scratch* で次のプログラムを実行します。
(setq aaa 100) ; パッケージ user の変数 aaa 100 bar::aaa ; パッケージ bar の変数 aaa 10
defpackage はパッケージを定義するマクロです。あとで詳しく説明しますが、ここでは bar という名前のパッケージを定義しています。マクロ in-package は、シンボルが所属するパッケージを指定します。Lisp 処理系は、グローバル変数 *package* の値をカレントパッケージとして扱い、このパッケージの中からシンボルを探したり、シンボルを新規に登録します。in-package は *package* の値を切り替えます。これ以降、ファイル bar.l で定義される関数や変数名はパッケージ bar に属します。
通常、カレントパッケージは user という、Lisp 処理系があらかじめ用意しているパッケージになっています。*scratch* で定義する変数や関数は user に登録されます。したがって、最初 aaa に 100 を代入しましたが、この変数はパッケージ user 内に定義されます。
ほかのパッケージの変数や関数は、パッケージ名::名前のようにアクセスすることができます。これをパッケージ修飾子といいます。パッケージ bar の変数 aaa は、bar::aaa でアクセスすることができ、その値は 10 になります。このように、同じ変数名 aaa でも、パッケージによって区別されるのです。変数 aaa が衝突することはありません。
関数の呼び出しも同じです。bar に定義されている関数 test は、次のように呼び出すことができます。
(bar::test) "package bar"
大昔の Lisp 処理系では、システム内のシンボルを oblist というリストで管理していました。今では、ハッシュ表を使って管理するのが一般的です。拙作の Lisp インタプリタ VTOL の場合、oblist はシステム内のシンボルをリストに格納して返す関数として定義しています。昔の Lisp 処理系は、oblist はひとつしかありませんでした。VTOL の場合も、シンボルを管理するハッシュ表はひとつしかありません。
パッケージとは、「複数のハッシュ表を使ってシンボルを管理するシステム」と考えてください。パッケージ user に定義されているシンボルは、user に対応するハッシュ表に登録され、bar で使用されているシンボルは、bar に対応するハッシュ表に登録されるのです。そして、使用するハッシュ表を決めるのが、カレントパッケージなのです。
ところで、異なるパッケージの変数や関数を使うときに、いちいちパッケージ修飾子をつけるのは面倒ですね。このため Common Lisp には、ほかのパッケージで定義された名前を取り込む機能インポート (import) が用意されています。ただし、このためにはパッケージ側でも名前を外へ出すための準備が必要です。これを エキスポート (export) といいます。エキスポートされたシンボルを外部シンボル (external symbol) といい、そうでないシンボルを内部シンボル (internal symbol) といいます。パッケージには、この 2 種類のシンボルがあるのです。
シンボルをエキスポートするには関数 export を使います。
export symbols &optional package
引数 symbols はシンボルのリストか、ただひとつのシンボルでなければいけません。これらのシンボルは、パッケージ package の外部シンボルとしてアクセスすることができます。package が省略されると、カレントパッケージが対象となります。簡単な例を示しましょう。
; ファイル bar.l (defpackage "bar") (in-package "bar") (export '(aaa bbb test)) (defvar aaa 10) (defvar bbb 20) (defun test () (print "package bar"))
これで、シンボル aaa, bbb, test がエキスポートされます。
シンボルをインポートするには関数 import を使います。
import symbols &optional package
引数 symbols は export と同じです。これらのシンボルは package 内でパッケージ修飾子なしでアクセスできるようになります。これらのシンボルが、すでに package 内に存在する場合はエラーとなります。パッケージ bar のシンボル aaa, test をインポートするには、次のように指定します。
(import '(bar:aaa bar:test))
エキスポートされているシンボルのパッケージ修飾子はパッケージ名:名前となります。これで、aaa と test をパッケージ修飾子なしで利用することができます。エキスポートされているシンボルをすべてインポートしたい場合は、関数 use-package を使うと便利です。
use-package packages-to-use &optional package
引数 packages-to-use はパッケージかパッケージの名前のリストです。ひとつしかない場合は、それをそのまま与えてもかまいません。パッケージ bar の外部シンボルをすべてインポートするには、次のように指定します。
(use-package "bar")
これで、エキスポートされている aaa, bbb, test を利用することができます。
ところ、export や use-package は defpackage でも行うことができます。Common Lisp の場合、パッケージの定義する関数 make-package がありますが、マクロ defpackage を使った方が簡単です。
defpackage package-name &rest options
package-name には、パッケージ名を表す文字列かシンボルを与えます。よく使われる options を次に示します。
xyzzy Lisp 0.2.1.160 の場合、:export と :import-from は動作しないようです。その場合は、export と import を使ってください。
パッケージのロードは、プログラムファイルのロードと同じです。load や load-library を使うことができますが、このほかに、モジュールをロードする require という関数が用意されています。
モジュール (modules) を簡単に説明すると、ある機能を実現するためのプログラムの集まりや構造のことです。たとえば二分探索木の場合、データ構造の定義と基本的な操作関数が複数ありますが、それらをひとつにまとめてモジュールとして考えることができます。プログラムの構造を表す名前はいろいろあって、プログラミング言語によって呼び方はまちまちです。オブジェクト指向であればクラスと呼ばれるでしょう。
provide modules-name require modules-name &optional path-name
provide はモジュール名を定義する関数です。modules-name は、モジュール名を表す文字列かシンボルです。provide はファイルの先頭に書いておきます。require はモジュールをロードする関数です。モジュール名とファイル名は同じにしておくのが一般的です。
ロードされたモジュールはグローバル変数 *modules* に登録されます。require でモジュールをロードするときに *modules* をチェックして、モジュールがロード済みであればロードしません。あとは load-library と同じです。
それでは、前に作成した二分探索木をパッケージにしてみましょう。ファイルの先頭に次のプログラムを追加します。
List 10 : パッケージの定義 (provide "tree") (defpackage "tree") (in-package "tree") (export '(search-tree insert-tree print-tree make-tree))
make-tree は二分木のルートを作成する関数です。構造体の定義はパッケージ tree で行われるので、生成されるマクロは tree 内でのみ使用することができます。まあ、make-Tree をエキスポートすることもできますが、関数を定義したほうがわかりやすいでしょう。
List 11 : ルートの設定 (defun make-tree (func) (make-Tree :compare func))
とても簡単ですね。比較関数 func を受け取り、マクロ make-Tree を使えばＯＫです。また、スロット :compare が make-tree に隠されるので、データ抽象の点でも良いですね。
パッケージ tree は、次のように利用することができます。
(require "tree") (use-package "tree")
これで tree.l をバイトコンパイルして site-lisp に置いておけば、二分探索木を簡単に利用することができます。
自分で作ったマクロも、パッケージにまとめておくと簡単に再利用することができます。この場合、バイトコンパイルするときに注意が必要です。簡単な例題として、prog3 というマクロを作りましょう。
prog1 が最初に評価した S 式の値、prog2 が 2 番目に評価した S 式の値を返すように、prog3 は 3 番目に評価した S 式の値を返します。このマクロをパッケージ mymacro に格納することにします。パッケージの定義は次のようになります。
List 12 : パッケージ mymacro
(defpackage "mymacro")
(in-package "mymacro")
(export '(prog3))
; マクロの定義
(defmacro prog3 (first second third &rest body)
`(progn
,first
,second
(prog1
,third
,@body)))
prog3 は xyzzy Lisp の prog2 (evalmacs.l) を改造しただけです。パッケージ mymacro をインタプリタで使う場合は、(require "mymacro") でマクロをロードすればいいのですね。たとえば、test_macro.l で mymacro を使うには、次のようにします。
(require "mymacro") (use-package "mymacro") (defun foo (a b) (prog3 (+ a b) (- a b) (* a b) (/ a b)))
これでマクロ prog3 を使うことができます。ところが、test_macro.l をバイトコンパイルする場合、これでは動作しないのです。もちろん、バイトコンパイルは正常に終了しますが、test_macro.lc をロードして foo を実行すると、「関数 foo が定義されていない」というエラーが発生します。
マクロはバイトコンパイルするときにマクロ展開されます。(require "mymacro") とありますが、mymacro をロードするコードにコンパイルされるだけで、実際にロードされるわけではありません。つまり、コンパイラは prog3 がマクロであることを認識していないのです。このため、コンパイラは関数呼び出しのコードを出力するのですが、prog3 という関数は存在しないため、foo を実行するとエラーになるのです。
したがって、コンパイルするときにも mymacro を実際にロードしなければいけません。このために用意されている関数（特殊形式）が eval-when です。
eval-when ({situation}*) Ｓ式
eval-when はsituation (状況) で指定した状況においてのみ、本体の S 式を評価します。situation には次の 3 種類があります。
eval-when の使い方はけっこう難しいです。xyzzy のリファレンスには、次のように書いてありました。
よくわからなかったら、3 つ全部つけておけば大丈夫という説もある^^;
この教えに従うと、test_macro.l は次のようになります。
(eval-when (:compile-toplevel :load-toplevel :execute) (require "mymacro") (use-package "mymacro")) (defun foo (a b) (prog3 (+ a b) (- a b) (* a b) (/ a b)))
これで prog3 をマクロとしてバイトコンパイルできます。そして、test_macro.lc をロードすれば、関数 foo を実行することができます。