Lambda kifejezések

A függvény az egyik legalapvetőbb absztrakciós eszközünk a programozásban. Segítségével tudjuk az algoritmikai egységeket, részfeladatokat absztrahálni: különválasztani egymástól, névvel ellátni, több helyről is elérhetővé tenni. A legegyszerűbb programjainkat is függvényekből építjük fel.

Gyakran előfordul, hogy egy függvénytörzs valamely részét szeretnénk kicserélni, például egy rendező algoritmusnak egy rendezési relációt szeretnénk megadni paraméterként. Ebben az esetben a függvénynek paraméterként átadott adat egy programrész: egy kifejezés, amelyet ki kell értékelnie. Másképp fogalmazva, a függvénynek átadott adat maga is egy függvény. A függvényekkel, függvényeken dolgozó függvényeket magasabb rendű függvényeknek nevezzük (higher order procedures). Ilyen a következő JavaScript kódrészlet deriváló függvénye is.

function deriv(f) {
    var dx = 0.001;
    function derived(x) {
        return (f(x+dx) - f(x)) / dx;
    }

    return derived;
}

Tehát függvény is lehet paraméter, és lehet akár visszatérési érték is. Láttuk a funarg problémák kapcsán, hogy az ilyesmi implementációja nem triviális. A példában a derivált függvénynek látnia kell azt a környezetet, ahol létrehozták. A dx és az f változó értékét ismernie kell a meghívása pillanatában is, pedig a paramétere csak az x.

A C és a C++ nyelvekben a függvények csak másodrendű szerepet töltenek be: ez a két nyelv közvetlenül nem képes arra, hogy a függvényeket adatként kezelje. A C-ben a függvényekre mutató pointereken keresztül meg tudunk hivatkozni egy lefordított kódrészletet, de a függvényhívásnak kontextusa nincs: csak a konkrét függvényparaméterekkel tudunk kommunikálni vele.

C++-ban az ehhez hasonló működést tudjuk imitálni olyan objektumokkal, amelyek rendelkeznek függvényhívó operátorral (functor). Ezekbe az objektumokba akármilyen adatot betehetünk, a használatnál pedig végülis mindegy, hogy egy függvényre mutató pointerről vagy objektumról van szó – ha használhatjuk rajta a kerek zárójel () operátort, függvénynek fogjuk érzékelni. Ezt a módszert általában sablonfüggvényekkel szoktuk használni. A nehézsége, hogy nekünk kell végiggondolnunk a memóriakezelést. Van a függvénynek kontextusa? Ha igen, mely változókat kell látnia? Mikor jönnek létre ezek a változók, mikor szűnnek meg? Referencia vagy érték szerint kell őket látni?

A C++11 lambda kifejezés nyelvi eleme, és a functional fejlécfájl sablonjai ezen problémák megoldásában segítenek.

function deriv(f) {
    var dx = 0.001;
    function derived(x) {
        return (f(x+dx) - f(x)) / dx;
    }
    return derived;
}

Az STL-ben rengeteg alapalgoritmushoz találunk sablon implementációt. Az std::for_each egy iterátorok által megadott tartomány összes elemére meghív egy függvényt, az std::copy tartományok között másol, az std::count_if bizonyos tulajdonságú elemeket számlál meg, az std::accumulate összegzi az elemeket, az std::sort rendez, és így tovább. Lássunk néhány (kitenyésztett) példát ezek használatára!

Az std::ref() függvény

Az STL std::for_each függvénysablonja egy tartomány összes elemére meghívja a harmadik paraméterként megadott függvényt:

template<class InputIterator, class Function>
  Function for_each(InputIterator first, InputIterator last, Function fn)
{
    while (first != last) {
        fn(*first);
        ++first;
    }
    return std::move(fn);
}

Észrevehetjük, hogy ez értékként veszi át a meghívandó függvényt. Ha sima függvényről van szó (azaz globális függvényre mutató pointerről), akkor ez lényegtelen. Ha azonban függvényobjektumról, akkor viszont fontos lehet. Tegyük fel, hogy van egy függvényobjektumunk, ami a neki paraméterként átadott értékeket sorszámozva írja ki:

class IntPrinter {
  private:
    int count = 0;
  public:
    void operator() (int i) {
        std::cout << ++count << ". " << i << std::endl;
    }
};

int main() {
    int arr1[] = { 5, 9, 2, 4 };
    int arr2[] = { 33, 97, 41, 73, 14 };
    std::for_each(std::begin(arr1), std::end(arr1), IntPrinter{});
    std::for_each(std::begin(arr2), std::end(arr2), IntPrinter{});  // :(
}

Ha a számok több tartományból vannak, két for_each hívásra van szükség. Ezekhez azonban nem hozhatunk létre különálló IntPrinter objektumokat, mert mindegyiknél újraindul a számozás. Ha egyetlen IntPrinter objektumunk van, az érték szerinti paraméterátadás akkor is bekavar, mivel azt az egyetlen egy objektumot mindig lemásolja a hívás, és mindig újraindul a sorszámozás. Ezt a problémát hivatott megoldani az std::for_each visszatérési értéke. Ezért adja vissza a megváltozott függvényobjektumot. Ebben a példában így kellene ezt használnunk:

int arr1[] = { 5, 9, 2, 4 };
int arr2[] = { 5, 8, 4, 7, 9 };
IntPrinter p;
p = std::for_each(std::begin(arr1), std::end(arr1), p); /* 1. 2. 3. 4. */
p = std::for_each(std::begin(arr2), std::end(arr2), p); /* 5. 6. 7. 8. 9. */

