ユーティリティ関数

Common Lispのオペレータは3種類に分かれる: 関数にマクロ(ユーザが作れるもの)と,特殊オペレータ(ユーザには作れない)だ. この章では,Lispを新しい関数で拡張するテクニックを説明する. しかしここで言う「テクニック」は普通の意味のものではない. そういった関数について知るべき重要な点は, それらをどうやって書くかということではなく,それらがどこから来たのかということだ. Lispの拡張には,他の関数を書くときと大体同じテクニックが使われることになる. そういった拡張を書くとき難しいのは, どうやって書くかを決めることではなく,何を書くかを決めることだ.

ユーティリティの誕生

一番単純な場合では,誰がユーザのLispをデザインしようと, ボトムアップ・プログラミングとは後から付いた名前に過ぎない. また同時に,ユーザはプログラムを書きながら, プログラムを書き易くする新しいオペレータをLispに追加していく. これらの新しく作られたオペレータはユーティリティと呼ばれる.

「ユーティリティ」という言葉に正確な定義などない. ある短いコードがユーティリティと呼ばれるのは, それが短すぎて独立のアプリケーションとは見なせず, しかも用途が一般的過ぎてあるプログラムの一部とも見なせない場合だ. 例えば,データベース・プログラムはユーティリティにはならないが, リストに単一の操作を行う関数はユーティリティになりうる. 大部分のユーティリティはLispが既に備えている関数やマクロに似ている. 実際,Common Lispの組み込みオペレータの多くはユーティリティとして生まれたものだ. 関数remove-if-notはリストの要素のうちある述語を満たすものを全て集めるが, Common Lispの一部になるまでの何年もの間,個々のプログラマによって使われていた.

ユーティリティの書き方は, 書くときのテクニックとするよりも心得とした方が上手く説明できる. ボトムアップ・プログラミングとは, プログラムとプログラミング言語を同時に書いていくことだ. これを上手にこなすには, プログラムにどのオペレータが欠けているかを鋭く感じる感覚を鍛えないといけない. プログラムを見て,「ああ,あなたが本当に言いたいのはこれでしょう.」 と言えるようにならなくてはいけない.

例えば,ここでnicknamesが名前を引数に取り, それから派生しうる愛称の全てをリストにまとめる関数だとしよう. この関数が与えられたとき, 名前のリストから得られる愛称を全て集めるにはどうすればいいだろう? Lispを学習中の誰かが次のようなコードを書くかもしれない:

(defun all-nicknames (names)
  (if (null names)
      nil
      (nconc (nicknames (car names))
        (all-nicknames (cdr names)))))

経験を積んだLispプログラマは,こんな関数を見て 「ああ,本当に欲しいのはmapcanだろ.」と言う. それならある人々の愛称を全て探す新しい関数を定義して呼び出さなくても,1個の式で済む:

(mapcan #'nicknames people)

all-nicknamesは車輪の再発明だ. だが,それがまずいのはその点だけではない: 汎用オペレータで可能なことを特定の関数に埋もれさせてしまっている.

この場合オペレータmapcanは既に存在していた. mapcanを知っていた人はall-nicknamesを見ると少し変な気がしただろう. ボトムアップ・プログラミングに上達するには, 使われていないオペレータがまだ書かれていないものだったとき, 同じような不快感を感じられるようにならなくてはいけない. 「本当に欲しいのはxだろ.」と言えなくてはならず, 同時にxがどういうものであるべきか分かっていなければならない. Lispプログラミングは,何よりも必要に応じて新ユーティリティを生み出すことを必然的に伴う. この章の狙いは,そういったユーティリティがどのように生まれるかを示すことだ.

ここで,townsは近隣の街を近い方から順に並べたリストで, bookshopsは市内の全ての書店のリストを返す関数だとしよう. 書店がある一番近い街と,その中の書店を探したいとき,まず次のものから始めよう:

(let ((town (find-if #'bookshops towns)))
  (values town (bookshops town)))

しかしこれは少し格好悪い:find-ifが 「bookshopsが非nilの値を返すような要素」を見つけたときもその値は捨てられ, find-ifから戻った直後に再びその値を求めるようになっている. bookshopsの呼び出しのコストが大きいとすると, 慣用法に従ったこの方法は格好悪いばかりか非効率にもなるだろう. 不必要な処理を避けるため,代わりに次の関数を使う:

(defun find-books (towns)
  (if (null towns)
      nil
      (let ((shops (bookshops (car towns))))
        (if shops
            (values (car towns) shops)
            (find-books (cdr towns))))))

(find-books towns)の呼び出しでは, 少なくとも必要最低限の計算で望みの結果が出る. しかしちょっと待て ---いつか将来,再び似たような検索をしたくなることはないだろうか? ここで本当に必要なのは,find-ifと, 発見された要素と比較関数の返り値の両方を返す何かの関数を結合するユーティリティだ. そのようなユーティリティは

(defun find2 (fn lst)
  (if (null lst)
      nil
      (let ((val (funcall fn (car lst))))
        (if val
            (values (car lst) val)
            (find2 fn (cdr lst))))))

として定義できる. find-booksfind2が似ていることに注意しよう. 実際,後者は前者の全体構造として表せる. 今,新しいユーティリティを使えば,最初の目的を1個の式で達成できる:

(find2 #'bookshops towns)

Lispプログラミング独特の特徴の一つは,引数としての関数の重要性だ. これはLispがボトムアップ・プログラミングに適している理由の一部だ. 関数の骨格を抽象化するのは,引数に関数を使うことで肉付けができるときには比較的簡単だ.

プログラミングの入門課程では,最初に「抽象化は二度手間の回避につながる」と教える. その中の初歩の一つに「動作を重複させてはいけない」とある. 例えば,1〜2個の定数に従って同じことをする関数を定数別に定義するのではなく, 1個の関数を定義し,それに定数を引数として与えればいい.

Lispでは関数全体を引数として渡せるので,この考えをさらに深めることができる. 前述の例の両方で,特定の関数から始めて,関数を引数に取る一般的な関数に進んだ. 1番目の例では既に定義されていたmapcanを使い, 2番目の例では新しいユーティリティfind2を書いたが, 全体的な原則は同じだ: 一般部分と個別部分を混ぜ合わせるのでなく, 一般部分を定義して個別部分を引数として渡すこと.

注意深く適用すれば,この原則は目覚ましい程エレガントなプログラムをもたらす. ボトムアップ・プログラミングを支える力はそれだけではないが,これは主要なものだ. この章で定義した32個のユーティリティのうち,18個が関数を引数に取ることができる.

抽象化への投資

簡潔さがウィットの魂ならば,それはまた,効率と並んで,いいソフトウェアの真髄でもある. プログラムを書いたり保守するのにかかるコストは, プログラムが長くなるにつれて高まる\note{MaintainningCost}. 他の条件が同じなら,短いプログラムの方がいい.

この視点からは,ユーティリティの作成は主要な労力配分の対象と見なされるべきだ. find-booksをユーティリティfind2で置き換えた結果, コードの行数は変わらなかった. しかしある意味ではプログラムを短くしたことになった. なぜならユーティリティの長さは現在製作中のプログラムの長さに加えなくてもいいからだ.

Lispの拡張を主要な労力配分の対象として扱うのは,単なる数字上のごまかしではない. ユーティリティは独立したファイルに収めることもできる. プログラム製作に従事しているときには,それらは私達の目を煩わせないし, 後でそのプログラムの何かを変更しないといけなくなったときにも, それらの中身が関わってくることはまずないだろう.

しかし,主要な労力配分の対象として,ユーティリティには余分に注意を払わないといけない. それは上手く書けていることが特に重要だ. 繰り返し使われるものだから,間違いや非効率な動作も繰り返されるだろう. そのデザインにも余分な注意が必要だ: 新しいユーティリティは,目前の問題だけではなく一般的な状況に対して書かなければいけない. 最後に,その他の主要な労力配分の対象と同様,慌てて書いてはいけない. 新しい何かのオペレータを生み出そうと考えているが, 別のときに必要になるかどうかよく分からないときは,それを書いてしまうこと. しかし,それを使う特定のプログラム内にまだ置いておくのだ. その後,他のプログラムでその新オペレータを使うことがあれば, それをサブルーチンからユーティリティへ昇格させて広く利用可能にすればいい.

ユーティリティfind2はよい投資だったようだ. 7行の投資をすることで即座に7行が節約できた. ユーティリティというものは,1回使うだけで元が取れる. Guy Steeleの言葉に,プログラミング言語は 「私達の持つ簡潔さへの自然な傾向と協調」しなければならない,とある.

... プログラミング構造のコストはプログラマの強いられた苦労の量に比例する, と信じがちだ (ここで「信じる」という言葉は,熱烈な確信ではなく無意識の傾向という意味で使った). 実際,プログラミング言語デザイナがこの精神的原則を心に留めておくのは 悪いことではない\note{belief}. 加算操作をコストの低いものと思う理由の一つは, それを1文字"+"で表記できることだ. あるプログラミング構造に高いコストがかかるとは思っても, それがコード書きの労力を半分にしてくれるなら, しばしばコストの低いものよりそちらが好まれる.

どのプログラミング言語でも「簡潔さへの傾向」は, それを新しいユーティリティに適応させられる柔軟性がない限り,問題の種になる. 一番短い慣用法が一番効率的なことは滅多にない. あるリストが別のリストより長いかどうか知りたいとき,素のままのLispでは

(> (length x) (length y))

と書きたくなる. ある関数を複数のリストの要素に適用したいときも,同様にリストを次のように連結したくなる:

(mapcar fn (append x y z))

こうした例から, ユーティリティはそれなしでは非効率的になってしまう状況に対して書くことが大事だと分かる. 適切なユーティリティによって補強されたプログラミング言語があれば, 一層抽象的なプログラムが書けるだろう. 更にそれらのユーティリティは,適切に定義されていれば, 効率的なプログラムを書けるよう導いてくれる.

ユーティリティ集は確実にプログラミングを簡単にしてくれる. しかしユーティリティ集の役割はそれだけではない: いいプログラムが書けるようにもしてくれる. 芸術の神は,コックと同じで,材料を目にした時点で行動に移る. だから芸術家はアトリエ内にたくさんの道具や画材を持っておきたがるのだ. 彼らは,必要なものを手元にしっかり準備しておけば,新しいことを始め易いことを知っている. 同じ現象はボトムアップ・スタイルで書かれるプログラムでも現れる. 新しいユーティリティを書くと,それを予想より多く使うことに気付くだろう. 次の章では,数種類のユーティリティ関数を説明する. それらは,どのような意味においても, あなたがLispに追加したいと思うような関数の全ての種類を代表しているわけではない. しかし,例示されたユーティリティはどれも現場で価値を証明されたものばかりだ.

リストに対する操作

元々,リストはLispの主要なデータ構造だった. 事実,"Lisp"という名前は"LISt Processing"から来ている. しかしLispがこの歴史上の事実のせいで誤解されては困る. ポロシャツがポロ専用でないのと同じく,Lispはリスト操作用に生まれたのではない. 高度な最適化を施されたCommon Lispプログラムでは,リストを全く見かけないだろう.

しかし,Lispプログラムはコンパイル時にはやはりリストだ. 高度に洗練されたLispプログラムは実行時には余りリストを使わないが, 逆にその分,コンパイル時のマクロ展開を生成するときには多くのリストを使う. だから現代のLisp方言ではリストの役割は減少したが, リストに対する操作は依然としてLispプログラムの大きな部分を占めることがある.

(proclaim '(inline last1 single append1 conc1 mklist))

(defun last1 (lst)
  (car (last lst)))

(defun single (lst)
  (and (consp lst) (not (cdr lst))))

(defun append1 (lst obj)
  (append lst (list obj)))

(defun conc1 (lst obj)
  (nconc lst (list obj)))

(defun mklist (obj)
  (if (listp obj) obj (list obj)))
\caption{リストに作用する小さな関数} \label{fig:SmallF}

第\ref{fig:SmallF}図と第\ref{fig:LargeF}図には, リストを生成したりリストに関する条件判断を行う関数を幾つか示した. 第\ref{fig:SmallF}図のものは,定義する価値のあるユーティリティの中でも最小規模のものだ. 効率性のため,それらにはみなインライン宣言をするべきだ.

1番目のlast1はリストの最後の要素を返す. 組み込み関数lastが返すのはリストの最後のコンスで,最後の要素ではない. lastを使うのは大抵(car (last ...))として最後の要素を得るためだ. そんな場合に新しいユーティリティを書く価値があるだろうか? そう,それが実質的に組み込み関数の代わりになるようなときは書く価値がある. last1はエラー・チェックをしないことに注意すること. 一般的には,この本で定義されたコードはどれもエラー・チェックをしない. これは例を簡潔にするためもあるが, 短いユーティリティ内ではとにかくエラー・チェックを一切しない方が理に適っている. もし次のようにすると

> (last1 "blub")
>>Error: "blub" is not a list.
Broken at LAST...

エラーはlast自身に捉えられる. ユーティリティが小さいときは,それが形成する抽象化の層は大変薄く,ほとんど透明だ. 薄い氷の向こうが透けて見えるように, last1のようなユーティリティの向こうは透けて見えるので, その背後の関数で起きたエラーは解釈することができる.

関数singleは引数が1個の要素を持つリストかどうかを調べる. Lispのプログラムではこれをかなり頻繁に調べなくてはならない. 最初はつい人間語からの自然な翻訳を使いがちだ:

(= (length lst) 1)

こうして調べるのはとても非効率的だ. 第1要素を見終わった直後にはもう必要な情報は分かっているからだ.

次はappend1conc1だ. 両方ともリストの末尾に新しい要素を付け加えるが,後者は破壊的だ. これらの関数は小さいが,大変頻繁に使われるので定義しておく価値はある. 実際,append1は以前のLisp方言では組み込み関数だった.

mklistも(少なくとも)Interlispでは組み込み関数だった. これは引数がリストであるかどうかを確かめる. Lispの関数の多くは,単一の値と複数の値のリストのどちらかを返すようになっている. lookupがそんな関数で, dataというリストの要素全てについてそれを呼び出した結果を集めたいとしよう. それは次のようにすれば可能だ:

(mapcan #'(lambda (d) (mklist (lookup d)))
        data)

第\ref{fig:LargeF}図にはリスト用ユーティリティの長めの例が示されている. 1番目は長いが,抽象性もさることながら効率の面から見ても有益なものだ. それは2個の連続構造(sequence)を比較し,1番目の方が長いときのみ真を返す. 2個のリストの長さを比較したいとき,つい次のようにしたくなる:

(> (length x) (length y))

この慣用法は,両方のリスト全体を探索しているので非効率だ. もし片方の方がずっと長ければ,その差の部分を探索した手間は無駄になってしまう. longerのように2個のリストを並行的に探索する方が速い.

longerの中には2個のリストの長さを比べる再帰関数が埋め込まれている. longerは長さを比べるためのものだから, その再帰関数はlengthの引数に与えられるもの全てに対して機能するべきだ. しかし並行的に長さを比較することができるのはリストに適用されたときだけなので, 内部の再帰関数は引数が両方リストだったときのみ呼び出される.

次の関数filterの性質は, find-ifに対するremove-if-notの性質と似ている.

組み込み関数remove-if-notの返り値は, find-ifに関数を渡してリストの連続したcdr部に適用したときの返り値全体と同じだ. それと似たように, filterの返り値は,ある関数がリストの連続したcdr部に対して返すものと同じだ:

> (filter #'(lambda (x) (if (numberp x) (1+ x)))
    '(a 1 2 b 3 c d 4))
(2 3 4 5)

filterは関数と1個のリストを取り, その関数がリストに適用されたときに非nil値が返されるような要素全てをリストにして返す.

filterは,第2.8節の末尾再帰関数と同様な総和変数を使っている点に注意して欲しい. 実際,末尾再帰関数を書くことの狙いは, コンパイラにfilterと同じ構造のコードを生成させることにある. filterに対しては,反復構造による直接的な定義の方が末尾再帰によるものより単純だ. filterの定義コード内でのpushnreverseとの組み合わせは, Lispでリストの総和を求める際の一般的な慣用法だ.

(defun longer (x y)
  (labels ((compare (x y)
                    (and (consp x)
                         (or (null y)
                             (compare (cdr x) (cdr y))))))
    (if (and (listp x) (listp y))
        (compare x y)
        (> (length x) (length y)))))

(defun filter (fn lst)
  (let ((acc nil))
    (dolist (x lst)
      (let ((val (funcall fn x)))
        (if val (push val acc))))
    (nreverse acc)))

(defun group (source n)
  (if (zerop n) (error "zero length"))
  (labels ((rec (source acc)
                (let ((rest (nthcdr n source)))
                  (if (consp rest)
                      (rec rest (cons (subseq source 0 n) acc))
                      (nreverse (cons source acc))))))
    (if source (rec source nil) nil)))
\caption{リストに作用する関数の大規模なもの} \label{fig:LargeF}

第\ref{fig:LargeF}図の最後の関数は, リストを新しいリストの部分リストとしてまとめるものだ. groupにリストlと数nを与えると新しいリストが返され, その中ではlの要素は長さnの部分リストにまとめられている. 余りは最後の部分リストに入る. だから第2引数に2を与えると

> (group '(a b c d e f g) 2)
((A B) (C D) (E F) (G))

という連想リストが得られる. この関数は,末尾再帰形式(第2.8節)にするためにかなり入り組んだ方法で書かれている. ラピッド・プロトタイピングの原則は,プログラム全体と同様に個々の関数にも適用できる. flattenのような関数を書くとき,可能な限り単純な実装方法から始めるのがいいだろう. そして単純なものが正しく動作すれば, 必要に応じて効率的な末尾再帰版や反復版に変えることができる. 最初のものは(十分短ければ)コメントとして残せば,交換後の関数の動作の説明になる. (groupや第\ref{fig:SmallF}図と第\ref{fig:LargeF}図内の他の関数の単純な実装は, 第vaomページ内のnoteに書かれている.)

(defun flatten (x)
  (labels ((rec (x acc)
                (cond ((null x) acc)
                      ((atom x) (cons x acc))
                      (t (rec (car x) (rec (cdr x) acc))))))
    (rec x nil)))

(defun prune (test tree)
  (labels ((rec (tree acc)
                (cond ((null tree) (nreverse acc))
                      ((consp (car tree))
                       (rec (cdr tree)
                            (cons (rec (car tree) nil) acc)))
                      (t (rec (cdr tree)
                              (if (funcall test (car tree))
                                acc
                                (cons (car tree) acc)))))))
    (rec tree nil)))
\caption{2重再帰を使ったリスト・ユーティリティ} \label{fig:Doubly-recursive}

groupの定義は最低でも1種類のエラーチェックをする点で他と異なっている: 第2引数が0であるかどうかだ. その場合,チェックをしないと無限の再帰に陥ってしまう.

この本の中の例は,ある1点で通常のLispの慣習から外れている: それぞれの章を独立させるため,コード例は可能な限り素のLispで書かれている点だ. しかしgroupは例外だ. これはマクロ定義に大変便利なので,この後の章でも数回再登場する.

第\ref{fig:LargeF}図の関数は,みなリストのトップレベル構造に沿って動作する. 第\ref{fig:Doubly-recursive}図には入れ子になったリスト内へ下っていく関数の例を2個示した. 1番目のflattenもInterlispでは組み込み関数になっている. これは引数のリストの要素であるか,要素の要素であるか,そのまた要素の... といった全てのアトムのリストを返す.

> (flatten '(a (b c) ((d e) f)))
(A B C D E F)

第\ref{fig:Doubly-recursive}図の2番目の関数pruneistoremove-ifとの関係は copy-treecopy-listとの関係と似ている. つまり,再帰的に部分リスト内へ下っていく:

> (prune #'evenp '(1 2 (3 (4 5) 6) 7 8 (9)))
(1 (3 (5)) 7 (9))

引数として与えた関数が真を返す葉は全て除かれる.

検索

この章では,リストを検索する関数の例を幾つか与える. Common Lispにはそのための組み込みオペレータが豊富にあるが, それでも困難な ---少なくとも効率的に実行するのは困難な--- 課題はある. このことは第pumpページで説明した仮想的な状況の中で既に見た\note{HypotheticalCase}. 第\ref{fig:SearchLists}図の1番目の関数find2は,それへの回答として作られたものだ.

(defun find2 (fn lst)
  (if (null lst)
    nil
    (let ((val (funcall fn (car lst))))
      (if val
          (values (car lst) val)
          (find2 fn (cdr lst))))))

(defun before (x y lst &key (test #'eql))
  (and lst
       (let ((first (car lst)))
         (cond ((funcall test y first) nil)
               ((funcall test x first) lst)
               (t (before x y (cdr lst) :test test))))))

(defun after (x y lst &key (test #'eql))
  (let ((rest (before y x lst :test test)))
    (and rest (member x rest :test test))))

(defun duplicate (obj lst &key (test #'eql))
  (member obj (cdr (member obj lst :test test))
          :test test))

(defun split-if (fn lst)
  (let ((acc nil))
    (do ((src lst (cdr src)))
      ((or (null src) (funcall fn (car src)))
       (values (nreverse acc) src))
      (push (car src) acc))))
\caption{リストを検索する関数} \label{fig:SearchLists}

次のユーティリティbeforeは似た意図を持って書かれた. これはあるオブジェクトがリスト内で別のオブジェクトよりも先に現れるかどうかを調べる:

> (before 'a 'b '(a b c d))
(B C D)

これを素のLispを使って愚直に調べることも十分簡単だ:

(< (position 'a '(a b c d)) (position 'b '(a b c d)))

しかしこの慣用法は非効率だし,エラーにつながり易い. 非効率な理由は,この関数は本当は両方のオブジェクトを見つける必要はなく, 先に現れるものだけを見つければいいからだ. またエラーにつながるというのは,オブジェクトがどちらもリスト内にないとき, nilが < に引数として渡されてしまうからだ. beforeを使えば両方の問題が解決する.

beforeの精神は集合への所属関係を調べることに似ているので, 組み込み関数memberに似せて書かれた. memberと同様に比較関数(デフォルトではeql)をオプショナル引数として取る. また,ただtを返すだけでなく, 第1引数で与えられたオブジェクトで始まるcdr部という,有益な情報を含んだ値を返す:

beforeが真を返すのは, 第2引数を見つける前に第1引数を見つけたときだということに注意. そのため,第2引数がリスト内に存在しないときには真が返される:

> (before 'a 'b '(a))
(A)

もっと精密に調べるには,after (引数が両方リスト内に存在しないと真を返さない)を使う:

> (after 'a 'b '(b a d))
(A D)
> (after 'a 'b '(a))
NIL

(member o l)がリストl内にoを見つけたとき, ただのtでなくoで始まるlのcdr部を返す. この返り値は,例えば重複して存在するオブジェクトを調べるために使える. l内にoが重複して存在していると, それはmemberの返したリストのcdr部内にも存在する. この慣用法は次のユーティリティduplicate内に埋め込まれている:

> (duplicate 'a '(a b c a d))
(A D)

重複を調べるユーティリティは同じ原則に基づいて他にも定義できる. 潔癖性のプログラミング言語デザイナは, Common Lispでは「偽」と「空リスト」の両方をnilで表すことに衝撃を受ける. 確かにそれが問題を起こすこともある(第14.2章を参照)が, duplicate等の関数では便利だ. 連続構造の包含関係を問うとき, 偽であることを空の連続構造として表現するのは自然に思える. 第\ref{fig:SearchLists}図の最後の関数も,memberの一般化の一種だ. memberは,それが発見した要素から始まるリストのcdr部を返すのに対し, split-ifは元のリストの前半分もあわせて返す. このユーティリティは,主に何かの順番で整列されたリストに対して使われる:

> (split-if #'(lambda (x) (> x 4))
            '(1 2 3 4 5 6 7 8 9 10))
(1 2 3 4)
(5 6 7 8 9 10)
(defun most (fn lst)
  (if (null lst)
      (values nil nil)
      (let* ((wins (car lst))
             (max (funcall fn wins)))
        (dolist (obj (cdr lst))
          (let ((score (funcall fn obj)))
            (when (> score max)
              (setq wins obj
                    max score))))
        (values wins max))))

(defun best (fn lst)
  (if (null lst)
      nil
      (let ((wins (car lst)))
        (dolist (obj (cdr lst))
          (if (funcall fn obj wins)
              (setq wins obj)))
        wins)))

(defun mostn (fn lst)
  (if (null lst)
      (values nil nil)
      (let ((result (list (car lst)))
            (max (funcall fn (car lst))))
        (dolist (obj (cdr lst))
          (let ((score (funcall fn obj)))
            (cond ((> score max)
                   (setq max score
                         result (list obj)))
                  ((= score max)
                   (push obj result)))))
        (values (nreverse result) max))))
\caption{要素を比較する検索関数} \label{fig:CompareElements}

第\ref{fig:CompareElements}には別の種類の検索関数が載っている: 要素同士を比較する関数だ. 最初のmostは要素を1度に1個ずつ調べる. これはリストと点数付け関数を引数に取り,最高点を与える要素を返す. 等しい点を与える要素があったときは,リスト内で最初に現れたものを返す.

> (most #'length '((a b) (a b c) (a) (e f g)))
(A B C)
3

mostは返した要素の与えた(最高)点も返す(その方が便利だ).

もっと一般的な種類の検索にはbestを使う. このユーティリティも関数とリストを引数に取るが, これに使う関数は2個の引数を取る述語でなければいけない. 返り値は1個の要素で,述語がその他の要素全てに対して勝っていると判断するものだ.

> (best #'> '(1 2 3 4 5))
5

bestsortの結果のcar部と見ることもできるが, こちらの方がずっと効率がいい. リスト内の要素に完全な順位を定義する述語を提供するかどうかは呼び出し側次第だ. そうでなければ要素の並び順は結果に影響し, mostと同様,等しい点が出たときには最初の要素が返される.

最後のmostnは点数付け関数とリストを引数に取り, 関数が最高点を付ける要素全てから成るリスト(と最高点)を返す:

> (mostn #'length '((a b) (a b c) (a) (e f g)))
((A B C) (E F G))
3

対応付け

広く使われるLispの関数の種類には,他に対応付け関数 ---ある関数を複数の引数に適用するもの--- がある. 第\ref{fig:Mapping1}, \ref{fig:Mapping2}図には新しい対応付け関数の例を示した. 最初の3個は関数をある範囲の数に(それらの数を含むリストをコンシングせずに) 適用するためのものだ. 最初の2個,map0-nmap1-nは,正の整数の範囲で動作する:

> (map0-n #'1+ 5)
(1 2 3 4 5 6)

両方ともさらに一般的なmapa-b(任意の範囲の数に対して動作する) を使って定義されている.

> (mapa-b #'1+ -2 0 .5)
(-1 -0.5 0.0 0.5 1.0)

mapa-bの次はさらに一般的なmap->で, これは任意のオブジェクトの連続構造に対して機能する. 連続構造は第2引数で与えられたオブジェクトから始まり, 第3引数で与えられたオブジェクトで終わって, その間のオブジェクトは第4引数で与えられた関数によって生成される. map->を使うと,数の連続への操作と同様に,任意のデータ構造を扱うことが可能だ. mapa-bmap->を使うと次のように定義できる:

(defun mapa-b (fn a b &optional (step 1))
  (map-> fn
         a
         #'(lambda (x) (> x b))
         #'(lambda (x) (+ x step))))

組み込み関数mapcanは効率のために破壊的関数として作られている. それは次のようにして定義できる:

(defun our-mapcan (fn &rest lsts)
  (apply #'nconc (apply #'mapcar fn lsts)))

mapcannconcを使ってリストをつなぎ合わせているので, 第1引数によって返されるリストは新しく作られたものの方がいい. そうしないと次にそのリストを使うときには変更を受けていることだろう. nicknames(doveページ)が, 愛称の「リストを生成する」関数として定義されたのはそういった理由による. それがただどこかに保持されたリストを返すだけなら, mapcanを使うのは安全でなくなるだろう. 代わりに,返されたリストをつなぎ合わせるのにはappendを使わなければならなくなる. そのような場合のため,mappendは「非破壊的なmapcan」を提供する.

次のユーティリティmapcarsが使われるのは, mapcarで関数を適用したいリストが複数あるときだ. ここで数のリストが2個あり,両方のリストの要素の平方根から成る1個のリストが欲しいとしよう. 素のLispを使って

(mapcar #'sqrt (append list1 list2))

とすれば実現できるが,そうすると不必要なコンシングが行われている. list1list2とをつなぎ合わせても,その結果はすぐに捨てられてしまう. mapcarsを使うと

(mapcars #'sqrt list1 list2)

によって同じ結果が得られ,不必要なコンシングは行われていない.

(defun map0-n (fn n)
  (mapa-b fn 0 n))

(defun map1-n (fn n)
(mapa-b fn 1 n))

(defun mapa-b (fn a b &optional (step 1))
  (do ((i a (+ i step))
       (result nil))
    ((> i b) (nreverse result))
    (push (funcall fn i) result)))

(defun map-> (fn start test-fn succ-fn)
  (do ((i start (funcall succ-fn i))
       (result nil))
    ((funcall test-fn i) (nreverse result))
    (push (funcall fn i) result)))
\caption{対応付け関数1} \label{fig:Mapping1}
(defun mappend (fn &rest lsts)
  (apply #'append (apply #'mapcar fn lsts)))

(defun mapcars (fn &rest lsts)
  (let ((result nil))
    (dolist (lst lsts)
      (dolist (obj lst)
        (push (funcall fn obj) result)))
    (nreverse result)))

(defun rmapcar (fn &rest args)
  (if (some #'atom args)
      (apply fn args)
      (apply #'mapcar
             #'(lambda (&rest args)
                 (apply #'rmapcar fn args))
             args)))
\caption{対応付け関数2} \label{fig:Mapping2}

第\ref{fig:Mapping2}図の最後の関数は,mapcarのツリー対応版だ. rmapcarという名前は``recursive(再帰的) mapcar''の省略で, これはmapcarが単層リストに対して行う操作をツリーに対して行う:

> (rmapcar #'princ '(1 2 (3 4 (5) 6) 7 (8 9)))
123456789
(1 2 (3 4 (5) 6) 7 (8 9))

これはmapcarと同様,複数のリストを引数に取れる.

> (rmapcar #'+ '(1 (2 (3) 4)) '(10 (20 (30) 40)))
(11 (22 (33) 44))

この後で登場する関数のうち幾つか(第prepページのrep等)は, 本当はrmapcarを使うべきものだ.

伝統的なリストの対応付け関数は,CLtL2で導入された数列マクロにより, 時代遅れなものとしてある程度置き換えられた. 例えば

(mapa-b #'fn a b c)

は次のように変えることができる:

(collect (#Mfn (scan-range :from a :upto b :by c)))

しかし対応付け関数への需要はまだある. 場合によっては対応付け関数の方が明確でエレガントなことがある. map->で表現できるものも数列では表現し辛いこともある. 最後に,対応付け関数は引数として渡すことができる(関数としての性質).

入出力

(defun readlist (&rest args)
  (values (read-from-string
            (concatenate 'string "("
                         (apply #'read-line args)
                         ")"))))

(defun prompt (&rest args)
  (apply #'format *query-io* args)
  (read *query-io*))

(defun break-loop (fn quit &rest args)
  (format *query-io* "Entering break-loop.~%")
  (loop
    (let ((in (apply #'prompt args)))
      (if (funcall quit in)
          (return)
          (format *query-io* "~A~%" (funcall fn in))))))
\caption{入出力関数} \label{fig:IO}

第\ref{fig:IO}図ではI/Oユーティリティの例を3個示した. この種のユーティリティへの需要はプログラム毎にまちまちだ. 第\ref{fig:IO}図のものは代表的な例に過ぎない. 1番目のものはプログラムのユーザに括弧なしで式を入力させたいときに使う. これは1行分の入力を読み取り,それをリストとして返す:

> (readlist)
Call me "Ed"
(CALL ME "Ed")

valuesを呼び出すことで返り値を1個に限定している (read-from-string自身,ここでは無駄な第2値を返す).

関数promptは質問の表示と回答の読み取りを統合したものだ. これはformatに対する引数と同じもの (ただしストリーム指定用の第1引数以外)を引数に取る.

> (prompt "Enter a number between ~A and ~A.~%>> " 1 10)
Enter a number between 1 and 10.
>> 3
3

最後のbreak-loopを使うのはLispのトップレベルを真似たいときだ. これは引数に2個の関数とレスト引数(プロンプトとして繰り返し渡される)を取る. 2番目の関数が入力に対して偽を返す限り,1番目の関数が入力に適用される. だから,例えば実際のLispのトップレベルは次のように模倣できる:

> (break-loop #'eval #'(lambda (x) (eq x :q)) ">> ")

するとbreak-loopの中に入る.

>> (+ 2 3)
5
>> :q
:Q

ところで,Common Lispのヴェンダが一般的に実行時ライセンスを主張するのはこれが理由だ. 実行時にevalを呼べば,任意のLispプログラムがLisp自身を包含できる.

シンボルとストリング

シンボルとストリングは大変近い関係にある. 表示関数と読み取り関数の手段として,二つの表現は混用できる. 第\ref{fig:SymbolsAndStrings}図にはこの境界で動作するユーティリティの例を示した. 最初のmkstrは任意の数の引数を取り, それらの印字表現を連結してストリングとして返す:

> (mkstr pi " pieces of " 'pi)
"3.141592653589793 pieces of PI"

symbはそれに基づいて作られたもので,主にシンボルの生成に使われる. これは1個以上の引数を取り,その印字名を連結したものを印字名とするシンボルを (必要ならば新しく生成して)返す. これは印字表現を持つ任意のオブジェクト ---シンボル,ストリング,数,さらにリストまで--- を引数に取れる.

> (symb 'ar "Madi" #\L #\L 0)
|ARMadiLL0|

mkstrを呼んで引数をみな1個のストリングに連結した後, symbはそれをinternに送る. これはLispの伝統的なシンボル生成用関数で, ストリングを引数に取り,そのストリングで表示されるシンボルを返すか,新しく生成する. 任意のストリングが(小文字や,括弧などのマクロ文字を含むものでも) シンボルの印字名として使える. シンボルの名前にそういった変わった文字が使われているときは, 名前は上のように縦棒に挟まれて表示される. ソースコードでは,そういったシンボルは縦棒の間にあるか, "\"が文字の前に付いていなければいけない:

> (let ((s (symb '(a b))))
(and (eq s '|(A B)|) (eq s '\(A\ B\))))
T

次の関数rereadは,symbの一般形だ. オブジェクトの列を引数に取り,それらを表示し,再び読み込む. これはsymbと同様にシンボルを返せるが, 他にもreadが返せるものなら何でも返せる. リードマクロはシンボルの名前の一部としては扱われず,対応する関数が呼び出される. またa:bはカレント・パッケージの|a:b|というシンボルではなく, パッケージa内のシンボルbとして読み込まれる \footnote{パッケージの紹介は,powページから始まる付章を参照.}. 一般的な関数は几帳面でもある: rereadは,引数が正しいLisp文法に従っていないとエラーを発生する.

(defun mkstr (&rest args)
  (with-output-to-string (s)
    (dolist (a args) (princ a s))))

(defun symb (&rest args)
  (values (intern (apply #'mkstr args))))

(defun reread (&rest args)
  (values (read-from-string (apply #'mkstr args))))

(defun explode (sym)
  (map 'list #'(lambda (c)
                 (intern (make-string 1
                                      :initial-element c)))
       (symbol-name sym)))
\caption{シンボルとストリングに作用する関数} \label{fig:SymbolsAndStrings}

第\ref{fig:SymbolsAndStrings}図の最後の関数は,昔の幾つかの方言では組み込み関数だった: explodeはシンボルを引数に取り, そのシンボルの名前に使われている文字から作られるシンボルから成るリストを返す.

> (explode 'bomb)
(B O M B)

この関数がCommon Lispに含まれなかったのは偶々という訳ではない. シンボルを分解したいようなときには,おそらく非効率的な作業をしているのだ. しかし製品にするソフトウェアでなくてその原型の中なら, この類のユーティリティを使う余地はある.

密度

コード内に多くの新ユーティリティを使うと,理解し辛いと言ってくる人がいる. Lispをまだ使いこなせない人は素のLispしか読みとれない. そういう人は拡張可能なプログラミング言語という考えが全く身に付いていないのだ. そういう人がユーティリティをふんだんに使ったプログラムを目にすると, その作者は全く変人で, プログラムを一種の個人用プログラミング言語で書くことに決めてしまったと思うことだろう.

それらの新オペレータは,どれも(議論の余地はあるが)プログラムを読み辛くしてしまう. プログラムを読み取れるようになる前に,それらのユーティリティを全て理解しなければいけない. こういった言明がなぜ誤解されるのかについては, popページで説明した例(一番近い書店を探した例)のことを考えてみて欲しい. そのプログラムをfind2を使って書けば, 「プログラムを読み取れるようになる前に, この新ユーティリティの定義を理解しなければいけないじゃないか.」 と不満を言う人が出てくる. それでは,find2を使わなかったとしてみよう. するとfind2の定義は理解しなくてもいいが, find-booksの定義を理解しなければいけない. その中ではfind2の仕事が「書店を見つける」という個別の課題と混ざっている. find2を理解するのはせいぜいfind-booksと同じくらい難しいだけだ. また,ここでは新ユーティリティは1回しか使っていない. ユーティリティは繰り返し使うよう意図されたものだ. 実際のプログラムでは,find2を理解しなければいけないか, または3, 4個の特定目的の検索ルーチンを理解しなければいけないかの,どちらかの選択だろう. 前者の方が確実に簡単だ.

そう,ボトムアップ形式のプログラムを読み取るには, 作者の定義した新ユーティリティを全て理解しなければいけない. しかしこれにかかる労力は, ユーティリティなしの場合に必要なコードを理解しなければならないときの労力よりは, ほとんど常に少ないだろう. ユーティリティを使うとコードが読み辛くなると言う人がいたとすれば, その人達はユーティリティを使わないとコードがどんなものになるか理解していないのだろう. ボトムアップ・プログラミングは,それなしでは巨大なプログラムになった筈のものを, 小さくて単純なプログラムに見えるように変えてくれる. こうするとそのプログラムは大した量の処理を行っていないとの印象を与え, そのため理解が簡単になる筈だ. Lispに未熟な人がコードをよく見て,実際はかなりの処理を行っていることに気付くと, 狼狽するのだ.

同じ現象は別の分野でも発見できる: 上手に設計された機械の部品は少ないが,より複雑に見える. それは部品が狭い空間に詰め込まれているからだ. ボトムアップ形式のプログラムは概念の密度が高い. それは読み取るのに労力が必要かもしれないが, それはプログラムがボトムアップ形式で書かれていなかったときに 必要になった筈の労力程ではない. 慎重に考えた上でユーティリティの使用を避けた方がいい場合が一つある: コードの大部分とは独立して配布する小さなプログラムを書かなければいけないときだ. ユーティリティというものは通常2, 3回使って始めて元が取れるものだが, 小規模なプログラムではユーティリティを含める意味がある程には使えないことがある.


←: 関数的プログラミング     ↑: On Lisp     →: 返り値としての関数

Copyright (c) 2003-2011 野田 開     NODA Kai <nodakai@gmail.com>