独学Common Lisp

再帰とループ、計算機の醍醐味

繰り返しのスタイル

計算機による計算にとって条件分岐とともに重要な仕組みが繰り返しです。計算機はとても処理が高速なので、似たような処理を何回も実行してもらうのに都合がいいのです。多くのプログラミング言語では重要なオペレータとして様々な繰り返し命令が実装されています。

Common Lispは歴史的に繰り返しを行う根源的なオペレータを持っていません。その理由の一つは「マクロ」があるので繰り返しを行うマクロを自分で作れるからということであり、もう一つは「再帰」によって繰り返しが実現できるからということです。このページではその両方を示します。

再帰的定義

通常、国語辞典を引いて語彙を調べると、その言葉以外の言葉で説明されているはずです。しかし、調べたいその言葉を使って説明した方が、より簡潔に表現できる場合があります。例えば、「二進法における数」はどのように定義できるでしょうか。数学的帰納法のような方法で定義してみると、下のようになります。

まず、0は二進法における数です。次に、1も二進数における数です。そして、二進法における数を<binary>と表記することにします。すると、二進法における全ての数は次の形で定義できます。

<binary> ::= 0
           | 1
           | 0 <binary>
           | 1 <binary>

|は「または」を表しますので、この定義を言葉で表すと、「'二進法における数'は、0、または1、または最初が0で残りが'二進法における数'であるもの、または最初が1で残りが'二進法における数'であるもののいずれかである」となります。例えば11011はこの条件に合致するでしょうか。

11011 -> 1 1011
      -> 1 1 011
      -> 1 1 0 11
      -> 1 1 0 1 1
      -> 1 1 0 1 <binary>
      -> 1 1 0 <binary>
      -> 1 1 <binary>
      -> 1 <binary>
      -> <binary>

定義に定義対象の言葉自身が含まれているので、定義式に沿って分解しつつ全て定義に合致することが確認できた時点で、11011<binary>であると分かります。しかし、この定義に曖昧さはなく、2以上の数や小数点が混じっていると定義に合致しないので<binary>ではないと判断されます。

このように自分自身を使って定義を行うことを「再帰的定義」と呼びます。再帰的定義には必ず終了条件が必要であり、今回であれば0または1だけになった時点で定義の探索が反転して戻っていくことが分かります。

再帰的定義が用いられるのは、簡潔かつ明瞭に表すことができるからです。ややこしいように見えるかもしれませんが、実は論理的な計算機にとっては「二進法における数」をたった4つの条件で表現できる再帰的定義はとても明瞭なのです。

再帰的定義の対極に位置する定義は繰り返しによる定義です。例えば、1回以上の繰り返し記号として+を導入すると、<binary>は以下のように定義できます。

<binary> ::= (0 | 1)+

しかし、そもそも繰り返し記号である+自体は計算機にはただの記号(シンボル)であり、その意味を明確に定義できなければ結局<binary>も定義できません。「1回以上の繰り返し」ということをそもそも計算機がネイティブに理解できない限り、再帰的定義よりも簡潔かつ明瞭に定義することができません。再帰的定義は、再帰的定義を認めるだけでサポートされます。なぜなら再帰的な評価を繰り返しながら定義に合致するかどうかをリアルタイムに判定することができるからです。事前の100%の定義を行わない代わりに、結果として100%の定義を簡潔かつ明瞭に与えることができます。

再帰関数

前節で述べた通り、再帰的な定義はリアルタイムな判定に向いています。もし全てのバイナリが8桁だと分かっていたら、最初から簡潔かつ明瞭な定義ができます。何桁か分からないからこそ再帰的定義が生きてきます。

また、前節の例を見て気づいた方がいるかもしれませんが、実は再帰的定義はリストのcarcdrととても相性がいいのです。再帰が行っているのは、carを判定してcdrを次の判定対象として渡し、振り出しに戻ることです。

例えば、「次のリストの要素の数を数えよ」という問題に対してどう対処するでしょうか。

