Introduction

C++ is known to be a multi-paradigmed language. This is often construed
to mean you can program in both a procedural and and object oriented
style. This is too limiting a view. C++, particularly with modern
library support, is more than capable of supporting programming in
the functional style. Even without modern libraries like boost, or
std::tr1, the Standard Template Library embodies many functional
concepts.

It also turns out that the template system in C++ defines a
metaprogramming language that is a pure, non-strict, lazy, functional
language. Of course, since this was not by design, it is not a
particularly elegant language, as anyone who has had to do template
metaprogramming can attest. For right now, though, I’m going to stay
away from metaprogramming, and look just at what can be done in the
language with the facilities provided.

What is functional programming

At the base, it is performing computations by the pure application of
functions, with no side-effects. Of course C has allowed this since
its inception, and it is never considered a functional language.
There is a lot of debate, and at least a little acrimony, in
determining if a language is functional. There are certainly many
claims of ‘my language is more functional that yours.’

Languages that are widely regarded as pure functional languages are Haskell and
ML. Haskell is also getting a lot of alpha geek buzz, for a number of
reasons, and has finally hit the stage where people are learning it
in order to work on something other than a Haskell compiler.

The flavor of ML most commonly encountered is O’caml. The optimizing
compilers for the language are quite powerful, and programs often
compete, and beat, equivalent C programs in efficiency and
performance.

The LISP family has deep functional roots, with Scheme being the version
that focuses the most on functional purity, as well as simplicity and
ease of teaching. Common Lisp has a much broader range of libraries
and facilties defined for it and standardised for it.

JavaScript, Ruby and Python also all have a strong functional component to them.

Examining these languages leads to the observation that the real keys seem to
be

1. Functions as first class objects
2. Referential transparency of expressions
3. Partial application, a.k.a currying.
4. Unnamed functions, a.k.a lambda expressions

All of these features have been implemented in C++, in the language
itself, in the Standard Library, in TR1, in Boost, or in custom
libraries such as FC++. This article will examine these in more
depth, and show how they can be profitably incorporated into your
existing practice.

First let’s examine what the four cornerstones of functional programming
really mean.

Functions as first class objects means that functions can be used in the same
way as all other entities in the language. In particular, that they
can be passed as values to functions, returned as values from
functions, and new ones can be created at runtime. In C, function
pointers can be passed and returned as values, but creating new
functions is not (portably) possible. In C++, however, we can create
objects that overload operator(), that satisfy all of the desired
properties. Function pointers can also be treated much more generally
with std::tr1::function objects.

Referential transparency of expressions means that an expression, or any of its
sub-expressions can be replaced by the value of that expression or
sub-expression without changing the behavior of the program as a
whole. A computation will always return the same result, and will
only depend on the value of its arguments. This implies that there
are no side-effects to evaluating an expression. No globals that can
be changed, producing non-local changes elsewhere. This property
gives the programmer, and the compiler and runtime, strong
capabilities to reason about the program, optimize it, and
demonstrate its correctness.

Partial application is one of the most unusual, and most powerful, features
of functional programming. This is also known as currying, after
Haskell Curry, a mathematician in the mid 20^th Century who
did some of the fundamental work in combinatory logic and the lambda
calculus. Currying takes a function of N parameters and turns it into
a function of N-1 parameters by fixing the value of one of the
formers arguments. Or, another way of looking at it, is to say that a
function that takes N arguments is equivalent to a chain of N
functions, each taking 1 argument and returning a function that
consumes the next argument. Haskell Curry invented it as a way of
talking about multi-variate functions in a theory of functions of one
variable. Well, Shoenfinkel invented it first, but shoenfinkling
never really caught on.

Unnamed functions don’t sound very useful. However, combined with
higher-order functions, that is functions that take and return
functions as parameters, they become very powerful, and quite useful.
If you’ve ever wanted to supply a simple function inline in a one of
the STL algorithms, but were frustrated with the syntax:

compose2(

plus(),
compose2(multiplies(),

bind2nd(plus(),0.0),

bind2nd(plus(),0.0)),
bind2nd(plus(),1))

you’ve wanted a better way of writing lambda expressions. Lambda calculus is one of the fundamental theories of computation, and while I’m temptedto start a lengthy exposition, I think a few of quick examples willgive you the flavor.

(Haskell)

\x -> x*x + x + 1

(Lisp)

(lambda (k) (+(+(* k k) k) 1) )

(Boost.Lambda (c++))

_1 * _1 + _1 + 1

The key is that you can provide a definition of a function and then bind
it to a variable, rather than a fixed name. Ideally with nearly the
same syntax as you would use if you did name the function. Functional
languages are often defined in terms of lambda expressions and the
lambda calculus, with syntactic sugar sprinkled on top to make it
more palatable. I’m using syntactic sugar in the techincal sense of a
well defined transformation from one syntactic form to a more
primitive syntactic form. The thing to keep in mind is that too much
syntactic sugar causes truth decay.

