Functional programming in C++. Why would you want to do that and is it possible? In this series of posts I’m going to introduce functional programming concepts and show how they can be implemented in C++. See below for an introduction to the series and the kick-off article on Algebraic Data Types.
Since the dawn of computing there have been two parallel approaches to understanding and using what we now call software. The first line of thought, from which C++ was born, focuses on immediate practicality and the capabilities of the machines that are available. The second line of thought, which produced the discipline of functional programming, is a search for simple and beautiful mathematical constructs that captures the underlying essence of software and the domains modeled within it.
The concern of this series is the latter. By lifting thinking about design from the level of pointers, classes, and templates to mathematical concepts, which include algebraic data types, the resulting programs are more simple, general, concise, and composable.
Some of the material may seem difficult at first but if you keep trudging along, the benefits will become clear soon enough. My hope is that once someone works through these articles in their entirety, they will be convinced that a) C++ can be used as an advanced (more powerful than Haskell 2010), functional language that has the added feature of being performance tunable and b) that functional programming is an approach that produces readable, correct, and composable code.
The concern of this article is the mathematical basis and notation for Algebraic Data Types. The sequal will explain how to apply ADTs directly to C++. As you learn these concepts, I encourage you to ponder how a data type you designed recently would be implemented abstractly with ADTs. When I do this I often come up with something more simple or general than my first thought.
Let’s begin…
A type can be thought of as a set of possible values. We use a ∈ A to say that a is in the set A, or in relation to types a has the type A. long in c++ is an example of a type. We’d say 64l ∈ long since the literal 64l has that type.
Algebraic data types deal with how we can create more complex types based on combining others. ADTs are described using 5 symbols: 1, ⊕, ⊗, ::=, and :=. We’ll be looking at each of them below.
Please consider this a guided tutorial. If you have a question or something needs clarification, please make a comment below.
Unit Types
A unit type is a type that has exactly one possible value. There is a primitive unit type 1 that is called Unit. 1 is the single value of type 1. That is, 1 ∈ 1.
Product Operation
Given two types, A and B, we call the type A ⊗ B the product of A and B. A value of type A ⊗ B can be thought of as containing an element of A and an element B. Mathematically, this is often referred to as a pair where the value (a,b) is of type A ⊗ B if a ∈ A and b ∈ B.
Pairs can be generalized to form n-tuples.
Exercise. If ℝ is the type of the real numbers, what would be the type of points in 3-space?
Solution. ℝ ⊗ ℝ ⊗ ℝ
Sum Operation
Given two types, A and B, we call the type A ⊕ B the sum of A and B. A value of type A ⊕ B can be thought of as containing an element of type A or an element of type B.
Values of a sum like A ⊕ B can be represented denotationally as either (0,a) where a ∈ A or (1,b) where b ∈ B.
Given the sum int ⊕ char where int and char are the normal C++ types of the same name, some elements would be (0, 12), (1, ‘a’), and (0, 33). Note that the 0 or 1 discriminates which of the underlying types are being stored in the pair’s second element.
As with the product operation, sums can be extended to n elements.
Exercise. If n is the number of values of a type A. How many values are in type A ⊗ A? How about A ⊕ A?
Solution. n × n for the product and n + n for the sum. Because we define our sum operation to be a disjoint union, values of A ⊕ A are tagged with which side of ⊕ they fall upon. If sum were defined to be a non-disjoint union, A ⊕ A would have only n elements.
Exercise. Using what we’ve covered so far, come up with a type for representing the values of booleans.
Solution. 1 ⊕ 1. The only two values of this type are (0,1) and (1,1).
Type Definitions
Type definitions allow us to use shorthand names for more complex types. The general form is a := e where a is the newly bound identifier and e is the type expression. We read := as “is the same as”.
Expanding on our bool exercise, Bool₁ := 1 ⊕ 1 allows us to conveniently use Bool₁ wherever we would otherwise use 1 ⊕ 1.
Bool₁ as defined suffers from a major drawback however. The type 1 ⊕ 1 can be used to represent any type with two elements. For example, a state of “on” or “off” could be represented as 1 ⊕ 1 just as easily.
To remedy this we include an alternative type definition ::= (note the two colons), called “is implemented with”. a ::= e states that a is a distinct type from e (for all v ∈ a, it is not true that v ∈ e), yet there is an affinity between them (given a va ∈ a there is a corresponding ve ∈ e and vice versa).
To denote elements of type a where a ::= e, we surround an element of type e with parentheses and give it the subscript a. For example if ve ∈ e, (ve)a is the value of type a that corresponds to ve of type e.
Exercise. Denote the values of type Bool₂ where Bool₂ ::= 1 ⊕ 1.
Solution. ((0,1))Bool₂ and ((1,1))Bool₂
Exercise. Consider the following definition of Bool₃:
T ::= 1
F ::= 1
Bool₃ := T ⊕ F
Denote the values of type Bool₃.
Solution. We start with elements of base types and work our way up.
T has exactly one element, (1)T.
Similarly the element of F is (1)F.
Therefore the elements of Bool₃ are:
(0,(1)T)
(1,(1)F)
Type Functions
Type functions allow us to create reusable type templates. The general forms for type functions are f a₁ a₂ … an := e and f a₁ a₂ … an ::= e where f is the name of the newly bound type function and the type expression e may use a₁…an.
Consider an OpInt type that can be either an integer or nothing. A simple way to declare OpInt is as follows:
none ::= 1
OpInt := none ⊕ int
If we think optional values are useful in a more general context, we can declare a type function Op that creates various optional types based on its type argument:
none ::= 1
Op a := none ⊕ a
Exercise. Define OpInt using Op from above.
Solution. OpInt := Op int
Recursive Types
Interesting types occur when type definitions are allowed to be recursive. That is, the name to the left of the ‘=’ symbol also appears on the right hand side. Here are a few examples:
The natural numbers N:
Z ::= 1
N := Z ⊕ N
If z is the single value of type Z, values of N take the form:
n0 = (0, z)
n₁ = (1, n0) = (1, (0, z))
n₂ = (1, n₁) = (1, (1, (0,z)))
n₃ = (1, n₂) = (1, (1, (1, (0, z))))
Exercise. Define a list type L of arbitrary types a. Show a few values of type L char.
Solution.
emptyList ::= 1
L a := emptyList ⊕ (a ⊗ L a)
And a couple values of type L char:
- “” = (0, emptyList)
- “Hi” = (1, (‘H’, (1, (‘i’, (0, emptyList)))))
Since the types in the sum are disjoint, we can also represent these values unambiguously as follows:
- “” = emptyList
- “Hi” = (‘H’, (‘i’, emptyList))
Exercise. Declare a type for binary trees BTree, with values of type a at leaf nodes. Each node is either a leaf or has exactly two subtrees:
Solution. BTree a ::= (BTree a ⊗ BTree a) ⊕ a
Exercise. Declare a type for binary trees BTree₂, with values of type a at leaf nodes and b at branch nodes. Again, each node is either a leaf or has exactly two subtrees:
Solution. BTree₂ a b ::= (b ⊗ BTree₂ a b ⊗ BTree₂ a b) ⊕ a
Exercise. How do the above trees differ from BTree₃ (Thanks to Peter Marendic for inspiring this exercise):
emptyTree ::= 1
BTree₃ a ::= emptyTree ⊕ (a ⊗ BTree₃ a ⊗ BTree₃ a)
Solution. BTree₃ allows for a empty trees and branch nodes containing 1 subtree as well as 2.
Next up, we’ll talk about how to realize algebraic datatypes in C++ using Boost libraries. See you soon!
- Algebraic Data Types
- Algebraic Data Types in C++
Nice introduction, though I must profess that I found the last two examples unnecessarily confusing.
I’ve always thought of binary trees as having values at their roots, so my solution for a data type for binary trees with type a at their leaves was:
Btree a ::= (a x BTree a x BTree a) + a
The confusion with the second example resided in the term ‘branch’: normally by branch of a tree I consider a whole subtree rooted at a particular node. Only by looking at the solution did I actually see what you meant
Thanks for the comments!
So would you consider “BTree a ::= (BTree a ⊗ BTree a) ⊕ a” to not qualify as a binary tree?
I thought that branch/leave terminology were standard fare for trees. How would you reword the exercises to be more clear in your mind?
Well, if I’m reading it correctly that expression is describing a tree whose only “a typed” values can be found at the leaves. In that case, it’s just a matter of definition. I don’t have a relevant math book at hand, so I would not hazard to guess what the actual customary definition is.
In my experience, all the binary trees I’ve worked with were of the type:
emptyTree ::= 1
bTree a ::= emptyTree ⊕ (a ⊗ bTree a ⊗ bTree a)
As for the wording of the second exercise, I would put it like this:
Exercise. Declare a type for binary trees BTree₂, with values of type a at leaf nodes and b at non-leaf nodes
Your bTree is an excellent example! I’ve added it to the exercise and attempted to clear up the wording. Thanks!
At first I found it rather mind-bending to consider that values of the natural numbers all have distinct structure (and not just distinct data), but then I realized that the type you defined has arbitrary precision. It will be interesting to see how C++ integral types are represented algebraically.
The C++ integral types are “special” because we only have lower limits on the number of values they have.
Consider
unsigned int(uint). We could represent it in a unary wayWhere there are at least 65536 1‘s in that expression.
Assuming the number of possible values for
uintmust be a power of 2 (I don’t think this is the case, although I think it is generally true), we can use a binary representation.Where there are at least 16 bits in that expression.
Assuming the number of possible values for
uintmust be of the from 28n we could use octets to add another level of structure…It should be:
bit::= 1 + 1 uint::= bit x bit x …. (instead of +)
Fixed. Thanks!
I’m curious about how type functions would interact with ::=. Does
make sense, and if so, how would its meaning differ from the definition you gave?
Yes, it makes sense. “is implemented with” (a ::= e) introduces a new type a that is distinct, but related, to the type e whereas “is the same as” (a := e) is introducing a convenient name a for the exact same type e.
Imagine I have a function f
If Op a := none ⊕ a, I can call this function with the value (1none, 33). If, on the other hand Op a ::= none ⊕ a, I cannot call the function with the value (1none, 33) because it no longer has the type Op a. I must call it with (1none, 33)Op int.
Hmm…
So, in this exercise, values of type X are written as ( … )X
So shouldn’t that be
(0,(1)T)Bool₃
(1,(1)F)Bool₃
?
Recall that Bool₃ “is the same as” T ⊕ F. The (v)a notation is for values of type a where a “is implemented with” another type (a ::= e). The subscript is required to distinguish between values of type a and values of type e.
Am I the only one waiting for the next article in the series?
I enjoyed the style and your appetizer (more powerful thank Haskell !) is interesting to me.
As a remark: is there a reason for using the word “affinity” when introducing “::=” instead of something like “isomorphism”? As far as I can tell, your “is implemented with” corresponds to an invertible mapping P from A to E, from which it follows that (assume that a, b belong to A, g is a function on A) 1) g a = b implies that 2) g P^(-1) P a = P^(-1) P b (since P^(-1)P is the identity) and applying P to both sides you have 3) P g P^(-1) P a = P b which amounts to 4) g’ a’ = b’, where a’ and b’ belong to E and g’ is a function on E. This is an isomorphism, isn’t it?
Since I have no particular background in category theory I could be wrong, please correct me.
Thanks for the comments! I ran into a couple technical hurdles and timing issues, but the next article should be out soon.
Yes. The reason I used the word affinity instead of isomorphism is to help the reader build an intuition without getting into technical detail. The affinity we speak of is precisely the isomorphism you mentioned, that is, a structure preserving mapping.
Rather than trying to plough back and forth until I think my understanding is right, and then asking you to confirm it, I’m going to take a different tack. I’ll post something that I think means my understanding is wrong, and by the way that you guide me with a correction should lead me to be sure I understand.
You posted that:
and later in a comment:
Would that mean that:
Values of a sum like A ⊕ B ⊕ C can be represented as either (0,a) where a ∈ A or (1,b) where b ∈ B or (2,c) where c ∈ C.
In case what I have inadvertently done is to post something that only a crank would post (which isn’ t my intention at all), you could probably set me straight just by completing the phrase “Values of a sum like A ⊕ B ⊕ C can be represented as …”
“Values of a sum like A ⊕ B ⊕ C can be represented as …”
Well, there are a couple options here actually. If we want A ⊕ B ⊕ C to be a distinct type from A ⊕ (B ⊕ C) then your suggestion will work, that is
values of a sum like A ⊕ B ⊕ C can be represented as either (0,a) where a ∈ A or (1,b) where b ∈ B or (2,c) where c ∈ C.
If, on the other hand, we want A ⊕ B ⊕ C to be the same as A ⊕ (B ⊕ C), then we’re just saying that ⊕ is right associative and:
values of a sum like A ⊕ B ⊕ C can be represented as either (0,a) where a ∈ A or (1,(0,b)) where b ∈ B or (1,(1,c)) where c ∈ C.
Does this help?
I too come from a more mathematical background. But it seems to me that pretty much all programming concepts that are not language specific have mathematical roots: any programmer looking at algorithmic complexity or graph structures or parsers or artificial intelligence needs to know some set theory et al. It is part of the power of C++ that there can be fairly immediate translations from these abstractions into actual code.
So I would argue yes, topics like this have direct relevance for real-world programmers.
Interesting aspects. I was always thinking if it is possible to adapt the ideas of ”Algebraic Dynamic Programming” http://bibiserv.techfak.uni-bielefeld.de/adp/ in the world of C++.
Giegerich et al write powerful algorithms in a (purely) functional language (haskell in this case) and translate then into C-Programs, so they run fast
Your Algebraic Datatypes might be the first step on bringing his generic, functional approach to C++. His algebra though uses “parser algebra”, I think, it seems more complex then mathematical operations, but I am note sure.
I was always wondering, why go through Haskell? Couldn’t I write a readable C++-Program with the right ADP Template Library? Then the C++ compiler would translate my program into a nicely running program directly.
Thanks for the pointer! I haven’t been exposed to ADPs yet.
That kind of question is exactly the motivation for this series! My hope is that once someone works through these articles in their entirety, they will be convinced that a) C++ can be used as an advanced (more powerful than Haskell 2010), functional language that has the added feature of being performance tunable and b) that functional programming is an approach that produces readable, correct, and composable code.
Is 1 ⊕ 1 the canonical way Boolean is defined in ADT-land, or is it a “hack” that fits Booleans into the context of the concepts you’re discussing? It feels a little like a hack to me, in the sense that the value of the Boolean actually gets entirely represented by the discriminator. i.e. in (0, 1) and (1, 1), it is the first element of the pair that represents the entire value of the Boolean. Nobody would use
boost::variant<Unit,Unit>where they meantbool, would they?Considering 1 ⊕ 1 to be the same as Boolean is problematic. Although both types contain exactly two possible values, the type Boolean implies meaning beyond the fact that it has two elements.
For example, Boolean implies an algebra with operations such as
!,&&, and||.To use 1 ⊕ 1 to implement Boolean (assuming it wasn’t built in), while keeping their distinction, I’d use “is implemented with” (Boolean ::= 1 ⊕ 1). In C++, the topic of the next post, this would look something like:
//Boolean ::= **1** ⊕ **1** struct Boolean { typedef boost::variant<Unit,Unit> Impl; Impl impl; explicit Boolean( Impl impl_ ) : impl( impl_ ){} }; const Boolean true = Boolean( boost::make_variant_c<0>( Unit() ) ) const Boolean false = Boolean( boost::make_variant_c<1>( Unit() ) )So no, I wouldn’t use
boost::variant<Unit,Unit>where I mean bool. I see these as distinct types although one can be implemented in terms of the other.As an aside, I do want to note that the template arguments to
boost::variantmust be distinct types otherwise behavior is undefined.Back to your question. 1 ⊕ 1, on the other hand, may be the canonical type that has two elements and 1 ⊕ 1 ⊕ 1 the canonical type that has three. For four elements, we have two different candidates for cannon!
Perfect explanation, thanks!
Surely these concepts could have been conveyed in a way that didn’t use a whole bunch of mathematical jargon and symbols without defining them first or motivating their need. I suspect this article is totally impenetrable and uninteresting to the vast majority of programmers who would benefit from it.
This article series is about realizing mathematical concepts in C++. It makes sense to introduce the accepted terms (i.e. “jargon”) and symbols of that domain at the beginning, and I don’t think David started using any of those symbols or terms without defining them first. I agree that it would be nice to have a little more motivation for why one should care about algebraic datatypes, but I’m willing to be patient and see where the series leads.
Whether or not the subject of this article is going to be accessible enough to the general readership of C++Next, I cannot say. It’s obviously not easy material, and it certainly leaves me with a few questions, which I’ll post in other comments. However, C++Next is an advanced C++ blog and there is at least a segment of our readership that can benefit from what David is doing.
I feel quite the opposite.
I think trying to add more motivation than the slightly-tongue-in-cheek introduction would lead to tangents that might discourage the reader from getting to part that describes the formal concepts (5 “symbols” + type functions).
The readership of this blog shouldn’t have any trouble with the jargon and symbols presented in this post, and for anyone having tried to read a paper from the functional programming community, this may already feel illuminating. Conciseness is sometimes a quality in itself (and I think it is in this case).
Excuse me for my ignorance, but what is the point of this exercise? Has it any real-world applications (if so, which ones?) or is it of pure academic interest? /Steve
I’m not to sure how to answer your first question because I think it is pretty clear that the intent of this post is to introduce ADTs which are prerequisite for the next post on ADTs in C++.
To answer your second question, yes it has real world applications! ADTs are so fundamental that they apply to most applications. By lifting thinking about design from the level of pointers, classes, and templates to mathematical concepts, which include ADTs, the resulting programs are more simple, general, concise, and composable.
As another exercise, take any data type that you created recently and try formulate it into an ADT and see what you come up with. When I do this I often find a deeper meaning in what I was trying to do and perhaps something simpler or more general.
At this point in the series we’re pretty high in the platonic world of mathematical forms. I hope in the next post to show how to plant our feet firmly back on the ground with ADTs in C++.
In contrast to the comments of Steve and Eric, let me say I loved this post.
I left the world of pure mathematics behind 10 years ago when leaving university to become an in-the-trenches commerical C++ programmer.
To see the two themes of my working life married together like this so explicitly is fantastic. Roll on the next post!
David, that beautifully and concisely sums up the motivation for this article. I think if you put all this in the beginning of the article you could replace most of what you just added.
Thanks for pointing this out. I wonder what specifically you think I ought to keep/remove from what I added.
I don’t know; I find the current style a bit florid where the first revision was probably a bit too terse, but that may just be a matter of taste. The current revision deals mostly with the culture clash between purists and pragmatists, but doesn’t say much about the practical motivation for wanting to explore this stuff beyond satisfying my idle curiosity about whether and how these two styles can be made compatible. I think, rather than asking people to be patient with the unfamiliar in the intro, it would be more powerful to give them a real reason to be interested, as you do here.
I loved the article.
I felt that I didn’t get type composition from EoP very well. This introduction was very enlightening already.