読者です 読者をやめる 読者になる 読者になる

iterateパッケージ

common lisp library

Wikipediacommon lispの項目を読んでいたら、iterateというパッケージの存在を知った。

少し興味を引かれたのでマニュアル(簡単に)目を通してみた。


名前の通り、繰り返し処理を行うためのパッケージで、立ち位置的にはloopマクロに近いようだ。

>(iter (FOR i FROM 1 TO 10)
       (COLLECT i))
--> (1 2 3 4 5 6 7 8 9 10)

ただ、loopとは異なり拡張が可能とのこと。
せっかくなので(?)、試してみる。

拡張

どんな拡張にしようか少し悩んだが、以前、ハフマン木を作成する関数を書いた際に、ヒープに対する(ポップ操作の)繰り返しをdoを使って実装していたことを思い出したので、それをiterateを使って置き換えてみることにした。
以前のハフマン木云々に関してはこっちを参照。


拡張用の関数・マクロはいくつか用意されているようだが、今回はFORフォーム(?)に新しい節を追加するための、defmacro-driverというマクロを使った。
以下が拡張を定義したコードだが、引数の中身が若干異なること以外は、ほとんど普通のマクロと同じ感覚で書くことができた。

(require :iterate)
(use-package :iterate)

;; (iter (FOR ... POP-FROM ... PACKAGE ...)  ※ PACKAGE節はオプショナル
;;       (.....))
(defmacro-driver (FOR var POP-FROM container &optional PACKAGE (pack common-lisp:*package*))
  (declare (ignorable generate)) ; defmacro-driverマクロが自動で用意している変数
  (let* ((pop  (find-symbol "POP" pack)) ; packパッケージから'POPシンボルを探す(繰り返し用)
         (next-exp (if (consp var)
                      `(loop REPEAT  ,(length var)
                             COLLECT (,pop ,container))
                    `(,pop ,container))))
    (assert pop () "symbol POP not found in the ~A package" (package-name pack))
    `(for ,var next ,next-exp)))


使い方:

> (defvar *list* '(1 2 3 4 5 6))

;; リストが空になるまで、要素を取り出す: (pop *list*)が毎回呼ばれる
> (iter (FOR x POP-FROM *list*)
        (COLLECT x) 
        (UNTIL (null *list*)))
--> '(1 2 3 4 5 6)

;; 副作用あり
> *list*
--> NIL

> (setf *list* '(1 2 3 4 5 6))

;; リストが空になるまで、2つずつ要素をpopする
> (iter (FOR (x y) POP-FROM *list*)
        (COLLECT x)
        (UNTIL (null *list*)))
--> '(1 3 5)

リストに対して使う分には、副作用があることを除けば、ほとんど初めからある(FOR ... IN ...)構文と変わらない。

リスト以外の(スタックやキュー的な動作をする)コンテナに適用する場合は、繰り返し中に使用されるpop関数を含むパッケージを、PACKAGE節で指定すれば良い*1※ common-lisp:*package*にcommon-lispパッケージがバインドされている場合

ハフマン木作成

これを、ハフマン木作成関数に適用してみる。


まず、もともとの関数:

;; ハフマン木を作成
(defun make-huffman-tree (freq-map)
  (let ((hp (heap:make-heap :test #'freq<)))
    ;; 1] 初期heap作成
    (maphash (lambda (char freq)
               (heap:push (make-node freq char) hp))
             freq-map)

    ;; 2] heapが空になるまで、「頻度最小の二つのnodeを取り出し、併合して、heapに戻す」という操作を繰り返す
    (do ((node #1=(heap:pop hp) #1#))
        ((heap:empty? hp) node)    ; heapに最後に残ったnodeがハフマン木
      (let ((node2 (heap:pop hp)))
        (heap:push (make-node (freq+ node node2) (cons node node2)) hp)))))

この2の部分を、上で作成した(FOR ... POP-FROM ...)ルーブで置き換える。
※ ついでに、1の部分もiterateを使うように修正してある。


修正後の関数:

(defun make-huffman-tree (freq-map)
  (let ((hp (heap:make-heap :test #'freq<)))
    ;; 1] 初期heap作成
    (iter (FOR (char freq) IN-HASHTABLE freq-map)
          (heap:push (make-node freq char) hp))

    ;; 2] heapが空になるまで、「頻度最小の二つのnodeを取り出し、併合して、heapに戻す」という操作を繰り返す
    ;; XXX: ヒープの要素数が2未満の場合にはエラーとなる ※1
    (iter (FOR (1st 2nd) POP-FROM hp PACKAGE :heap) ; <- heap:pop関数を使って要素を取り出す           
          (FOR merged-node = (make-node (freq+ 1st 2nd) (cons 1st 2nd))) 
          (when (heap:empty? hp)                                         
            (leave merged-node))                                         
          (heap:push merged-node hp)))) 

;; ※1 修正版: 若干分かりにくい
;;(iter (FOR (1st 2nd) POP-FROM hp PACKAGE :heap)
;;      (when (null 2nd)
;;        (leave 1st))
;;      (heap:push (make-node (freq+ 1st 2nd) (cons 1st 2nd)) hp))           

行数は多くなってしまった*2が、doを使ったものよりは、分かりやすくなったと思う。

###

今回の拡張が使えるかどうかはともかく、(普通のマクロを書くくらい)簡単に独自の繰り返し処理を定義できるのはいいと思う。
標準の制御構造を使ったり、似たようなマクロを書くことも難しくはないが、iterateパッケージを使った方がシンタックスが統一できるし、基盤が既にあるので新たに作成する労力も少なくて済む。
まあ、依存パッケージが増えるというのが(個人的には)デメリットなので、常用することはないと思うが、いろいろ試してみるのは良いかもしれない。
※ それはそうと、clsqlではcommon lispのloopを拡張してるっぽいのだが、どうやってやっているのだろう?

*1:使うpop関数を直接指定するようした方が分かりやすい

*2:効率も悪くなった