2015-12-11-01-非順序連想コンテナとコンストラクタオーバーロード - project-enigma

2015-12-11-01-非順序連想コンテナとコンストラクタオーバーロード

>> Site top >> weblog >> 月別アーカイブ >> 2015年12月のlog >> 2015-12-11-01-非順序連想コンテナとコンストラクタオーバーロード

最終更新日付:2015/12/11 20:00:00


非順序連想コンテナとコンストラクタオーバーロード

2015 年 12 月 11 日

先日書いた通り、STL の非順序連想コンテナ(要するにハッシュコンテナ)を CL-STL に導入するための作業を始めている。今回はそれで困った(困っている)ことについて少し。

困っていることというのは、コンストラクタオーバーロードだ。これまでのコンテナと違い、パラメータが多く、そしてデフォルトパラメータまで考慮に入れるとかなり幅がある。これを CL-OVERLOAD の仕組みで実現しようとすると骨が折れる作業になりそうなのだ。

unordered_map を例に取ろう。読み難いヘッダファイルから読み取る限り、CL-STL がサポートしなければならないコンストラクタは以下の形式になることがわかった(アロケータ関連は除外してある)。

// normal constructor.
unordered_map(size_type __n = 10,
              const hasher& __hf = hasher(),
              const key_equal& __eql = key_equal());

// range constructor.
unordered_map(_InputIterator __f, _InputIterator __l,
              size_type __n = 0,
              const hasher& __hf = hasher(),
              const key_equal& __eql = key_equal());

// copy constructor.
unordered_map(const unordered_map&);

// move constructor.
unordered_map(unordered_map&&);

// constructor with initializer-list.
unordered_map(initializer_list<value_type> __l,
              size_type __n = 0,
              const hasher& __hf = hasher(),
              const key_equal& __eql = key_equal());

 

おさらいしておくと、CL-OVERLOAD は総称関数にマクロのラッパーを被せただけのものだから、型による解決の前にパラメータ数での絞り込みを(通常はコンパイル時点で)行なう。そのため、実際の使用においてどのパラメータ数でコールされた場合でも、適切なメソッド呼び出しに解決できるような実装になっていなければならない。これを単純愚直に書き下すと以下のようになる‥‥‥なんと、26メソッド! (まともに読まなくていいよ)

(declare-constructor unordered-map (0 1 2 3 4 5))

