2014-04-19-01-代入と move:ここまでのまとめ - project-enigma

2014-04-19-01-代入と move:ここまでのまとめ

>> Site top >> weblog >> 月別アーカイブ >> 2014年04月のlog >> 2014-04-19-01-代入と move:ここまでのまとめ

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


代入と move:ここまでのまとめ

2014 年 04 月 19 日

代入の実装に関連して、出力反復子から(擬似的に)値を取得することがでなければならず、また move の実装に関連して入力反復子へ値を設定できなければならない‥‥‥っぽいことがわかってきた。しかし、自分でもこれらの問題について考えていると何がなんだかわからなくなってくる。ここらへんでちょっとまとめてみよう。

 

現在検討中の演算子オーバーロードを全て実装した場合のアルゴリズム copy の実装を以下に示す。ここで問題になるのは、opr= による「代入」が行なわれる部分だ。

(defmethod copy ((first input-iterator)
                 (last  input-iterator) (result output-iterator))
  (let ((dest (clone result)))
    (if (opr== first last)
        dest
        (do ((itr (clone first)))
            ((opr== itr last) dest)
          (opr= (opr* dest) (opr* itr))    ; assignment.
          (++opr itr)
          (++opr dest))))))

 

ここで、opr= はマクロで、オーバーロードのための総称関数 operator= およびそのデフォルト実装とともに以下のように定義されている。

(defgeneric operator= (a b))
(defmethod  operator= (a b)
  b)

(defmacro opr= (a b)
  (multiple-value-bind (vars forms var set ref) (get-setf-expansion a)
    `(let* (,@(mapcar #'list vars forms))
       (let ((,@var (operator= ,ref ,b)))
         ,set
         ,@var))))

 

これにより、前述の copy における (opr= (opr* dest) (opr* itr)) という部分は以下のように展開される。

(LET* ((#:DEST861 DEST))
  (LET ((#:NEW860 (OPERATOR= (OPR* #:DEST861) (OPR* ITR))))
    (FUNCALL #'(SETF OPR*) #:NEW860 #:DEST861)
    #:NEW860))

 

そもそも何故こんなことをしなければならないかというと、この opr= による代入は C++ で言うところの「代入演算子オーバーロード」にあたるものだからだ。例えば、代入先と代入元の双方が同じ型のコンテナであった場合、その中身を「代入」する。一方で、例えば fixnum の場合には単純に setf しなければならない。そのために get-setf-expansion マクロまで担ぎ出すハメに陥っているのだ。やれやれ。

で、結果として、上記の総称関数 operator= をコールするためには代入の元と先の双方に格納されている値をいったん取り出す必要がある。その結果、出力反復子 dest に対して (opr* dest) とせねばならなくなってしまったのだ。これが実態としてコンテナの反復子であれば問題ない。しかし、back-inserter のようなものを使う場合、それは(変な表現だが)生粋の出力反復子だから、値の取得はできないはずなのだ。

一方、代入が一般的にコスト高となる以上、move の動作もできると嬉しい、というわけで入力シーケンスから出力シーケンスに強制的に setf する move アルゴリズムもやってみることにした。copy に酷似しているが、その実装は(ひとまず)以下のようになっている。

(defmethod move ((first input-iterator)
                 (last  input-iterator) (result output-iterator))
  (let ((dest (clone result)))
    (if (opr== first last)
        dest
        (do ((itr (clone first)))
            ((opr== itr last) dest)
          (setf (opr* dest) (opr* itr))    ; move
          (setf (opr* itr) nil)            ; move
          (++opr itr)
          (++opr dest))))))

 

ここで問題になっているのは、入力反復子であるところの itr に (setf (opr* itr) nil) としていることだ。コピーによる代入を行うことなく、setf によって出力先シーケンスに要素を移動させる以上、入力シーケンスからは要素を破棄しなければならない。だからとりあえず nil を設定しているわけだが、これは [first, last) の実態がコンテナの反復子ではれば何の問題もない。上記の move 実装は入力シーケンスとして input-iterator で特定化しているが、例えば list コンテナの反復子 list-iterator はbidirectional-iterator から派生しており、bidirectional-iterator は input-iterator と output-iterator の両方から派生しているからだ。しかし、例えばファイルや標準入力から内容を取得するだけの反復子 ── つまり生粋の入力反復子 ── であれば、値の設定はできないはずなのだ。

ここに至って、入力反復子の setf opr* と出力反復子の opr* を「空振りさせる」ためのデフォルトの実装を用意する、という(間違っているかもしれない)対処案が持ち出されてくるわけだ。これは以下のようなものになる。入力反復子の setf opr* は move semantics 専用なので設定値として nil だけを受け付ける。出力反復子は単純に nil を返す。

#+cl-stl-0x11
(defmethod (setf opr*) ((new-val (eql nil)) (itr input-iterator))
  new-val)

(defmethod opr* ((itr output-iterator))
  nil))

 

これによって、現時点で目論んでいることは全て実現できそうではある‥‥‥できそうではあるのだが、本当にこれで良いのだろうか。特に move の考え方は、まだ良く理解できてないから、何か根本的なところで誤っている可能性が高い。まだまだ探求と検討が続きそうな気配。

 

コメント

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

 

このページのタグ

Page tag : Common Lisp

Page tag : STLとその移植

 

 


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