Van azonban egy másik megoldás is. Érezzük, arra lenne szükség, hogy az std::for_each függvénynek a p objektumot referencia szerint adjuk át, csak sajnos az úgy lett megírva, hogy érték szerint várja a függvényt. Ennek a problémának a megoldására való a C++11 std::ref() adaptere. Ennek paramétere egy becsomagolandó függvényobjektum referenciája; a visszatérési értéke pedig egy olyan funktor, amely minden hívást továbbít az eredeti függvényobjektumnak, de referenciával hivatkozza azt. Így az érték szerinti paraméterátadás nem fogja a p-t másolni:

int arr1[] = { 5, 9, 2, 4 };
int arr2[] = { 5, 8, 4, 7, 9 };
IntPrinter p;
std::for_each(std::begin(arr1), std::end(arr1), std::ref(p)); /* 1. 2. 3. 4. */
std::for_each(std::begin(arr2), std::end(arr2), std::ref(p)); /* 5. 6. 7. 8. 9. */

Az std::bind() függvény

Az alábbi kódban növekvő sorba rendezzük egy tömb elemeit.

#include <algorithm>
#include <iterator>
#include <iostream>

int main() {
    int arr[] = { 7, -4, 8, -3, -7, 9, 2, 4 };
    std::sort(std::begin(arr), std::end(arr));  // rendezés
    for (auto i : arr)
        std::cout << i << " ";
}

Az std::sort-nál alapértelmezett a növekvő sorrendbe történő rendezés. Ehhez az std::less osztálysablont példányosítja a tároló elemeinek típusával, és létrehoz a kapott osztályból egy objektumpéldányt: egy függvényobjektumot, amely az összehasonlításokat fogja végezni. A fent jelölt sor egyenértékű ezzel:

std::sort(std::begin(arr), std::end(arr), std::less<int>{});

Vizsgáljuk meg jobban az std::less sablont! Az std::less<int>{} objektum függvényhívó operátora kétparaméterű: a két összehasonlítandó egész számot veszi át. Tegyük fel, hogy meg szeretnénk számolni a tömbben a negatív számokat az std::count_if függvénnyel. Az arra képes, hogy megmondja, egy tartományban hány olyan elem van, amely megfelel egy feltételnek (predikátumnak, predicate). Érezzük, hogy ehhez valahogyan használható lenne az std::less, mert az megmondhatná, hogy kisebb-e a szám a nullánál. A probléma az, hogy az std::count_if egy unáris, egyparaméterű predikátumot vár, a számlálásban if (pred(x)) alakú a kód. Míg az std::less bináris, kétparaméterű predikátum, a rendezésben if (pred(x, y)) módon hívva.

Ez a probléma általánosítható: gyakran a bináris predikátumból unáris predikátumot szeretnénk létrehozni. Még általánosabban: egy valahány paraméterű függvényt nála kevesebb paraméterű függvénnyé szeretnénk alakítani, az előbbi függvény némelyik paraméterét fix értékre lekötve (bind). C++11-ben erre való az std::bind nevű variadikus függvény. Ez első paramétereként a manipulálandó függvényt kapja. Többi paramétereként pedig annyi értéket, amennyit az eredeti függvény várt. Vagy értékek helyett az std::placeholders::_1, _2... helyőrző szimbólumok valamelyikét, amelyek a megtartandó paramétereket helyettesítik. A sorrend a manipulált függvény paramétersorrendjével kell megegyezzen. A keletkező függvény annyi paraméterű lesz, ahány helyőrzőt használtunk; a többi paraméter a megadott konstansokkal lesz helyettesítve.

Visszatérve az eredeti problémára: hogy tudunk a less(x, y)-ból negative(x)-et csinálni? Egyszerűen, mert a negatív azt jelenti, hogy kisebb nullánál. Kódban: negative(x) ugyanaz, mint less(x, 0). Vagyis a less() első paramétere az lesz, amit a negative() kapott, a második pedig mindig 0. Az std::bind() segítségével könnyen létrehozható ez a függvény:

#include <functional>

auto less = std::less<int>{};
auto negative = std::bind(less, std::placeholders::_1, 0);      /* less(p1, 0) */

std::cout << negative(-1) << std::endl;  /* igaz */
std::cout << negative(1) << std::endl;   /* hamis */

int arr[] = { 7, -4, 8, -3, -7, 9, 2, 4 };
std::cout << std::count_if(std::begin(arr), std::end(arr), negative);   /* 3 db */

Az std::bind tetszőlegesen sok paraméterhez és értékhez használható (variadic template). Segítségével bármennyi érték bármilyen sorrendben átadható, pl.

using namespace std::placeholders;
auto less = std::less<int>{};

auto negative = std::bind(less, _1, 0);     /* negative(p1) → less(p1, 0) */
auto positive = std::bind(less, 0, _1);     /* positive(p1) → less(0, p1) */
auto greater = std::bind(less, _2, _1);     /* greater(p1, p2) → less(p2, p1) */

Az std::bind() visszatérési értékének típusát a szabvány nem adja meg, ezért egyszerűbb auto-t használni. Általában valami függvényobjektumról van szó. Ha kell, ez eltárolható egy std::function<F> objektumban, ahol F a keletkező függvény típusa, pl. bool (int, int) a fenti greater esetén, vagy bool (int) a negative esetén. Az std::function<> sablonról lentebb lesz szó. Az std::greater<> sablon meg egyébként beépítetten is létezik.

