There have been several attempts at reconciliation of the procedural (think Assembly or C), object-oriented (think C++ or Java) and the functional (think Haskell or Erlang) paradigms. Most prominent of them has arguably been Scala. I believe Scala is a very complex language but enjoys the benefit of the JVM ecosystem, which Eta and Frege also tried to achieve but were hit by JVM’s downside of garbage collection. C++ is also a very complex language but provides the benefit of greater performance and direct memory control, without any dynamic garbage collection, reducing the memory footprint, so we can run our programs on microcontrollers with tiny memory such as network interface cards (NICs) so as to reduce latency in automated trading.
In this post we will focus on developing a first approach to functional programming in C++ and contrast the modern syntax, using the C++17 and C++20 standards.
1 A Note on Java
As for Java, it has undergone significant improvements, beginning with the introduction of Java 8, also embedding some functional-programming concepts. But Java is poised to remain a retrograde (in a good sense) language, always a few years if not decades behind its younger descendants such as Kotlin and Scala in the facilities it offers on the syntactic level.
Roughly, Haskell => Scala -> Kotlin -> Java, where he arrows denote the flow of language and library features, on the JVM essentially originating in the Scala ecosystem acting as the melting pot of the FP and OOP fusion, with droplets trickling through into Kotlin, and only then filtered into Java the language; and Haskell’s ecosystem can be seen as the implementation origin of most if not all FP concepts (Lisp and Erlang are actually far more significant than most developers realize). We could also juxtapose C++ besides Haskell in that flow diagram as the originator of OOP concepts.
This is only intended as a mental picture, without any claim for ultimate correctness. In reality, everyone language community borrows something presumably good from another, in fact some things just work much better with one compiler than another, e.g., Haskell’s concepts are above and beyond more performant than their Scala implementations.
With the ascent of GraalVM and polyglot projects, the JVM ecosystem has entered its fruitful period of rejuvenation, bringing about significant results. Suffice it to mention Vert.x as the epitome of the progress already achieved.
Thanks to inline-java there is a wonderful compatibility layer between Haskell and Java (and the JVM). I’ll introduce you to it at a later time. Let’s now return to C++ and Haskell.
2 Functional Paradigms
In his book “Category Theory for Programmers”, Bartosz Milewski already used C++ to introduce developers to category theory and Haskell. I highly recommend his book to the interested, but also its slight modification that includes the corresponding Scala code. The approach I’m taking here will be different. We will focus on applications of category theory as approximated and implemented in Haskell libraries, only the most important parts of it that are relevant to the problems of software architecture that we will face, and start with practical Haskell, and see how we could write the same with the modern C++ libraries.
First off, we will only need to deal with the most basic FP concepts such as functor, applicative functor, monad, and lazy (or infinite) streams. If you need a recap, you’ll find a lot under the tag “Haskell” on my blog.
3 Function Types
In Haskell and PureScript, we define a function simply as f :: a -> b, in papers, in Idris and Agda we use single colons for the type inhabitant relation, i.e., f : a -> b. In TypeScript, we declare a function type as function f (a: a, b: b): c. In Python, it’s def f(a: a, b: b) -> c with type annotations. And in Scala, it’s def f(a: A, b: B): C. All pretty clear and concise. But in C and its derivatives such as C++ and Java, the type is specified ahead of the variable name, i.e., C f(A a, B b); and there is no distinction between a type name and a variable name, wheres in Haskell the names live on different levels. But starting C++11, functions can also be declared more succinctly as auto f(A a, B b) -> C; where the so-called “trailing type” C requires the “leading type” auto.[cppRudiments] In C#, it’s Func<A, B, C> f.
Let’s round this up by contrasting anonymous functions, lambda expression, or lambda abstractions, or even “delegates” in C#. Suppose f is given as above.
\a b -> f a bin Haskell and PureScript.(a, b) => { f(a, b); }in JavaScript starting with ECMAScript 6, in TypeScript, and in Scala (capturing nontrivial and depends onstrict).lambda a b: f(a, b)in Python (note the capture of outer-scope vars in Python 2).[&](auto a, auto b) { f(a, b) }in C++11 (with explicit outer-scope capture specification).(a, b) => f(a, b)in C# (outer-scope capture), but C# is far from making FP easy, but given F# the lack of push is apparent.
4 Type Inference, Generics, and Templates
Haskell, Agda and Idris shine when it comes to automated type inference, more so under their vastly advanced type systems.
Haskell also provides both generics and templates, as C++ does. And C++11 introduced automated type inference which can be invoked with the auto type specification.
5 Evaluation Strategies, Referential Transparency, Immutable Data, Purity, and Side-Effects
Given an expression, it must be evaluated in order to obtain the value that is represents. With lazy evaluation, an expression is reduced to its normal form by-need and only as far as needed at a computational step. In fact, its lazy-by-default evaluation sets Haskell apart among the vast variety of languages. However, it makes reasoning about space complexity harder in general. On the other hand, it enables powerful structural reductions, where the compiler simply omits many otherwise necessarily executed computational steps, and leaves only an expression that is much much easier to compute and evaluate. This is huge!
5.1 Referential Transparency
An expression is said to be referentially transparent if it is amenable to substitution by its value or its (weak-head) normal form, anytime and everywhere, without introducing any change to the result of the program. In other words, we have just a rewrite system.
As noted above, this gives us a perfect foundation for software verification, refactoring, optimization, memoization, and parallelization. It also enables lazy evaluation in the first place.
For a better understanding, a referent of an expression is the semantic object that it represents, a meaning, a value. And referential transparency of an expression x therefore means that whenever we replace one subexpression y for a referent with another expression z for the same referent, the meaning that x represents will not change. For example, in process of reduction to the WHNF, we can simply take the expression at every step and substitute it for the original y. Here’s a catamorphism example for lists in Haskell:
So for f = (:) :: a -> [a] -> [a], where b ~ [a],
foldr f [0] [1,2,3] == foldr f (1 `f` [0]) [2,3] == foldr f (2 `f` (1 `f` [0])) [3] == foldr f (3 `f` (2 `f` (1 `f` [0]))) [] == 3 `f` (2 `f` (1 `f` [0]))
foldr (:) [0] [1,2,3] == foldr (:) (1:[0]) [2,3] == foldr (:) (2:1:[0]) [3] == foldr (:) (3:2:1:[0]) [] == [3,2,1,0]5.2 Purity
Formally, a (not necessarily in mathematical sense proper) function is said to be pure if the function evaluates to the same result for every combination of arguments, under all states of the world, and thereby does not produce any side-effects.
5.2.1 Same result
Let’s dissect this definition. So first of all, under all states of the world, for every set of argument values, the function must evaluate to the same result. In symbols, suppose x : a represents the collection of arguments to our function f : a -> b, but it also depends on the state of the world, \(\omega \in \Omega\). We could also say that this function is said to be measurable if we endow \(\Omega\) and the set representing our type b with \(\sigma\)-algebras, or just the exponential object \(b^a\), and consider this f as a random process or random field, but this would lead us astray if it already hasn’t.
So let’s just stay with f : a -> b and state that, regardless of the state of the world, which is beyond the reach of f and includes all static variables, global (i.e., non-local) variables which can but need not be controlled by the caller of f, any mutable reference arguments, and even streaming data from however-random IO devices such as the file system or simply the keyboard.
5.2.2 No side-effects
5.2.3 Explanation
Purity is not limited to Haskell. C++ functions can also be pure. All we need to do is avoid mutable state and mutable data.
Purity essentially amounts to absence of state mutation and to immutable data.
Purity means that a function produces no side-effects; this is a guarantee of predictable behavior. Essential purity means that a function may semantically produce side effects but syntactically this is represented by a side-effects modeling type, such as IO a or Writer w a. The function does nothing until its monadic value gets evaluated. Until then it “lazily” defines what it is.
In Haskell, all functions are pure or essentially pure and there’s only one interface to the RealWorld — via IO. In C++ in contrast functions are impure or essentially impure.
Here’s a pure function in C++, with using std::atomic;
Impurity means that a function can change a global state, and this is not signified in its type signature. Essential impurity means that we can define a function to be “pure,” i.e., avoid any side-effects, but the language and its type system do not give us such a guarantee. For example,
void f(int, const int (&)[2] = {}) {}
void g() {
int x = 17;
auto g1 = [](auto a) { x += a; f(x); }; // Calls #1, does capture x.
auto g2 = [=](auto a) { f(x); }; // Does not capture x in C++14, captures x in C++17.
}But how would we know that f would not modify its argument x? In Haskell we know for sure, while in C++ we can’t without looking carefully at f and the name scopes. What if x also is a dependent variable, determined by some impure computation and all states altered are intertwined? This downside of impure languages makes reasoning very hard and regular debugging almost necessary. Static code analyzers and linters can help a bit. The greater the benefit of functional concepts introduced to C++.
Here’s another example, in C++14,
int x = 4;
auto y = [&r = x, x = x + 1]() -> int {
r += 2;
return x * x;
}(); // updates ::x to 6 and initializes y to 25.When you have a mental picture of memory registers that you access and the program remains simple enough to quickly retrace every impure state modification, it might be fine. But the larger the project grows, and the more people are involved on a team, and the more features get introduced, the greater the risk of irreparable damage done by benign changes. This is where continuous integration and quality assurance come into play. But all these efforts can be subsumed by simply using a more advanced type system like Haskell’s. Regardless, C++ has its unmatched benefits.
The issues highlighted above can be summarized as the lacking of referential transparency.
6 When Should I Use Which?
This question is good and simple to answer: it depends on your project requirements and the team cost–benefit trade-off. By project requirements I mean whether you need easy integration, high performance, rapid delivery, low maintenance, but also the deadlines and the budget. By the cost–benefit trade-off I refer to skills and experience of your team.
For example, if you know that your target platform depends on the JVM ecosystem, it’s smart to implement your business logic in a JVM-native language while using the JDK libraries. With polyglot and GraalVM there are huge boons available now. If you know that you need to deal with mostly high-performance code without regard to its runtime environment and your team knows how to manage the memory, go for C++ (or perhaps Rust if it’s not too avant-garde for you).
In essence, whenever you feel you need more control of your memory and don’t trust the garbage collector of the runtime platform, go for C++.
In practice, when writing Haskell, you sit and ponder about what you want to accomplish, perhaps even sketch some hopefully commuting diagrams with pen and paper, and then simply write it down in Haskell, and the compiler tells you whether this makes sense, curiously you’re usually mostly correct. In contrast, when writing C++, you imagine the procedures that hopefully meticulously describe the evolution of the state of your system, and prescribe the actions in each step, provoking you to rush into the battle so to say, the compiler helps you with the syntax and some metaprogramming typos but when it comes down to the system architecture, it will remain silent — in contrast with Haskell’s compiler. In this sense these are really two different worlds. In C++ and other imperative languages you have to leverage your testing skills, trying heuristically to ensure compliance with the specification, whereas in Haskell you simply encode the specification as types and let the compiler ensure that you preserve conformance with the spec, and only then do you add tests to ensure that your model implementation corresponds to your model logic. The state of the mind is different. With C++ you’re focused on managing an inherently imperative or procedural memory model, whereas with Haskell you manage a functional architecture.
Writing Haskell is akin to coding against a spec, essentially a form of test-driven development. Maybe this is what makes it uneasy to start with for many developers not used to testing but those who are used to testing seem to take up Haskell in a whim. A good approach to starting a new Haskell project is just to begin with the architecture; once you know what the inputs and the outputs of your project are and how you’re going to process the data, start writing down the individual functions with their types and leaving the function body undefined. Once the project skeleton is set up, it’s time to start filling the gaps, one by one, any way you feel most comfortable with. When done, only then is it time to look around what you have and refactor pieces of your code in any abstract profunctors and what not that you still understand. This will also help the compiler understand your actual intentions. You don’t have to do everything at once, just run a quick sanity and coherence check; and after a first swoop, it’s time for testing with HSpec, HUnit, and QuickCheck — choose any framework that you like (see my post on testing in Haskell). When your test suite is complete, take a second swoop at refactoring and make sure to run tests after each refactoring, if you have an automated build pipeline (CI/CD), it’s a breeze to implement. That way, you have all your essential business logic encoded in types, the test suite guarantees certain invariants, and you are free to roam in the category-theoretic realm of abstract nonsense and perhaps express some clunky piece of code that is hard to read for others on your team into something agreed upon — but you should first mutually agree on the maximal level of abstraction and discuss the individual notions that you decide to choose. Make also sure to establish a benchmarking suite. With Stack or directly with Cabal it is fairly straightforward. It’s not hard at all, just don’t start with the very abstract ideas, and rather consider them as an optimization step. In my experience, working with Haskell occurs to some 90% on the type level, not the term level as with almost every other programming languages.
Haskell is perfect for software architecture, quality assurance, prototyping and high-performance parallel computations. My approach is to implement everything in Haskell first, so as to have a great prototype; then I perform tests and run benchmarks, and if I see no other way to improve performance and it is crucial, I just turn to IPC with C++ and write some API bindings for Haskell. This has long been popular with “Python as a glue” approach. By the way, Numba is phenomenal (Julia’s JIT is awesome too).
In short, there are different situations in which one language and its ecosystem or another one fits best the bill.