Most of us are accustomed to programming in an imperative fashion. Programs are an ordered set of commands that govern what the CPU should process and in what order. Even in a parallel program written in an imperative fashion, each of the concurrent executions are an ordered set of instructions. In contrast, functional programming consists of expressions that are evaluated to produce a final value. In pure functional languages, there is no state per se, there is no notion of assignment. In functional programming, the treatment of functions and data are unified. Expressions can evaluate to be functions, for example. That is, the value of an expression can be function, just as the value of an expression could also be a number or a string or a list. Using Scheme as an example, the following expression evaluates to be a function.
(lambda (x) (* x x))
The value of this expression is a function – a lambda expression. Note that this function has no name – it just is a function. The function itself is distinct from the body of the function. The expression is the value obtained by applying the multiplication operator to x and x.
Now, the thing we do with functions is apply them to arguments. Even a function
with no name can be applied to arguments and evaluated. This nameless function
takes one parameter x
and evaluates the product of that parameter with itself (i.e., it
squares it).
In Scheme (as in other languages), we can give a function a name and then used the named function.
=> (define (square x) (* x x))
=> (square 4)
16
This might look a little more familiar (maybe?). We are defining square as a function of one argument x and the function multiplies x with itself.
In Scheme, the above expression would be something called “syntactic sugar.” That is, it looks like it is doing something special – defining a function, but what it is really doing is something that can be realized with more basic operations in Scheme – namely, just defining a variable.
=> (define square (lambda (x) (* x x)))
=> (square 5)
25
The two definitions of square are exactly the same – we are creating a variable square and giving it a value – in this case, the value is a function.
What is important when we apply a function is that there be a function. We can use a name whose value is a function – or, we can just directly apply an unnamed function:
=> ((lambda (x) (* x x)) 7)
49
The expression above applies the anonymous function to the value 7 and returns 49.
C++11 (and the Boost.Lambda library before it) provides support for
lambdas – for unnamed functions – in C++. Besides the expressiveness in
being able generate new functions from other functions, lambdas are
convenient when one wants to pass a function to another function, such
as when we use std::async.
A sequential version of the matrix-vector multiply function looks like this:
void matvec(const Matrix& A, const Vector& x, Vector& y) {
double sum = 0.0;
for (int i = 0; i < A.numRows(); ++i) {
sum = 0.0;
for (size_t j = 0; j < A.numCols(); ++j) {
sum += A(i, j) * x(j);
}
y(i) = sum;
}
}
We can apply a simple parallelization to this nested loop by performing the inner loop as parallel tasks. However, to realize that without lambda, we must create a helper function and put the inner loop computation there.
double matvec_helper(const Matrix& A, const Vector& x, int i, double init) {
for (size_t j = 0; j < A.numCols(); ++j) {
init += A(i, j) * x(j);
}
return init;
}
void matvec(const Matrix& A, const Vector& x, Vector& y) {
std::vector<std::future <double> > futs(A.numRows());
for (int i = 0; i < A.numRows(); ++i) {
futs[i] = std::async(matvec_helper, A, x, i, 0.0);
}
for (int i = 0; i < A.numRows(); ++i) {
y(i) = futs[i].get();
}
}
Unfortunately, now the logic of the original single algorithm is spread across two functions.
With a lambda on the other hand, we don’t need to create a separate,
named, helper function. We just need to create an anonymous function
right at the call site to std::async.
void matvec(const Matrix& A, const Vector& x, Vector& y) {
std::vector<std::future <double> > futs(A.numRows());
for (int i = 0; i < A.numRows(); ++i) {
futs[i] = std::async( [&A, &x](int row) -> double {
double sum = 0.0;
for (size_t j = 0; j < A.numCols(); ++j) {
sum += A(row, j) * x(j);
}
return sum;
}, i);
}
for (int i = 0; i < A.numRows(); ++i) {
y(i) += futs[i].get();
}
}
In C++, lambdas begin with [], which can optionally have “captured”
variables passed (that is, variables outside of the scope of the lambda
that will be accessed – in this case A and x). The value that
the function is really parameterized on is the row we are performing the
inner product with, so we make row a parameter to the lambda. The
function returns a double, which we indicate with ->. Finally we
have the body of the function, which is just like the helper function
body – and just like the inner loop we had before. Finally, we indicate
that the argument to be passed to the function when it is invoked is
i.
Since is in the outer scope of the lambda, we can also capture it:
void matvec(const Matrix& A, const Vector& x, Vector& y) {
std::vector<std::future <double> > futs(A.numRows());
for (int i = 0; i < A.numRows(); ++i) {
futs[i] = std::async( [&A, &x, i]() -> double {
double sum = 0.0;
for (size_t j = 0; j < A.numCols(); ++j) {
sum += A(i, j) * x(j);
}
return sum;
});
}
for (int i = 0; i < A.numRows(); ++i) {
y(i) += futs[i].get();
}
}
There are a variety of online references to learn more about C++ lambdas and I encourage you to learn more about – and to use – this powerful programming feature.