2015-11-08-01-CL-STLにおけるファンクタの仕組み - project-enigma

2015-11-08-01-CL-STLにおけるファンクタの仕組み

>> Site top >> weblog >> 月別アーカイブ >> 2015年11月のlog >> 2015-11-08-01-CL-STLにおけるファンクタの仕組み

最終更新日付:2015/11/08 20:22:19


CL-STLにおけるファンクタの仕組み

2015 年 11 月 08 日

さて、今回は CL-STL におけるファンクタの仕組みを説明してみよう。いささか毛深いのでうんざりされないことを祈りつつ。

STL でアルゴリズムなどに処理を渡す場合、(アダプタをかますのでない限り)関数を(正確にはそのポインタをだが)直接渡すことができる。そして STL ではファンクタクラスは operator() をオーバーロードしているから、これまた直接インスタンスを渡すことができる。CL-STL でもできる限り同じようにしたい。まずはこれがスタート地点だ。

Common Lisp では、関数というのは funcall 可能だ。だが funcall は関数であって総称関数ではないから、なんらかの defclass されたクラスのインスタンスに対して funcall できるようにすることは不可能だ(と認識している)。だから、最初の毛深いポイントとして、CL-STL には stl:functor-call というものがある。これに Common Lisp の関数や CL-STL のファンクタを渡すことで、その処理を呼び出すことができる。以下のように。

