Zaawansowane CPP/Wykład 11: Funktory

11.1 Wstęp

Na poprzednim wykładzie prezentowane były inteligentne wskaźniki, czyli obiekty które rozszerzają pojęcie zwykłego wskaźnika. Na tym wykąadzie będę omawiał obiekty, które stanowią rozszerzenie pojęcia wskaźnika do funkcji. Motywacja wprowadzenia takich obiektów funkcyjnych jest jednak inna. Funkcje obiektami nie są i wskaźniki do nich nie mają kłoptów z prawami własności, współdzieleniem referencji, itp. Same wskaźniki do funkcji są obiektami ale typów wbudowanych (lub raczej typów złożonych). Możemy je kopiować, przepisywać, przekazywać do funkcji, ale nie mamy nad tym kontroli.

Obiekty funkcyjne posiadaja składnię wywołania funkcji, ale są też pełnoprawnymi obiektami, mogą więc posiadać stan, konstruktory, destruktory i inne metody, jak również typy stowarzyszone, no i oczywiście posiadają też swój własny typ. Te dodatkowe informacje pozwalają implementowanie wielu ciekawych rozwiązań niedostępnych dla zwykłych funkcji i wskaźników do nich.

11.2 Funkcje, wskaźniki i referencje do funkcji

11.2.1 Typy funkcyjne

Zanim zajmiemy się bardziej skomplikowanymi obiektami jakimi są funktory chciałbym najpierw wyjaśnić kilka faktów dotyczących funkcji i wskaźników do nich. Jak już wspomniałem w poprzednim podrozdziale funkcje nie są obiektami. Nie można ich kopiować ani przypisywać do siebie:

void f(double x) {};

void  g(double) = f; niedozwolone
void h(double);
h=f; niedozwolone

Funkcje posiadają jednak typ. Typ funkcji (nazywany typem funkcyjnym) jest określony przez typ jej wartości zwracanej i typy jej argumentów. Typy funkcyjne możemy używać np. w poleceniu typedef

typedef void f_type(double) 

definiuje f_type jako typ funkcji o jednym argumencie tyuu double i nie zwracającej żadnej wartości. Taki typ ma jednak ograniczone zastosowanie, możemy go używać do deklarowania, ale nie definiowania innych funkcji:

f_type g;

Typ funkcyjny może też być użyty jako parametr szablonu:

template<typename F> Function {
F _fun;
};
Function<void (double)> 

Niewiele jednak będziemy mieli pożytku z pola _fun, bo jak już widzieliśmy, nie będziemy w stanie nic do niego przypisać ani go zainicjalizować.

Możemy również używać typów funkcyjnych w deklaracjach argumentów funkcji:

double sum(double (double),...)

oznacza że funkcja sum oczekuje jako pierwszego argumentu funkcji zwracającej double o jednym argumencie typu double. Ten zapis jest jednak mylący! W rzeczywistości nie można przekazać funkcji jako argumentu wuwołania i dlatego w deklaracjach argumentów typ funkcyjny jest automatycznie zamieniany na typ wskaźnika do funkcji i powyższa deklaracja jest równoważna deklaracji:

double sum(double (*)(double),...)

11.2.2 Wskaźniki do funkcji

Wskaźniki do funkcji są normalnymi obiektami i mogą być kopiowane i przypisywane:

void f(double x) {};

void  (*g)(double) = &f;
void (*h)(double);
h=&f;
(*h)(0.0);
(*g)(1.0); 

C++ posiada wygodną własność, która jednak zwiększa konfuzję pomiędzy funkcjami i wskaźnikami do nich. Otóż operatory * i & są aplikowane automatycznie do funkcji i powyższy kod można zapisać jako:

void f(double x) {};

void  (*g)(double) = f;
void (*h)(double);
h=&f;
h(0.0);
g(1.0); 

Jest to dość wygodne ale powoduje, że część ludzi słabo rozróżnia funkcje od wskaźników do nich (Państwo oczywiście już do nich nie należą :).

11.2.3 Referencje do funkcji

Żeby już skończyć ten temat i zupełnie zamieszać państwu w głowach napiszę że można też definiować referencje do funkcji:

void f(double x) {};
typedef void f_type(double)

f_type  &g  = f; 
f_type  &h  = g;
const f_type  &ch = g; równoważne z wyrażeniem f_type &ch  = g;
h=g; niedozwolone  h jest refencją do stałej

Należy dodać że typ const f_type & nie jest obsługiwany przez kompilator g++-3.3.

11.2.4 Dedukcja typów funcyjnych

Ponieważ funktory i funkcje często przekazywane są jako argumenty wywołania szablonów, ktorych typ podlega dedukcji, warto wiedzieć jak ten mechanizn rozpoznaje typ przekazywanej funkcji. Rozważmy najpierw następujacą definicję:

template<typename  F> test(F f) {
  F _fun(f);
}

Jeśli teraz wywołamy

 void (*g)(double) = f ;
 void (&h)(double) = f;

test(f);          F = void (*)(double)
test(g);          F = void (*)(double)
test(h);          F = void (*)(double)

to w każdym przypadku typ F zostanie wydedukowany jako wskaźnik do funkcji void (*)(double).

Jeśli przypomnimy sobie że argumenty do funkcji można dla oszczędności przekazywać jako referencje do stałych, to możemy napisać:

template<typename  F> test(const F &f) {
  F _fun(f);
}

czeka nas jednak niepospodzianka, kod

 void (*g)(double) = f ;
 void (&h)(double) = f;

test(f);          F = void ()(double), nie skopmpiluje  się
test(g);          F = void (*)(double)
test(h);          F = void ()(double) nie skompiluje się

zachowuje się już inaczej, w przypadku przekazanie funkcji lub referencji do funkcji, wededukownym typem będzie typ funkcyjny. Ponieważ nie można inicjalizować zmiennych typu funkcyjnego, wyrażenie F _fun(f) się nie skompiluje. Nie będzie kłopotów jeśli przekażemy wskaźnik do funkcji, ale tym razem musimy to zrobić jawnie, nie następi atomatyczna konwersja nazwy funkcji na wskaźnik do niej.

Można by przedefiniować funkcję test następująco:

template<typename  F> test(const F &f) {
  F *_fun(f);
}

Teraz wywołania

test(f);          F = void ()(double)
test(h);          F = void ()(double)

skompilują się, ale nie skompiluje się linijka

test(g);          F = void (*)(double)

bo pole _fun stanie się typu void (**)(double). Kompilator g+-3.3 nawet tego kodu nieskompiluje bo nie zezwala na referencje do stałych typów funkcyjnych.

Widać więc że najlepiej przy przekazywaniu funkcji najlepiej używać wywołania przez wartość, które i tak jest automatycznie konwertowana na przekazywanie wskaźnika do funkcji.

11.3 Obiekty funkcyjne

Definiowanie własnych obiektów funkcyjnych jest możliwe dzięki możliwości przeładowania operatora wywołania (będziemu go też nazywać operatorem nawiasów): operator()(...). Np.

struct Sin {
double operator()(double x) {return sin(x);}
}

Z obiektów typu Sin możemy teraz korzystać jak z funkcji:

Sin c_sin;
c_sin(0);

Nie jest być może porywający przykład, ale głownym powodem używania obiektów funkcyjnych jest to, że mogą posiadać stan. Skorzystamy z tego, aby umożliwić wybór typu argumentu funkcji sin. Zwyczajowo kalkulatory (ktoś wie co to jest?) zezwalają na podawanie argumentów funkcji trygonometrycznych w radianach, stopniach lub gradusach. Możemy to zaimplemetować następująco:

class Sin { 
public:
  enum arg {radian,degree,grad};
  Sin(arg s = radian):_state(s) {};

  void set_radians() { _state=radian;}
  void set_degrees() {_state=degree;}
  void set_grads()   {_state=grad;}

  double operator()(double x) {return sin(conv(x));}
private:
  arg _state;
  double conv(double x) {
    switch (_state) {
    case radian: return x;
    case degree : return x*(M_PI/180.0);
    case grad   : return x*(M_PI/200.0);
    }
  }  
};

