M.Hiroi's Home Page

xyzzy Lisp Programming

Common Lisp 入門

[ PrevPage | xyzzy Lisp | NextPage ]

ちょっと特殊な制御構造

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 やC言語などのブロック構造を定義する関数 (特殊形式) で、return-from を使って block から脱出することができます。

block name S式 ...

block は progn と同じように S 式を左から右へ順番に評価します。そして、最後に評価された S 式の値を返します。S 式の評価中に name と同じシンボルを指定した return-from が評価されると、それ以降の S 式の評価を中止して、return-from が評価した値を block の評価値として返します。つまり、block から脱出することができるのです。

return-from name [result]

return-from の引数 name は評価されず、シンボルでなければいけません。return-from は result の評価結果を返します。result が省略された場合は nil を返します。

それから block の name に nil を指定した場合、return-from だけではなく return でも脱出することができます。do や while などの繰り返しから return で脱出できるのは、繰り返し処理が block nil の中で定義されているからです。また、name の有効範囲はレキシカルスコープです。次の図をみてください。

たとえば、繰り返し関数 dotimes から呼び出された関数 foo の中で return が評価されても、脱出先の name (nil) の有効範囲はレキシカルスコープなので、関数 foo1 の dotimes から脱出することはできません。ご注意くださいませ。

それでは、簡単な使用例を示しましょう。2 次元配列の中から値を探す関数 search-matrix を作ります。次のプログラムを見てください。