Az std::bind arra is jó, hogy egy osztály tagfüggvényét összekössük egy konkrét objektummal. Az így keletkező függvényobjektum önálló függvényként használható, nem csak objektummal együtt. Ehhez a bind első paramétere egy tagfüggvény mutató kell legyen, a második pedig az az objektum, vagy annak az objektumnak a címe, amelyikhez kötni szeretnénk azt. Például ha szeretnénk egy olyan unáris predikátumot (egyparaméterű funktort) létrehozni, amely akkor tér vissza igazzal, ha a paraméterként adott szám eleme egy halmaznak:

std::set<int> s1 = { 3, 6, 9, 12 };
auto element_of_s1 = std::bind(&std::set<int>::count, &s1, std::placeholders::_1);

std::cout << element_of_s1(3) << std::endl;
std::cout << element_of_s1(4) << std::endl;

Kis csalás a fenti kódban, hogy a set::count tagfüggvény nem igazzal vagy hamissal, hanem 1-gyel vagy 0-val tér vissza. Az element_of_s1(x) hívás visszatérési értéke megegyezik s1.count(x) visszatérési értékével. De logikai értékként tekintve ez egyenértékű a keresett válasszal.

A predikátumok írásakor sokszor nagyon kényelmetlen az, hogy a használatuk helyétől távol kell megírni egy függvényt. Vegyünk példának megint a rendezést! Az alábbi kód akkor lenne a legolvashatóbb, ha az std::sort() harmadik paramétereként egyszerűen beírhatnánk azt, hogy a > b, ahogy a range-based for() ciklus törzsébe is közvetlenül beírhattuk a kiírás műveletet:

#include <algorithm>
#include <iterator>
#include <iostream>

bool greater(int a, int b) {
    return a > b;
}

int main() {
    int arr[] = { 7, 4, 8, 3, 7, 9, 2, 4 };
    std::sort(std::begin(arr), std::end(arr), greater);
    for (auto i : arr)
        std::cout << i << " ";   // 9 8 7 7 4 4 3 2
}

A külön függvény távol van a kódban, és fölöslegesen látszik a globális névtérben. Ez az, amit megelégeltek a C++-ban, és a C++11-ben lett ennek kiváltására egy új nyelvi elem. Ennek neve lambda kifejezés (lambda expression). A fenti csökkenő sorrendű rendezés lambda kifejezés használatával így írható:

std::sort(std::begin(arr), std::end(arr),
          [](int a, int b) { return a > b; }
);

A „lambda” név a funkcionális programozásból ered, ahol a függvényeket a λ karakterrel szokás jelölni. Több olyan nyelv is van, ahol konkrétan a lambda kulcsszó a függvények definícióját jelzi. Ilyen értelemben a lambda kifejezés egy névtelen függvényt ad meg: egy függvényként használható objektumot hozunk létre. A példában ez az std::sort() harmadik paramétere, most szándékosan egy különálló sorba került. A kifejezés egyes részei az alábbiakat jelentik:

• []: a szögletes zárójelpár vezeti be a lambda kifejezést. Ez az ún. lambda introducer vagy capture clause, amelyről lentebb részletesen lesz szó.
• (int a, int b): ezek a létrehozott függvény paraméterei.
• { return a > b; }: ez pedig a függvény törzse.

Egy lambda függvénynek akárhány paramétere lehet. Ha nincs paraméter, akkor a formális paramétereket körbezáró, üres zárójelpár () akár el is hagyható. Az alábbi programrész két dobókocka összegével húsz dobást szimulál:

int dice[20];
std::generate(std::begin(dice), std::end(dice),
    [] { return rand()%6 + 1 + rand()%6 + 1; }
);

std::generate(): sorozatosan hívja a harmadik paraméterben megadott függvényt, és a visszatérési értékeket eltárolja a tartományba.

A visszatérési típust a lambdáknál általában nem kell megadni, az auto változómegadáshoz hasonlóan működik. A fordító olyan visszatérési értékűnek tekinti a lambdát, mint amilyen típusa a benne lévő return utasításnál megadott kifejezésnek van. Ha mást szeretnénk, akkor az trailing return type szintaxissal megadható. Az alábbi példákban egy const char * → std::string konverzió miatt, illetve érték helyett referenciával visszatérés miatt:

[] (int i) -> std::string { return i % 2 == 0 ? "paros" : "paratlan"; }

[] (int &a, int &b) -> int& { return a > b ? a : b; }

bool greater(int a, int b) {
    return a > b;
}
int main() {
    int arr[] = { 7, 4, 8, 3, 7, 9, 2, 4 };
    std::sort(std::begin(arr), std::end(arr), greater);
    for (auto i : arr)
        std::cout << i << " ";   // 9 8 7 7 4 4 3 2
}

std::sort(std::begin(arr), std::end(arr),
          [](int a, int b) { return a > b; } );

Észrevehetjük, hogy a lambda kifejezéssel függvényt definiálunk függvényben. Vajon mit jelent ez a változók láthatósága és élettartama szempontjából? Látja-e egyáltalán a lambda kifejezéssel megadott függvény az őt befoglaló függvény változóit? Ha látja, akkor a lambda kifejezés létrehozásának pillanatában, vagy a meghívás pillanatában tárolt értéküket látja, azaz érték vagy referencia szerint éri el őket? Mi lesz ezekkel a belül is használt változókkal, ha a külső függvény már visszatért?