Nie jest to najwydajniejsza implementacja, bo za każdym wywołaniem funkcji sin wykonywana jest insrukcja switch. Przerobimy ją więc na:

class BetterSin {  
public:
  enum arg {radian,degree,grad};

  void set_radians() { _conv=&BetterSin::to_radians;}
  void set_degrees() { _conv=&BetterSin::to_degrees;}
  void set_grads()   { _conv=&BetterSin::to_grads;}

  double operator()(double x) {return sin( (this->*_conv)(x) );}

  BetterSin(arg s = radian) {
    switch (s) {
    case radian: set_radians();break;
    case degree : set_degrees();break;
    case grad   : set_grads();break;
    }
  }
private:
  double (BetterSin::* _conv)(double);
  double to_radians(double x) {return x;};
  double to_degrees(double x) {return x*(M_PI/180.0);};
  double to_grads(double x) {return x*(M_PI/200.0);};
};

11.3.1 Wskaźniki do metod (funkcji składowych)

Ten przykład, który powinien działać szybciej, ilustruje ponadto użycie wskaźników do funkcji składowych (metod). Roóżnice pomiedzy wskaźnikami do funkcji i wskaźnikami do metod są opisane w D. Vandervoorde, N. Josuttis: "C++ Szablony, Vademecum profesjonalisty" oraz "objectmodel", tutaj zwrócę tylko uwagę na różnice w ich używaniu. Jak już pisałem wskaźniki do funkcji można używać na skróty, bez jawnego wywoływania operatorów & i *: W przypadku wskaźników do metod, musimy pobierać adres jawnie i dereferencjonować go przed wywołaniem. Ponadto każda metoda ma dodatkowy niejawny argument, którym jest wskaźnik na obiekt przez który została ona wywołana, dlatego wywołując metodę poprzez wskaźnik też musimy ten argument podać:

struct X {
  void f(){std::cout<<"f1"<<"";};
};
main(){
  typedef void (X::*f_ptr)();
    //f_ptr pf1=X::f; bład kompilacji
  f_ptr pf1=&X::f;
    X x;
  X *px = new X;
    (x.*pf1)();
    (px->*pf1)();
}

11.3.2 Adaptery funktorów

Obiekty mogą jednak posiadać więcej informacji niż tylko swój stan, mogą zawierać również informacje o typie. Przede wszystkim funktory same posiadają typ, konsekwencje tego faktu omówię poźniej, teraz zajmę się typami stowarzyszonymi. Nasuwająca się od razu możliwość, to stowarzyszenie z funktorem typu wartości zwracanej oraz typów jego argumentów. Można stowarzyszyć również informację o liczbie argumentów. W przypadku szablonu Sin i BetterSin moglibyśmy dodać

typedef double result_type;
typedef double argument_type;
enum {n_arguments = 1}; 

Taki schemat nazewnictwa nie najlepiej się rozszerza na większą ilość argumentów, ale właśnie takie definicje typów są wymagane dla jednoargumentowych obiektów funkcyjnych w STL. W celu ułatwienia tworzenia własnych funktorów spełniających te wymagania dostarczony jest szablon klasy z której można dziedziczyć:

template <class Arg, class Result>
struct unary_function {
typedef Arg argument_type;
typedef Result result_type;
};

czyli moglibyśmy również napisać:

class BetterSin: public unary_function<double,double> {...}; 

STL nie wymaga definiowania liczby argumentów.

Podobnie zdefiniowany jest szablon dla funkcji dwuargumentowych:

template <class Arg1, class Arg2, class Result>
struct binary_function {
typedef Arg1 first_argument_type;
typedef Arg2 second_argument_type;
typedef Result result_type;
};

