00101010001010100010101000101010001010100010101000101010001010100010101000101010001010100010101000101010001010100010101000101010
0
1
0
1
0
1
0
0
0
1
0
1
0
1
0
0
0
1
0
1
0
1
0
0
0
1
0
1
0
1
0
0
0
1
0
1
0
1
0
0
0
1
0
1
0
1
0

Carl Gibbs – Blog

11/08/2013

Functional Programming in C++

Filed under: programming — Tags: , , — Carl @ 19:51

This is not a new topic, and there have been plenty of comments recently from various C++ developers. But most comments are only about lambdas and using them as higher-order functions.  While I can’t claim any deep knowledge of functional programming (some experience with functional techniques in Scala, F# and C#) I can’t help think the real functional programmers are laughing at us for missing the point. Yes it’s called function-al programming, functions are in the name, but that doesn’t mean functions are the only important feature to consider before we can make use of functional techniques in C++.

Possibly C++ could evolve to allow code in a fully functional style, alongside the procedural, object-oriented and generic styles it already supports.  But I don’t think this actually matters to be able to take advantage of many functional techniques. C# already allows nearly-functional code without supporting some key compiler features. I think a similar approach could be followed in C++, possibly with only library support and no more language features.

 

There are a number of important features in functional programming:

Higher order functions

Functions you can pass around and return, allowing fine grained reuse, currying, composition.

C++ std::function class or functions as template arguments allow this.

Closures

Functions that capture data when created, and keep it available to use when the function is run later.

C++ 11 lambdas allow this and have been widely discussed, as expected as they are one of the most exciting features in C++ 11.  These do add a lot of flexibility and simplicity to C++ compared to previous library-only approaches.

Immutable data

const in C++ already allows this. Many functional languages allow mutable data to make interfacing with other languages and the external environment (UI, db, networks) so mixing mutable and immutable data is not alien, and const puts C++ in a better position  compared to most other nearly-functional languages, with the compiler able to enforce at least some of this.

The use of immutable data to ease concurrent code has already been widely discussed (e.g. Sutter’s Mill GotW 6a) and again const puts C++ ahead of the pack as the compiler the helps make your code more thread safe.  It only helps, it can’t stop you making every member-function const and marking all member-data with the mutable keyword without any locks.  But most popular languages have no concept of immutable at all, and for years other developers have treated const in C++ as an old-fashioned restriction like checked exceptions.  Well, the joke’s on the other foot now.

Immutable collections

The list-based immutable collections in most pure functional languages are often said to require garbage collection, although I wonder if they may be possible with C++ move semantics or certainly shared_ptr though admittedly with more overhead.

But I don’t think such collections are required for nearly-functional languages, they are only one way to support the algorithms that apply to the data.

Lazy Evaluation

Lazy Evaluation is mostly used to only process as much of a set of data as required, and in functional languages list-based immutable collections and higher-order functions are used to great effect.

Some form of iteration over collections while applying multiple functions together is required. Each data item is pulled through the series of functions one at time without needing to store the whole collection at each intermediate steps. But .Net LINQ, Scala collections and Java 8 streams show a different approach that works well, and which can also be parallelized.

C++ could easily follow this approach but C++ iterators currently make this hard. Passing a data-set around as separate begin and end parameters make code verbose and make it hard to chain calls together in a natural way. But boost::range may make this feasible, especially Range Adapters.  This gives a nice syntax to chain functions together and may give a natural way to separate non-modifying functions from modifying functions.

e.g.

boost::copy( vec | boost::adaptors::reversed, // adapter "reversed" doesn't modify the input vec
    std::ostream_iterator<int>(std::cout) ); // function "copy" does modify the target cout

With this we may not even need any language changes to support this approach.

Tail recursion

This is the elephant in the room of any serious discussion about functional languages, or at least any discussion with proponents of functional languages.  But while important for processing and navigating the immutable collections that give pure functional languages much of their power, I don’t think it’s as all-important as it seems.
A lot of recursion is actually hidden in higher level functions. Map, reduce etc. iterate over a container by using recursion over an immutable container. For this tail recursion is essential as the container is unbounded so the recursion is unbounded. But if map, reduce, … hide how the iteration is done, then it doesn’t have to be done by recursion. It can be simple iteration, or split across many threads.

There are algorithms that are more natural with recursion and these are used commonly in functional languages.  But many of these actually have sharply limited depth requirements.  Recursion over a visibly recursive data structure e.g. a binary tree, is generally limited by the depth of the tree.  Recursion from repeatedly dividing the problem space is likewise is limited to log2 n or limited by how accurate the result needs to be.

So while this might be an area of research to see if C++ could support tail recursion I don’t think tail recursion is essential to enable us to use and benefit from many functional programming techniques.

 

So now I’m hoping someone will tell me this has all been considered and there’s a book or a library that demonstrates just what I’m suggesting. 
C++ is already an embarrassingly full toolbox, I feel greedy asking for even more. But it would be good if the functional techniques were available as another style in C++ to mix in where suitable.  These techniques are helping other languages grow more robust in concurrent environments, and helping developers think in different ways.  With quite a small effort C++ developers can reap the same benefits.

 

Links:

4 Comments »

  1. Regarding recursion — see Question #1 in the following:
    http://ridiculousfish.com/blog/posts/will-it-optimize.html
    :-)

    Comment by MD — 12/08/2013 @ 22:25

  2. As for the libraries — Boost.Phoenix is worth checking out: http://boost.org/libs/phoenix

    Comment by MD — 12/08/2013 @ 22:50

  3. C++ does suport tail recusion, it’s actually just a compiler optimization, not a language feature. It’s currently available for C/C++ in GCC, (and possibly other compilers)
    Source:
    http://stackoverflow.com/questions/2693683/tail-recursion-in-c

    Comment by Ryan O'Connell — 13/08/2013 @ 05:26

  4. You might be interested in FTL (https://github.com/beark/ftl). It’s an in-development library tackling some of what you’re talking about.

    It doesn’t do too much with laziness yet (and what it does might be considered somewhat unsafe, due to circular references leaking memory presently), but there are plans to expand upon it, including proper lazy and immutable lists.

    The link to FC++ was interesting, hadn’t heard of that before.

    Comment by bjorn — 13/08/2013 @ 09:17

RSS feed for comments on this post. TrackBack URL

Leave a comment

Powered by WordPress