List 1 : 配列から値を探す(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 は次のように書いても動作します。

List 2 : 配列から値を探す(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 を指定すれば、見つけた要素の値を返すことができます。

●tagbody と go

tagbody と go は制御構造を実現するために用いられます。xyzzy Lisp の evalmacs.l には、do や while など基本的な繰り返しが block と tagbody を用いて定義されています。

tagbody name-or-form .....

tagbody は go のラベルとして使用されるシンボル (name) と、評価されるフォーム (form : S 式のこと) からなります。name は評価されません。tagbody は form を順番に評価していき、最後まで評価すると nil を返します。もしも form の評価中に go が評価された場合、go で指定された name に分岐し、そこから評価を続けます。

go name

go は tagbody 内で使用され、実行の制御を name によってラベル付けされた場所に移すために用いられます。name はシンボルでなければいけません。tagbody 内に該当する name がない場合はエラーとなります。go でジャンプできる有効範囲はレキシカルスコープです。ご注意ください。

簡単な例題として、あえて tagbody と go を使って階乗を計算する fact を作ってみます。

List 3 : 階乗の計算

(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 を使ってはいけません。

●使用上の重要な注意

Common Lisp に tagbody と go が用意されているのは、基本的な繰り返しや制御構造をマクロで実現するためです。Common Lisp には便利なマクロが多数用意されているので、一般的なプログラムであれば tagbody と go を使う必要はまったくありません。go の使用について CLtL2 (参考文献 [3]) より引用します。

『スタイルの問題として、go を用いる前に二度考えることを勧める。go のほとんどの目的は、繰り返しのための基本構文のうちの1つ、入れ子になった条件フォーム、あるいは return-from を用いて達成することができる。もし go の使用が避けられないと思われるならば、おそらく go によって実現される制御構造は、マクロ定義としてパッケージ化されるべきである。』

tagbody と go を安易に使用してはいけません。くれぐれもご注意くださいませ。

●大域脱出

Common Lisp の場合、catch と throw を使って評価中の関数からほかの関数へ制御を移すことができます。これを大域脱出 (global exit) といいます。catch と throw の使い方を説明します。

catch tag-name S式 ...
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"))
(defun bar2 () (throw 'exit t))
(defun bar3 () (print "call bar3"))
(defun foo () (bar1) (bar2) (bar3))

(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 が評価されていることがわかります。


クロージャ

クロージャ (closure) は、実行する関数とアクセス可能なレキシカル変数をまとめたものです。クロージャは関数のように実行することができますが、クロージャを生成するときに、その時点で有効なレキシカル変数も保持することろが異なります。Common Lisp の場合、レキシカルスコープ (lexical scope) という規則によって、レキシカル変数の有効範囲が決められます。このため、レキシカルクロージャと呼ばれることもあります。

クロージャという概念は、ちょっと難しいところがあります。まあ、難しいといってもC言語のポインタほどではありません。それでも基礎知識がしっかりしていないと、正しく理解するのは難しいでしょう。このポイントがレキシカル変数の有効範囲です。レキシカルスコープは レキシカル変数の有効範囲 で簡単に説明しましたが、ここで詳しく説明しましょう。

●レキシカルスコープ

変数の有効範囲を表すのに「スコープ」という用語を使います。Common Lisp のスコープ規則はレキシカルスコープです。レキシカルとは文脈上という意味があり、プログラムで変数を定義した場所によって、その変数にアクセスできるかどうかが決まります。Common Lisp では、関数の引数や let などで定義したレキシカル変数はレキシカルスコープで扱われます。次の例を見てください。

たとえば、(foo 10) を評価したとしましょう。引数 a には 10 がセットされますね。変数 a の値は関数 foo の全体で有効です。つまり、foo の中で変数 a にアクセスすると、その値は 10 となります。次に、let でレキシカル変数 b を定義しています。変数 b は、それを定義した let の中だけが有効です。同様にレキシカル変数 c を let で定義しています。この状態で、レキシカル変数の有効範囲はどのようになるでしょうか。

1 の位置では、レキシカル変数は a と b の 2 つが定義されていますが、c は定義されていません。この位置で a と b にアクセスすると、それぞれ 10 と 20 の値になりますが、c にアクセスすることはできません。もし、変数 c がスペシャル変数として定義されていれば、スペシャル変数にアクセスします。

2 の位置では 3 つのレキシカル変数 a, b, c が定義されているので、その値は 10, 20, 30 となります。3 の位置では、レキシカル変数 b と c を定義した let の範囲外ですね。この場合、アクセスできるレキシカル変数は a だけなのです。つまり、レキシカル変数はそれを定義した S 式の範囲内でのみ有効なのです。関数の引数であれば、それを定義した defun の S 式が範囲内であり、let, dotimes, dolist などの場合も同じです。

また、ある関数で定義されたレキシカル変数は、ほかの関数からアクセスすることはできません。定義されていない変数はスペシャル変数として扱われます。もしも、スペシャル変数に値がセットされていなければエラーとなります。このように、S 式という文脈からレキシカル変数のアクセスを決定できるので、レキシカルスコープと呼ばれています。

●ダイナミックスコープ

ところが、伝統的な Lisp はレキシカルスコープではありません。ある関数で定義した局所変数に、ほかの関数からアクセスできる場合があるのです。次の例を見てください。

(defun foo ()
  (let ((a 100)) (bar)))
(defun bar (print a))

(setq a 10)
(foo)
10

xyzzy Lisp で foo を実行すると 10 が表示されます。bar の中でレキシカル変数 a は定義されていないので、変数 a はスペシャル変数としてアクセスされます。

ところが、このプログラムを Emacs Lisp で実行すると、100 が表示されます。つまり、foo で定義した変数 a に、関数 bar からアクセスすることができるのです。これをダイナミックスコープといいます。ダイナミックスコープの場合、foo から呼ばれた関数ならば、foo で定義された局所変数にアクセスすることができるのです。これを図に示すと次のようになります。

ダイナミックスコープの場合、局所変数はひとつの連想リストで管理されていると考えてください。この場合、キーが局所変数を表し、データがその値に対応します。局所変数にアクセスするときは、この連想リストから該当する変数を探すのです。見つからない場合はグローバル変数を検索します。

関数呼び出しや let などで局所変数が定義されたときに、変数とその値が連想リストの先頭へ追加されます。そして、関数や let の評価が終了したときに、連想リストから変数が削除されます。関数が呼び出されるたびに、新しい変数が連想リストに追加されますが、呼び出した側で定義した局所変数も、この連想リストの中に残っています。

たとえば、(1) のように関数 bar を呼び出した場合、関数の引数がなくて局所変数の定義もないので連想リストは空です。ところが、(2) のように関数 foo を呼び出した場合、局所変数 a が定義されているので、連想リストに (a . 100) がセットされます。この状態で関数 bar が呼び出されると、連想リストには foo で定義した (a . 100) が残っているので、bar では a の値が 100 となるのです。

このように、ダイナミックスコープでは、変数のアクセスは関数を評価する順番に左右されます。したがって、関数の中で定義されていない変数があっても、それがグローバル変数として扱われるとは限らないのです。

●関数の中で関数を定義する

ダイナミックスコープで便利なところは、ほかの関数から局所変数をアクセスできるところです。ですが、プログラムを見ただけでは、どの変数にアクセスしているのかわからないという欠点があります。Common Lisp では、関数の中で別の関数を定義することで、ほかの関数のレキシカル変数にアクセスすることができます。

たとえば、関数 foo の中で関数 bar を定義し、bar から foo のレキシカル変数にアクセスすることができるのです。Pascal をご存知の方には、お馴染みの機能だと思います。Common Lisp の場合、labels を使って関数内で別の関数を定義することができます。

(labels 
  ((func1 (args ...) body1)  
   (func2 (args ...) body2)
   .....)
  labels-body)

labels は最初に関数を定義して、labels の本体 labels-body を評価します。関数は複数定義することができますが、呼び出すことができるのは labels-body の中だけであることに注意してください。さきほどの foo と bar を labels を使ってプログラムすると、次のようになります。

(defun foo ()
  (let ((a 100))
    (labels ((bar () (print a)))
            (bar))))

プログラムに意味はありませんが、レキシカル変数 a に注目してください。a の有効範囲は let の中ですが、この中で labels により関数 bar が定義されていますね。この場合、関数 bar はレキシカル変数 a にアクセスできるのです。したがって、foo を実行するとレキシカル変数 a の値 100 が表示されます。

簡単な処理ならば、ラムダ式を使ってもいいでしょう。ですが、ラムダ式には関数名がありませんね。labels は関数として定義するわけですから、再帰関数も定義することができます。これはなかなか強力な機能です。

それでは簡単な例題として、リストの中から data を見つける find-tree を作りましょう。labels を使わないと、次のようになるでしょう。

List 4 : データの探索

(defun find-tree (data tree)
  (cond ((atom tree) (eql data tree))
        ((endp tree) nil)
        (t (or (find-tree data (car tree))
               (find-tree data (cdr tree))))))

簡単すぎるので例題には適さないかもしれませんが、ご了承くださいませ。これを labels を使って書き直すと、次のようになります。

List 5 : データの探索(labels版)

(defun find-tree (data tree)
  (labels ((find-tree-sub (tree)
             (cond ((atom tree) (eql data tree))
                   ((endp tree) nil)
                   (t (or (find-tree-sub (car tree))
                          (find-tree-sub (cdr tree)))))))
    (find-tree-sub tree)))

find-tree-sub から find-tree の引数 data にアクセスすることができます。また、find-tree と find-tree-sub には同じ引数 tree が使われていますね。この場合、find-tree-sub は自分の引数 tree にアクセスします。find-tree の引数 tree は、find-tree-sub から見えなくなることに注意してください。ただし、find-tree-sub の引数 tree を別名にすれば、find-tree の引数 tree にアクセスできるようになります。

●クロージャとは?

それでは「クロージャ (closure) 」の話に入りましょう。ラムダ式の頭に付いている #' のことを思い出してください。#' は function 特殊形式の省略形です。function はシンボルに格納されている関数を取り出す働きをします。そして function が返す値がクロージャなのです。クロージャは関数だけではなく、そのときに有効なレキシカル変数とその値も取り出して保存します。次の例を見てください。

この例では評価する関数はラムダ式です。そして、クロージャを生成するときに有効なレキシカル変数は、関数 foo の引数 a と let で定義された変数 b です。これらの変数と値がクロージャに保持されます。ここでは連想リストに格納されていると考えてください。この連想リストを環境 (environment) と呼びます。クロージャを評価するときは、取り出した関数をこの「環境」で評価するのです。ここがクロージャを理解するポイントです。

ラムダ式が評価される場合、まず引数の値がセットされますね。たとえば、c に 30 がセットされたとしましょう。すると、クロージャに保持されている環境に (c . 30) が追加されます。

環境 : ((c . 30) (b . 20) (a . 10))

ラムダ式の本体はこの環境で評価されるため、ラムダ式の引数 c 以外のレキシカル変数、つまり foo の引数や let で定義されたレキシカル変数にアクセスできるのです。

●クロージャを変数に代入する

今度は、クロージャ独特の使い方を見ていきましょう。クロージャは function の返り値です。つまり Lisp で扱うことができるデータのひとつです。ということは、クロージャを変数に代入することもできるはずです。次の例を見てください。

List 6 : この関数は何をする?

(defun foo (x) #'(lambda (y) (* x y)))

関数 foo はクロージャを返します。このクロージャを変数にセットしておいて、funcall や apply などの高階関数を使って呼び出すことができます。次の例を見てください。

(setq t2 (foo 2))
=> #<lexical-closure: (lambda (y) (* x y))>
(funcall t2 4)
=> 8
(funcall t2 5)
=> 10

(setq t10 (foo 10))
=> #<lexical-closure: (lambda (y) (* x y))>
(funcall t10 1)
=> 10
(funcall t10 2)
=> 20

この例からもわかるように、変数 t2 に格納されたクロージャを評価すると、引数を 2 倍した値を返します。変数 t10 のクロージャは、引数を 10 倍しています。つまり、関数 foo は引数を定数倍する関数を生成していたのです。

(foo 2) を評価すると、そのクロージャには評価する S 式と環境がセットされます。このとき、定義されているレキシカル変数は foo の引数 x だけです。したがって、環境は ((x . 2)) となります。このクロージャを評価するときは、この環境で行われます。したがって、(funcall t2 4) を評価すると、y = 4, x = 2 なり、ラムダ式の評価結果は 8 となるのです。

(foo 10) の場合も同様です。これは x の値が 10 になるだけです。環境の保存はクロージャを生成するときに行われます。引数 x は同じだからといって、環境も共通で使われるわけではありません。(foo 2) と (foo 10) で生成したクロージャの環境は異なることに注意してください。

●ジェネレータ

クロージャの応用例として、ジェネレータ (generator) というプログラムを作りましょう。ジェネレータは呼び出されるたびに新しい値を生成します。たとえば、関数 random は評価するたびに乱数を返しますね。random は乱数列を発生する「ジェネレータ」と考えることができます。

簡単な例題として、フィボナッチ数列 ( 1, 1, 2, 3, 5, 8, ..... ) を発生するジェネレータを作ってみます。関数名は gen-fibo としましょう。ジェネレータはスペシャル変数を使って実現することができますが、クロージャを使った方がスマートです。まず、ジェネレータを作る関数を定義します。

List 7 : ジェネレータ生成(1)

(defun make-gen-fibo ()
  (let ((a0 1) (a1 0) (a2 0))
    #'(lambda () (prog1 a0
                   (setq a2 a1 a1 a0)
                   (setq a0 (+ a1 a2))))))

関数 make-gen はクロージャを返します。そして、このクロージャがジェネレータの役割を果たすのです。それでは、実際に実行してみましょう。

(setq f1 (make-gen-fibo))
#<lexical-closure: ..... >
(dotimes (x 6) (print (funcall f1)))

1 
1 
2 
3 
5 
8 
nil

make-gen-fibo で作成したクロージャを変数 f1 にセットし、funcall で評価します。1, 1, 2, 3, 5 とフィボナッチ数列を生成していますね。新しいクロージャを変数 f2 にセットし、このクロージャを評価すれば、新しいフィボナッチ数列が生成されます。

クロージャで保存される環境は、let で定義された変数 a0, a1, a2 です。これらの変数は let が評価されたときに初期化される、つまり、クロージャを生成するときに初期化されることに注意してください。

環境はクロージャによって異なります。f1 のクロージャが評価されると、そのクロージャの環境が更新されるのであって、ほかのクロージャに影響を与えることはありません。したがって、あるジェネレータが発生するフィボナッチ数列が、ほかのジェネレータに影響を与えることはないのです。あとは必要な数だけジェネレータを make-gen-fibo で作り、生成したクロージャを変数に格納しておけばいいわけです。

●ジェネレータをリセットする

次はフィボナッチ数列を最初に戻す、つまり、ジェネレータをリセットすることを考えましょう。この場合、クロージャ内の変数を書き換えるしか方法はありません。そこで、gen-fibo に引数を与えて、value ならばフィボナッチ数列を発生させる、reset ならばリセットするようにしましょう。数列を発生させる処理とリセットする処理をラムダ式で作成し、それを make-gen-fibo の定義するレキシカル変数に格納しておけば、その処理を呼び出すことができます。プログラムは次のようになります。

List 8 : ジェネレータ生成(2)

(defun make-gen-fibo ()
  (let* ((a0 1) (a1 0) (a2 0)
         (reset-func #'(lambda () (setq a0 1 a1 0 a2 0)))
         (value-func #'(lambda () (prog1 a0
                                    (setq a2 a1 a1 a0)
                                    (setq a0 (+ a1 a2))))))
    #'(lambda (type)
        (cond ((eq type 'reset) (funcall reset-func))
              ((eq type 'value) (funcall value-func))))))

変数 reset-func にジェネレータをリセットする処理を、value-func にフィボナッチ数列を発生する処理をセットします。レキシカル変数の定義には let* を使っていることに注意してください。これでラムダ式内から変数 a0, a1, a2 にアクセスすることができます。

ジェネレータ本体の処理は、引数が reset ならば reset-func を、value ならば value-func を呼び出すだけです。このラムダ式は let* 内で定義されているので、reset-fucn と value-func にアクセスすることができます。

それでは実行してみましょう。

(setq f1 (make-gen-fibo))
#<lexical-closure: (lambda (type) .....)>
(dotimes (x 5) (print (funcall f1 'value)))

1 
1 
2 
3 
5 
nil

(funcall f1 'reset)
0

(dotimes (x 5) (print (funcall f1 'value)))

1 
1 
2 
3 
5 
nil

正常に動作していますね。リセットの動作はジェネレータを初期化するだけです。リセットの動作でフィボナッチ数列の最初の値を出力してもいいでしょう。簡単に改造できるので試してみてください。

●難しいかな?

クロージャの話は少し難しかったかもしれません。とくに、ジェネレータのような使い方は、C言語などの手続き型言語を使いこなしているユーザーでも驚くことなのです。私が 参考文献 [1] でジェネレータのプログラムを見たときは、「Lisp はこんなこともできるのか!」とたいへん驚いたものです。

最近では、Perl 5 でも無名関数やクロージャが取り入れられていますが、Lisp の方が元祖なのです。クロージャは少々歯応えがある機能ですが、これもプログラミングの面白いところだと思います。じっくりとを味わってみてください。

●追記 (2014/05/23)

昔の Lisp は「ダイナミックスコープ」なので、高階関数に関数を渡すときクォートを使っても動作することがあります [*1]。Common Lisp の場合、defvar で宣言された変数はダイナミックスコープで管理されます。次の例を見てください。

(defun times-element (n xs)
  (mapcar '(lambda (x) (* n x)) xs))
=> times-element
(defvar n)
=> n
(times-element 10 '(1 2 3 4))
=> (10 20 30 40)

ダイナミックスコープの場合、呼び出された関数から呼び出し元の関数で定義された局所変数にアクセスすることができます。関数は times-element -> mapcar -> ラムダ式 の順番に呼び出されているので、ラムダ式から times-element の引数 n の値を参照することができるわけです。

ただし、mapcar の定義で変数 n が使われていると、ダイナミックスコープでは times-element の引数 n を隠蔽してしまうので、プログラムは正常に動作しません。次の例を見てください。

(defun my-mapcar (n xs)
  (if (null xs)
      'nil
    (cons (funcall n (car xs)) (my-mapcar n (cdr xs)))))
=> my-mapcar

(my-mapcar '(lambda (x) (* x x)) '(1 2 3 4))
=> (1 4 9 16)

(defun times-element (n xs)
  (my-mapcar '(lambda (x) (* n x)) xs))
=> times-element

(times-element 10 '(1 2 3 4))
=> 不正なデータ型です: (lambda (x) (* n x)): number

これは、ラムダ式を高階関数に渡すときの環境と、それを実行するときの環境が異なることが原因です。このような問題を「funarg 問題」といいます。my-mapcar にラムダ式を渡すとき、変数 n の値は times-element の引数 n の値 (10) になりますが、my-mapcar でラムダ式を実行するとき、my-mapcar の引数 n で隠蔽されるので、参照したい値 (10) にアクセスすることができないわけです。

このような funarg 問題を解決するため、昔の Lisp (LISP 1.5) で導入されたのが function 式 (#') です。ただし、昔の Lisp はダイナミックスコープのままなので、完全に funarg 問題が解決されたわけではありません。けっきょく funarg 問題を解決するには、スコープをレキシカルスコープに変更する必要がありました。最初にレキシカルスコープを採用した Lisp 処理系が Scheme です。

Scheme は関数 (ラムダ式や局所関数も含む) をクロージャとして統一して扱うことで、レキシカルスコープを実現しています。もちろん、funarg 問題は発生しません。Common Lisp の場合も、レキシカルクロージャを使うかぎり funarg 問題は発生しません。詳しい説明は拙作のページ Common Lisp 入門 : 番外編 funarg 問題 をお読みください。

-- note (2015/06/07) --------
[*1] ANSI Common Lisp の場合、'(lambda ...) を関数として渡すことはできません。CLISP での実行例を示します。
> (mapcar '(lambda (x) (* x x)) '(1 2 3 4 5))

*** - FUNCALL: argument (LAMBDA (X) (* X X)) is not a function.
      To get a function in the current environment, write (FUNCTION ...).
      To get a function in the global environment, write (COERCE '... 'FUNCTION).

ちょっと寄り道

■ベクタによるキューの実装

リストの破壊的修正 では、リストを使ってキュー (queue) を実現しました。キューは配列を使っても簡単に実現できます。先頭位置を示す front と末尾を示す rear を用意し、front と rear の間にあるデータをキューに格納されているデータとするのがポイントです。次の図を見てください。

まずキューは空の状態で、rear, front ともに 0 です。データの追加は、rear が示す位置にデータを書き込み、rear の値をインクリメントします。データ 10, 20, 30 を追加すると、図のようにデータが追加され rear は 3 になります。このとき front は 0 のままなので、先頭のデータは 10 ということになります。

次に、データを取り出す場合、front の示すデータを取り出してから front の値をインクリメントします。この場合、front が 0 なので 10 を取り出して front の値は 1 となり、次のデータ 20 が先頭になります。データを順番に 20, 30 と取り出していくと、3 つしかデータを書き込んでいないので当然キューは空になります。このとき front は 3 になり rear と同じ値になります。このように、front と rear の値が 0 の場合だけが空の状態ではなく、front と rear の値が等しくなると、キューは空になることに注意してください。

rear, fornt ともに値は増加していく方向なので、いつかは配列の範囲をオーバーします。このため、配列を先頭と末尾がつがっているリング状と考え、rear, front が配列の範囲を超えたら 0 に戻すことにします。これを循環配列とかリングバッファと呼びます。一般に、配列を使ってキューを実現する場合は、リングバッファとするのがふつうです。

■プログラム

Common Lisp の場合、リングバッファを操作する関数は用意されていないので、実際に作ってみることにしましょう。最初に、基本的な操作関数を説明します。

述語 emptyp と fullp は Lisp らしく最後に p を付けてみました。 次に、キューを表す構造体を定義します。

List 9 : キューを表す構造体

(defstruct Queue
  (front  0)
  (rear   0)
  (count  0)
  (buffer (make-array 16)))

スロット count はキューに格納されたデータ数をカウントします。この変数を用意することで、キューの状態を簡単にチェックすることができます。スロット buffer にはベクタをセットします。デフォルトは大きさ 16 のベクタですが、大きさを変更したい場合は、構造体を生成する make-Queue でスロットの初期値を設定してください。

(make-Queue :buffer (make-array 32))

これで大きさ 32 のベクタがスロット buffer にセットされます。

次はデータを追加する enqueue を作ります。

List 10 : キューにデータを追加する

(defun enqueue (queue data)
  (when (< (Queue-count queue) (array-total-size (Queue-buffer queue)))
    (setf (aref (Queue-buffer queue) (Queue-rear queue)) data)
    (incf (Queue-count queue))
    (incf (Queue-rear queue))
    (if (= (array-total-size (Queue-buffer queue)) (Queue-rear queue))
        (setf (Queue-rear queue) 0))
    t))

まず、スロット count の値とベクタの大きさを比較して、キューにデータを格納できるかチェックします。ベクタの大きさは列関数 length で求めることができますが、今回は関数 array-total-size を使ってみました。array-total-size は配列の全要素数を返します。次の例を見てください。

(setq a (make-array '(2 2))
=> #2A((nil nil) (nil nil))
(array-total-size a)
=> 4

(setq a (make-array 10 :fill-pointer 0))
=> #()
(length a)
=> 0
(array-total-size a)
=> 10

make-array で 2 行 2 列の配列を作りました。この配列に array-total-size を適用すると、要素の総数 4 を返します。ただし、:fill-pointer を設定したベクタの場合、length の返す値は fill-pointer に左右されますが、array-total-size はベクタの大きさを返すことに注意してください。

データは rear の位置に格納し、count と rear の値を更新します。そして、rear の値がベクタの範囲を超えたならば 0 に戻します。rear の値を更新する処理は、次のようにプログラムしてもかまいません。

(setf (Queue-rear queue)
      (mod (1+ (Queue-rear queue))
           (array-total-size (Queue-buffer queue))))

剰余を求める関数 mod を使うのがポイントです。

次は、キューからデータを取り出す関数 dequeue を作ります。

List 11 : キューからデータを取り出す

(defun dequeue (queue)
  (when (plusp (Queue-count queue))
    (prog1
      (aref (Queue-buffer queue) (Queue-front queue))
      (decf (Queue-count queue))
      (incf (Queue-front queue))
      (if (= (array-total-size (Queue-buffer queue)) (Queue-front queue))
          (setf (Queue-front queue) 0)))))

まず、キューにデータがあるかチェックしてから、aref で front の位置にあるデータを取り出します。prog1 を使っているので、aref で取り出したデータが dequeue の返り値になることに注意してください。あとは、count と front の値を更新し、front の値がベクタの範囲を超えたら 0 に戻します。

あとの関数 front, emptyp, fullp, clear は簡単なので説明は省略します。リストを見てください。

List 12 : キューの操作関数

; 先頭のデータをリード
(defun front (queue)
  (when (plusp (Queue-count queue))
    (aref (Queue-buffer queue) (Queue-front queue))))

; キューが空か
(defun emptyp (queue) (zerop (Queue-count queue)))

; キューが満杯か
(defun fullp (queue)
  (= (Queue-count queue) (array-total-size (Queue-buffer queue))))

; キューを空にする
(defun clear (queue)
  (setf (Queue-rear queue)  0
        (Queue-front queue) 0
        (Queue-count queue) 0))

■使用例

これでプログラムは完成です。それでは、簡単な使用例を示しましょう。

(setq a (make-Queue))
=> #S( 省略 )
(dotimes (x 16) (enqueue a x))
=> nil
(enqueue a 100)
=> nil
(while (not (emptyp a))
  (format t "~D " (dequeue a)))
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 
nil

make-Queue でキューを作成して変数 a にセットします。dotimes でキューにデータを 16 個セットします。これでキューは満杯になるので、これ以上データを追加することはできません。次に、dequeue でデータを取り出します。先に入れたデータから順番に取り出されていることがわかりますね。これでキューは空の状態になります。


Copyright (C) 2000-2003 Makoto Hiroi
All rights reserved.

[ PrevPage | xyzzy Lisp | NextPage ]