(stl:functor-call #'< 0 1)
;=> T

(stl:functor-call (new stl:less) 0 1)
;=> T

 

しかし、stl:functor-call が総称関数かといえばさにあらず。これはマクロで、以下のように定義されている。

(defmacro functor-call (func &rest args)
  #+cl-stl-0x98
  (ecase (length args)
    (1 `(funcall (functor-function ,func) ,@args))
    (2 `(funcall (functor-function ,func) ,@args)))
  #-cl-stl-0x98
  `(funcall (functor-function ,func) ,@args))

 

0x11 よりも前の C++ では、ファンクタといえば(一部の例外を除いて)unary_function または binary_function だった。だから、:cl-stl-0x98*features* に登録されている状態で CL-STL をロードした場合、stl:functor-call でファンクタ(または関数)に渡せるパラメータの数は1または2に限定される。stl:functor-call はその部分を制御し、実質的にはパラメータ func に対して functor-function をかけ、その結果を funcall するコードを生成しているだけだ。そう、重要なのは functor-function なのだ。察しはついているだろうが、これが何かを説明することにしよう。

stl:functor-function は総称関数だ。パラメータを1つとり、それが cl:function の場合はパラメータをそのまま返す。

(defgeneric functor-function (func))
(defmethod  functor-function ((func cl:function))
  func)

 

そういうワケなので、CL-STL のファンクタは stl:functor-function に応答して funcall 可能な関数やクロージャを返さなければならない。軽く先走っておくとしよう。ファンクタのための stl:functor-function はどうなっているかと言うと、次のようになっている。

(defmethod functor-function ((func functor))
  (__functor-closure func))

 

stl:functor とは何か、その詳細はもう少し後に説明するとして、先に「なぜ処理を呼び出すためだけにこんな毛深い仕組みになっているのか」という疑問に対する説明(の一部)を書いておこう。

総称関数呼び出しがどれくらいのコストになるのか詳しくは知らないのだけれど、直接的な関数呼び出しよりも遅いことは間違いないだろう。アルゴリズムに処理を渡す場合、そのほとんどは内部にループを抱えている。そのループ内部で毎回 functor-call するのは、当然ながら毎回総称関数呼び出しのコストを負担することになる。以下はそのように実装した場合の for-each の例だ。

(defmethod for-each ((first input-iterator) (last input-iterator) func)
  (with-operators
      (let ((func (clone func)))
        (if (_== first last)
            func
            (for (((itr (clone first))) (_/= itr last) ++itr :returns func)
              (functor-call fnc *itr))))))

 

まだ説明していない事項がいくつかあるのでコードの詳細は理解しなくてもいい。ループは最後の2行で、その内部で functor-call していることがわかってもらえれば良い。この呼び出しコストを抑えるために、以下のようにすることができる。

(defmethod for-each ((first input-iterator) (last input-iterator) func)
  (with-operators
      (let ((func (clone func)))
        (if (_== first last)
            func
            (let ((fnc (functor-function func)))
              (for (((itr (clone first))) (_/= itr last) ++itr :returns func)
                (funcall fnc *itr)))))))

 

こうなっていれば、総称関数呼び出しのコストをループの外側に追い出すことができる。CL-STL のアルゴリズムは、全てこのような書き方をしている。これが、ファンクタの仕組みが毛深い理由のひとつだ。

もうひとつの(変な言い方だが)毛深さは、パラメータの「値渡し」に関わるものだ。C++ では、ポインタ渡しや参照渡しでない限り、パラメータは値で渡される。値で渡すというのは、コピーを(作って)渡すということだ。反復子も、ファンクタも、STL ではコピーが渡される。CL-STL が STL と同じように書いて同じ挙動を示すためには、これらのパラメータはコピーされなければならない。しかし、自動的にコピーすることは残念ながらできない。そのために、CL-STL では clone という仕組みを用いている。これは CL-OPERATOR が規定しているものだ(CL-OPERATOR が CL-STL から分離される以前は CL-STL の機能だった)。

見てみよう。CL-OPERATOR の clone は以下のように宣言されている。デフォルトでは全てのパラメータに対して、渡されたモノをただ返すだけだ。値渡しを実現したいクラスの場合、operator_clone の実装を追加することになる。

(defgeneric operator_clone (obj))
(defmethod  operator_clone (obj) obj)

(defmacro clone (obj)
  `(operator_clone ,obj))

 

CL-STL のアルゴリズムなどがパラメータとして反復子やファンクタを受け取った場合、原則として clone によるコピーを行なう。もちろん、本当にコピーをする場合はクラスオブジェクトのアロケーションが発生するため、必要がない場合はコピーをしない。値のコピーが実際に別のインスタンスを生み出す必要があるようなファンクタでは、operator_clone の実装を追加し、その時点で保有しているデータなどをコピーした別のインスタンスを作成して返す必要がある。

ここで、ちょっと「必要がない場合はコピーをしない」という部分の実例を見ておこう。先程の for-each の例にもう一度登場願おう。

(defmethod for-each ((first input-iterator) (last input-iterator) func)
  (with-operators
      (let ((func (clone func)))
        (if (_== first last)
            func
            (let ((fnc (functor-function func)))
              (for (((itr (clone first))) (_/= itr last) ++itr :returns func)
                (funcall fnc *itr)))))))

 

for-each は結果として与えれらたファンクタのコピーを返す仕様になっているから、ファンクタについては何があろうとコピーが必要だ。だから (clone func) は無条件に実施される。一方で与えられたシーケンスが長さゼロの場合は反復子をコピーする必要はないから、(clone first) は必要性が確定するまでは実施されないし、全く移動することがない last についてはまったくコピーが作成されない。「必要がない場合はコピーをしない」というのは大体こういうことだ。

実際問題として、ファンクタが「コピー」をサポートしたくなるような局面というのはほとんど存在しない。まともな設計をしていれば、ファンクタは大抵の場合純粋関数として作成できるからだ。仮にパラメータ以外の何かを参照するとしても、パラメータを含め全ての参照対象を定数として扱う。だが、状態を持ち、それを変更し、コピーをサポートするようなファンクタを作成したい場合が無いとは言えないし、STL でそれができるなら CL-STL でもできるようにしなければならない。そんなわけで、ファンクタの仕組みは毛深い‥‥‥そういうわけだ。

さて、残すところは実際のファンクタの構造やその作成の話だ。stl:functor やらが今回のコード例に出てきたが、その詳細の説明が残っている。しかし、今回はちょっと長くなってしまったし、続きは次回に持ち越すとしよう。

 

コメント

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

 

このページのタグ

Page tag : STLとその移植

Page tag : Common Lisp

 

 


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