Nézzünk meg néhány programrészletet, ahol ezek a problémák előjönnek! A lenti példában a belső függvény létrehozása után megváltoztatjuk az általa is hivatkozott j változó értékét. Kérdés, mit ír ki a kódrészlet: 2-t vagy 5-öt? Ha a lambda objektum érték szerint tárolja a változókat, akkor a létrehozáskori értéket fogja látni. Ha pedig referencia szerint, akkor a létrehozása után történt változásokat is érzékelni fogja.

int j = 2;
auto func = [] () { // ?
    return j;
};

j += 3;
std::cout << func();

A választás nem triviális, mert egyik sem jó minden esetben. Ha referencia szerint látja a változókat a függvény, akkor például a többszálúság esetén lehet gondunk. Az alábbi programrészben két külön tevékenységet indítanánk el párhuzamosan, amelyek mindketten a local nevű változón dolgoznak. Mi történik, ha ezek módosítják ennek az értékét? Hogyan függ a végrehajtás eredménye a több szál ütemezésétől?

void fv() {
    Stuff local = ...;
    parallel( []{ do_stuff(local); } );
    parallel( []{ do_other_stuff(local); } );
}

Néha az érték szerint megjegyzett változó a legváratlanabb esetekben okozhat gondokat. Az alábbi programrészben egy vektorban a find() hívás megkeresi a 42-es szám első előfordulását, aztán előállít egy függvényt, amely onnantól kezdve tud megkeresni egy másik számot. Ez a függvény azonban csak addig lesz működőképes, amíg a vektor át nem méretezi magát: az átméretezés miatt az iterátorok érvénytelenné válnak, hiába tároltuk el őket.

vector<int> v = ...;
auto firstit = find(v.begin(), v.end(), 42);
auto findnextfunc = [](int i){ return find(firstit, v.end(), i); };

A C++-ban a lambda függvényekben nem válnak a külső függvény lokális változói automatikusan elérhetővé. Nekünk kell megmondanunk, melyik változót szeretnénk látni; és azt is, hogy melyiket érték, melyiket referencia szerint. (De ezt C++-ban már megszoktuk: választhatunk és választanunk is kell.) A lambda kifejezés típusa ettől függően egy olyan függvényobjektum lesz, amelybe a hivatkozott változók értékei belemásolódnak, vagy amelybe a hivatkozott változó referenciája kerül. Érték esetén a létrehozáskori pillanatképet látjuk (snapshot), referenciák esetén pedig utólag a változásokat is (living view). Ezt adja meg a capture clause, a lambda kifejezés szögletes zárójeles része. A lehetőségek az alábbiak:

• []: nem látjuk a létrehozó függvény változóit.
• [x, &y]: az x változót érték szerint (capture by value), az y változót referencia szerint (capture by reference) tároljuk.
• [=]: minden hivatkozott változót érték szerint. Ilyenkor a fordító megkeresi a hivatkozott változókat, és csak azokat teszi bele a lambda objektumba (implicit capture).
• [&]: minden hivatkozott változót referencia szerint.
• [&, x]: mindent referencia szerint; kivétel az x-et, azt érték szerint.
• [=, &x]: mindent érték szerint; kivétel az x-et, azt referencia szerint.
• [this]: osztályban, a kapott függvény annak az objektumnak a tagfüggvényeként fog viselkedni, amelyikben létrehoztuk. Vigyázat: a this egy pointer, ezért a befoglaló objektumot referencia szemantikával fogjuk látni! C++17-ben [*this] is lehetséges.
• [x = 0]: csak a lambda belsejében létező változó. Kezdeti értékét kötelező megadni, az x változó pedig auto-ként meghatározott típusú lesz. C++14 óta.

Az alsó szintaxis teszi lehetővé azt, hogy egy lambda objektumba mozgassunk egy objektumot. Ehhez [x = std::move(x)] formában kell használni. x =, tehát a lambdában jön létre egy változó; std::move(x), tehát jobbértékből lesz inicializálva. Ezek után a külső függvényben az x objektum már üres lesz, mert a lambda létrehozásakor a capture specifier-ben megadott kifejezések kiértékelődnek, tehát x mozgató konstruktora is lefut.

Példák érték és referencia szerinti tárolásra

Példa referencia szerinti tárolásra. A következő lambda kifejezéssel megszámoljuk, hány összehasonlításra volt szükség a rendezéshez:

int arr[] = { 4, 7, 18, 16, 14, 16, 7, 13, 10, 2, 3};
int n = 0;
std::sort(std::begin(arr), std::end(arr),
    [&n](int a, int b) { ++n; return a < b; }   // referencia szerint
);
std::cout << n << " összehasonlítás";

Példa érték szerinti tárolásra. Az alábbi lambda kifejezéssel a felhasználó által adott center számtól való távolság szerint rendezzük sorba a tömb elemeit. A hívás pillanatában a center változónak már nem is kellene léteznie, mert másolat készül róla.

int arr[] = { 4, 7, 18, 16, 14, 16, 7, 13, 10, 2, 3 };
int center;
std::cin >> center;
std::sort(std::begin(arr), std::end(arr),
    [center](int a, int b) {
        return abs(center-a) < abs(center-b);   // érték szerint
    }
);

A lambda objektumba érték szerint eltárolt változók konstansnak számítanak – mondhatni, a létrehozott függvény objektum függvényhívó operátora konstans tagfüggvény. Ha azt szeretnénk, hogy a függvény törzsében meg tudjuk azokat változtatni, akkor ún. mutable lambdát kell létrehoznunk, ugyanezzel a kulcsszóval. Pl.:

