第6章「繰り返し」

概要

ANSI Common Lispの第6章における繰り返しのオペレータを紹介します。ただし、高機能なloopマクロについては概要のみを示します。

回数を指定した繰り返し: dotimes

dotimesマクロは回数を指定した繰り返しです。
(let ((vec (make-array 10)))
  (dotimes (i 10 vec)
    (setf (svref vec i) (* i i))))

; => #(0 1 4 9 16 25 36 49 64 81)

この例では、10の要素を持つベクトル(1次元配列)を用意し、0から9までの数の2乗の値をセットしていきます。dotimesは変数と上限の値に加え、dotimesフォームの返り値となる値を指定することができるので、ここではそのベクトルを指定しています。もし返り値の指定がなければnilとなります。

リストの要素の繰り返し: dolist

リストの各要素を順番に処理していく場合は、dolistマクロを使います。
(let ((result '())
      (list '("12" "34" "56" "7.8" "9.1")))
  (dolist (v list (reverse result))
    (push (read-from-string v) result)))
; => (12 34 56 7.8 9.1)

ただし、ANSI Common Lispの標準仕様でリストに対する操作は様々な高階関数が定められているため、dolistマクロを使用するべき状況は少ないかもしれません。例えば、上記のサンプルは以下の1行で簡潔かつ明瞭に記述できます。
(mapcar #'read-from-string '("12" "34" "56" "7.8" "9.1"))
; => (12 34 56 7.8 9.1)

高階関数で対応できる場合はほぼ必ず高階関数を用いた方がソースコードが美しくなるでしょう。副作用ベースで用いる場合も、対象がリストならmapcを使うことができます。

変数と終了条件を伴う繰り返し: do, do*

doマクロとdo*マクロは高機能なループとして準備されていますが、ANSI Common Lispではもっと高機能なloopマクロが用意されていることに加え、iterate パッケージなどの標準仕様を補完する独自のループ構文が用意されているので、直接doを使うことは稀です。
むしろdoマクロは別のマクロの基礎として使われることが多いでしょう。例えば、Common LispにはなくC言語にある繰り返しの構文としてforがありますが、この構文はdoマクロを使ってマクロを定義することが簡単に利用可能になります。

(defmacro for ((v init end) &body body)
  (let ((end-sym (gensym)))
    `(do ((,v ,init (1+ ,v))
          (,end-sym ,end))
         ((< ,end-sym ,v))
       ,body)))
; => FOR

(for (i 0 10)
  (format t "~a~%" i))
; 0
; 1
; 2
; 3
; 4
; 5
; 6
; 7
; 8
; 9
; 10
; => NIL
doマクロは複数の変数を束縛し、そのステップも制御することができます。注意点は、終了条件がC言語と逆であることです。C言語のforは真の間に継続しますが、ANSI Common Lispのdoの終了条件は真になると終了します。上記の終了条件は((< ,end-sym ,v))の部分です。

なお、終了条件の部分をgensymで一旦変数に束縛しているのは、複数回の評価を防ぐためです。終了条件が定数であれば問題ありませんが、評価のたびに結果が異なるような式であれば無限ループに陥る可能性もあります。,endは一度だけ評価し、その結果を束縛しておくことで、複数回の評価を回避することができます。

無限ループ: シンプルなloop

シンプルなloopマクロは無限ループを作ります。returnやその他の特殊制御オペレータで脱出しなければ無限に続きます。

階乗の計算を行う関数をシンプルなloopで実装してみました。
(defun fact (n)
  (let ((i 1)
        (result 1))
    (loop
       (when (= i n)
         (return (* result i)))
       (setq result (* result i))
       (incf i))))
; => FACT

(fact 10)
; => 3628800

万能なループ: loop

loopマクロは非常に高機能であり、その機能を説明するには膨大な紙面が必要です。ここでは必要十分と考えられるだけの機能を「総論」と「各論」に分けて紹介します。loopキーワードの用法は各論に記載し、キーワード以外の機能について総論に記載します。
以下の節は次の構成で記載しています。
  • 総論
    • loop キーワード
    • loop の構文解析
    • named節とreturn
    • 実行の順序
    • 変数の分配機能
  • 各論
    • 変数初期化の節: for, as, with, in, on, across, being the
    • 集計の節: collect, append, nconc, sum, count, minimize, maximize
    • 終了条件の節: repeat, while, until, always, never, thereis
    • 無条件実行の節: do
    • 条件分岐の節: if, when, unless, else, end
    • その他の節: initially, finally
まずは総論です。

loop キーワード

loopマクロはその内部で様々なキーワードを使用することができます。キーワードの使い方は各論で示します。
loopキーワードは真のキーワードではなく、loopマクロ内部のみで有効なシンボルです。loopマクロはこのキーワードを頼りに構文を解析します。

Common Lispは一般に「S式」というリストで構文を記述し、それがそのまま構文木( syntax tree )として用いられますが、loopマクロはキーワードの出現によって構文を構築します。そのため、loopマクロはLisp的ではないともよく言われますが、Lisp的な記述よりもカッコが少なく、普通の英語の文章を記述しているかのように記述することになります。

なお、loop内部にキーワードが出現しない場合、それは前節のシンプルなloopとして扱われ、無限ループを構築します。キーワードがあればここで説明する拡張されたloopとして扱われます。

loop の構文解析

loopマクロの内部はキーワードによっていくつかの「節( clauses )」に分けられます。以下の例は、有名な "FizzBuzz問題" をloopマクロで解いた例です。
(loop
   for i from 1 to 100
   if (zerop (mod i 15))
   collect 'FizzBuzz into result
   else if (zerop (mod i 3))
   collect 'Fizz into result
   else if (zerop (mod i 5))
   collect 'Buzz into result
   else collect i into result
   finally (format t "~{~a~^,~}~%" result))
; 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,31,32,FIZZ,34,BUZZ,
; FIZZ,37,38,FIZZ,BUZZ,41,FIZZ,43,44,FIZZBUZZ,46,
; 47,FIZZ,49,BUZZ,FIZZ,52,53,FIZZ,BUZZ,56,FIZZ,58,
; 59,FIZZBUZZ,61,62,FIZZ,64,BUZZ,FIZZ,67,68,FIZZ,
; BUZZ,71,FIZZ,73,74,FIZZBUZZ,76,77,FIZZ,79,BUZZ,
; FIZZ,82,83,FIZZ,BUZZ,86,FIZZ,88,89,FIZZBUZZ,91,
; 92,FIZZ,94,BUZZ,FIZZ,97,98,FIZZ,BUZZ
; => NIL
loopマクロのキーワードを使う場合、このように「キーワード + 式」の節が羅列する形式になります。この例では、1行1節になっています。基本的にはこのように節単位で記述すると、それがloopマクロ上の構文になります。

なお、ifを通常のスペシャルオペレータとして使う場合は(Emacsにおいては)次の行が自動でインデントされますが、loopマクロではインデントを行いません。基本的には1行1節で記述していくので、loopマクロ内では余計なインデントは行わず、単純に上から下へ流れるように記述していきます。(インデントは全てEmacsに任せるのがベターです。)

ただし、do, initially, finallyのキーワードが使われている節は暗黙的にprognで囲まれるため、1行1節が該当しない場合があります。

named節とreturn

loopマクロはnamed節を指定することで名前を付けることができます。loopマクロの内容は暗黙的にblockで括られ、何も名前を指定しなければnilblockを作ります。そのため、named節のないloopからはreturnマクロにて、named節のある named loopからはreturn-fromスペシャルオペレータにて脱出することができます。

そのほか、loopマクロのキーワードとしてreturnが用意されているため、return節で脱出することも可能です。return節の場合はそれ自体が節なのでdo節などが不要ですが、(return)マクロや(return-from ...)スペシャルフォームを使う場合はdo節などでloopマクロの構文節を設定しなければなりません。

以下の例では、九九の計算を行う二重ループにおいて、6までで強制的に脱出しています。内側のloopにはnamed節でinnerという名前を付け、return-formスペシャルオペレータで脱出していますが、外側のloopでは名前を付けず、return節で脱出しています。
(loop
   for x from 1 to 9
   collect (loop named inner
              for y from 1 to 9
              collect (* x y) into row
              when (= y 6)
              do (return-from inner row))
   into kuku
   when (= x 6)
   return kuku)
; => ((1 2 3 4 5 6) (2 4 6 8 10 12)
;     (3 6 9 12 15 18) (4 8 12 16 20 24)
;     (5 10 15 20 25 30) (6 12 18 24 30 36))

実行の順序

loopマクロ内部ではすでに見てきたように、ソースコードの現れる順序で実行され、脱出や終了条件に到るまで繰り返されます。しかし、以下の状況では、評価の順序が変更されます。
  • 変数は全て最初に初期化されます。初期化の順序は、ソースコード上の順序です。
  • initially節が複数存在する場合、全てが1つに集められます。変数の初期化が終わったら、集められたinitially節が1度だけ評価されます。
  • finally節も複数存在する場合は1つに集められて実行されますが、明示的に脱出する場合は実行されません。
  • with節は変数の束縛を1度だけ行います。
また、for-from-to節のような繰り返し制御を行う節は暗黙的に以下のように動作します。
  1. 変数を初期化する
  2. 一般的にはloopbody を1度評価するたびに、変数の値を変化させる
  3. 一般的にはloopbody を評価する前に、終了時判定を行う

変数の分配機能

loopマクロのfor節やwith節は変数の束縛を伴いますが、そこには以下の簡易的な機能が付随しています。
  • 変数の型をdeclareなしで指定できます
  • 変数を構造化代入することができます
いずれも簡易的なものなのですが、型の指定は最適化に威力を発揮します。構造化代入(分配)はあまり使うことがないと思いますが、そのような機能があるということだけ覚えておけば足りるでしょう。

以下にその例を示します。3重のリストを2重にします。
(loop
   for ((a b c) (d e f))
   of-type ((fixnum fixnum fixnum) (fixnum fixnum fixnum))
   in '(((1 2 3) (4 5 6))
        ((7 8 9) (10 11 12))
        ((13 14 15) (16 17 18)))
   collect (list a b c d e f))
; => ((1 2 3 4 5 6)
;     (7 8 9 10 11 12)
;     (13 14 15 16 17 18))
of-type節がなくても型の指定ができるようになっていますが、ANSI Common Lispの標準仕様上は構造化代入を用いる際の型の指定はof-typeを付けるようです。構造化代入がない場合は仕様上も不要です。
loopマクロの総論についてはこれで終わりです。以下では様々な節の使い方について示します。

変数の初期化

loopマクロの最も基本的な節はforです。forはループ中に用いる変数を初期化すると共に、その変化も合わせて定義することで、ループする毎に自動的に値を変化させます。as節はfor節と等価ですが、forの方が圧倒的によく利用されます。
for節がループの度に変化させることができる値の種類の代表例は以下の通りです。
  • 数(加算): (for ... from ... to ...)
  • 数(減算): (for ... downfrom ... to ...)
  • リスト( car ): (for ... in ...)
  • リスト( cdr ): (for ... on ...)
  • ベクトル(文字列含む): (for ... across ...)
  • ハッシュ(キー): (for ... being the hash-keys in ...)
  • ハッシュ(バリュー): (for ... being the hash-values in...)
  • パッケージ(シンボル): (for ... being the symbols in ...)
  • パッケージ(公開シンボル): (for ... being the external-symbols in ...)
  • その他汎用: (for ... = ... then ...)
また、いくつかの副節は上記以外の種類が用意されています。代表的なものは以下の通りです。
  1. 数の変化は以下の副節が利用できます。
    • to: 次に続く値を超えるまで変化させ、超えた時点でループが停止します。
    • below: 次に続く正の値まで変化させ、一致した時点でループが停止します。
    • above: 次に続く負の値まで変化させ、一致した時点でループが停止します。
  2. 数とリストの場合は値の変化の方法をbyで変更できます。
    • 数: byに続く数の分だけ変化させます。デフォルトは1または-1です。
    • リスト: byに続く関数で値を取り出していきます。デフォルトは#'cdrです。
  3. for節が複数存在する場合、値の変化は直線的となります。
    • and: 2番目以降のforの代わりにandを使うと並列的になります。
  4. =副節でthen副節を指定しない場合、=に続く式が繰り返し評価されます。
また、for節はループの度に値が変更する変数ですが、一度だけしか評価しない補助変数を用意することもできます。そのためにはwith節を利用します。

集計

loopマクロは単に繰り返しの構文を提供するだけでなく、繰り返しの中で得られた値を集計する機能がいくつか用意されています。
  • リストの累積
    • collect: 次に続く値を結果となるリストに加えていきます。
    • append: 次に続くリストを結果となるリストに連結していきます。
    • nconc: 次に続くリストを結果となるリストに破壊的に連結していきます。
  • 統計
    • sum: 次に続く数を加算していきます。
    • count: 次に続く値がnil以外の場合に累積的に数を数えます。
    • minimize: 次に続く数が手前の数よりも小さい場合、その数を残します。
    • maximize: 次に続く数が手前の数よりも大きい場合、その数を残します。
これらの集計の節には補助的な機能があります。
  1. into: into副節を用いることで、集計の結果を特定の変数に束縛できます。
  2. it: when節などで条件判定を用いた直後の集計でitシンボルを使うと、条件判定の結果を利用できます。
  3. 集計の結果は自動的に返り値になります。
itシンボルはloopマクロで特別な用途で用いるため、自分で束縛する変数としては利用しないようにしてください。例えば、以下のように用います。
(loop
   for i from 1 to 10
   when (evenp i)
   count it)
; => 5

なおappendnconcの違いは破壊的であるかどうかですが、リストの操作については第14章で扱います。

終了条件

繰り返しには必ず終了条件が必要ですが、総論で示したreturn節(脱出)以外にもloopマクロには終了条件に用いる節が用意されています。
  • 指定したループ回数を実行して終了するタイプ
    • repeat: 次に続く数だけループを繰り返します。
  • 条件が満たされたり満たされなくなったりすると終了するタイプ
    • while: 次に続く式がnilになった時点で終了します。
    • until: 次に続く式がtになった時点(nilではなくなった時点)で終了します。
  • 繰り返し自体を述語として利用するタイプ
    • always: 次に続く式がtであるかを判定し、nilになった時点で終了します。返り値は途中で脱出した場合nilとなり、最後までtだった場合tとなります。
    • never: 次に続く式がnilであるかを判定し、tになった時点で終了します。返り値もalwaysと逆です。
  • 値が存在するかどうかを判定するタイプ
    • thereis: 次に続く式がtであるかを判定し、tになった時点で終了しますが、返り値は真偽値ではなく、判定に用いた値自体にしたい場合に用います。最後までtになる値が存在しない場合は、nilが返り値となります。
thereisが最もイメージが湧きにくいと思うので、サンプルを示します。
(loop
   for i in '(1 3 6 7 9)
   thereis (when (evenp i) i))
; => 6

なお、上の式は以下のように高階関数を用いたものと同じになりますが、高階関数を用いた方が美しく記述できます。
(find-if #'evenp '(1 3 6 7 9))
; => 6

無条件実行

loopマクロの中では様々な loop キーワードが存在し、構文はloopマクロ独自のものに従わなければなりません。しかし、do節の中では一般のLisp構文をそのまま利用でます。また、do節は自動的にprognされるため、複数の式を置くこともできます。

条件分岐

loopマクロの中でdo節を用いればifスペシャルオペレータやcondマクロなどを利用することができますが、loopマクロにはあらかじめいくつかの条件分岐節が用意されています。
  • when: 次に続く式がtの時に、その次の節を実行します。
    • if: whenと同じです。
  • unless: 次に続く式がnilの時に、その次の節を実行します。
条件分岐には以下の副節が用意されています。
  • else: condマクロのように条件節を連結します。
  • and: 条件を満たした時に実行する節を複数記述する場合に、節を連結するのに用います。
  • end: 複数記述した節の終わりを示すのに用います。
これらの副節は実際にはあまり用いません。whenunlessで実行する場合の節としてdo節を用いれば不要になるからです。このページのFizzBuzz問題の際はelse副節を用いましたが、do節の中でcondマクロを用いる方が見やすい可能性があります。

その他の節

各論ではなく総論に記述した節は以下の2つです。
  • named: ループに名前を付けます。
  • return: ループから脱出します。
また、総論でも少しだけ触れましたが、他に以下の2つの節が用意されています。
  • initially: 必ず最初に実行される節です。
  • finally: 脱出などがない場合、最後に実行される節です。
finally節をunwind-protectスペシャルオペレータのように利用してはいけません。ループ内の制御が複雑になる場合、finallyが確実に実行されるかどうかを見極めることはかなり困難になります。そのため、これらの節もあまり用いられません。
loopマクロはこれまで見てきた通り非常に高機能なため、最初はとっつきにくいかもしれませんが、慣れると手放せなくなります。ANSI Common Lispの標準仕様でここまでのループが定められているのは、ループがプログラムにとって欠かせない存在であることの証です。高階関数でシンプルに書けるようなものは高階関数で書くべきですが、高階関数で書こうとする方が複雑になるような場合はためらうことなくloopマクロを使用してください。

0 件のコメント :

コメントを投稿