; normal constructor.
(define-constructor unordered-map () #|...|#)
(define-constructor unordered-map ((n integer)) #|...|#)
(define-constructor unordered-map ((n integer) (hasher cl:function)) #|...|#)
(define-constructor unordered-map ((n integer) (hasher functor)) #|...|#)
(define-constructor unordered-map ((n integer) (hasher cl:function) (key-eql cl:function)) #|...|#)
(define-constructor unordered-map ((n integer) (hasher cl:function) (key-eql functor)) #|...|#)
(define-constructor unordered-map ((n integer) (hasher functor)     (key-eql cl:function)) #|...|#)
(define-constructor unordered-map ((n integer) (hasher functor)     (key-eql functor)) #|...|#)

; range constructor.
(define-constructor unordered-map ((itr1 input-iterator) (itr2 input-iterator)) #|...|#)
(define-constructor unordered-map ((itr1 input-iterator) (itr2 input-iterator) (n integer)) #|...|#)
(define-constructor unordered-map ((itr1 input-iterator) (itr2 input-iterator) (n integer) (hasher cl:function)) #|...|#)
(define-constructor unordered-map ((itr1 input-iterator) (itr2 input-iterator) (n integer) (hasher functor)) #|...|#)
(define-constructor unordered-map ((itr1 input-iterator) (itr2 input-iterator) (n integer) (hasher cl:function) (key-eql cl:function)) #|...|#)
(define-constructor unordered-map ((itr1 input-iterator) (itr2 input-iterator) (n integer) (hasher cl:function) (key-eql functor)) #|...|#)
(define-constructor unordered-map ((itr1 input-iterator) (itr2 input-iterator) (n integer) (hasher functor)     (key-eql cl:function)) #|...|#)
(define-constructor unordered-map ((itr1 input-iterator) (itr2 input-iterator) (n integer) (hasher functor)     (key-eql functor)) #|...|#)

; copy constructor.
(define-constructor unordered-map ((obj unordered-map)) #|...|#)

; move constructor.
(define-constructor unordered-map ((ref remove-reference)) #|...|#)

; constructor with initializer-list.
(define-constructor unordered-map ((il initializer-list)) #|...|#)
(define-constructor unordered-map ((il initializer-list) (n integer)) #|...|#)
(define-constructor unordered-map ((il initializer-list) (n integer) (hasher cl:function)) #|...|#)
(define-constructor unordered-map ((il initializer-list) (n integer) (hasher functor)) #|...|#)
(define-constructor unordered-map ((il initializer-list) (n integer) (hasher cl:function) (key-eql cl:function)) #|...|#)
(define-constructor unordered-map ((il initializer-list) (n integer) (hasher cl:function) (key-eql functor)) #|...|#)
(define-constructor unordered-map ((il initializer-list) (n integer) (hasher functor)     (key-eql cl:function)) #|...|#)
(define-constructor unordered-map ((il initializer-list) (n integer) (hasher functor)     (key-eql functor)) #|...|#)

 

いくらなんでもこれは酷い。これに加えて、さらに入力反復子のかわりにベクタのポインタまで受け入れなければならないのだ。ここまで膨れ上がった理由のひとつに、2つのファンクタをパラメータとして取るパターンがいくつもあるというのがある。CL-STL では、ファンクタと関数は全然別のモノだし、テンプレートではなく総称関数で色々なんとかしている。だからパラメータとしてのファンクタおよび関数はそれぞれ個別にメソッド定義してやらなければならないのだ。

では、そこのところをメソッド特定化から外してやったらどうだろう? つまり、hasherkey-eql は特定化せず、メソッドの内部でチェックするわけだ。以下のように。これで 14個になった。

(declare-constructor unordered-map (0 1 2 3 4 5))

; normal constructor.
(define-constructor unordered-map () #|...|#)
(define-constructor unordered-map ((n integer)) #|...|#)
(define-constructor unordered-map ((n integer) hasher) #|...|#)
(define-constructor unordered-map ((n integer) hasher key-eql) #|...|#)

; range constructor.
(define-constructor unordered-map ((itr1 input-iterator) (itr2 input-iterator)) #|...|#)
(define-constructor unordered-map ((itr1 input-iterator) (itr2 input-iterator) (n integer)) #|...|#)
(define-constructor unordered-map ((itr1 input-iterator) (itr2 input-iterator) (n integer) hasher) #|...|#)
(define-constructor unordered-map ((itr1 input-iterator) (itr2 input-iterator) (n integer) hasher key-eql) #|...|#)

; copy constructor.
(define-constructor unordered-map ((obj unordered-map)) #|...|#)

; move constructor.
(define-constructor unordered-map ((ref remove-reference)) #|...|#)

; constructor with initializer-list.
(define-constructor unordered-map ((il initializer-list)) #|...|#)
(define-constructor unordered-map ((il initializer-list) (n integer)) #|...|#)
(define-constructor unordered-map ((il initializer-list) (n integer) hasher) #|...|#)
(define-constructor unordered-map ((il initializer-list) (n integer) hasher key-eql) #|...|#)

 

で、ここからつい色気を出して以下のようにしたくなる。つまり、hasherkey-eql 部分をオプショナル引数にするのだ‥‥‥しかし、これはハマるパターンだ。

(declare-constructor unordered-map (0 1 1-3 2 2-4 3-5))

; normal constructor.
(define-constructor unordered-map () #|...|#)
(define-constructor unordered-map ((n integer) &optional (hasher #'hasher) (key-eql #'operator_==)) #|...|#)

; range constructor.
(define-constructor unordered-map ((itr1 input-iterator) (itr2 input-iterator)) #|...|#)
(define-constructor unordered-map ((itr1 input-iterator)
                                   (itr2 input-iterator) (n integer)
                                   &optional (hasher #'hasher) (key-eql #'operator_==)) #|...|#)

; copy constructor.
(define-constructor unordered-map ((obj unordered-map)) #|...|#)

; move constructor.
(define-constructor unordered-map ((ref remove-reference)) #|...|#)

; constructor with initializer-list.
(define-constructor unordered-map ((il initializer-list)) #|...|#)
(define-constructor unordered-map ((il initializer-list) (n integer)
                                   &optional (hasher #'hasher) (key-eql #'operator_==)) #|...|#)

 

何がマズいかというと、CL-OVERLOAD はパラメータ数だけで最初の解決をしてしまうということだ。そしてその順序は declare-constructor のパラメータによって決まる。具体的には、上記の declare-constructor がどう展開されるかを見れば良い。どうなるか。こうなる。

(progn
 (defgeneric __new-unordered-map-0   ())
 (defgeneric __new-unordered-map-1   (v1))
 (defgeneric __new-unordered-map-1-3 (v1 &optional v2 v3))
 (defgeneric __new-unordered-map-2   (v1 v2))
 (defgeneric __new-unordered-map-2-4 (v1 v2 &optional v3 v4))
 (defgeneric __new-unordered-map-3-5 (v1 v2 v3 &optional v4 v5))
 (defun __new-unordered-map (&rest args)
   (let ((cnt (length args)))
     (cond ((=  0 cnt)   (apply #'__new-unordered-map-0   args))
           ((=  1 cnt)   (apply #'__new-unordered-map-1   args))
           ((<= 1 cnt 3) (apply #'__new-unordered-map-1-3 args))
           ((=  2 cnt)   (apply #'__new-unordered-map-2   args))
           ((<= 2 cnt 4) (apply #'__new-unordered-map-2-4 args))
           ((<= 3 cnt 5) (apply #'__new-unordered-map-3-5 args))
           (t (error "can't resolve overload for ~a" 'unordered-map)))))
 (define-compiler-macro __new-unordered-map (&rest args)
   (let ((cnt (length args)))
     (cond ((=  0 cnt)   `(,'__new-unordered-map-0   ,@args))
           ((=  1 cnt)   `(,'__new-unordered-map-1   ,@args))
           ((<= 1 cnt 3) `(,'__new-unordered-map-1-3 ,@args))
           ((=  2 cnt)   `(,'__new-unordered-map-2   ,@args))
           ((<= 2 cnt 4) `(,'__new-unordered-map-2-4 ,@args))
           ((<= 3 cnt 5) `(,'__new-unordered-map-3-5 ,@args))
           (t (error "can't resolve overload for ~a" 'unordered-map))))))

 

これだと、少なくとも (new stl:unordered-map #{...} 10) とした場合には失敗する。パラメータをきっかり2つ取るメソッド(つまり __new-unordered-map-2 )は入力反復子の範囲を取るものしかないからだ。つまり、CL-OVERLOAD の仕組みで動作させるには、オプショナル引数を使った例ではメソッドが足りないのだ。declare-constructor に与えるパラメータの順序を変えれば解決すると思うかもしれない。たとえば、最大数を基準に降順にするとか。以下のように。

(declare-constructor unordered-map (3-5 2-4 1-3 2 1 0))

 

これで解決する部分もあるが、しない部分も(多分)ある。そして、新たに発生する問題もある(かもしれない)。非常に注意深く考えればわかるし解決もできる(かもしれない)だろう。しかし、ぱっと見てわかるだろうか。少なくとも自分には(すぐには)わからない。そこに問題がある。試行錯誤を重ねて、全ての穴を塞ぐのにどれだけ時間がかかるか、そして結果的にメソッド数はいくつになるか、ひょっとしたら2番目の例の14個を超えるかもしれない(超えないかもしれないが)。そんなわけで、まぁこの問題に関して言えば2番目のやり方を取るつもりでいる。

結局のところ、これは CL-OVERLOAD が抱えている問題だ。(総称関数が担当しているところの)型によって解決する部分と、(CL-OVERLOAD が担当しているところの)パラメータ数によって解決する部分を上手に統合できれば、この問題をエレガントに解決できるだろうし、C++ の関数オーバーロードに(完全に同じではなくともかなり)近いものにできるだろう。しかし、それはマクロ・コンパイラマクロのレベルで可能だろうか。少なくとも総称関数が実行時解決であるという理由で、これは無理なのではないかと思う。自分は新しい Lisp 方言を作るつもりはないので、CL-OVERLOAD にせよ CL-STL にせよ、あくまで Common Lisp のライブラリとして作成したい。そんなわけで、まぁなんというか、困っているわけだ。

 

コメント

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

 

このページのタグ

Page tag : STLとその移植

Page tag : Common Lisp

 

 


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