2014-04-16-01-脱線して swap について - project-enigma

2014-04-16-01-脱線して swap について

>> Site top >> weblog >> 月別アーカイブ >> 2014年04月のlog >> 2014-04-16-01-脱線して swap について

最終更新日付:2014/04/16 23:50:00


脱線して swap について

2014 年 04 月 16 日

前回書いた代入演算子の実装方法を眺めていたら、あきらめていた swap がなんとかなることに気付いた。今回はこれについて。

 

なぜ「あきらめていた」のかというと、STL の世界では swap には以下の2つがあるからだ。

  1. コンテナのメンバ関数としての swap。
  2. アルゴリズムとしての swap。

で、コンテナの swap は同じ型のコンテナの内容を入れ替える。中身を入れ替えるだけだから、これは総称関数で実現していた。しかし、アルゴリズムとしての swap は、「交換対象の2つの参照を取り、入れ替えを行う」。これは Common Lisp の世界で言えば、rotatef にあたる動作だ。つまり、マクロでなければ実現できないのだ。

Lisp や CLOS には「メンバ関数」という概念はないから、全ては関数、または総称関数の実装として表現される。だから、上記の1と2は同じかたちになるわけだ。しかし、コンテナの内容を入れ替える場合には総称関数的に動作させ、それ以外の場合にはマクロ的な方法で入れ替えを行う、それをどうやって実現したら良いのか、自分にはわからなかった。うん、数日前までは。

しかし、昨日の代入演算子に関する話題を書いていて、これはそのまま swap の実装にも使えることに気がついた。つまり、マクロを用いて、総称関数呼び出しの結果を setf するような展開を行うのだ。代入演算子同様、多少効率が犠牲になるが動作する。まず最初に、総称関数 __swap とそのデフォルト動作を定義しておく。

(defgeneric __swap (a b))
(defmethod  __swap (a b)
  (values b a))

 

これは単純に、2つのパラメータを入れ替えた二値を返すだけだ。そして、get-setf-expantion を用いてマクロを以下のように実装する。

(defmacro swap (a b)
  (multiple-value-bind (vars1 forms1 var1 set1 ref1) (get-setf-expansion a)
    (multiple-value-bind (vars2 forms2 var2 set2 ref2) (get-setf-expansion b)
      `(let* (,@(mapcar #'list vars1 forms1)
              ,@(mapcar #'list vars2 forms2))
         (multiple-value-bind (,@var1 ,@var2) (__swap ,ref1 ,ref2)
           ,set1
           ,set2
           nil)))))

 

展開形を見る限り、これは rotatef と非常に良く似ているようだ。そして、__swap のデフォルト実装であれば、これは単純に2つの値を入れ替えたものを setq することになる。では、2つのパラメータが CL-STL のコンテナだった場合、__swap はどのように動作するべきか。これはメンバ関数としての swap の扱いになるので、互いのコンテナの内容を交換してから values で返却することになる。__swap はこういう感じだ。values で返している a と b の順番が先程とは逆になっているところがポイントだ。

(defmethod __swap ((a CL-STL::vector-container)
                   (b CL-STL::vector-container))
  ; Here, swap contents of a and b
  (values a b))

 

これで動作する‥‥‥たしかに。問題は、これがわかりやすいかどうかという点だ。あと、「パラメータのうち、片方がコンテナだった場合」にどうするのか、という点だ。STL のswap アルゴリズムは同じ型の2つのパラメータしか受け付けないが、CL-STL ではそのような制限を設けるのは良くないだろう。そうなると、swap の動作はおおまかに以下のようになる。

また、上記以外でも、総称関数 CL-STL::__swap の実装が個別に提供されている組み合わせであれば、それに従って動作することになる。CL-STL の外でそのような特定化を定義することをやめさせることはできないから、これは仕方のないことだろう。

もう少し考えを進めてみる。__swap の第1パラメータが CL-STL コンテナだった場合を「コンテナの swap メンバ関数呼び出し」として扱うのであれば、第2パラメータが同じタイプのコンテナでなければエラーとすべきだろうか? それとも、そのような場合は「アルゴリズムの swap 呼び出し」とみなすべきだろうか? これはどちらが正しいという問題ではないような気がするが、前者の考え方を取った場合、以下のコードは常にエラーとなる。

(let ((c1 (stl:new :list ()))
      (c2 (stl:new :vector ())))
  (stl:swap c1 c2))

 

個人的には、これはアルゴリズムの swap として動作すべきだろう。つまり後者の考え方を取るということだ。しかし、それは「実行時までその swap 呼び出しがコンテナのものかアルゴリズムのものか決まらない」ということでもあるので、それはそれでなんだかなぁという気がしないでもない。あぁまた歯切れが悪くなってる。

CL-STL は CLOS で実装しているが、これに着手する前、全てをクロージャで実装したCLSTL というのを作っていた(紛らわしい名前だな)。CLOS を使った CL-STL の方がパフォーマンスが良かったので CLSTL は捨てることにしたのだが、CLSTL は alrogithm とか functional とか、カテゴリごとに異なるパッケージに分割していたのだ。だから今回の swap のような名前の問題はなかった。しかし以前、一度だけ人前で CLSTL の紹介をさせてもらったことがあるのだが、その時「パッケージ分け過ぎじゃない?」という指摘を頂いたので、CL-STL ではパッケージは1つにした。この点についてはもう変えるつもりはない。

そんなわけで、swap が解決! と思って書き始めたものの、書いているうちにまた「どうしたもんかな」に辿りついてしまった。これまたしばらく寝かせてみようか。

 

コメント

このページにコメントする

 

このページのタグ

Page tag : Common Lisp

Page tag : STLとその移植

 

 


Copyright(C) 2005-2017 project-enigma.
Generated by CL-PREFAB.