int arr[] = { 4, 7, 18, 16, 14, 16, 7, 13, 10, 2, 3};
std::for_each(std::begin(arr), std::end(arr),
    [count = 0] (int i) mutable {
        std::cout << ++count << ". " << i << std::endl;
    }
);

A lambda kifejezések jelentése

Minden alkalommal, amikor egy lambda kifejezést kiértékelünk, létrehozunk egy objektumot, amelybe eltároljuk a szögletes zárójelben megadott változókat. Egy lambda kifejezés megírása és kiértékelése nem más, mint egy osztály definíciója (fordítási időben) és az osztály konstruktorának hívása (futási időben). Például ez a kódrészlet:

int i = 1, j = 2;
auto my_lambda = [i, &j](int k) { return i * ++j - k; };
my_lambda(3);

Lényegében nem különbözik attól, mintha ezt írtuk volna:

class MyLambda {
  private:
    int i;
    int &j;
  public:
    MyLambda(int i, int &j): i{i}, j{j} {}
    int operator() (int k) const {
        return i * ++j - k;
    }
};
 
int i = 1, j = 2;
auto my_func = MyLambda{i, j};
my_func(3);

int j = 2;
auto func = [] () { // ?
    return j;
};

j += 3;
std::cout << func();

Ahány lambda kifejezésünk van a programban, annyiféle paraméterük lehet, és annyiféle belsőváltozó-listával rendelkezhetnek. Sejthetjük, hogy a lambda objektumoknak inkompatibiliseknek kell lenniük egymással, és ez így is van. Minden egyes lambda kifejezés egy egyedi típusú objektumot hoz létre, amelynek a fordító által generált, a forráskódban láthatatlan nevű típusa van. Ezért kellett a fenti kódban a lambda objektumot egy auto típusú változóban eltárolni: mert amúgy nem tudtuk volna megnevezni a típusát.

Ez alól csak azok a lambdák kivételek, amelyeknek a változólistája teljesen üres: mivel ezek az őket létrehozó függvénynek semmilyen lokális változóját nem látják; tulajdonképp olyanok, mint a globális függvények. Az üres változólistával rendelkező, tehát kontextus nélküli lambdák függvénypointerré konvertálhatóak. Így akár egy C-ben írt függvénynek is adhatunk lambda kifejezést paraméterként, a lényeg csak az, hogy üres változólistával [] kezdődjön. Egy példa (bár C++-ban a C-s qsort() függvényt nem szokás már használni):

int arr[] = { 7, 4, 8, 3, 7, 9, 2, 4 };
qsort(arr, sizeof(arr)/sizeof(arr[0]), sizeof(arr[0]),
    [] (void const *pa, void const *pb) {
        return *static_cast<int const *>(pa) - *static_cast<int const *>(pb);
    }
);
for (auto i : arr)
    std::cout << i << " ";

