Home     Back     Up     Next Browse Files

Lambda-Ausdrücke

Jedesmal eine vollständige Klassendeklaration aufzuschreiben, wenn nur eine einzeilige Funktion mit etwas Kontext übergeben werden soll, erscheint aufwendig. Auch tragen solche Konstrukte eher zur Unübersichtlichkeit des Programmtexts bei.

Es gibt in anderen Programmiersprachen schon sehr lange ein Konstrukt für anonyme Funktionen, bei denen

Solche anonymen Funktionen bzw. Ausdrücke, die eine Funktion erzeugen, werden Lambda-Ausdrücke genannt. Dies geht zurück auf das Lambda-Kalkül von Alonzo Church und Stephen Kleene, die in den 30er-Jahren damit ein formales System für berechenbare Funktionen entwickelten. Zu den wichtigsten Arbeiten aus dieser Zeit gehört der Aufsatz von Alonzo Church: An Unsolvable Problem of Elementary Number Theory. American Journal of Mathematics, Band 58, Nr. 2 (April 1936), S. 345-363. Im Netzwerk der Universität Ulm abrufbar.

Bei den Programmiersprachen wurden diese Ausdrücke zuerst von Lisp eingeführt und anschließend auch von anderen Sprachen übernommen. Ein Nachteil der Lambda-Ausdrücke ist der Implementierungsaufwand, da lokale Variablen, die normalerweise effizient auf dem Stack untergebracht werden, dank eines Lambda-Ausdrucks unter Umständen länger überleben müssen. Das wird normalerweise gelöst, indem die Variablen aus der closure auf dem Heap angelegt werden und mit Hilfe der garbage collection später wieder automatisiert freigegeben werden. Diese Vorgehensweise erschien für eine Programmiersprache wie C++ so unattraktiv, dass erst sehr spät der Gedanke kam, hier eine Lösung zu finden.

Die prinzipielle Idee in C++ sieht so aus:

Das bedeutet, dass die Lebenszeit lokaler Variablen sich nicht verändert, wenn sie zur closure eines Lambda-Ausdrucks gehören. Wenn mit Referenzen gearbeitet wird, liegt es in der Verantwortung des Programmierers darauf zu achten, dass der Lambda-Ausdruck nicht länger benutzt wird als die lokalen Variablen leben.

So ließe sich die Funktion init_value durch einen Lambda-Ausdruck ersetzen:

GeMatrix<double> A(4, 5, StorageOrder::ColMajor);
initGeMatrix(A, [&](std::size_t i, std::size_t j) -> double {
   return j * A.n + i + 1;
});

Ein Lambda-Ausdruck beginnt in C++ immer mit der capture, d.h. einem in [...] gefassten Konstrukt, das angibt, wie lokale Variablen aus der Umgebung zu übernehmen sind. Hier bedeutet [&] konkret, dass alle benötigten Variablen per Referenz übernommen werden. Das betrifft hier konkret nur A, das wir nicht unbeabsichtigt kopieren wollen.

Nach der capture folgt die Parameterliste in gewohnter Weise. Der Return-Typ des Lambda-Ausdrucks darf erst hinter der Parameterliste angegeben werden. Vor dem Return-Typ ist hierbei -> anzugeben. Danach folgt der Anweisungsblock der anonymen Funktion, die jetzt alle Parameter und auch die von der capture erfassten lokalen Variablen verwenden darf.

Der Übersetzer erzeugt für diesen Lambda-Ausdruck implizit eine anonyme Klasse, die in etwa wie folgt aussieht:

struct Anonymous {
   GeMatrix<double>& A;
   Anonymous(GeMatrix<double>& A) : A(A) {
   }
   double operator(std::size_t i, std::size_t j) const {
      return j * A.n + i + 1;
   }
};

Bemerkenswert ist hier, dass der Funktions-Operator implizit mit const deklariert wird und somit die Matrix A nicht verändern darf. Da bei der capture [&] angegeben worden ist, wurde hier A per Referenz übergeben und nur eine Referenz behalten. Dort wo der Lambda-Ausdruck steht, erzeugt dann der Übersetzer ein temporäres Objekt der anonymen Klasse:

GeMatrix<double> A(4, 5, StorageOrder::ColMajor);
initGeMatrix(A, Anonymous(A));

Daraus lässt sich auch erkennen, dass Lambda-Ausdrücke temporäre Funktionsobjekte erzeugen.

Analog können wir auch herangehen, die Initialisierung mit Pseudo-Zufallszahlen einem Lambda-Ausdruck zu überlassen. Allerdings wäre ein const-Funktionsoperator nicht hilfreich, da wir den Status des Pseudo-Zufallszahlengenerators bei jedem Abruf verändern. Deswegen muss hier mutable angegeben werden. Die anonyme Funktion benötigt hier mt und uniform aus der Umgebung. Diese könnten wir hier auch per Referenz übernehmen. In diesem Fall erscheint aber das Kopieren einfacher:

GeMatrix<double> B(3, 7, StorageOrder::ColMajor);
{
   std::random_device random;
   std::mt19937 mt(random());
   std::uniform_real_distribution<double> uniform(-100, 100);
   initGeMatrix(B, [=](std::size_t i, std::size_t j) mutable -> double {
      return uniform(mt);
   });
}

Aufgaben

Vorlage

session11/step05/bench.h 
#ifndef HPC_BENCH_H
#define HPC_BENCH_H 1

#include <chrono>
#include <cmath>
#include <complex>
#include <random>

namespace bench {

template <typename T, typename Index>
T
asumDiffGeMatrix(Index m, Index n,
                 const T *A, Index incRowA, Index incColA,
                 T *B, Index incRowB, Index incColB)
{

    T asum = 0;

    for (Index j=0; j<n; ++j) {
        for (Index i=0; i<m; ++i) {
            asum += std::abs(B[i*incRowB+j*incColB] - A[i*incRowA+j*incColA]);
        }
    }
    return asum;
}

template <typename T, typename Index, typename InitValue>
void
initGeMatrix(Index m, Index n, T *A, Index incRowA, Index incColA,
             InitValue initValue)
{
    for (Index j=0; j<n; ++j) {
        for (Index i=0; i<m; ++i) {
            A[i*incRowA+j*incColA] = initValue(i, j);
        }
    }
}

template <typename T>
struct WallTime
{
    void
    tic()
    {
        t0 = std::chrono::high_resolution_clock::now();
    }

    T
    toc()
    {
        using namespace std::chrono;

        elapsed = high_resolution_clock::now() - t0;
        return duration<T,seconds::period>(elapsed).count();
    }

    std::chrono::high_resolution_clock::time_point t0;
    std::chrono::high_resolution_clock::duration   elapsed;
};


} // namespace bench


#endif // HPC_BENCH_H
session11/step05/gematrix.h 
#ifndef HPC_GEMATRIX_H
#define HPC_GEMATRIX_H 1

#include <cstddef>
#include <cassert>
#include "bench.h"

namespace matvec {

enum class StorageOrder {
    ColMajor,
    RowMajor
};

template <typename T, typename I>
    struct GeMatrixView;

template <typename T, typename I=std::size_t>
struct GeMatrix
{
    typedef T                       ElementType;
    typedef I                       Index;
    typedef GeMatrix<T,Index>       NoView;
    typedef GeMatrixView<T,Index>   View;

    GeMatrix(Index m, Index n, StorageOrder order=StorageOrder::ColMajor)
        : m(m), n(n),
          incRow(order==StorageOrder::ColMajor ? 1: n),
          incCol(order==StorageOrder::RowMajor ? 1: m),
          data(new T[m*n])
    {
    }

    ~GeMatrix()
    {
        delete[] data;
    }

    const ElementType &
    operator()(Index i, Index j) const
    {
        assert(i<m && j<n);
        return data[i*incRow + j*incCol];
    }

