Functional programming for embedded systems

Functional programming (FP) becomes more and more popular nowadays. A lots of modern languages adopt different concepts of functional programming, like mapping, filtering and folding. For example, Haskell had a huge impact on Rust and Swift. Beside this, the functional data structures come hand in hand with their methodological counterparts, which boost the ability for earily abstraction in day-to-day code. This makes the software more fail-safe and allows better error handling, which should result in better products on the markets.

In embedded development, the runtime constraints are too restricted for languages like Haskell, because the garbage collection would take too much resources on most platforms like ARM Cortex M. As a result, most embedded development stays in C and sometimes C++. Great languages like Rust try to provide better embedded support for these targets out of the box, but the current approaches are too experimental for now and rely on unsafe code. All this leads me to the assumption that most of these fancy IoT gadgets out there run software in C/C++, which is really disturbing in relation to cybersecurity.

Why? Becuse C++ is an old candidate and a lots of embedded developers use it to just encapsulate C into (static) classes, whereby they rely on old standards (C++98) from the last century. This results, for example, in voided functions void myFunction(void);, which modifies global mutable states. This is one anti-pattern of functional programming. Also the assumption that C++ is a object-oriented programming language is simply not correct: The Standard Template Library (STL) does not use inheritance-based polymorphism which is one of the main paradigms of the Object-Oriented Programming (OOP) methodology. Alexander Stepanov, a main critic of OOP, initially created the STL, which is heavily based on templates. This means C++ is a multi-paradigm language, whereas the STL models a lot of FP concepts. This means in general: C++ is a great candidate for functional development for embedded systems, if you are aware of the pitfalls…

One simple example is to calculate the average of a vector of numbers. Some classic implementation might look like:

This implementation is not very functional: The for loop cannot be parallized out of the box and the indexing is unsafe. Beside this, the average() function holds an internal mutable state (the sum variable). The STL already provides a solution for this: std::accumulate. The much better solution of the average function is now:

Now we use a common function of the STL and the vector iterator API instead of our own looping implementation. One more problem left: This cannot be parallized out of the box. For embedded systems this is no problem at all, since there is mostly no real multi-threading available (except some RTOS scheduling). For sake of completeness, the STL has already a solution for a multi-processing accumulation: std::reduce. This allows the usage of an execution strategy, like std::execution::par.

Not all compilers will support this for now, but the idea is so automatically parallelize the execution of the reduction algorithm.

Another example for functional programming is filtering collections. In Haskell, we would filter a list of numbers for items larger than the value 3 simply like this: filter (> 3) [1..5] . This will result in the list [4, 5]. But how to do this in C++? Fortunately the STL provides std::copy_if as a solution:

The iterators of the vector v are passed into the function and the std::back_inserter is a convenience method to keep the correct order of the items. The last argument of the function is the predicate lambda, which filters for items larger than 3. This approach is surely not as compact as the Haskell variant, but it works like the same: The selected items of the vector have to be copied into a new one. This can be a huge performance problem on embedded systems and has to be considered before using this kind of implementation. If it is not sure how large the filtered and result vectors will be in production environment, another strategy is valid: The erase and remove idiom. The STL algorithm std::remove_if provides an API to remove items from a vector, where the unnecessary copying can be avoided:

Since std::remove_if and std::remove operate on a range of elements defined by a pair of iterators, they can not actually remove the elements from the underlying collections. These two algorithms only move all the elements that do not satisfy the criteria for removal to the beginning of the collection. The erase() function of the collection will perform the actual removal afterwards.

The last example handles folding. You might already recognized that std::accumulate does the folding for is. One big pitfall is that the accumulation does unnecessary copies of the data. This can be avoided passing references to the accumulation algorithm:

The copy assignment operator is now able to see that the string tries to assign to itself, which does not invoke any copying at all.

Composing functions is one of the keys of functional programming. But doing this with the STL algorithms will lead into different kind of problems. The STL implementations does unnecessary copies of collections and it creates additional vectors which are not needed. One compensation appraoch would be to use references or smart pointers. The need to do this extra code is a clear indication that the STL has a slight architectural problem there, which has been known for some time. C++20 will introduce Ranges which will allow us to create composable smaller functions, without having any performance penalties for doing so.

This article showed that C++ has nowadays the capabilities for functional programming, which is also suitable for embedded development. There are some pitfalls related to the STL which are mainly memory reasoned. These can be avoided using smart references/iterators until the C++20 ranges in the future appear.

Thank you very much for reading.