Opis bardziej uniwersalnego schematu obiektów funkcyjnych, uwzględniający funktory z dowolną ilością argumentów znajduje się w D. Vandervoorde, N. Josuttis: "C++ Szablony, Vademecum profesjonalisty". Dodajmy że do określenia typów argumentów można użyć listy typów przedstawione na wykładzie {[##|Uzupelnic |]}, razem z szablonem indeksowania (zobacz Alexandrescu: "Nowoczesne projektowanie").

My jednak pozostaniemy na razie przy schemacie z STL. Trzeba jasno powiedzieć że obiekty funkcyjne uzywane przez algorytmy STL, nie muszą posiadać wymienionych typów stowarzyszonych, w szczególności mogą to być zwykłe funkcje. Ale, jeśli takie typy posiadają, to można używać ich w adapterach funkcji.

Adaptery funkcji to funktory które w jakiś sposób modyfikują działanie innych funktorów. STL definiuje dość skromny wybór adapterów, ale na szczęście istnieje wiele innych niezależnych źródeł, w szczególności SGI i boost.

Jak działają adaptery wyjaśnie na przykładzie adaptera binder1st z STL. binder1st reprezentuje funktor jednoargumentowy, powstały przez zastąpienie pierwszego argumentu podanego funktora dwuargumentowego podaną wartością. Rozważmy następujący przykład:

class Cov:public std::binary_function<double,double,double> {
  const double _ax,_ay,_axy;
public: 
  Cov(double ax,double ay,double axy):_ax(ax),_ay(ay),_axy(axy) {};
  double operator()(double x,double y) {return _ax*x*x+_ay*y*y+_axy*x*y;}
};

main() {
  Cov f(1.0,2.0,2.0);

  std::cout<<f(1.0,1.0)<<"";
  std::cout<<f(1.0,2.0)<<"";

  std::cout<<::bind1st(f,1.0)(1.0)<<"";
  std::cout<<::bind1st(f,1.0)(2.0)<<"";
}

Działanie adaptera nie trudno zrozumieć, jeśli się zrozumiało działanie szablonów wyrażeń (wykład {[##|Uzupelnic |]}). Szablon binder1st można zdefiniować nastepująco:

template<typename F> class binder1st {
  typedef  typename F::first_argument_type  bind_type;
  typedef  typename F::second_argument_type first_argument_type;
  typedef  typename F::result_type result_type;

  const bind_type _val;
  F _op;
  public:
  binder1st(F op,bind_type val):_op(op), _val(val) {};

  result_type operator()(first_argument_type x) {
    return op(_val,x);
  }
};

Podobnie jak w przypadku szablonów wyrażeń będziemy jeszcze potrzebowali funkcji która wytworzy nam taki obiekt, to zadanie spełni nam funkcja bind1st:

template<typename F> 
binder1st<F> 
bind1st(F op,typename F::first_argument_type val) {
return binder1st<F>(op,val);
} 

Na podstawie tego przykładu mam nadzieję że już łatwo państwu będzie wywnioskować implementację pozostałych adapterów STL: binder2nd, unary_negate i binary_negate.

STL dostarcza ponadto dodatkowe adaptery które opakowywują zwykłe wskaźniki do funkcji i wskaźniki do metod tak, aby można było ich użyć razem z adapterami obiektów.

11.3.3 Składanie funktorów

Żaden z adapterów zaimplemntowanych w STL nie umożliwia składania funktorów, czyli tworzenia funktora poprzez połączenie dwu lub wiecej innych funktorów. Oczywiście istnieje wiele możliwych sposobów składania funkcji, w pozycji STL autor wyróżnia pięć takich adapterów realizujących następujące złożenia:

Uzupelnij tytul

$f(g(x))$	({unary_compose})
$f(g(x,y))$
$f(g(x),h(x))$	({binary_compose})
$f(g(x),h(y))$

Dwa z nich (unary_compose i binaru_compose) są zdefiniowane w implementacji STL firmy SGI, a więc dostępne razem z kompilatorem g++.

Implementacja ich jest analogiczna do implementacji binder1st, ale dla wprawy podam tu możliwą implementację złożenia $f(g(x,y))$.

template<typename F,typename G> class compose_f_gxy_t {
  typedef typename F::result_type result_type;
  typedef typename G::first_argument_type  first_argument_type;
  typedef typename G::second_argument_type  second_argument_type;

  F _f;
  G _g;

public:
  compose_f_gxy_t(F f,G g):_f(f),_g(g) {};

  result_type operator()(first_argument_type x,
                         second_argument_type y) {
    return _f(_g(x,y));
  }

};

template<typename F,typename G> 
compose_f_gxy_t<F,G>
compose_f_gxy(F f,G g) {return  compose_f_gxy_t<F,G>(f,g);};

Używamy tego funktora następująco:

std::cout<<compose_f_gxy(
                         __gnu_cxx::compose1(std::ptr_fun(exp),
                                       std::negate<double>()),
                         f)(1.0,1.0)<<"";

Powyższe wyrażenie efektywnie produkuje funktor obliczający $\exp (-f(x,y))$ gdzie $f(x,y)=a_x{x}^2+a_y{y}^2+a_{xy}x*y$. Wykorzystaliśmy w nim szereg konstrukcji

1. Adapter realizujący złożenie dwu funkcji jednoargumentowych unary_compose (zwrócony przez funkcję compose1()) dostarczony wraz z kompilatorem g++.
2. Za pomocą tego adaptera złożyliśmy funkcję $\exp$ ze standardowej biblioteki C z obiektem funkcyjnym std::negate<double> predefiniowanym w STL.
3. Aby móc użyć funkcji $\exp$ w adapterze musiałem ją opakować za pomocą adaptera std::ptr_fun.
4. Funkcję $\exp (-f)$ złożyłem z $f(x,y)$ za pomocą compose_f_gxy.

Na powyższym przykładzie widać siłe, ale i też pewnie niedogodności używania funktorów, przynajmniej w takiej postaci, jak zdefiniowanej w STL. Podany kod jest dość rozwlekły i mało czytelny, co gorsza, tak zdefiniowanego funktora nie możemy łatwo przechowa w jakiejś zmienniej, bo jego typ też jest bardzo skomplikowany (zobacz zadania).

11.3.4 Klasy cech dla funktorów

Programowanie uogólnione za pomocą funktorów mogłoby być prostsze gdybyśmy posiadali jakiś uniwersalny sposób dostępu do informacji o nich. Taki uniwersalny szkielet funktora z możliwościami introspekcji jest opisany w {szablony} rozdz. 22. Tutaj zaprezentuję tylko możliwą implementację klasy cech dostarczającej informacji o funktorach w stylu STL i wskaźnikach na funkcje.

Załóżmy że mamy jakiś typ {F} i chcemy się dowiedzieć czy jest on funktorem czy nie. W C++ nie mamy możliwości sprawdzić czy dana klasa posiada operator nawiasów czy nie. Funktory będziemy więc rozpoznawać po posiadanych typach stowarzyszonych. Skorzystamy z zasady rozstrzygania przeciążenia szablonów funkcji: "nieudane podstawienie nie jest błędem". Podobnie jak w przypadku szablonu {Is_class} Uzupelnic | wykorzystamy dwa typy:

template<typename F> funktor_info { typedef char one; typedef struct {char a[2];} two;

i dwa szablony funkcji:

template<typename C> one test_arg(typename C::argument_type *) ; template<typename C> two test_arg(...) ;

za ich pomocą możemy sprawdzić czy dany typ {F} posiada zdefiniowany stowarzyszony typ {argument_type}:

enum {has_argument = (sizeof(test_arg<F>(0))==sizeof(one))};

podobnie możemy zdefiniować jeszcze trzy stałe logiczne:

enum {has_result = (sizeof(test_res<F>(0))==sizeof(one))}; enum {has_first_argument = (sizeof(test_arg1<F>(0))==sizeof(one))}; enum {has_second_argument = (sizeof(test_arg2<F>(0))==sizeof(one))};

Pary funkcji {test_...} są zdefiniowane analogicznie do {test_arg}. Za pomocą tych stałych możemy wyrazić inne własności obiekty {F} np:

enum {has_one_argument = has_argument && !has_first_argument && !has_second_argument}; enum {has_two_arguments = has_first_argument && has_second_argument && !has_argument}; enum {has_no_arguments = !has_argument && !has_first_argument && !has_second_argument}; enum {is_generator = has_result && has_no_arguments}; enum {is_unary_function = has_result && has_one_argument}; enum {is_binary_function = has_result && has_two_arguments}; enum {is_functor = is_generator || is_unary_function || is_binary_function}; enum {is_function= false};

Funkcje możemy rozpoznawać za pomocą specjalizacji częściowych:

template<typename A1,typename A2 , typename R > struct functor_info<R (*)(A1,A2) >{

enum {has_result = true}; enum {has_argument = false}; enum {has_first_argument = true}; enum {has_second_argument = true}; /*... tak samo jak powyżej */ };

Podobnie dla funkcji zero i jednoargumentowych. Mając już klasę {functor_info} można zdefiniować klasę

template<typename F,int n_args = functor_info<F>::n_args> struct functor_traits ;

i jej specjalizacje:

template<typename F> struct functor_traits<F,2> { typedef typename F::result_type result_type; typedef typename F::first_argument_type arg1_type; typedef typename F::second_argument_type arg2_type; typedef std::binary_function<arg1_type,arg2_type,result_type> f_type; enum {n_args=2}; }; template<typename F> struct functor_traits<F,1> { typedef typename F::result_type result_type; typedef typename F::argument_type arg1_type; typedef empty_type arg2_type; typedef std::unary_function<arg1_type,result_type> f_type; enum {n_args=1}; }; template<typename F> struct functor_traits<F,0> { typedef typename F::result_type result_type; typedef empty_type arg1_type; typedef empty_type arg2_type; typedef generator<result_type> f_type; enum {n_args=0}; };

podobnie dla wskaźników do funkcji

template<typename R,typename A1,typename A2> struct functor_traits<R (*)(A1,A2),2> { typedef R result_type; typedef A1 arg1_type; typedef A2 arg2_type; typedef std::binary_function<arg1_type,arg2_type,result_type> f_type; enum {n_args=2}; }; /* ... */

Jeśli teraz użyjemy klasy {functor_traits} w definicji adaptera {binder1st}:

template<typename F> class binder1st { typedef typename functor_traits<F>::arg1_type bind_type; typedef typename functor_traits<F>::arg2_type first_argument_type; typedef typename functor_traits<F>::res_type result_type;

const bind_type _val; F _op; public: binder1st(F op,bind_type val):_op(op), _val(val) {};

result_type operator()(first_argument_type x) { return _op(_val,x); } };

template<typename F> binder1st<F> bind1st(F op,typename functor_traits<F>::arg1_type val) { return binder1st<F>(op,val); };

To bedziemy mogli używać go z wskaźnikami do funkcji bez konieczności opakowywania ich w adapter {ptr_fun}.

Można stosunkowo łatwo rozszerzyć kod adaptera {binder1st} tak, aby można go było używać zarówno do funktorów dwu jak i jednoargumentowych.

11.3.5 Biblioteki funktorów

Kod przedstawiony w poprzednim podrozdziale daje, mam nadzieję, pewne wyobrażenie o tym, jak można implemetować bardziej zaawansowane funktory i operacje na nich. Widać jednak, że nie jest to zbyt proste: kod szybko staje się skomplikowany i trudny do debugowania.

Na szczeście istnieją już gotowe implementacje. Jak już wspomiałem propozycje bardziej rozwiniętego szkieletu funktorów znajdą państwo w {szablony} rozdz. 22. Ponadto biblioteka {boost} oferuje szereg narzędzi, w tym biblioteki {lambda} i {bind}. O tej pierwszej już wspominałem przy omawianiu szablonów wyrażeń. Biblioteka {lambda} dostarcza funkcjonalności adapterów {bind...} i {compose...} za pomocą wyrażenia jednego wyrażenia {bind}. Korzystając z niego, można kod podany w poprzednim podrozdziale zapisać następująco:

1. include<boost/lambda/lambda.hpp>
2. include<boost/lambda/bind.hpp>

using namespace boost::lambda;

double x=1; std::cout<<bind(f,1.0,_1)(x)<<""; std::cout<<bind(f,1.0,_1)(make_const(2.0))<<""; /* wyrażenie z biblioteki lambda nie przyjmują stałych stąd konieczność użycia zamienej x, lub wyrażenia makeconstant()

• /

std::cout<<bind(exp,-bind(f,_1,_2))(x,x)<<"";