    ElementType &
    operator()(Index i, Index j)
    {
        assert(i<m && j<n);
        return data[i*incRow + j*incCol];
    }

    View
    operator()(Index i, Index j, Index numRows, Index numCols)
    {
        assert(i+numRows<=m);
        assert(j+numCols<=n);
        return View(numRows, numCols, &(operator()(i,j)), incRow, incCol);
    }

    const Index     m, n, incRow, incCol;
    ElementType*    data;
};

template <typename T, typename I=std::size_t>
struct GeMatrixView
{
    typedef T                       ElementType;
    typedef I                       Index;
    typedef GeMatrix<T,Index>       NoView;
    typedef GeMatrixView<T,Index>   View;

    GeMatrixView(Index m, Index n, T *data, Index incRow, Index incCol)
        : m(m), n(n), incRow(incRow), incCol(incCol), data(data)
    {
    }

    GeMatrixView(const GeMatrixView &rhs)
        : m(rhs.m), n(rhs.n), incRow(rhs.incRow), incCol(rhs.incCol),
          data(rhs.data)
    {
    }

    const ElementType &
    operator()(Index i, Index j) const
    {
        assert(i<m && j<n);
        return data[i*incRow + j*incCol];
    }

    ElementType &
    operator()(Index i, Index j)
    {
        assert(i<m && j<n);
        return data[i*incRow + j*incCol];
    }

    View
    operator()(Index i, Index j, Index numRows, Index numCols)
    {
        assert(i+numRows<=m);
        assert(j+numCols<=n);
        return View(numRows, numCols, &(operator()(i,j)), incRow, incCol);
    }

    const Index     m, n, incRow, incCol;
    ElementType*    data;
};

//
//  Interface for bench
//
template <typename GeMatrix, typename InitValue>
void
initGeMatrix(GeMatrix &A, InitValue initValue)
{
    bench::initGeMatrix(A.m, A.n, A.data, A.incRow, A.incCol, initValue);
}

template <typename GeMatrix>
typename GeMatrix::ElementType
asumDiffGeMatrix(const GeMatrix &A, const GeMatrix &B)
{
    return bench::asumDiffGeMatrix(A.m, A.n,
                                   A.data, A.incRow, A.incCol,
                                   B.data, B.incRow, B.incCol);
}

} // namespace matvec

#endif // HPC_GEMATRIX_H
session11/step05/test_initmatrix.cpp 
#include <cstdlib>
#include <cstdio>
#include "gematrix.h"

template<typename T, typename Index>
T init_value(Index i, Index j, Index m, Index n) {
   return T(j)*T(n) + T(i) + T(1);
}

template<typename T, typename Index>
std::complex<T> init_complex_value(Index i, Index j, Index m, Index n) {
   return std::complex<T>(T(i), T(j));
}

void print_value(double value) {
   std::printf(" %10.1lf", value);
}

void print_value(std::complex<double> value) {
   std::printf(" (%4.1lf, %4.1lf)", value.real(), value.imag());
}

template<typename Matrix>
void print_matrix(const Matrix& A) {
   for (std::size_t i = 0; i < A.m; ++i) {
      std::printf("  ");
      for (std::size_t j = 0; j < A.n; ++j) {
         print_value(A(i, j));
      }
      std::printf("\n");
   }
}

int main() {
   using namespace matvec;
   GeMatrix<double> A(4, 5, StorageOrder::ColMajor);
   initGeMatrix(A, [&](std::size_t i, std::size_t j) -> double {
      return j * A.n + i + 1;
   });
   printf("A:\n");
   print_matrix(A);

   GeMatrix<double> B(3, 7, StorageOrder::ColMajor);
   {
      std::random_device random;
      std::mt19937 mt(random());
      std::uniform_real_distribution<double> uniform(-100, 100);
      initGeMatrix(B, [=](std::size_t i, std::size_t j) mutable -> double {
         return uniform(mt);
      });
   }
   printf("B:\n");
   print_matrix(B);
}
Home     Back     Up     Next