Objects vs Values

“Just like an int” has been a mainstay of C++ programming since the very
beginning. The phrase indicates that you can create a new type with
all of the capabilities of a built-in type. What many programmers
don’t realize is that the behavior of ints is a polar opposite of the
behavior expected of objects. That is because ints are quintessential
value types. And whereas an object is an entity with state and
identity, values have neither. This 7 here is indistinguishable from
that 7 over there. And 7 never changes (unless you;re using an old
version of FORTRAN) into 8. You evaluate an expression such as 7+1,
and produce an 8, but the original 7 is unaffected. Objects are
different. This object is always distinct from that object, even if
they have the same state. You can change Bob, and everyone who has a
reference to Bob sees the change also. Unfortunately, the mechanism
by which you produce new value types in C++ is exactly the same as
how you produce new object types. You declare a new class.

What you permit and accept by default with that class determines whether
instances of the class behave like values or like objects. The key
pieces of machinery in the language are familiar to all C++
programmers: default construction, copy construction, copy assignment
and destruction. The compiler will provide ones that by default act
(mostly) like a value. Mostly, because of the shallow vs deep issue,
and the fact that pointers are values, even if what they point to
isn’t. So what all the compiler instantiated methods do is treat each
member of the class as a value, and then create, copy, assign or
destroy it, in the order they are declared. Unfortunately, for the
programmer concerned with efficiency, and almost all C++ programmers
are, these copies are, or can be very expensive.

Objects, on the other hand, typically either do not accept the default
implementations, or they avoid invoking them. Usually when you say
object2 = object1, you want them to continue to refer to the same
entity. In fact, assignment is fraught with danger, with potential
slicing when assigning a derived to a base. Programmers will either
use a Handle/Body or pimpl_ pattern to separate the implementation
side of the class from the reference side of it, or use a smart
pointer such as std::tr1::shared_ptr. In the evil past, some
programmers would attempt to use raw pointers, and manage the
allocated resources by hand. In practice, it turns out that no one is
smart enough to do so successfully in any program of interesting
size. Or at the very least, if the original programmer is that smart,
the next person to attempt to enhance the system, or fix a bug, is
not that smart.

Lazy functional programming languages, such as Haskell, avoid the price of
copying values by only evaluating an expression when it is needed.
This is guaranteed to be correct because of referential transparency.
Although it can lead to puzzling runtime behavior. I’ve coded some
benchmarks which seem to take practically no time, because it turns
out that the calculation is never fully evaluated. This takes not
paying for what you don’t use to the n-th degree. This call-by-need
behavior is why they are characterized as lazy.

Getting this behavior in C++ is tricky, but far from unheard of. One
technique, used in numerical libraries such as Blitz++, and pioneered
by Todd Veldhuizen, is known as expression templates.

The problem expression templates were introduced to solve is the creation
of unneeded temporaries. Take for example the code

Array A,B,C,D;

//
… stuff

D = A * B + C

Where each of A, B, C and D are two-d arrays, with the usual definitions
for multiplication and addition. The straightforward implementation
of operators *() and +() lead to the creation and destruction of
temporaries, with associated memory allocation and destruction. e.g.

Array operator *(const Array& lhs, const Array& rhs);

has to create and return a new array, which might be quite large, only to
have it used temporarily in Array operator +(const Array&, const
Array&) and then discarded. And even once the expression on the
right hand side of the assignment statement is evaluated, it has to
be passed into the copy assignment operator and very likely discarded
afterwards. (note that this is not an initialization, so that
permitted optimization does not apply).

Template expressions change the operators to return something else, an
expression that encapsulates the arguments, and evaluates them only
when necessary.

ArrayExpression operator +(const Array&, const Array&);

Where ArrayExpression looks something like

class
ArrayExpression {

const Array& lhs;

const Array& rhs;

//….
more stuff

double operator(int,int); //compute the value at the point

}

Now, for lazy languages, like Haskell, this can be built into the language
itself, and in this case the concept is called a ‘thunk’. Because by
the time you need to think about it, the thought has already been
thunk. Yes, it’s a really awful joke. You have to remember, we work
in an industry where an extremely popular language is named after an
obscure, although influential, comedy troupe. Other industries do not
consider understanding why Norwegian Blue Parrots are funny a job
qualification. Nor do most of our managers, unless they came up
through the ranks themselves.

Referential transparency makes thunks extremely powerful because not only can
they be passed around instead of fully evaluated values, once they
are fully evaluated, the system can remember that value and use it
from then on. This is very much like common sub-expression
elimination, only it is a runtime feature, as well as a compile time
optimization.