(defvar data '(a b (c d) (e (f (((g h) i) j) k) l) m))

アルファベットは13個ありますから欲しい答えは13です。しかし、組み込みのlengthは期待の答えを返してくれません。

(length data)
; => 5

この5という数は'a, 'b, '(c d), '(e (f (((g h) i) j) k) l), 'mという5つの要素を示しています。問題は要素がリストであるときもその中の探索に入らず、リスト全体で1つとカウントしていることです。

試しに自分でlengthを自分で定義してみましょう。

(defun my-length (list &optional n)
  (cond ((null n) (my-length list 0))
        ((null list) n)
        (t (my-length (cdr list) (1+ n)))))

(my-length data)
; => 5

この&optionalの使い方は推奨されません。初期値として第二引数を与えると実際の要素数ではない数が得られてしまいます。この防ぎ方はあとで述べますが、ここでは関数の定義にのみ注目してください。

最初は&optionalな引数nが与えられないことを想定していますので、0を付加して自分自身を呼び出しています。次のcondの条件は終了条件で、nullは空リストであるかどうかを判定します。nは要素数を保持する引数として利用します。

最後の条件式がカウント用で、リストのcdrを取り出して、さらにnに1を足して自分自身を呼び出しています。

再帰的な定義において最も重要なのは、「終了条件が存在すること」と「終了条件に向かって進行すること」です。リストをcdrしていくと要素数が減りますから、終了条件に向かって進行していきます。

今回の場合、carで取り出したものがaでも(c d)でも同じように1でカウントされますが、問題に答えるためにはこの2つを区別しなければなりません。そして、(c d)の時には(c d)の要素数を数えて、1+ではなく2を加算して((+ n 2))から計算を続ける必要があります。

つまり、改変の必要があるのは2点です。

  1. carで取り出した部分がリストである場合の条件分岐を増やす
  2. 1の場合には取り出したリストの要素数を数える処理に移ってから、その答えを加算する

逆に言うと、carで取り出した部分がaのような値であれば今まで通りで構いません。aのように単体の分割できないデータを「アトム」と言い、atomと言う述語で判定することができます。

これらの点を踏まえ、my-lengthを改良してみます。

(defun my-length* (list &optional n)
  (cond ((null n) (my-length* list 0))
        ((null list) n)
        ((atom (car list))
         (my-length* (cdr list) (1+ n)))
        (t
         (my-length* (cdr list) (+ n (my-length* (car list)))))))

(my-length* data)
; => 13

言葉で説明したことをソースコードにしました。atomを使って条件分岐を増やし、こちらで今まで通りの処理を記述しました。最後のtにはcarで取り出した部分がアトムではない場合、つまりリストかコンスセルの場合に適用されます。そしてその時は1+ではなく、加算すべき値を探索する新しいmy-length*に突入するように変更しました。

Common Lispには関数の動きをキャッチできる便利なtraceという機能があります。Clozure CLを使っている場合は1行だけ関数に追記してから、(trace my-length*)を実行した後で関数を適用してみてください。

(defun my-length* (list &optional n)
  (declare (notinline my-length*))
  (cond ((null n) (my-length* list 0))
        ((null list) n)
        ((atom (car list))
         (my-length* (cdr list) (1+ n)))
        (t
         (my-length* (cdr list) (+ n (my-length* (car list)))))))

(trace my-length*)
(my-length* data)

declareの行を追加してください。Clozure CLでは何も指定しないと最適化が行われるのでトレースができません。これを追加して関数をトレースすると、以下のように表示されるはずです。

0> Calling (MY-LENGTH* (A B (C D) (E (F (((G H) I) J) K) L) M))
 1> Calling (MY-LENGTH* (A B (C D) (E (F (((G H) I) J) K) L) M) 0)
  2> Calling (MY-LENGTH* (B (C D) (E (F (((G H) I) J) K) L) M) 1)
   3> Calling (MY-LENGTH* ((C D) (E (F (((G H) I) J) K) L) M) 2)
    4> Calling (MY-LENGTH* (C D))
     5> Calling (MY-LENGTH* (C D) 0)
      6> Calling (MY-LENGTH* (D) 1)
       7> Calling (MY-LENGTH* NIL 2)
       <7 MY-LENGTH* returned 2
      <6 MY-LENGTH* returned 2
     <5 MY-LENGTH* returned 2
    <4 MY-LENGTH* returned 2
    4> Calling (MY-LENGTH* ((E (F (((G H) I) J) K) L) M) 4)
     5> Calling (MY-LENGTH* (E (F (((G H) I) J) K) L))
      6> Calling (MY-LENGTH* (E (F (((G H) I) J) K) L) 0)
       7> Calling (MY-LENGTH* ((F (((G H) I) J) K) L) 1)
        8> Calling (MY-LENGTH* (F (((G H) I) J) K))
         9> Calling (MY-LENGTH* (F (((G H) I) J) K) 0)
          10> Calling (MY-LENGTH* ((((G H) I) J) K) 1)
           11> Calling (MY-LENGTH* (((G H) I) J))
            12> Calling (MY-LENGTH* (((G H) I) J) 0)
             13> Calling (MY-LENGTH* ((G H) I))
              14> Calling (MY-LENGTH* ((G H) I) 0)
               15> Calling (MY-LENGTH* (G H))
                16> Calling (MY-LENGTH* (G H) 0)
                 17> Calling (MY-LENGTH* (H) 1)
                  18> Calling (MY-LENGTH* NIL 2)
                  <18 MY-LENGTH* returned 2
                 <17 MY-LENGTH* returned 2
                <16 MY-LENGTH* returned 2
               <15 MY-LENGTH* returned 2
               15> Calling (MY-LENGTH* (I) 2)
                16> Calling (MY-LENGTH* NIL 3)
                <16 MY-LENGTH* returned 3
               <15 MY-LENGTH* returned 3
              <14 MY-LENGTH* returned 3
             <13 MY-LENGTH* returned 3
             13> Calling (MY-LENGTH* (J) 3)
              14> Calling (MY-LENGTH* NIL 4)
              <14 MY-LENGTH* returned 4
             <13 MY-LENGTH* returned 4
            <12 MY-LENGTH* returned 4
           <11 MY-LENGTH* returned 4
           11> Calling (MY-LENGTH* (K) 5)
            12> Calling (MY-LENGTH* NIL 6)
            <12 MY-LENGTH* returned 6
           <11 MY-LENGTH* returned 6
          <10 MY-LENGTH* returned 6
         <9 MY-LENGTH* returned 6
        <8 MY-LENGTH* returned 6
        8> Calling (MY-LENGTH* (L) 7)
         9> Calling (MY-LENGTH* NIL 8)
         <9 MY-LENGTH* returned 8
        <8 MY-LENGTH* returned 8
       <7 MY-LENGTH* returned 8
      <6 MY-LENGTH* returned 8
     <5 MY-LENGTH* returned 8
     5> Calling (MY-LENGTH* (M) 12)
      6> Calling (MY-LENGTH* NIL 13)
      <6 MY-LENGTH* returned 13
     <5 MY-LENGTH* returned 13
    <4 MY-LENGTH* returned 13
   <3 MY-LENGTH* returned 13
  <2 MY-LENGTH* returned 13
 <1 MY-LENGTH* returned 13
<0 MY-LENGTH* returned 13

これは関数が呼び出される様子と、呼び出されたところへ戻っていく様子を示しています。その様子は一直線ではなく、行ったり来ているように見えると思います。これは、carがリストだった時にその探索に入るので、一段深いところに関数が潜り込んで行くとともに、そのcarの計算が終わったら一旦元に戻るので関数が行ったり来たりしています。

このトレース結果は計算機による「探索」そのものです。与えられた条件に従って計算機が自らの判断で深いリストの探索に潜り込んでいることが分かります。このmy-length*を再帰を用いずに表現することはとても難しいでしょう。なぜなら、深く潜るその階層分だけ新しいループが必要ですが、事前にそのループが何層・何回分になるのかがわからないので、リアルタイムにループを構築する手続きが必要だからです。

末尾呼出しと最適化

実は、前節の再帰関数はより効率化することができます。

前節の再帰関数に非効率な点があるとすれば、関数が「戻る」ことです。関数が戻るのは当然だと思う人もいると思いますが、関数は必ずしも戻る必要はありません。関数が戻る(返り値を返す)べきなのは、戻った後で計算が残っている時だけです。今回の場合、関数my-length*の返り値にnを加算して探索を続けるので、関数は戻らなければなりません。

しかし、関数が戻った後に計算が残っていなければ、関数は戻る必要がありません。「関数が戻った後の計算」を「継続(continuation)」と呼びますが、今回のように深い探索に入る関数はこの継続が「成長」します。つまり、戻った後に計算すべきものがどんどんと増えていくのです。

再帰関数は「継続が成長しない」ように書き換えることができます。つまり、何も計算すべきものを残さずに再帰させると、関数が戻った時の処理はただ「戻って来た値を呼び出した関数に戻すこと」が「継続」になります。戻って来た値を返すだけなら、最後の計算が終わった時にその値を一気に最初の呼び出し元まで返してしまえば、結果的に「継続が成長しない」状態にすることができます。

まとめると、効率化は2つの処理を行うことになります。

  1. 関数を呼び出した後、戻って来た時に何も残りの計算がないようにする
  2. 1の状態から呼び出された時、関数の返り値を呼出し元の呼出し元にまで一気に返す

1を「末尾呼出し」と呼び、2を「末尾呼出しの最適化」と呼びます。2は自分では対応できず、コンパイラが対応している必要がありますが、Common Lispの主要な処理系は対応しています。1は自分で関数を書き換える必要があります。

長々と説明して来たのには訳があり、効率化のためには再帰の簡潔さを犠牲にしなければならないのです。以下に、末尾呼出しに対応したソースコードを提示します。

(defun my-length+ (list &optional n rest)
  (declare (notinline my-length+))
  (cond ((null n) (my-length+ (car list) 1 (cdr list)))
        ((null rest) n)
        ((null list)
          (my-length+ (car rest) n (cdr rest)))
        ((atom list)
          (my-length+ (car rest) (1+ n) (cdr rest)))
        (t
          (my-length+ (car list) n (cons (cdr list) rest)))))

引数を一つ追加しました。これは、残りの計算、今回は要素を数えるべき残りのリストを保持する引数です。条件分岐も変更しました。初期条件は、リストをcarcdrに分割して計算を始めるようにしました。この変更に伴い、cdr(rest)が空リストになることを終了条件にしました。carが空リストになった時は、restからcarを取り出してそちらの計算に移るようにしています。取り出したcarがリストの場合をキャッチするのが最後の条件判定で、car(list)のcdrrestにくっつけて残りの計算を構築しています。

この変更に伴い、関数は直線的に動作するようになりました。同じようにトレースしてみます。

0> Calling (MY-LENGTH+ (A B (C D) (E (F (((G H) I) J) K) L) M)) 
 1> Calling (MY-LENGTH+ A 1 (B (C D) (E (F (((G H) I) J) K) L) M)) 
  2> Calling (MY-LENGTH+ B 2 ((C D) (E (F (((G H) I) J) K) L) M)) 
   3> Calling (MY-LENGTH+ (C D) 3 ((E (F (((G H) I) J) K) L) M)) 
    4> Calling (MY-LENGTH+ C 3 ((D) (E (F (((G H) I) J) K) L) M)) 
     5> Calling (MY-LENGTH+ (D) 4 ((E (F (((G H) I) J) K) L) M)) 
      6> Calling (MY-LENGTH+ D 4 (NIL (E (F (((G H) I) J) K) L) M)) 
       7> Calling (MY-LENGTH+ NIL 5 ((E (F (((G H) I) J) K) L) M)) 
        8> Calling (MY-LENGTH+ (E (F (((G H) I) J) K) L) 5 (M)) 
         9> Calling (MY-LENGTH+ E 5 (((F (((G H) I) J) K) L) M)) 
          10> Calling (MY-LENGTH+ ((F (((G H) I) J) K) L) 6 (M)) 
           11> Calling (MY-LENGTH+ (F (((G H) I) J) K) 6 ((L) M)) 
            12> Calling (MY-LENGTH+ F 6 (((((G H) I) J) K) (L) M)) 
             13> Calling (MY-LENGTH+ ((((G H) I) J) K) 7 ((L) M)) 
              14> Calling (MY-LENGTH+ (((G H) I) J) 7 ((K) (L) M)) 
               15> Calling (MY-LENGTH+ ((G H) I) 7 ((J) (K) (L) M)) 
                16> Calling (MY-LENGTH+ (G H) 7 ((I) (J) (K) (L) M)) 
                 17> Calling (MY-LENGTH+ G 7 ((H) (I) (J) (K) (L) M)) 
                  18> Calling (MY-LENGTH+ (H) 8 ((I) (J) (K) (L) M)) 
                   19> Calling (MY-LENGTH+ H 8 (NIL (I) (J) (K) (L) M)) 
                    20> Calling (MY-LENGTH+ NIL 9 ((I) (J) (K) (L) M)) 
                     21> Calling (MY-LENGTH+ (I) 9 ((J) (K) (L) M)) 
                      22> Calling (MY-LENGTH+ I 9 (NIL (J) (K) (L) M)) 
                       23> Calling (MY-LENGTH+ NIL 10 ((J) (K) (L) M)) 
                        24> Calling (MY-LENGTH+ (J) 10 ((K) (L) M)) 
                         25> Calling (MY-LENGTH+ J 10 (NIL (K) (L) M)) 
                          26> Calling (MY-LENGTH+ NIL 11 ((K) (L) M)) 
                           27> Calling (MY-LENGTH+ (K) 11 ((L) M)) 
                            28> Calling (MY-LENGTH+ K 11 (NIL (L) M)) 
                             29> Calling (MY-LENGTH+ NIL 12 ((L) M)) 
                              30> Calling (MY-LENGTH+ (L) 12 (M)) 
                               31> Calling (MY-LENGTH+ L 12 (NIL M)) 
                                32> Calling (MY-LENGTH+ NIL 13 (M)) 
                                 33> Calling (MY-LENGTH+ M 13 NIL) 
                                 <33 MY-LENGTH+ returned 13
                                <32 MY-LENGTH+ returned 13
                               <31 MY-LENGTH+ returned 13
                              <30 MY-LENGTH+ returned 13
                             <29 MY-LENGTH+ returned 13
                            <28 MY-LENGTH+ returned 13
                           <27 MY-LENGTH+ returned 13
                          <26 MY-LENGTH+ returned 13
                         <25 MY-LENGTH+ returned 13
                        <24 MY-LENGTH+ returned 13
                       <23 MY-LENGTH+ returned 13
                      <22 MY-LENGTH+ returned 13
                     <21 MY-LENGTH+ returned 13
                    <20 MY-LENGTH+ returned 13
                   <19 MY-LENGTH+ returned 13
                  <18 MY-LENGTH+ returned 13
                 <17 MY-LENGTH+ returned 13
                <16 MY-LENGTH+ returned 13
               <15 MY-LENGTH+ returned 13
              <14 MY-LENGTH+ returned 13
             <13 MY-LENGTH+ returned 13
            <12 MY-LENGTH+ returned 13
           <11 MY-LENGTH+ returned 13
          <10 MY-LENGTH+ returned 13
         <9 MY-LENGTH+ returned 13
        <8 MY-LENGTH+ returned 13
       <7 MY-LENGTH+ returned 13
      <6 MY-LENGTH+ returned 13
     <5 MY-LENGTH+ returned 13
    <4 MY-LENGTH+ returned 13
   <3 MY-LENGTH+ returned 13
  <2 MY-LENGTH+ returned 13
 <1 MY-LENGTH+ returned 13
<0 MY-LENGTH+ returned 13

トレース結果の形が違います。ギザギザしていません。これは、前述の1の「末尾呼出し」による変更が効いているからです。つまり、残る計算である「継続」が成長しないので、どんどん次の処理へと映ることができるのです。

2の「末尾呼出しの最適化」は、declareを取り除くことで適用されますが、逆にトレースできなくなるのでこのように見ることはできません。このトレース結果は「逆くの字」になっていますが、最適化を行うと下半分が全くなくなり、一番右まで行った後一気にトップレベルまで戻るような処理に最適化されます。

末尾呼出し最適化が「再帰」関数で行われることを「末尾再帰最適化」と呼びます。Common Lisp処理系のうちGNU CLISPは「末尾再帰最適化」には対応していますが、より広い「末尾呼出し最適化」には対応していません。つまり、自分を呼び出すときだけ最適化されますが、例えば相互再帰のように奇数、偶数、奇数、偶数というように自分以外の関数を呼び出すときは最適化されないようです。

末尾呼出し最適化が行われると事実上関数呼出しのコストが無くなりますから、どのように深い探索でもスタックオーバーフローを起こさずに実行できます。複雑な問題を解決するには必ず必要となるスキルですから、全ての場合に末尾再帰に書き換える必要はありませんが、書き換え方を知っておいた方がいいと思います。

labels

既に少し述べましたが、今回のような&optionalの使い方は推奨されません。第二引数を与えられると正常に動作しないため、バグの原因になります。これを防ぐには2通りあります。

  1. 内部関数と外部関数を分ける
  2. 関数の内部化をする

内部関数は再帰を行うためだけに使い、my-length自体は外部関数として&optionalを排除しておきます。一般的には再帰を行う内部関数には%my-lengthのように先頭に%がつけられます。

もう一つの方法はfletのようにレキシカルな関数を定義し、それを再帰することです。fletは残念ながら再帰に対応していません。再帰にも対応しているレキシカル関数の定義はlabelsで行います。再帰部分を内部化したmy-lengthを示します。

(defun my-length (list)
  (labels ((len (lst n)
             (if (null lst)
                 n
                 (len (cdr lst) (1+ n)))))
    (len list 0)))

labelsfletと同じように使いますが、定義部分で自分自身を含めることができる点が違います。letlet*に似ています。

好き嫌いの問題ですが、このlabelsは私には分かりにくいように感じます。それはletについて説明した時と同じで、束縛される初期値が決まっていて必ず呼び出されるにも関わらず、束縛変数と値が分断されており、自分で呼び出す必要があります。labelsは複数の関数を定義することにも対応していますので相互再帰などにも使えますが、多くの場合はこのように一つの内部関数を定義して、それを再帰するような場合でしょう。このような使い方では、私はSchemeの名前付きletの方が好きなので、マクロを定義して使うことが多いです。

(defmacro nlet (name args &body body)
  `(labels ((,name ,(mapcar #'car args)
              ,@body))
     (,name ,@(mapcar #'cadr args))))

(defun my-length2 (list)
  (nlet len ((lst list)
             (n 0))
    (if (null lst)
        n
        (len (cdr lst) (1+ n)))))

名前付きletという通り、nletの後に名前をつける以外はほとんどletと同じように使うことができます。

なお、このように内部化をするとトレースはできなくなります。動きをトレースしたい場合は内部関数と外部関数を分ける方がいいでしょう。

また、Steel Bank Common Lispは宣言を付けることで末尾呼出し最適化に対応しますので、適切な宣言をつけるようにしてください。詳しくは"Tail Call Optimisation in Common Lisp Implementations"を参照してください。SBCLは(declare (optimize speed))を付けると積極的な最適化を行おうとするため、非常に多くのコンパイルメッセージを吐き出します。私はこれがあまり好きではないのでClozure CLを使うことが多いです。

dolist, loop

再帰は複雑な問題に対して力を発揮しますが、逆に単純な問題に対しては冗長になってしまいます。そこでCommon Lispには複数の繰り返しマクロが用意されています。ここではよく使うと思われるdolistloopだけを紹介します。

dolistはリストの各要素に対して繰り返しを行うマクロです。

(let ((bool nil)
      (pos nil)
      (len 0))
  (dolist (x '(a b abc d e))
    (if (equal x 'abc)
        (progn
          (setf bool t)
          (setf pos len)))
    (incf len))
  (values bool pos len))
  ; => T
  ;    2
  ;    5

dolist(dolist (変数 リスト) 内容)という形で使います。リストの要素を自動的に変数に束縛してくれるので便利です。もちろん、あるリストから別のリストを作るというときはmapcarを検討してください。dolistlambdaで表すことができるようなリストを得ることを目的とするのではなく、より柔軟にリストの各要素に対して操作したい場合に使います。今回であれば、リストに'abcという要素が含まれるかどうか、含まれる場合はどの位置か、全部でいくつの要素があるかを多値で返しています。

もう一つ紹介する繰り返しはloopです。実はloopにはシンプルなloopと複雑なloopの二つが定義されています。私が使うのは複雑なloopですので、そちらを紹介します。

loopマクロは事実上、Common Lispに埋め込まれた全く別のプログラミング言語と考えてください。よく使われるマクロの中で最も複雑なマクロであり、これを嫌う人もいますが、実際のところとてつもなく強力なので、一度知ってしまうとなかなか手放せません。

loopマクロのCommon Lisp HyperSpecを参照してください。"The simple loop form"の説明は1行だけで、これはただ言葉通りループするものです。見て欲しいのはその下の"The extended loop form"です。色々書いてありますが、とりあえず覚えておくべきは以下のキーワードです。

これだけで独自の言語ですね。loopマクロの中ではラムダ計算やリスト処理などは忘れて、loopマクロの流儀に従うしかありません。

2つだけ例を示しましょう。

(loop
   for i from 1 to 10 by 2
   collect i)
; => (1 3 5 7 9)

これは1から10までの奇数を集めてリストにするマクロです。

(loop
   for i from 1 to 30

   when (and (= (mod i 3) 0)
             (= (mod i 5) 0))
   collect 'FizzBuzz

   when (and (= (mod i 3) 0)
             (/= (mod i 5) 0))
   collect 'Fizz

   when (and (= (mod i 5) 0)
             (/= (mod i 3) 0))
   collect 'Buzz

   when (and (/= (mod i 3) 0)
             (/= (mod i 5) 0))
   collect i)
; => (1 2 FIZZ 4 BUZZ FIZZ 7 8 FIZZ BUZZ 11 FIZZ 13 14 FIZZBUZZ
;     16 17 FIZZ 19 BUZZ FIZZ 22 23 FIZZ BUZZ 26 FIZZ 28 29 FIZZBUZZ)

こちらは、「FizzBuzz問題」をloopマクロだけで解いたものです。あまり効率的ではありませんが、3の倍数でfizz、5の倍数でbuzz、3と5の倍数はFizzBuzzを集め、それ以外は自然数を集めます。

loopマクロはその中だけで使われるキーワードと処理の連鎖で記述します。loopマクロだけで1ページ作らなければならないほど高機能ですから、詳しく知りたければCommon Lisp HyperSpecを参照してください。ただ、私は単純なことを効率的に行うことだけに使用することが多く、複雑なことをしたければ末尾再帰を使います。

おまけ: 高速なCommon Lisp

ちなみに、なぜこのFizzBuzz問題が非効率か、分かりますか? 条件分岐が重複しているからです。Common Lispらしくloopを使って、条件分岐を一回で行い、しかも高階関数とラムダを使用して書いてみると、このようになります。

(mapcar (lambda (x)
          (cond ((and (zerop (mod x 3))
                      (zerop (mod x 5)))
                 'FizzBuzz)
                ((zerop (mod x 3)) 'Fizz)
                ((zerop (mod x 5)) 'Buzz)
                (t x)))
                (loop for i from 1 to 30 collect i))

これもまだ非効率です。1から30までの数列を作った後でその数列に対してマップしているからです。もっと効率化しようと思えば、マクロでC言語スタイルのforを定義してから使うのも面白いでしょう。また、高速な処理には別のページで説明するベクターが使えます。(ただ、今回のような処理はベクタでもリストでもあまり速度が変わらないかもしれません。Common Lispのリストは良く最適化されており、最初から順番に処理するような場合はベクタよりも早いことがあるようです。)

(defmacro for (var test change &body body)
  `(let (,var)
     (loop
        while ,test
        do 
          ,@body
          ,change)))

(defun fizzbuzz (n)
  (let ((fb (make-array n)))
    (for (i 1) (<= i n) (incf i)
      (cond ((and (zerop (mod i 3))
                  (zerop (mod i 5)))
             (setf (svref fb (1- i)) 'FizzBuzz))
            ((zerop (mod i 3))
             (setf (svref fb (1- i)) 'Fizz))
            ((zerop (mod i 5))
             (setf (svref fb (1- i)) 'Buzz))
            (t (setf (svref fb (1- i)) i))))
    fb))

(fizzbuzz 30)

loopマクロは便利ですが、時にC言語のようなforが欲しいと思うこともあるでしょう。しかし、その時は自分でforを作ればいいだけです。

参考文献


Copyright © 2017- satoshiweb.net All rights reserved.