スペシャル変数とダイナミックスコープ
●defvar
Common Lisp では、マクロ defvar でスペシャル変数の使用を宣言することができます。
defvar symbol [initial-value [doc-string]]
defvar はシンボル symbol をスペシャル変数として宣言します。initial-value と doc-string は省略することができます。initial-value を指定すると、スペシャル変数の値は initial-value に初期化されます。
doc-string には変数の意味を説明する文字列を与えることができます。doc-string は 関数 documentation で取得することができます。
documentation symbol doc-type
defvar の doc-string を取得する場合、引数 doc-type にはシンボル VARIABLE を指定してください。
簡単な使用例を示しましょう。
* (defvar *foo*)
*FOO*
* (defvar *foo1* 100)
*FOO1*
* *foo1*
100
* (defvar *foo1* 200)
*FOO1*
* *foo1*
100
* (defvar *foo2* 10 "テストです")
*FOO2*
* *foo2*
10
* (documentation '*foo2* 'variable)
"テストです"
Common Lisp の場合、スペシャル変数は * で囲んで表す習慣があります。それから、スペシャル変数の値は defvar で書き換えることはできません。指定した symbol のスペシャル変数が値を持っていない場合にのみ、initial-value の値で初期化されます。ご注意ください。
●ダイナミックスコープ
defvar でスペシャル変数を宣言すると、その変数は「ダイナミックスコープ」で管理されます。次の例を見てください。
* (defvar x 10)
X
* (defun foo () (print x))
FOO
* (foo)
10
10
* (defun foo1 () (let ((x 100)) (foo)))
FOO1
* (foo1)
100
100
* x
10
defvar で変数 X をスペシャル変数として宣言します。関数 foo1 では、let で変数 X を定義しているので、X の値は 100 になります。通常のレキシカルスコープであれば、呼び出した関数 foo からこの値にアクセスすることはできません。
ところが、defvar で X をスペシャル変数として宣言すると、変数 X はダイナミックスコープで管理されるため、foo から foo1 で定義した変数 X にアクセスすることができるのです。このため、foo1 から foo を呼び出すと X の値は 100 になります。そして、foo1 の実行が終了すると X の値は 10 に戻ります。
これを図に示すと次のようになります。
ダイナミックスコープの場合、局所変数はひとつの連想リスト [*1] で管理されていると考えてください。この場合、キーが局所変数を表し、データがその値に対応します。局所変数にアクセスするときは、この連想リストから該当する変数を探すのです。見つからない場合は大域的な環境 (スペシャル変数) を検索します。
関数呼び出しや let などで局所変数が定義されたときに、変数とその値が連想リストの先頭へ追加されます。そして、関数や let の評価が終了したときに、連想リストから変数が削除されます。関数が呼び出されるたびに、新しい変数が連想リストに追加されますが、呼び出した側で定義した局所変数も、この連想リストの中に残っています。
たとえば、(1) のように関数 foo を呼び出した場合、関数の引数がなくて局所変数の定義もないので連想リストは空です。ところが、(2) のように関数 foo1 を呼び出した場合、局所変数 X が定義されているので、連想リストに (X . 100) がセットされます。この状態で関数 foo が呼び出されると、連想リストには foo1 で定義した (X . 100) が残っているので、foo では X の値が 100 となるのです。let が終了すると連想リストから変数 X が削除されるので元の値に戻ります。
これは let だけではなく、関数の引数でも同じことができます。
* x
10
* (defun foo2 (x) (foo))
FOO2
* (foo2 1000)
1000
1000
* x
10
このように、defvar で宣言された変数の値は、関数の引数や let などで一時的に値を更新することができます。ただし、ダイナミックスコープには、プログラムを見ただけではどの変数にアクセスしているのかわからない、という欠点があることに注意してください。レキシカル変数とスペシャル変数は異なる名前にすることをお勧めします。Common Lisp の習慣に従い、スペシャル変数は * で囲むとよいでしょう。
-- note --------
[*1] 連想リストは説明のために用いたもので、今の実用的な Lisp / Scheme 処理系は、連想リストよりも効率的な方法で局所変数を管理していると思います。ただし、簡単な Lisp 処理系を自作する場合、局所変数の管理に連想リストを使う方法は有効です。
●defconstant と defparameter
マクロ defparameter は defvar と似ていますが、スペシャル変数の値を更新できるところが異なります。
defparameter symbol value [doc-string]
* (defparameter *x* 10)
*X*
* *x*
10
* (defparameter *x* 20)
*X*
* *x*
20
マクロ defconstant を使うと、スペシャル変数で定数を定義することができます。
defconstant symbol value [doc-string]
defconstant で定義した定数は、値を書き換えようとするとエラーになります。簡単な例を示します。
* (defconstant cc 100)
CC
* cc
100
* (setq cc 200)
=> エラー "CC is a constant and thus can't be set."
* (let ((cc 100)) (print cc))
=> エラー "CC names a defined constant, and cannot be used in LET."
最後の例のように、let で CC を使うとエラーになります。
●スペシャル変数の便利な使い方
標準入出力ストリームを格納する *standard-input* と *standard-outpu* はスペシャル変数です。この値を一時的に変更することで、標準入出力に対して動作する処理を他のファイルへ切り替えることができます。
たとえば、ファイル入出力 の問題 1 で作成した関数 cat-file はファイルの内容を標準出力へ書き込みます。
リスト : 複数のファイルを表示する
(defun cat-file (&rest args)
(dolist (file args)
(with-open-file
(in file :direction :input)
(let (buff)
(loop
(if (not (setq buff (read-line in nil)))
(return))
(write-line buff))))))
*standard-output* に他のファイルの出力ストリームをセットすれば、cat-file を変更せずに結果を他のファイルに書き込むことができます。
* (cat-file "test1.txt")
abcd
efgh
ijkl
NIL
* (with-open-file (*standard-output* "test2.txt" :direction :output) (cat-file "test1.txt"))
NIL
* (cat-file "test2.txt")
abcd
efgh
ijkl
NIL
●スペシャル変数の一時的な宣言
特殊形式 declare を使うと、局所変数を一時的にスペシャル変数として宣言することができます。
declare decl-spec ...
引数 desl-spec は宣言を表す S 式です。スペシャル変数を宣言する場合は (special symbol) とします。declare は特定の特殊形式の本体の先頭に記述します。ちょっとわざとらしいですが、簡単な例を示しましょう。
* (defun add-n (x) (+ x n))
;
; ワーニング (省略)
;
ADD-N
* (defun add-element-bad (n xs)
(mapcar 'add-n xs))
;
; ワーニング (省略)
;
ADD-ELEMENT-BAD
* (add-element-bad 10 '(1 2 3 4 5))
=> エラー "The variable N is unbound."
* (defun add-element (n xs)
(declare (special n))
(mapcar 'add-n xs))
ADD-ELEMENT
*
(add-element 10 '(1 2 3 4 5))
(11 12 13 14 15)
関数 add-n は引数 X に変数 N を足し算します。N はレキシカル変数ではないので、このままではスペシャル変数の値を探しにいきますが、定義されていなければエラーになります。したがって、関数 add-element-bad のように mapcar に add-n を渡しても動作しません。
そこで、関数 add-element のように declare で引数 N をスペシャル変数として宣言します。すると、add-element の引数 N は add-n から参照できるので、リストの要素に N を加算することができます。
本当は add-n のかわりにラムダ式 '(lambda (x) (+ x n)) を渡したかったのですが、ANSI Common Lisp ではエラーになります。ANSI 以前の Common Lisp は、'(lambda (x) (+ x n)) を mapcar に渡すことができたのですが、クロージャは生成されないので、add-n と同じように add-element-bad は動作しません。
●補足: ダイナミックスコープと funarg 問題
ところで、Common Lisp 以前の Lisp 処理系は変数を「ダイナミックスコープ」で管理しているので、add-element-bad のようなプログラムでも動作します。次の例を見てください。
* (defvar n)
N
* (defun add-n (x) (+ x n))
ADD-N
* (defun add-element (n xs) (mapcar 'add-n xs))
ADD-ELEMENT
* (add-element 10 '(1 2 3 4 5))
(11 12 13 14 15)
このように、defvar で N をスペシャル変数として宣言すると、add-element で mapcar に add-n を渡しても動作します。
ところが、もしも mapcar の定義で変数 N が使われていると、ダイナミックスコープでは add-element の引数 N を隠蔽してしまうので、プログラムは正常に動作しません。
* (defun my-mapcar (n xs)
(if (null xs)
'nil
(cons (funcall n (car xs)) (my-mapcar n (cdr xs)))))
MY-MAPCAR
* (defun add-element-ng (n xs) (my-mapcar 'add-n xs))
ADD-ELEMENT-NG
* (add-element-ng 10 '(1 2 3 4 5))
=> エラー "The value ADD-N is not of type NUMBER"
関数呼び出しは add-element-ng -> my-mapcar -> add-n の順番で行われます。add-element-ng を呼び出すとき、引数 N と XS が環境に追加されます。
環境 : ((N . 10) (XS 1 2 3 4))
次に、my-mapcar を呼び出しますが、このとき引数 N と XS が環境に追加されます。
環境 : ((N . ADD-N) (XS 1 2 3 4) (N . 10) (XS 1 2 3 4))
最後に add-n を評価しますが、このとき引数 X が環境に追加されます。
環境 : ((X . 1) (N . ADD-N) (XS 1 2 3 4) (N . 10) (XS 1 2 3 4))
ダイナミックスコープで変数を参照するとき、環境を先頭から線形探索します。add-n の本体は (* n x) ですね。環境を線形探索して最初に見つかる値は、N が add-n で、X が 1 になります。N は数値ではないのでエラーが発生します。このように、関数を定義するときの環境と実行するときの環境が異なると、プログラムが正常に動作しない場合があるのです。このような不具合を Lisp では「funarg 問題」といいます。
funarg 問題を解決するため、昔の Lisp (LISP 1.5, 1962 年) で導入されたのが function 式 (#') です。参考文献 2 によると、function 式を評価すると次のような funarg 形式が返されるそうです。
(funarg <lambda 式> <環境>)
funarg 形式は実行する関数本体 (ラムダ式) と function 式を評価したときの環境を格納したものです。その後、これを「クロージャ (closure) 」と呼ぶようになりました。
実をいうと、昔の Lisp にはもう一つ問題があって、小出さんの セマンティックウェブ・ダイアリー によると、『昔の Lisp は現在なら動的変数と呼ばれるものであり，そのために非常にわざとらしくプログラムすると，Lisp をコンパイルしないで実行した場合とコンパイルして実行した結果が異なるコードを書くことができて，これをFUNARG問題という名前で呼んでいた』 とのことです。
これはインタプリタとコンパイラで異なるスコープ規則を使っていたためです。コンパイラはダイナミックスコープでも作成できますが、性能を上げるにはレキシカルスコープのほうが有利だからです。Common Lisp - Wikipedia によると、『ZetaLisp や Franz Lisp といった Common Lisp の設計に寄与した LISP系のシステムの多くは、インタプリタ内では動的スコープを、コンパイラ内では構文スコープを使っていた。』 とのことです。
funarg 問題を解決するには、スコープ規則をレキシカルスコープにそろえる必要がありました。そして、クロージャを使うとインタプリタでも簡単にレキシカルスコープを実装することができます。
レキシカルスコープを採用した最初の Lisp 処理系が Scheme です。Scheme は関数 (局所変数やラムダ式も含む) をクロージャとして統一して扱うことで、第一級関数とレキシカルスコープを実現しています。その後、レキシカルスコープは Common Lisp にも採用されました。Common Lisp では function (#') を使うかぎり funarg 問題は発生しません。
●参考文献・URL
- 黒川利明, 『LISP 入門』, 培風館, 1982
- 小西弘一, 清水剛, 『ＣプログラムブックⅢ』, アスキー, 1986
- Guy L. Steele Jr. (著), 井田昌之 (翻訳監修), 『COMMON LISP 第 2 版』, 共立出版, 1991
ちょっと特殊な制御構造
Lisp は「関数型言語」と呼ばれるプログラミング言語ですが、完全な関数型言語ではありません。とくに Common Lisp の場合、手続き型言語からいろいろな機能が持ち込まれたため、ほかの関数型言語に比べると不純度の高い関数型言語になっています。
手続き型言語から持ち込まれた機能に block や tagbody があります。block はブロック構造を定義し、tagbody の中では無条件ジャンプ (go) を使うことができます。昔の Lisp では、prog という関数で局所変数とブロック構造を定義し、その中で go を使うことができました。Common Lisp の場合、prog の機能を block, tagbody, let の 3 つに分離し、必要な機能だけを使用できるようになっています。
今回はブロック構造や大域脱出など、Common Lisp に用意されている「ちょっと特殊な制御構造」について説明します。
●block と return-from
block は Pascal やＣ言語などのブロック構造を定義する関数 (特殊形式) で、return-from を使って block から脱出することができます。
block name Ｓ式 ...
block は progn と同じように S 式を左から右へ順番に評価します。そして、最後に評価された S 式の値を返します。S 式の評価中に name と同じシンボルを指定した return-from が評価されると、それ以降の S 式の評価を中止して、return-from が評価した値を block の評価値として返します。つまり、block から脱出することができるのです。name を「block 脱出点」といいます。
return-from name [result]
return-from の引数 name は評価されず、シンボルでなければいけません。return-from は result の評価結果を返します。result が省略された場合は NIL を返します。
それから block の name に NIL を指定した場合、return-from だけではなく return でも脱出することができます。do や loop などの繰り返しから return で脱出できるのは、繰り返し処理が block nil の中で定義されているからです。
それでは、簡単な使用例を示しましょう。2 次元配列の中から値を探す関数 search-matrix を作ります。次のプログラムを見てください。
リスト : 配列から値を探す (1)
(defun search-matrix (func a xmax ymax)
(block exit
(dotimes (x xmax)
(dotimes (y ymax)
(if (funcall func (aref a x y))
(return-from exit (aref a x y)))))))
search-matrix は 2 次元配列 a の中から述語 func を満たす要素を探します。dotimes が二重になっていますね。return を使うと内側のループから抜けることはできますが、外側のループから脱出することはできません。そこで、block で脱出先 exit を設定し、要素を発見したら return-from で exit へジャンプさせれば、二重のループからいっきに脱出することができます。
実は Common Lisp の場合、defun で定義された関数には暗黙のうちに block が置かれていて、その名前は関数名と同じです。つまり、defun で定義された関数は return-from を使って値を返すことができるのです。したがって、search-matrix は次のように書いても動作します。
リスト : 配列から値を探す (2)
(defun search-matrix (func a xmax ymax)
(dotimes (x xmax)
(dotimes (y ymax)
(if (funcall func (aref a x y))
(return-from search-matrix (aref a x y))))))
return-from の name に関数名 search-matrix を指定すれば、見つけた要素の値を返すことができます。
●block の脱出点はレキシカルスコープ
block の脱出点 name の有効範囲はレキシカルスコープです。次の図をみてください。
たとえば、繰り返し関数 dotimes から呼び出された関数 foo の中で return が評価されても、脱出先の name (NIL) の有効範囲はレキシカルスコープなので、関数 foo1 の dotimes から脱出することはできません。
逆に、block 脱出点がレキシカルスコープの範囲内にあれば、ラムダ式や局所関数の中から脱出することもできます。簡単な例を示しましょう。
* (defun foo (xs)
(mapcar (lambda (x) (if (minusp x) (return-from foo) (* x x))) xs))
FOO
* (foo '(1 2 3 4 5))
(1 4 9 16 25)
* (foo '(1 2 -3 4 5))
NIL
関数 foo は XS の要素を 2 乗したリストを返しますが、XS に負の要素が含まれていたら NIL を返します。このような処理は return-from を使えば簡単です。
block の脱出点 foo はレキシカルスコープなので、ラムダ式の中から参照することができ、return-from でそのブロックから脱出することができます。mapcar に渡したラムダ式の中で要素 X をチェックし、値が負ならば return-from で NIL を返します。このように、高階関数の処理を中断することができます。
また、前回作成した反復深化のプログラムで、深さ優先探索を局所関数で行えば、解を見つけたときに処理を中断して解を返すこともできます。
リスト : 経路の探索
;;; 隣接リスト
(defvar *adjacent*
'((A B C)
(B A C D)
(C A B E)
(D B E F)
(E C D G)
(F D)
(G E)))
;;; 反復深化
(defun id-search (start goal)
(labels
((dfs (limit goal path)
(if (= (length path) limit)
(when (eq (car path) goal)
(return-from id-search (reverse path)))
(dolist (x (cdr (assoc (car path) *adjacent*)))
(unless (member x path)
(dfs limit goal (cons x path)))))))
(do ((i 2 (1+ i)))
((> i 7))
(format t "----- ~d -----~%" i)
(dfs i goal (list start)))))
局所関数 dfs で goal に到達したとき、return-from id-search で見つけた経路 (reverse path) を返します。これで再帰呼び出しや do ループの繰り返しを脱出して、解をすぐに返すことができます。
* (id-search 'a 'g)
----- 2 -----
----- 3 -----
----- 4 -----
(A C E G)
もう一つ面白い方法を紹介しましょう。return-from name をラムダ式に包んで他の関数に渡すこともできます。この場合、渡されたラムダ式を実行すると、name で指定した block から脱出することができるのです。次のリストを見てください。
リスト : 行列の総和
(defun sum-list (failure xs)
(do ((xs xs (cdr xs))
(a 0 (+ a (car xs))))
((null xs) a)
(if (minusp (car xs))
(funcall failure))))
(defun sum-matrix (xs)
(do ((xs xs (cdr xs))
(a 0 (+ a (sum-list (lambda () (return-from sum-matrix -1))
(car xs)))))
((null xs) a)))
* (sum-matrix '((1 2 3) (4 5 6) (7 8 9)))
45
* (sum-matrix '((1 2 3) (4 5 6) (-7 8 9)))
-1
sum-matrix はリストの入れ子で表した行列 XS から 1 行ずつ取り出して sum-list に渡します。このとき、(return-from sum-matrix -1) を包んだラムダ式もいっしょに渡します。Common Lisp はレキシカルスコープなので、ラムダ式の中から脱出点 sum-matrix を参照することができます。次に、sum-list でリストの要素が負の場合、渡されたラムダ式 failure を評価します。すると、制御は sum-matrix に戻って -1 を返すことができます。
●tagbody と go
tagbody と go は制御構造を実現するために用いられます。
tagbody tag-or-form .....
tagbody は go のラベルとして使用されるシンボル (tag) と、評価されるフォーム (form : S 式のこと) からなります。tag は評価されません。tagbody は form を順番に評価していき、最後まで評価すると NIL を返します。もしも form の評価中に go が評価された場合、go で指定された tag に分岐し、そこから評価を続けます。
go tag
go は tagbody 内で使用され、実行の制御を tag によってラベル付けされた場所に移すために用いられます。tag はシンボルでなければいけません。tagbody 内に該当する tag がない場合はエラーとなります。
簡単な例題として、あえて tagbody と go を使って階乗を計算する fact を作ってみます。
リスト : 階乗の計算
(defun fact (x)
(let ((result 1) (num 1))
(tagbody
loop-tag
(if (> num x)
(return-from fact result))
(setq result (* result num))
(incf num)
(go loop-tag))))
繰り返しを実現するために tagbody と go を使っています。(go loop-tag) が評価されると loop-tag にジャンプし、次の S 式から評価を続けます。これで無限ループを構成しています。階乗を計算したら return-from で値を返します。なお、繰り返しは do などを使って簡単に実現できるので、このようなプログラムで tagbody と go を使ってはいけません。
ところで、tagbody と go のタグ (ジャンプ先) は block, return-from と同様にレキシカルスコープで管理されます。go をラムダ式に包んで他の関数に渡すこともできますが、go を使うことはおススメしないので、tagbody と go の説明はここまでにしておきましょう。
●使用上の重要な注意
Common Lisp に tagbody と go が用意されているのは、基本的な繰り返しや制御構造をマクロで実現するためです。Common Lisp には便利なマクロが多数用意されているので、一般的なプログラムであれば tagbody と go を使う必要はまったくありません。go の使用について CLtL2 (参考文献 2) より引用します。
『スタイルの問題として、go を用いる前に二度考えることを勧める。go のほとんどの目的は、繰り返しのための基本構文のうちの１つ、入れ子になった条件フォーム、あるいは return-from を用いて達成することができる。もし go の使用が避けられないと思われるならば、おそらく go によって実現される制御構造は、マクロ定義としてパッケージ化されるべきである。』
tagbody と go を安易に使用してはいけません。くれぐれもご注意くださいませ。
●大域脱出
Common Lisp の場合、catch と throw を使って評価中の関数からほかの関数へ制御を移すことができます。これを「大域脱出 (global exit)」といいます。catch と throw の使い方を説明します。
catch tag-name Ｓ式 ...
throw tag-name result
catch と throw は特殊形式で、その名が示すように catch が受け手で throw が投げ手としての役割を持っています。catch は最初に tag-name を評価します。このとき、評価結果はシンボルでなければいけません。
throw は tag-name を評価し、それと同じシンボルを持つ catch を探し、result を評価した結果を持って見つけた catch へジャンプします。そして、その値が catch の評価値となります。tag-name はダイナミックスコープで管理されることに注意してください。
それでは簡単な使用例を示しましょう。
* (defun bar1 () (print "call bar1"))
BAR1
* (defun bar2 () (throw 'exit t))
BAR2
* (defun bar3 () (print "call bar3"))
BAR3
* (defun foo () (bar1) (bar2) (bar3))
FOO
* (catch 'exit (foo))
"call bar1"
T <= catch の返り値
この様子を図に示すと、次のようになります。
通常の関数呼び出しは、呼び出し元の関数に制御が戻ります。ところが bar2 で throw が評価されると、呼び出し元の関数 foo を飛び越えて、制御が catch に移るのです。このように、大域脱出により関数を飛び越えて制御を移すことができます。catch と throw はとても強力な関数ですが、多用すると処理の流れがわからなくなる、いわゆる「スパゲッティプログラム」になってしまいます。使用には十分ご注意下さい。
このほかに、Common Lisp には「コンディション (condition)」という機能があります。ほかのプログラミング言語では「例外 (exception)」と呼ばれていて、おもに「エラー処理」で使われる機能です。これはあとで説明する予定です。
●unwind-protect
ところで、プログラムの途中で大域脱出が行われると残りのプログラムは評価されません。このため、必要な処理が行われない場合があります。たとえば、ファイルの入出力処理の場合、最初にファイルをオープンし最後でファイルをクローズしなければいけません。ファイルを関数 open でオープンして関数 close でクローズする場合、エラーや大域脱出で処理が中断されるとファイルをクローズすることができません。
ところが、ファイル入出力 で説明したマクロ with-open-file の場合、評価が終了するとファイルは自動的にクローズされますが、実はそれだけではなく、エラーや大域脱出などで処理が中断されてもファイルはクローズされます。とても便利な機能ですね。これは unwind-protect (特殊形式) を使って実現されています。
unwind-protect protected-form cleanup-form ...
unwind-protect は protected-form を評価し、そのあとで cleanup-form を評価します。protected-form の評価中にエラーや大域脱出などで処理が中断されても、cleanup-form は必ず評価されます。cleanup-form には複数の S 式を指定することができます。unwind-protect の返り値は protected-form の評価結果です。
簡単な例を示しましょう。大域脱出で作成した関数 foo を使います。
* (catch 'exit
(unwind-protect
(foo)
(print "cleanup1") (print "cleanup2")))
"call bar1"
"cleanup1"
"cleanup2"
T <= catch の評価結果
関数 bar2 の大域脱出により unwind-protect を飛び越えて catch に制御が移りますが、このとき cleanup-form が評価されていることがわかります。また、unwind-protect は大域脱出だけではなく return-from などによる脱出にも有効です。次の例を見てください。
* (block nil
(unwind-protect
(progn
(print 1)
(return)
(print 2))
(print "cleanup")))
1
"cleanup"
NIL
return で block から脱出しますが、このときに cleanup-form が評価されていることがわかります。