Ha nem ismerjük a lambda objektum típusát, mert nem tudjuk a nevét, akkor hogyan lehet olyan függvényt csinálni, amelyik egy lambda kifejezés értékével tér vissza? Ennek a problémának a megoldására találták ki az std::function nevű függvénysablont (#include <functional>). Ez a sablon konstruktorával és a sablon értékadó operátorával érték szerint le tud másolni bármilyen függvényszerű dolgot. Így érték szerint átadhatóvá tesz bármilyen funktort vagy lambda objektumot – lényegében type erasure-t valósít meg a függvényként viselkedő típusok számára. Az std::function sablon egyetlen sablonparamétere a hívandó függvény típusa (call signature), amely önmagában kicsit furcsán néz ki (egy függvényfejlécből elhagyva a függvény neve), de egy példa többet mond:

#include <functional>
#include <cmath>
#include <iostream>

class Linear {
    double a_, b_;
  public:
    Linear(double a, double b): a_{a}, b_{b} {}
    double operator() (double x) { return a_*x + b_; }
};

int main() {
    std::function<double(double)> f;    // double param, double vissza

    f = sin;
    std::cout << f(1.2) << std::endl;   /* sin(1.2); */

    f = Linear{1.2, 3.4};
    std::cout << f(6) << std::endl;     /* 1.2*6 + 3.4 */

    f = [](double x) { return x*x; };
    std::cout << f(3.14) << std::endl;  /* 3.14*3.14 */
}

Ez a függvénysablon elfedi a függvény objektumok, függvénypointerek közötti szintaktikai különbséget is. Használható visszatérési érték típusaként ott, ahol egy lambda objektummal szeretnénk visszatérni. Ezzel már meg tudjuk valósítani a JavaScript nyelven írt deriváló függvényünket C++11-ben:

#include <functional>
#include <cmath>
#include <iostream>

std::function<double(double)> derive(std::function<double(double)> f) {
    double dx = 0.001;
    auto derived = [=] (double x) {
        return (f(x+dx) - f(x)) / dx;
    };

    return derived;
}

int main() {
    auto my_cos = derive(sin);

    for (double x = 0; x < 3.14; x += 0.1)
        std::cout << cos(x) - my_cos(x) << std::endl;
}

Az std::function paraméter által biztosított absztrakció miatt a derive() függvényünk nem feltétlenül kell sablon legyen. A paramétere tetszőleges típus lehet, amely double(double) függvényként használható, mivel minden ilyen típussal inicializálható az std::function<double(double)> paraméter.

Pro tipp. Az std::function belső működése mögött dinamikus memóriakezelés van, mivel az általa tárolt tetszőleges típusú függvénypointer vagy -objektumnak akár a mérete is típusonként eltérő lehet. Ezért egy std::function másolása lassú művelet – meggondolandó, hogy konstans referenciával adjuk át paraméterként.

Érdekességként: rekurzív lambda?

A lambdák névtelen függvények. Ezért lambdával papírforma szerint nem lehet rekurziót csinálni, mert a rekurzív híváshoz tudni kellene a függvény nevét – márpedig ha nincs név, nem tudunk hivatkozni rá. Ha ilyenre van szükségünk, egyszerűbb rendes függvényként megírni, és legfeljebb a használatát csomagolni egy lambdába. Ennek ellenére, az std::function sablonnal megoldható egy helyen a rekurzív lambda létrehozása:

std::function<int(int)> fib;
fib = [&fib] (int n) {
    return n < 2 ? n : fib(n-1) + fib(n-2);
};

Ez nem túl hasznos, viszont a megoldás módja annál tanulságosabb. A fib objektum a létrejötte pillanatában üres (mint egy null pointer), még nem tartalmaz semmilyen függvényt. A létrehozásának célja csak az, hogy neve lehessen a függvénynek, és ez a név a lambda kifejezés kiértékelésének pillanatában már létezzen. A lambda létrehozása után történik meg az értékadás, akkor másolódik be a függvényobjektumba a lambda objektum. Ezért kell a fib változót referencia szerint hivatkoznia! Ha lemásolná, akkor még az értékadás előtti, üres állapotáról készítene másolatot. Írhatnánk a két sort egyben is, ilyen formában:

std::function<int(int)> fib = [&fib] (int n) {
    return n < 2 ? n : fib(n-1) + fib(n-2);
};

Ez ugyanazt jelenti. A lambda kifejezés kiértékelésének pillanatában a fib objektumnak még nincs értéke (később lesz inicializálva), de referenciája már létezhet. Az így létrehozott fib objektum nem másolható, mert a belsejében saját magára van referencia.

Nyelvészeknek: függvénysablonok és lokális típusok

A lefordított programot vizsgálva látszik a lambda objektum névtelen típusa. A hozzá tartozó függvényhívó operátornak lennie kell valahol. A fordító által ezekhez rendelt nevek egyediek, a tartalmazó függvényhez kötődnek:

int main() {
    int i = 2;
    auto f = [=] { return i; };
    f();
}

$ nm -C myprog
[...]
0000000000400650 T main
0000000000400680 t main::$_0::operator()() const    a lambdáé

C++98-ban nem lehetett egy függvényben, lokálisan megadott típussal példányosítani egy függvénysablont vagy osztálysablont. Ott ez nem működött:

int main() {
    class X {};
    std::vector<X> xvec;
}

C++11-ben már lehet ilyet. Ezzel bonyolultabbak lettek a fordítók, de muszáj volt megengedni ezt. A lambda kifejezések szinte mindig függvények belsejében szerepelnek, tehát csak lokálisan megadott típussal rendelkezhetnek. És pont azt szeretnénk, hogy a sablonfüggvényeket (pl. az std::sort() függvénysablont) példányosítani lehessen velük!

int arr[] = { 7, 4, 8, 3, 7, 9, 2, 4 };
qsort(arr, sizeof(arr)/sizeof(arr[0]), sizeof(arr[0]),
    [] (void const *pa, void const *pb) {
        return *static_cast<int const *>(pa) 
		       - *static_cast<int const *>(pb);
    }
);
for (auto i : arr)
    std::cout << i << " ";

Adott az alábbi feladat.

Baker, Cooper, Fletcher, Miller és Smith egy ötemeletes ház különböző emeletein laknak. Baker nem a legfölső emeleten lakik, Cooper pedig nem az alsó szinten. Fletcher lakhelye sem a legalsó szinten van, de nem is a legfölsőn. Miller magasabban lakik, mint Cooper. Smith nem Fletcherrel szomszédos emeleten lakik, ahogy Cooper és Fletcher sem emelet-szomszédok. A kérdés: melyik emelet kié?

Tehát bizonyos változók (itt: Baker, Cooper, Fletcher, Miller, Smith) különböző értékeket vehetnek föl (itt: 1, 2, 3, 4, 5), és az összes variációból a feladatban megadott megkötések egyetlen egyet jelölnek ki (itt: Baker = 3, Cooper = 2, Fletcher = 4, Miller = 5, Smith = 1). Mivel egy feladattípusról van szó, a favágó megoldása helyett ezért inkább írjunk most egy olyan keretrendszert, amely általánosságban képes ilyenek megoldására, és utána oldjuk meg ezt a konkrét feladatot a keretrendszer segítségével!

Terv – elnevezések

A leendő keretrendszerünk használatát valahogy így képzelhetjük el, egyelőre pszeudokód formájában:

Solver s

baker = s.add_variable( {1, 2, 3, 4, 5} )
cooper = s.add_variable( {1, 2, 3, 4, 5} )
fletcher = s.add_variable( {1, 2, 3, 4, 5} )

s.add_constraint( λ{baker ≠ cooper} )
s.add_constraint( λ{|cooper-fletcher| ≠ 1} )

s.solve( λ{print(baker, cooper, fletcher)} )

Lesz egy Solver objektum, amely végig fogja pörgetni az összes változók összes lehetséges értékeit, azaz előállítja az összes variációt. Minden változó megadása egy halmaz megadását jelenti a Solver számára, amely annak a változónak a lehetséges értékeit tartalmazza. A Solver megjegyzi a halmazt, és visszatér egy olyan objektummal, amely a változó aktuális értékét reprezentálja majd a megoldás keresése közben.

Ha megvannak a változókat reprezentáló objektumok, akkor megadhatjuk a megkötéseket is: ConstraintFunc. Minden megkötés egy kifejezés (pl. Baker ≠ Cooper), amely igazra vagy hamisra értékelődik ki; igazra, ha a megkötés teljesül, és hamisra, ha a változók értékei megsértik az adott megkötést.

Baker	Cooper	Fletcher	Miller	Smith	Jó?
1	1	1	1	1
1	1	1	1	2
...
3	2	4	5	1
...
5	5	5	5	5

A megkötések megadása után elindítjuk a Solver-t. Ez végigszalad az összes változó összes lehetséges értékein (az összes halmaz Descartes-szorzata). Az egyes variációknál a megkötések vizsgálata a ConstraintFunc függvények meghívását jelenti. A megoldás kereséséhez megadunk egy további függvényt is: ActivityFunc. Ez az a tevékenység, azaz függvény, amelyet a Solver majd meghív akkor, amikor megoldást talált.

A fenti példában ez azt jelenti, hogy az { 1, 2, 3, 4, 5 } halmazt megadjuk a Solver-nek, mire visszaad egy objektumot, amely Baker-t reprezentálja. Utána megmutatjuk neki még négyszer ugyanezt a halmazt, hogy megkapjuk Cooper-t, Fletcher-t stb., akik mind ugyanilyen sorszámú emeleten lakhatnak ebben a feladatban. A Solver az eltárolt halmazokhoz iterátorokat hoz létre, amelyek megoldáskeresés közben az épp vizsgált variációt adják meg. Az egyes ConstraintFunc függvények ezeket közvetve látni fogják, hogy az adott variációt ellenőrizni tudják.

Az említett függvények több paraméterrel is rendelkezhetnének. Pl. egy megtalált helyes variáció esetén a meghívott Activity függvény megkaphatná paraméterként a találat értékeit. Ezt azonban nehéz kezelni, mert nem tudjuk előre, hány változó lesz. Használjuk ki ezért azt, hogy egy lambda objektumban tetszőlegesen sok változót elrejthetünk! Írjuk elő, hogy az ActivityFunc egy void() alakú függvényobjektum kell legyen! Ha a Solver használója valamelyik változója értékét látni szeretné az ActivityFunc-ban, majd beleteszi a lambda objektumba.

Írjuk elő azt is, hogy a ConstraintFunc is legyen paraméter nélküli bool() alakú függvényobjektum! Egy alkalmas lambda kifejezés becsomagolhatja a változókat reprezentáló objektumokat is. Végül pedig, hogy lássuk, a lambda függvények bármire képesek, legyenek a változók (Baker, Cooper stb.) is függvények! Ezek szerint az egyes halmazok megadása után a Solver vissza fog adni olyan függvényeket, amelyeket ha meghívunk, a változók megoldáskeresés közben épp aktuális értékét látjuk.

Implementáció

A Solver a sablonparaméterében adott típusokkal fog dolgozni. A paraméterként megadott adatokat, a változók lehetséges értékeit belül std::vector típusú tárolókban tárolja a variables_ nevű tömbben. A bejárás közben minden ilyen tárolóhoz szükség lesz egy iterátorra is, ezért létrehozunk egy iterátorokból álló tömböt is: iterators_.

template <typename VALUETYPE>
class Solver {
  public:
    using VariableFunc = std::function<VALUETYPE const &()>;
    using ConstraintFunc = std::function<bool()>;
    using ActivityFunc = std::function<void()>;

  private:
    std::vector<std::vector<VALUETYPE>> variables_;
    std::vector<ConstraintFunc> constraints_;
    std::vector<typename std::vector<VALUETYPE>::const_iterator> iterators_;

A hozzáadás után a Solver visszaad majd egy VariableFunc típusú függvényt, amelyet meghívva lekérdezhetőek megoldáskeresés közben a változója mindenkori értékei.

A lenti add_variable() függvény kezeli egy új változó létrehozását. A változó létrehozásához el kell tárolni a paraméterként kapott értékeket, és vissza kell adni azt a függvényt, amelyet meghívva a változó megoldáskeresés közbeni értékét látjuk. Ez az egysoros lambda függvény. Itt most kicsit előre kell gondolkozni: azért kell a Solver objektum tagváltozójává tenni az iterátorok tömbjét is, hogy ebben a lambda függvényben már hivatkozni lehessen rá. A függvény dolga tulajdonképpen csak ennek az iterátornak a dereferálása. De ha az iterátor csak a tesztelést végző függvényben jönne létre lokális változóként, akkor ez a lambda nem látná azt! A lambda kifejezés két értéket tárol el: a this pointert, hogy lássa az őt létrehozó Solver-t, és azt a tömbindexet, ahányadik helyre az új változó került. Így tudni fogja, melyik iterátorról van szó.

    VariableFunc add_variable(std::vector<VALUETYPE> values) {
        variables_.push_back(std::move(values));
        size_t pos = variables_.size()-1;
        return [this, pos] () -> VALUETYPE const & {
            return *iterators_[pos];
        };
    }

A visszakapott változókat reprezentáló függvényeket használva adhatja meg a hívó a ConstraintFunc-okat, amelyek igaz/hamis függvények. Ezek mutatják majd, hogy teljesül-e egy bizonyos előírás vagy nem. ConstraintFunc hozzáadásakor egyelőre nincs teendő; ezeket a kifejezéseket majd csak a megoldáskeresés közben kell kiértékelni. Úgyhogy csak bekerülnek a constraints_ tömbbe:

    void add_constraint(ConstraintFunc constraint) {
        constraints_.push_back(std::move(constraint));
    }

Alább látható a megoldás keresése. Ha eközben a Solver osztály egy olyan variációra akad, amely teljesíti az összes feltételt, akkor a do_what függvényt fogja meghívni. A teszteléshez a következőket csinálja:

1. Először is, létrehozza a munkaiterátorokat, mindegyiket a megfelelő tömb elejére állítva.
2. Aztán elindít egy ciklust, amelynek akkor lesz vége, ha az összes variációt végigpróbálta.
3. Minden variációnál végig kell nézni a megkötéseket, hogy mindegyik teljesült-e. Az std::all_of végigmegy a tárolón, és akkor ad igazat, ha a harmadik paraméterként adott predikátum igazat válaszol mindegyik elemre. A predikátum itt: meg kell hívni a függvényeket, a ConstraintFunc-okat.
4. Ha mindegyik igaz volt, akkor el kell végezni a kért tevékenységet.
5. Végül pedig, léptetni kell az iterátorokat. A legelsővel kell kezdeni, és ha az a végére ért, akkor a tartomány elejére állítani vissza, és léptetni a következőt: mint egy túlcsordulás a +1 hozzáadásánál. Akkor kell vége legyen a 2-es ciklusnak, ha a legutolsó iterátor is „túlcsordult”.

    void solve(ActivityFunc do_what) {
        iterators_.clear();
        for (auto & v : variables_)
            iterators_.push_back(v.begin()); // 1

        bool end = false;
        while (!end) { // 2
            bool satisfied = std::all_of(
                constraints_.begin(), constraints_.end(),
                [] (ConstraintFunc const & cons) { return cons(); }   // 3
            );
            if (satisfied)
                do_what();  // 4

            bool carry = true;
            for (size_t i = 0; i < variables_.size(); ++i) {
                ++iterators_[i]; // 5
                carry = iterators_[i] == variables_[i].end();
                if (carry)
                    iterators_[i] = variables_[i].begin();
                else
                    break;
            }
            end = carry;
        }
        
        iterators_.clear();
    }

Ennyi a Solver kódja. A használata pedig a következő. Először is, létre kell hozni egy példányt.

int main() {
    Solver<int> s;

Baker, Cooper, Fletcher, Miller és Smith mind az 1–5 emeletek valamelyikén laknak. Itt kapjuk meg az öt függvényt, amelyek tesztelés közben megadják majd a tesztelés alatt álló értékeket. Tehát pl. a baker() hívás értéke majd az 1...5 számok valamelyike lesz – de egyelőre ezeket a függvényeket nem szabad meghívni.

    auto baker = s.add_variable({1, 2, 3, 4, 5});
    auto cooper = s.add_variable({1, 2, 3, 4, 5});
    auto fletcher = s.add_variable({1, 2, 3, 4, 5});
    auto miller = s.add_variable({1, 2, 3, 4, 5});
    auto smith = s.add_variable({1, 2, 3, 4, 5});

Első megkötés: a srácok mind különféle emeleten laknak. Ennek egyszerű kódbeli megfogalmazásához az öt függvényt betesszük egy tömbbe (egészen pontosan: egy inicializáló listába), hogy iterálni lehessen rajtuk. Minden párt meg kell vizsgálni; ha valamelyik pár épp egyforma számot ad, akkor nem teljesül a feltétel, hogy különféle emeleteken laknak. A feltétel függvényének megadásakor a változókat reprezentáló függvények bátran tárolhatóak érték szerint, mindig ugyanaz a lambda fog másolódni, amely ugyanazon Solver ugyanazon indexedik iterátorát látja.

    auto guys = { baker, cooper, fletcher, miller, smith };
    s.add_constraint([=] () -> bool {
        for (auto egyik = guys.begin(); egyik != guys.end(); ++egyik)
            for (auto masik = egyik+1; masik != guys.end(); ++masik)
                if ((*egyik)() == (*masik)())
                    return false;
        return true;
    });

Baker nem a legfölső emeleten lakik, Cooper pedig nem az alsó szinten.

    s.add_constraint([=] { return baker() != 5; });
    s.add_constraint([=] { return cooper() != 1; });

Fletcher lakhelye sem a legalsó szinten van, de nem is a legfölsőn.

    s.add_constraint([=] { return fletcher() != 1 && fletcher() != 5; });

Miller magasabban lakik, mint Cooper. Smith nem Fletcherrel szomszédos emeleten lakik, ahogy Cooper és Fletcher sem emelet-szomszédok.

    s.add_constraint([=] { return miller() > cooper(); });
    s.add_constraint([=] { return abs(smith() - fletcher()) != 1; });
    s.add_constraint([=] { return abs(cooper() - fletcher()) != 1; });

Melyik emelet kié? Ha találat van, akkor írjuk ki a neveket a hozzájuk tartozó emeletek sorszámával.

    auto print_all = [=] {
        std::cout << "Baker " << baker() << std::endl
                  << "Cooper " << cooper() << std::endl
                  << "Fletcher " << fletcher() << std::endl
                  << "Miller " << miller() << std::endl
                  << "Smith " << smith() << std::endl;
    };
    s.solve(print_all);
}

Baker 3
Cooper 2
Fletcher 4
Miller 5
Smith 1