iterate
iterateはCommon Lispの繰り返し処理のための老舗ライブラリで、言語標準のloopマクロの代替として使えるものです。
loopマクロは機能が豊富で、かつ英語として自然に読めるように意図して作られているため、Common Lispとしてはややイレギュラーな書き方になっています。そのためエディタの方で正しくインデントするには色々頑張ってパースしなければならず、開発環境によってもインデントルールが異なるので複数人で開発するときに問題になります。
iterateはloopマクロをよりLisp的な書き方にしたものです。さらにloopでは面倒なことを簡単に書けたり、ユーザにより構文の拡張が可能です。
インストール
quicklispからインストールできます。
(ql:quickload :iterate)
;; 作業用パッケージを定義、以下のコードはこのパッケージ内で実行しています
(defpackage iterate-test
(:use :cl :iterate))
(in-package :iterate-test)
基本構文
loopマクロの代わりにiterマクロを使います。基本的にはloopマクロと同じですが、forなどの意味のまとまり（節）ごとに括弧でくくる点が異なります。また、iterマクロの最後の要素が本体となり、loopマクロのdoに当たるものを書く必要がありません。
;; 0から9まで印字する
;; loop版
(loop for i from 0 to 10 do (princ i))
;; iterate版
(iter (for i from 0 below 10)
(princ i))
; 0123456789
;; 2つのリストの対応する位置の要素のペアのリストを返す（長さが合わなければ短い方に合わせて終了する）
(loop for x in '(1 3 5)
for y in '(2 4 6 8 10)
collect (cons x y))
(iter (for x in '(1 3 5))
(for y in '(2 4 6 8 10))
(collect (cons x y)))
; => ((1 . 2) (3 . 4) (5 . 6))
;; リスト中の最大と最小の要素を多値で返す
(loop for x in '(1 -1 2 -3 5 6)
maximize x into max
minimize x into min
finally (return (values max min)))
(iter (for x in '(1 -1 2 -3 5 6))
(maximize x into max)
(minimize x into min)
(finally (return (values max min))))
; => 6, -3
データ構造に対する繰り返し処理
何らかの並びを持つデータ構造に対して繰り返し処理を行うとき、loopマクロの場合はリストに対してはfor ... in、ベクタに対してはfor ... acrossが用意されていました。
iterマクロには、次のようなものが用意されています。
-
in-sequence: リスト、ベクタに対する繰り返し -
in: リストに対する繰り返し -
in-vector: ベクタに対する繰り返し -
in-string: 文字列に対する繰り返し（ただし文字列はベクタのサブセットなのでin-vectorでもin-sequenceでもいける） -
in-hashtable: ハッシュテーブルに対する繰り返し
loopにはin-sequenceに当たるものが無く、シーケンス汎用で使いたいときに処理を分けるしかなかったので便利です。
(loop for i across (vector 1 2 3) do (princ i))
(iter (for i in (list 1 2 3)) (princ i))
(iter (for i in-vector (vector 1 2 3)) (princ i))
(iter (for i in-sequence (vector 1 2 3)) (princ i))
(iter (for i in-sequence (list 1 2 3)) (princ i))
; 123
ハッシュテーブルの要素に対する繰り返しは、loopマクロでもできないことはないですが、iterマクロの方がより簡潔に書けます。
;; 最初にハッシュテーブルを用意
(defparameter ht
(alexandria:alist-hash-table
'((key1 . "foo")
(key2 . "bar")
(key3 . "baz"))))
;; loopマクロ版
(loop for key being the hash-key in ht using (hash-value val)
collect (list key val))
;; iterate版
(iter (for (key val) in-hashtable ht)
(collect (list key val)))
; => ((KEY1 "foo") (KEY2 "bar") (KEY3 "baz"))
loopではうまくいかない例
iterateでは、collectやappendingといったリストに溜め込んでいく記述を本体部分の任意の場所に入れられます。
(iter (for thing in '(:one :two :three))
(case thing
(:one (collect 1))
(:two (appending (list 2 2)))
(:three
(collect 3)
(appending (list 3 3)))))
; => (1 2 2 3 3 3)
このcaseはiterateで用意されている特殊なシンボルではなく、通常のCommon Lispのcase式です。条件分岐の先でcollectの対象を切り替えるようなことが可能になります。
なお、collectはloopと同様にオプショナルでintoを取ることができ、溜め込むリストに名前を付けられます。例えば、一回のループで複数のリストを組み立てて多値で返す式は以下のようになります。
(iter (for i from 1 to 10)
(collect i into identical)
(collect (* i i) into square)
(finally (return (values identical square))))
; => (1 2 3 4 5 6 7 8 9 10)
; => (1 4 9 16 25 36 49 64 81 100)
Finder
iterateにあってloopマクロにはない機能で、便利なものとしてFinderがあります。これはループの中で、ある指標を最大化/最小化したり（つまりargmax/argmin）、特定の条件に引っかかるようなものを探すというものです。loopマクロにもmaximizing/minimizing節がありますが、これは最大値/最小値そのものを返すもので、その値に対応する変数の値が何だったのかは分かりません。
例えば、次のような二次関数があるとします。
(defun f (x) (1+ (* x (- x 4))))
(ql:quickload :clgplot)
(let* ((x (iter (for x from -5 to 5 by 1/100) (collect x)))
(y (mapcar #'f x)))
(clgp:plot y :x-seq x :title "x^2-4x+1" :x-label "x" :y-label "y"))
このとき、次のようにして関数fの変曲点を求められます。
;; f(x)の最小値を求める
(iter (for x from -5 to 5 by 1/100)
(minimizing (f x)))
; => -3
;; f(x)が最小のときのxを求める
(iter (for x from -5 to 5 by 1/100)
(finding x minimizing (f x)))
; => 2
such-that
繰り返しの中で、特定の条件を満たすような最初の要素を返すにはsuch-thatを使います。
(iter (for i from 1 to 100)
(finding i such-that (and (zerop (mod i 11))
(zerop (mod i 3)))))
; => 33
型宣言
loopマクロでは変数に型を宣言することができ、総和を取るようなときは道中の変数と結果を溜め込む変数が同じ型で宣言されているかが速度上重要になったりします。
iterateではiterマクロ内のdeclareにより、導入した変数の型を指定することができます。
次に実際に、3つの関数opt0,opt1,opt2を定義し、その中で実行時の型チェックを外す最適化宣言をしてみます。それぞれの関数に対して(disassemble 'opt0)のようにして実際に実行される命令列を見てみましょう。
opt0はループ変数iには型宣言しているものの、sumの結果に型宣言されていないため型を特定しないGENERIC-+での加算が行なわれていることが分かります。opt1とopt2はloopマクロとiterマクロを使って、関与する変数全てをfixnumに宣言する書き方の例です。双方ほぼ同じ命令列にコンパイルされていることが分かります。
(defun opt0 ()
(declare (optimize (speed 3) (safety 0)))
(loop for i fixnum from 1 to 10
sum i))
; disassembly for OPT0
; Size: 43 bytes. Origin: #x52D0CA37 ; OPT0
; 37: B802000000 MOV EAX, 2
; 3C: 31D2 XOR EDX, EDX
; 3E: EB16 JMP L1
; 40: L0: 488945F8 MOV [RBP-8], RAX
; 44: 488BF8 MOV RDI, RAX
; 47: FF1425F8000052 CALL QWORD PTR [#x520000F8] ; GENERIC-+
; 4E: 488B45F8 MOV RAX, [RBP-8]
; 52: 4883C002 ADD RAX, 2
; 56: L1: 4883F814 CMP RAX, 20
; 5A: 7EE4 JLE L0
; 5C: 488BE5 MOV RSP, RBP
; 5F: F8 CLC
; 60: 5D POP RBP
; 61: C3 RET
(defun opt1 ()
(declare (optimize (speed 3) (safety 0)))
(loop for i fixnum from 1 to 10
sum i fixnum))
; disassembly for OPT1
; Size: 32 bytes. Origin: #x52D0CB66 ; OPT1
; 66: B802000000 MOV EAX, 2
; 6B: 31C9 XOR ECX, ECX
; 6D: EB08 JMP L1
; 6F: 90 NOP
; 70: L0: 4801C1 ADD RCX, RAX
; 73: 4883C002 ADD RAX, 2
; 77: L1: 4883F814 CMP RAX, 20
; 7B: 7EF3 JLE L0
; 7D: 488BD1 MOV RDX, RCX
; 80: 488BE5 MOV RSP, RBP
; 83: F8 CLC
; 84: 5D POP RBP
; 85: C3 RET
;; iterマクロ内のトップレベルにあるdeclareを全て探してから、先頭部分に再配置するので、declareはどこに書いても実は同じ
(defun opt2 ()
(declare (optimize (speed 3) (safety 0)))
(iter (for i from 1 to 10)
(sum i into s)
(declare (fixnum i s))
(finally (return s))))
; disassembly for OPT2
; Size: 32 bytes. Origin: #x52D0CDD6 ; OPT2
; D6: 31C0 XOR EAX, EAX
; D8: 31C9 XOR ECX, ECX
; DA: 31C0 XOR EAX, EAX
; DC: EB05 JMP L1
; DE: 6690 NOP
; E0: L0: 4801C1 ADD RCX, RAX
; E3: L1: 4883C002 ADD RAX, 2
; E7: 4883F814 CMP RAX, 20
; EB: 7EF3 JLE L0
; ED: 488BD1 MOV RDX, RCX
; F0: 488BE5 MOV RSP, RBP
; F3: F8 CLC
; F4: 5D POP RBP
; F5: C3 RET
情報源
- 公式マニュアル https://common-lisp.net/project/iterate/doc/index.html
- 書籍: Common Lisp Recipes 7-14 http://weitz.de/cl-recipes/
感想
Common Lispは言語自体は規格化されていて30年くらい変わっていないのですが、その規格内で言語機能の拡張方法も規定されており、標準の構文に不満があるときは、このiterateのようにライブラリとして実装してしまうというのが面白いところです。
ユーザ側がどの構文を採用するかを決め、問題に合わせて言語をカスタマイズしていくという開発プロセスは、うまくハマれば非常に快適です。