Functional C++
Henney, Kevlin
Functional C++? As opposed to what - dysfunctional? Well, kind of, yeah. Sure, in C++ the principal unit of composition is called a function, but that doesn't mean it's a functional language. And the idea of restricting mutability of state gets a nod with const, but it's a nod not a hug. And the STL shows influences of functional programming, although it falls short of being compositional. And, yes, sure, C++11 has lambdas, but then again, these days, who doesn't? Lambda calculus was invented in the 1930s. This talk looks at how to express functional programming ideas in (post)modern C++ in a way that can be considered idiomatic to C++, rather than trying to use the power of overloading and metaprogramming to pretend C++ is Haskell or Lisp. In short, immutability beyond const and into shared and persistent data structures, concurrency beyond threading and locks, and thinking about functions as transformations and units of composition rather than actions.
 Right, okay, I've just saved you from some very, very mellow music. Okay, so, this is what I'm going to talk about. Well, I'm going to talk a bit about this because as I was putting together the slides on the flight this afternoon, I realized I had far too much material for this talk, and I thought, okay, I'm going to have to subset it. So, I will, in some cases, I will talk, I will, because this is C++, I will use pointers to refer to other things. I will not include the whole thing. I will use that level of indirection that I feel is my privilege. So, this is, I guess this is as opposed to dysfunctional C++, which is a talk on C++ style, and I'm not doing that one today. Although this clearly has an impact on the style. Let me think. Anything else? Who's seen me give a talk before, just so I know how many jokes I can reuse? Okay, reuse is a good thing, just so we're all clear on that one. Right, Kevin and Henny, I've got my name on a couple of books there, and probably better name for 97 Things Every Program I Should Know, but I'm not going to be talking about these things. But I will start off with a quote from one of the contributors to 97 Things. That man there, Michael Feathers. A few years back, he made this very good observation. Object orientation makes code understandable by encapsulating moving parts. Functional programming makes code understandable by minimizing moving parts. It's a very, slightly different philosophy. Now, already, if you're astute, you will see that these two are not necessarily in contradiction, but there is a very large overlapping space, and it turns out that C++ can inhabit this space as well as or as badly as it does other spaces. And I want to explore that. Now, in preparing this talk, a perfect piece of timing. Yesterday, somebody tweeted this, a blog from Facebook about how they'd built, and it's gone about building Facebook moments, and the timing was perfect, because to keep our C++ API boundary simple, we adopted one-way data flow. I would like to talk about that at length, but that may be one of the things I'm going to shorten. The API consists of methods to perform fire and forget mutations, and methods to compute view models required by specific views. Now, some of that's going to go a little bit outside into the architectural space that surrounds this, but it all follows. To keep the code understandable, we write functional style code converting raw data objects into immutable view models by default. As we identify performance bottlenecks through profiling, we added caches to avoid recomputing unchanged intermediate results. What I find interesting about this is that they have specifically pursued an architectural style and said, this is the style we would like to build this in. This is the style we would like to code in, and if there are problems, instead of hacking the poor thing to pieces, as it happens in so many code bases, what we will do is we will preserve the model and support it, find out where it needs to support. In other words, build it so that it is easy to work with this stuff. In other words, that very clear idea, rather than a morpher's mass of code, you have an infrastructure that doesn't merely push bits around, but it actually supports specific styles and qualities of the code. The resulting functional code is easy to maintain without sacrificing performance. Those two phrases in one sentence, that's always good to hear. So what do we mean by functional programming? Well, this is a tag cloud that I kind of been using for the last couple of years. It's a lot. I mean, this is the thing. Functional programming covers a lot of things. I'm not going to cover all of these things. Some of them simply cannot be expressed in C++. Some of them have a natural limit. So for example, with recursion, actually we will cover recursion briefly a bit later, but there's no tail recursion, tail call optimization in C++, and that actually means that there's a certain things you cannot express conveniently. Pattern matching is not reg X's, and it's a little bit outside the space. One could say the whole of the language is a big monad and have a beer over that. I strongly suggest if you wish to understand monads, lots of alcohol. Lots of alcohol. I think I achieved an understanding of monads once when I had lots of alcohol, and I've been unable to recover that understanding since. It is lying on the floor of a hotel room somewhere. However, we will talk about this kind of more declarative approach, higher order functions, pure functions, immutability, landers, and so on. I'm going to start with a very simple example, a very humble example, because some folks from Down Under have been tweeting, that I know are in Oslo at the moment, have been tweeting, and sort of like what kind of weather is this? It's supposed to be summer here in the Northern Hemisphere. It's just like, well, I can say having just come from Southern England, yeah, it's warmer in Southern England by about three degrees. So yeah, that's totally sunburn weather. So we have two seasons basically in much of Northern Europe, grey and construction season. And because of that, when people talk about air conditioning, they're normally talking about offices. So I use the heating system example rather than anything else. The heating system, you want to turn it on, you want to turn it off. Nice and simple. We want to do it on a timer, so I'm going to create a convenient timer abstraction. I can pass in the time of day, I'm going to go ahead and I'm going to say, well, obviously I've read about this kind of thing. I need to perform an action, and I need to apply an action to an object independently and asynchronously from the very decision to do that. How do I decouple the decision that I want to do that from actually doing it? Well, I'm going to use the command pattern. So I'm going to go straight for it, and I'm going to have one of these. Oh, it's all classic Gang of Four stuff. And then we go ahead and we start implementing it. And it's just like, okay, this is the code for turning on. And that's without adding any ritualistic enterprise banners or other noise. And then there's the turn, oh, actually wait a minute, it's just minor, minor fix. This is the great thing about the PowerPoint Monad. Let's just fix that. Yeah, there we go. That's what I needed. I think this qualifies as live coding. There we go. And there we go. So that's what I'm fixing. It might look like I've just done copy and paste. I couldn't possibly comment. Because unfortunately, that is the feature that you're going to end up with. With this style, it's a very copy and paste approach. So to bring that into perspective, you're going to end up with lots of stuff like this. Copy, paste, copy, paste. And this is just a very simple thing. If you look at it, it's mostly programming language noise. We're doing a lot of work to support style. Some people say, wow, this is problem with objects. It's not. It's problem with doing objects in a sucky way. However, a lot of people in C++ won't look at it like that. They will say, oh, you know what? Within C++, there is another language trying to get out. And it's called C. So this is far too much code. I'm going to just go and use function pointers. I'm going to pass in a function pointer for an action to execute. Then I'm going to pass in the context data with it. And then I'm going to get one to execute on the other. So it's just like, yep, so this is it. Void pointers. So void pointer is a way of selling the compiler. Thanks. Thanks for all your help. But I'll take you from here. Trust me on this one. Don't need to tell me about types. It's trust the programmer time. And so we go ahead and we've got that. And this is nice because everything come down to sort of one-liners. The only problem is that there is a tacit agreement between, there's a contract here that is difficult to enforce within a language that has typing. In a language that is dynamically typed, this is curiously enough not a problem in the same way. Because it turns out that if I try and do the wrong thing with an object in a language that is dynamically typed, the language tells me in a useful way that I can do something about. As opposed to wandering off and doing mysterious things to bytes that I really shouldn't be entitled to do. If I do not pass in a thing that can be cast to a heating system, all bets are off. And it gets very exciting. So this is not the kind of stuff. The brevity we like, but the kind of the syntax noise, and sometimes people go, oh, that's OK. You can just use a C-style cast. No, no, no, no, no. Casts should be ugly and big and explicit. One, you can grep for them. And two, it's a big warning sign saying, look here. And I've actually had one person say, I don't like using those casts because all of my code, you get two levels of casting. Reinterpreted cast and casting. I said, that's your code trying to tell you that it sucks. Listen to your code. OK. So, OK, what we're going to do is we're going to say, ah, right. We're going to encapsulate a function concept of some kind and make it a complete one. In other words, I'm going to say, I need a thing that looks like a function. So I'm going to go over a little bit to the sort of looser side of things. I merely need to be able to call it as something that doesn't take any arguments and returns. Nothing. I'm going to say, right, OK, that's fine. I don't actually care that it's a function. It merely supports a function protocol. That's it. It can be a function object. And we can do a whole load of really neat things with that once we've got that. The only thing that we discover is we don't actually need to define a function as we did with the C-style. We certainly don't need to define a class as we did with kind of misapplication of the gang of four. So I can now create two objects on and off. This is when I want the time on. This is when I want it off. And I'm going to bind the very action itself turning on, which I already have in the heating system. In other words, we already have the functionality. We don't need to wrap it. I'm going to bind it immediately. At the object level. So I can do this. So bind is basically a higher order function that takes a function or something function like and yields a thing that can be executed as a function. So this is all good. That is now in the C++ standard. And I might have ported that one from boost code if I think about that one. So let me just be strictly politically correct here. There we go. I'll keep the police off my back. And but then obviously people are like, yeah, I can't get what you're doing. But then we've got lambdas. So it's even easier at that point. We just pass in a piece of code that is a function object, but that's the language doing it for us. Pass it in and we're done. So in other words, we haven't had to create any intermediate type level abstractions. We haven't had to create or declare other function abstractions. We haven't had to compose on the fly. And it's this compositionality that is the key to any style that we want. So we could say, well, you know, this is really very, you know, this is C++ 11 and this is all very 21st century except we need to remind ourselves that Lambda calculus is actually older. William Cook identified it as 1941 in rather good presentation and paper on understanding data abstraction revisited. But I did a bit more digging around and it turns out it's 1932. So C++ 11 now allows you to program like it was 80 years ago. Yay. On the other hand, there are some glorious pieces in that syntax, some of the syntax decisions. So if you've not really messed about with lambdas, I'd just like to point out that that is valid C++. And in fact, so is this because this executes that valid C++. This is something that takes no arguments, returns nothing, captures nothing, and does nothing perfectly. It's a very cohesive concept. This one executes it and therefore does nothing. Huh? With any luck, yes, yes. But it now gives your cat new and exciting opportunities for running across your keyboard and actually yielding a valid code base. All of which, you know, what is a program? Nicholas Verth answered this one for us many years ago. Algorithms for Stata Structure Equals Programs. Now, the thing here is that normally for a lot of people, that means historically, I'm going to take my algorithm and data structures and then mash them all together, and that's my program. Now, actually, the idea here is we would like to separate these things out. This kind of composition style thinking. Now, what we've actually seen already with just being able to treat functions as first class objects, that is you can argue, and both people and both sides do, which is why it's generally better to get yourself a seat to the side and watch both sides going at each other, because I think that the previous solution was a very good sort of functionally inspired solution or it was a very good object oriented solution. Both apply. But here's a different perspective. Let's take this a bit further. This kind of inspiring thought has been algorithms are a way of doing something. Data structures are merely what we do them with. The most obvious space in which this is separated in C++ is the STL. This was Alex Stepanov's original goal, basically, to be able to say, I wish to separate out the abstractions of representation from the choice of algorithm that I've got, and I wish to keep these separate, but in a way that is composable and allows me the efficiency. So, in honour of the fact that a couple of years back with Anders Noras at this conference, in fact, we did a whole bunch of stuff on functional programming messing about with languages. I thought I'd use one of the examples that I introduced in that one. It depends how good your memory is, but the world was going to end in 2011, twice, actually. The date advertised, and then when Harold Camping discovered that the date had not actually transpired as the end of the world, he said, no, no, no, I meant six months time in October or so, and that didn't happen either. But then we had the end of 2012 because apparently the Mayan calendar was going to run out. Nobody ever worries about the fact that the regular calendar runs out in December and then cycles back. It uses modular arithmetic. It turns out the Mayans were onto this one as well. So it didn't end in 2012, and it didn't end at the beginning of last year, which is supposed to be Ragnarok last February. That didn't work out either. However, this one was memorable because I was actually in New York. It was Friday the 13th. This is the site of the former World Trade Center, and if you're going to advertise the end of the world, this is a great way to do it. Stand there with a billboard on Friday the 13th, right next to this iconic and sad location, and there you have it. So let's find out. Friday the 13th, what do we know about it? Paris-Gavie-Decaturia phobia is the fear of Friday the 13th, so if you learn nothing else today, that's useful. And we need, for a certain class of the population, we need to find out when is this going to be. So we go away and we hack some C, and we use struct Tm. We do all kinds of stuff, and it's kind of all there. The only highlight is perhaps that we have daily sex. But, you know, you're kind of running around this loop looking for this stuff and looking for the next answer. Now, this works, but it's a bit messy. You've got the usual kind of hieroglyphic noise. There is something that we can do with this from a C++ perspective, and it's actually sort of a separation. Back to our friends at the Landers. I'd love to tidy up struct Tm, but I thought I'd leave that one outside the scope of this problem. Find if, from here, so I want to start from today, or actually tomorrow, then I'm going to have a token that is infinity. This is the best way to represent infinity, something that you can never reach. This is how we do this. The easiest way to deal with infinite lists, and this is something functional programmers do all the time, is you make sure you don't have all of the list at once. Infinity is incredibly easy to deal with if you start at the beginning. If you try and hold it all at once, you're screwed. But if you say, from now until beyond the end of time, then we're okay, because it turns out we will find Friday the 13th before that. You're guaranteed, if you go through it, you're guaranteed there's a couple every 500 days. So what we've done is apply a filter to this one. This is just a placeholder, and we've introduced a day iterator. This idea of using iterators, we tend to think of as a very classic object-oriented solution, but in another sense, it's actually a really good way of looking at lazy evaluation. I wish to consume the content of a container, physical or abstract, but I don't wish to do it all at once. I wish to do it one element at a time. I want to work from the head through to the tail, and then I will take the head of that tail and so on, and I will do this, and on demand, values will appear as I need them. This is the basic idea behind an iterator, although people don't tend to think of it like that. But that allows you an ordered simple access. Now, in the next C++ standard, C++ 17, they're coming thick and fast, C++ 11, C++ 14, then there's 17. The next C++ standard will introduce a range concept that will allow us to tidy a little bit of this up and actually use a much more pipeline-style notation to compose these things. Unfortunately, this is one of the reasons that, although I remember being very excited by STL iterators, because I used to think that operator overloading was really cool, and actually I still kind of do, the problem is that not everybody thinks like that, and so you have to go away and write stuff like this to wrap it up. So there's a bit of boilerplate, unfortunately, but this is a supporting abstraction. If you're only going to do it once in a piece of code, then you might be better off doing that, but the minute you do it twice, I think you're better off doing that. In other words, I am going to give you the tools from which to compose these elements, and then you can go and search for the, turns out Friday the 13th is geographically dependent. Some people don't like Tuesdays. For other people, 17th is bad, so you want to generalize this at that level. So suddenly I've got a way of doing this. Now, given this is a language of the obscure corners, and I want to talk about this idea of immutability and not having side effects, there's a kind of interesting piece of the language. A couple of you have seen this before. This is an interesting historical note. Irvin Unruh, Siemens, we used to work for Siemens, the compiler division, like all great works of art. This is untitled. He discovered, let me put it this way, this piece of code doesn't compile. It's a whole load of template stuff, and it doesn't compile. And you might be thinking that's not exceptional. People often create templated code that doesn't compile. Big deal. Yeah, but when this one fails to compile, it prints out the first few prime numbers as part of its compilation message. Now, that I don't get normally from this kind of code. And what Irvin had discovered was that C++ templates are chewing complete. It's one of those little accidents that wasn't the original plan. It turns out anything that you can compute can be computed with them. And this gave rise to template metaprogramming, which has turned out to be anything but temporary. It is a way that many C++ programmers will secure their job by writing code that people just will look at and go, I have no idea what that is. I really don't understand what it does at compile time. And then it's become so commoditized and sophisticated that people have been creating libraries for years. In Boost, there is a template metaprogramming library that Adam Peterson used to solve one of the harder problems that we know in software development, FizzBuzz. And again, this piece of code does not compile. And its compilation message is indeed FizzBuzz. One, two, Fizz, four, Fizz, seven, eight, Fizz, buzz, eleven. That's a great compilation message. Now, why am I showing this? One, it's frivolous, it's fun, and two, it's pure functional programming. There are no side effects. At compile time, you do not have state that you can manipulate. At compile time, you have an execution model that is based on, if you like, a pure value model. And functions, they're not functions in the, certainly not what I just showed you, are not functions in the classic sense. They are kind of meta functions. And Fizz is masquerading as if they were functions, they're doing computations on types or on compile time values. Now, it turns out that you can actually do useful stuff with template metaprogramming and have it compile. But C++11 went a step further and allowed us to do the stuff at compile time and have it compile, which is kind of useful. Again, not the most useful piece of code, but I can say that something that has no side effect, therefore, is a constant at compile time and actually have that expressed directly. Nothing with side effects is allowed in there. There are certain constraints on what you can put in a constant X for a function, which have been loosened a little bit with C++14. But the idea here is that you are able to use relatively ordinary C++ code rather than kind of weird out template metaprogramming or resorting to macros to achieve, to be able to use this to express yourself. And I think this is the key idea, to express yourself and say, I want that value and I would like it computed because either it needs to be a compile time constant or I do not wish to have a runtime computation cost associated with it. And therefore, it would be nice if it were done this way. And that I don't go off and have to pre-calculate it off to the side. I want it in the code. I want the code to express that as clearly as I would any other functional composition that I would use. So that one actually addresses that problem, which kind of leads us to this idea. This kind of classic quote from Lucius Carey, an unfortunate figure in the English Civil War, who left us with a rather useful quote, when it is not necessary to change, it is necessary not to change. And we know pretty much that within C++, the main reason that, the main way people express this unchangingness is through the const keyword. Now, it goes a bit further than that. I mean, there's not simply just const correctness. But const is basically a promise that is, well, it's C++, you can violate it quite easily. We want something that's a little bit deeper. We want to go much, much deeper than this. We really want to say, we don't want things to change. Now, a lot of people think it is kind of a right that an object should be able to change state, and that if I have a piece of state, therefore it is changeable. There is a kind of question here that is pushed at us by functional programming. Are you entitled to change state? Does that actually make sense? Now, there are a couple of other things that kind of go with const. One of them is reference. Pass things by reference, make sure they don't change. But const in this sense is only a read-only promise. So we need to be very careful with that when we start saying, actually, I want something to be truly immutable. C++11, we've also got r-value references, which also support this idea that maybe I can actually copy things around, rather than merely pass them around as references that are read-only. I can actually say, here, have a copy of something, even if it's a vector that's this big, and I can pass it to you, and that's a cheap operation. If you've not looked into r-value references, I strongly recommend it. They are one of those features in the language that is sure to allow people that know what they are to keep their jobs against people that don't know what they are. It's much harder than a lot of other ideas floating around at one level, but once you understand why they tick, why they work, then it kind of makes a lot of sense. But you have to have sort of an optimization head about you. It's very much for the person providing the abstractions. Now, I want to take this and contrast this with these two basic approaches. I'll take a description from a pose of four. So very commonly, a number of languages, we make these observations. References to value objects are commonly distributed, stored in fields, as stored as data members. Have a state change to a value caused by one object can have unexpected and unwanted side effects for any other object sharing the same value instance. This is a kind of a common problem. The minute you have any kind of aliasing and you combine it with state change, this becomes an issue. And C++ has no shortage of aliasing mechanisms. Copying the value can reduce the synchronization overhead, so we would care about this in a threaded environment. This matters, but I'm going to say even without threading, aliasing can produce enough surprises to keep you on your toes. But you've also got an object creation overhead. Copying is not for free. It turns out that in many cases, copying is the cost that we need to address. And this ultimately gives rise to the idea of immutable values. Therefore, define a value object whose instances are immutable. Now, this technique is used extensively in reference-based languages such as Java and C-Sharp and basically saying, I don't want to change that object, therefore, we can share it freely. Because I cannot actually change the state of it, it doesn't matter what you do with it because the one thing you can't do is something that's going to change my perception of that object. This is kind of anathema to a lot of C++ developers who regard the idea of assignment as a fundamental right. And we can kind of compromise a little bit. It's also not that idiomatic because it spends a... There's a lot of assumptions about heap usage here that are not shared in C++. So there's another technique that we're more likely to use. I'll skip the blurb. Copy value. C++, I get copying as part of the language. I don't get that in a number of other languages. If I pass an object back to you, you get a reference to that object. If you want to copy, you have to ask for it. It's unfortunate because the syntax, you have to add syntax and you have to remember to add syntax. So this is the bit you get for free. This is the thing the language does for you for free. So let's go and hack around with kind of one of those examples that people always wheel out. I certainly do. A date example, year, month and day. There is only one true ordering in case you're wondering. There are three orderings on the planet. And there is only one correct one. And there's one that's kind of correct. And then there's another one that reminds us why there's an Atlantic Ocean. And I've left out the r-value versions. The idea is that we're getting the copy operations for free. This is kind of hard-wired into C++ as a DNA. And it's not necessarily a bad thing, although people sometimes find themselves fighting against it because they work in a different style. They're trying to do a sort of Java style C++, which is not entirely successful. And they go ahead, and without even thinking, in fact they probably got it in their editor, they go ahead and they're kind of like, yeah, I'm going to type a getter, and then there's a setter because all getters have a friend, a setter. They have a buddy system, it turns out. And I just want to say, no, no, no, no, no, no, no, no. This is not a good thing. This is a bad thing. In fact, we want to question that. So let's get rid of that assumption. The idea of individual field sets for something that has a complex invariant like a date makes no sense whatsoever. You need to set it all at once or not at all. So the first thing we do is restrict the channel of change. So we might provide a set operation that does appropriate validation, and then we can go ahead and do sets. Okay. But actually, we got one of these for free. We've already got it. It's called the assignment operator. It does it. It does the right thing. It basically means that if you construct a date correctly, you need to do an extra set of checks, as I would have done with set. So for example, the validation here, this has to validate the new state. And if the new state is incorrect, I presume we may throw an exception, and leave the old state intact. Or if we're programming without that kind of mindset, we will just set it and say, well, you're on your own. It's an invalid object. But here we're saying, no, no, no, we're going to actually use this, which will do the validation. So you localize the validation in one place, the point of creation. That is what a constructor is there for. It is there to give you a valid object. Once you've got a valid object, you can pass it around. You can take copies of it for free, basically. So we've got that. Now, we've got a few other syntax choices we can mess about with. I'll leave it to you to sort of decide which one you want to go for. But there's one more refinement I'm going to make to this class. Honestly, people, what is it with the get? I'm a native English speaker, and I'm here to tell you that get, something, is imperative. If you're trying to get functional, don't use imperative naming. That's the first thing. And what does get imply? A lot of you ask a lot of programmers who speak a different language, and I'm also talking about people who speak English as a first language. Programmers suddenly forget that they already knew a language. And I say, what does get imply? And they say it implies it's a query. No, it doesn't. Really, it doesn't. So let me think. Today, I got up to get a flight. A few years ago, let me think, what did I do? I got married. I went to the cash machine today to get money. In every single one of these, there was a big, profound state change. Now, if you can show me a cash machine that doesn't, you know, have that little side effect of reducing my bank balance, I want to use it. But get means I am going to change your state. So next time somebody defends this as a naming convention, you say, you cannot have a const getter because, by definition, a getter is not a const thing. It is a state-changing thing. That's what it means in English. So we're also going to have this nice side effect. Oh, no. But it's okay. It's in the PowerPoint monad, this nice side effect of, oh, sensible names. It just means year, month, day, month. If you want to try and affect a functional style, then don't use imperative naming. Now, this point about values is interesting because values form kind of a staple ingredient of this space and this functional space. The idea is that we are trading not so much in objects with identity, but in values. And as we know, mathematical values are surprisingly unchanging. So if I take five, there is nothing I can do to it to make it any other number. If I ask to add one to it, I don't get back five modified, I get back six. Everybody else using five keeps using the same five. Now, in C++, we do this by copying things around and saying the state of those bits represents that value and there are a set of operators we may affiliate with them. But it also ties in more deeply. This is a number of years ago, oh, get the templates there. I had a column in C++ report very briefly, but I talked about substitutability and we often talk about substitutability with respect to the LISC-OFF substitution principle. And I basically pointed out that actually that's a very narrow view of what substitutability implies. And we can look at it from the point of view of conversions. You can substitute, in some cases, you can mix one numeric type with another or you can provide your own user-defined type and have it mix easily with existing types and then you can support using conversions, similarly, using overloading so that it can participate in the same kinds of expressions as other types and it is therefore substitutable, particularly in the context of, say, templates. And then there's the standard interpretation of LISC-OFF, which is inheritance, but the other one is to substitute something with respect to change or absence of change. And this is the bit where it gets interesting, is this idea of referential transparency is again going to support what we're doing. So the referential transparency idea, Edward Garson sort of pointed this one out in 97 Things Every Programme Should Know, very desirable property implies functions consistently yield the same results given the same input, irrespective of where and when they are invoked. That is, function evaluation depends less, ideally not at all, on the side effects of mutable state. If you go back to the Facebook quote at the beginning of the talk, you will notice that what they did is they basically say, okay, they wanted to have referential transparency. If something was slow, they would cache values in order to achieve that effect. And always the idea is on the outside, you're going to create abstractions that are consistent and their state is durable and it looks like they're recalculating it every time, but this is an optimization. You give yourself the opportunity to optimize. A very simple way of looking at this in item potence is Bertrand Meyer pointed out, asking a question should not change the answer and nor should asking it twice. There is this idea that my functions should represent pure computation and those ones should be very clear and separate from the ones that have side effects. In any large system, you're going to need these space of side effects. But the way I would try to appeal to you to think about it is instead of thinking here is a big mass of code and there's bits of it that have no side effects and I've got const over there and my friend, we had a chat down the pub and we've decided const over there and there's a few other things and we got rid of the word get in this place instead of this kind of patchwork architecture. What I'm suggesting here is that you carefully zone out the code base. You figure out which are the parts of the code base where I need the moving parts and which are the parts where I don't and actually be very strict in enforcing these and say the style in this part of code is very strictly to be pure functional or close to pure functional to give the illusion of that and we will endeavor to keep that style in this space. In other spaces, we may not follow that style particularly we're dealing with existing APIs and existing code but to have a very clear separation rather than kind of a muddled hodgepodge. Be very, very clear where are the more functional pieces of the code because that allows you to reason about it. That's one of the reasons they say, they were saying it's nice and maintainable because it's a lot easier to just reason about stuff. You don't have to keep ahead full of side effects. Now as an aside, one of the other things I'm going to say is when you adopt a stricter more function and functional style with more immutable state and clearer functions and objects that represent values and more value like, you also end up with a lot easier or a lot less mocking. Some people absolutely love mocking. They get up in the morning and they kind of like, okay, where's my nearest mock object? I need my mocks. It's just like really programming is not about mocking. Mobs have a role but they are not the role that a lot of people put them to, which is everything. So you might say, well, this is all very well for things like date and very fine-grained representational types. But what about containers? It's all very well to say, you know, what is inside the book is what matters. What is inside the containers, what matters. But what about the actual container itself? How am I going to make these guys immutable? Okay, well, let's imagine a little thought experiment. Create the FTL, Functional Template Library. What am I going to go for? Well, all the value types are going to be const. The iterators, they're going to be const because there is no point in having a const iterator because you cannot non-constit. I'm going to have a whole bunch of queries. I'm going to support assignment, but I'm going to treat that purely as the only state modification. I'm going to treat that as a rebinding of state rather than actually modifying an existing object. It's a pure rebinding. Now, if I'm fixing things at construction time, there's a couple of little things that I can get out of this. Oh, yes, in my simplification, I have avoided the nightmare that is allocators. For those of you who've not really had any experience with allocators, keep it that way. Okay, they're kind of like an experiment gone horribly, horribly wrong. It's a kind of Jurassic Park of code. And there have been some velociraptor refinements in recent standards, but really it's just making the best of a bad job. Life is much simpler without them. Besides which, if I want to have a collection of immutable stuff, one of the things I'm going to need is to really take control of memory from the container's point of view, not some memory allocators that doesn't know what I'm doing. And so we can immediately have this little advantage. I'm going to go for a set here. My sets are ordered, and I'm going to say, I'm going to take advantage of some syntax here. I'm going to initialize this set to these values. And there's duplicate 9's and duplicate 2, so it'll come out. So the sequencing will come out 245789, and we have a size of 6. I can query it. I can, from beginning to end, using an iterator, I can find values in it. Count occurrences preferably use lower bound and equal range to find things. And I have a very simple representation. I have simply an array of the values. And that is shareable. When I copy that set to somebody else, they get exactly the same set. We're actually sharing it under the hood. So I can pass this around. Once initialized, it's fixed. And this is great. This is nice and easy. And likewise, I can create an array, kind of a version of the array that we find in C++11. And again, similar kind of concepts. I can subscript it now. I can ask it front and back. I can even get its data, as long as I respect the const promise. But this is C++, so you can do what the hell you want. And again, I've got an underlying contiguous block. Now, the nice thing about this, again, the same notation, but the nice thing about this is that it seems to see, you'll see that suddenly our default for a lot of immutable stuff is actually arrays. Now, I remember reading a lot of books a number of years ago saying, you shouldn't use arrays for everything and this, that, and the other. They're a terrible data structure. Well, since then, we've discovered that stuff like cache locality actually matters. And arrays are brilliant. And also, a lot of people think that a certain array sucks, so therefore, arrays not as evil as people made them out to be. However, there is one constraint on this being practical, which is the fact that I am constrained to always have the same values. And you're thinking, well, hang on, I want to change things. How am I going to do this stuff? Turns out we have an answer. And I'm only going to show you a very small piece of this answer. Persistent data structures. Persistent data structure is a data structure that always preserves the various versions of itself when it is modified. Such data structures are effectively immutable, as their operations do not visibly update the structure in place, but instead always yield a new updated structure. And the idea there is your structure in one sense can be considered kind of versioned. You point to the bits and somebody else has a view of it. And don't get it confused with persistent storage. Now, we can have a very modest example of this if I do a kind of a vector version. So here's a kind of vector in FTL style. And one thing to note, let's zoom in on the pop front and pop back. This kind of justifies Steppanov's decision to originally make them void returning. Here, what we're doing is we are not actually popping the front, popping the back. What we're doing is we are returning the vector that would have resulted from popping the front and popping the back, which makes me think that the naming convention is a bit off, so I'm going to go for that. So you're asking it a question. The question for the vector is what would you look like if I took you at the front of you off or the back of you? Return me that. Now, if we go back to this, you can see the way this is going to be implemented. Very simply, as we're sharing this array, this true underlying array in memory, this vector facade is basically sitting there going, all right, okay, I've got a couple of iterators, pointers basically. I've got a couple of pointers to that. If you would like to pop one end or other, I will return me, but actually I'm going to move one of these back. The original element is exactly where it is. The original user of that is exactly where it is. So I've kept this kind of thematically related by calling it vector. Pushing is a no-no. That's not going to happen. Not for this kind of structure, but it's a very simple idea there. You've got a data structure from which you can consume elements, but nobody else can. One of the classic ones for this, where you can start adding stuff, and now we're going to have to move away from friendly cache locality, is to walk back through time. The original Lisp actually got this one right and actually had a very deep immutable model built into it. To the point that a few years ago, I actually wrote an article which was basically based on a pure obsession with Lisp. I still have a deep fondness for the Lisp. It's simple, elegant, and something with which all developers should have an infatuation at least once in their programming life. I was inspired to try and STL-ize or rather Lisp-ize an STL list. My conclusion was I called it Lisp. It's the best I can manage at the time. I still think it's quite funny. You don't have to share in that humor, but that's your fault, not mine. It looks a bit like this. Same kind of thinking, but all the operations are on the front. We've got underlying links, your classic linked list, but here we no longer modify elements within the list. You can now keep pushing and popping. This gives you the perfect stack for those that really want to recreate the classic computer science examples. The idea is that as time goes by, what you will end up with is effectively a tree if you were to look in memory. This person thinks they've got a list with these elements, and another person thinks they've got a list with these elements. It happens to share the representation at the back end and so on. You end up with sharing the underlying state. One of the nice things that I can do here that I find I cannot do with the same kind of confidence in certain other languages is actually pay attention to the constness, because I can say we are sharing these elements, and I'm just going to turn the dials up and say in this library, when we say const we mean const. Whereas I can't say that for a lot of other languages. I just have to say play nicely and don't modify things. Here I can actually get a bit of compiler support. We could say, we're sharing those. Those are not going to change. If they change, then it's somebody doing something inappropriate, just as if they were mem copying instead of copy constructing. But I've got that kind of basic structure. Now that's as far into the persistent data structures as I'm going to go. There are whole models for hash tables and B-trees and all kinds of stuff. It's great. But if you are, if you do program in C++, rather than just being a tourist here, you ended up in completely the wrong room, but we're far too polite to leave, there should be something that's annoying you and nagging you ever so slightly. I haven't talked about memory management at all. At all at all. It's great having all these shared data structures. How are we going to do this? Who's going to clean up, especially with this sharing? So it turns out we can go back in time. It turns out that the tragedy of Hamlet, Prince of Denmark, was actually about memory management as a play. Who knew? It's taken centuries to discover this. Shakespeare was indeed a programmer. And we see that there are two different perspectives. So here Hamlet says, Yay, from the table of my memory, I'll wipe away all trivial font records. What he's talking about here is garbage collection. Okay? It's just like... And Bjarne said, okay, so this is C++11. Garbage collection is optional. That is a garbage collector is not a compulsory part of an implementation. Hmm. So that's going to make it really difficult to kind of rely on as a library feature. Here, I've built this whole library on garbage collection. Okay. And could you tell me what garbage collection? There are three levels at which you can be running garbage collection. The one you want, the only one that will work, is this one. Anything else does not work. So now you either have an assertion failure and not a lot of program. You say, well, yeah, it works perfectly if you have a garbage collector. Yeah, but the runtime we're using doesn't have a garbage collector. It's like, ah, screwed then. Okay, okay. So clearly Hamlet is not going to offer us the answer, but a failure might, it is in my memory locked and you yourself shall keep the key of it. Yep, we're back to reference counting. It's okay. The library does a bit for us, but it's worth going back in time to Robert Murray's quite brilliant book. It's an often overlooked, but it kind of stands head and shoulders above a lot of the other stuff that was coming out in the early 90s, C++ strategies and tactics. And he made the observation back then. Just very, very simple. Everybody got really into reference counting. A used counting class is more complicated than a non-used counted equivalent. And all of this horsing around with used counts takes a significant amount of processing time. This is the thing that a lot of people overlook when they think, oh, garbage collection can't be that efficient. How efficient is it to be using the minute you have a multi-straded piece of C++ code and you use shared pointer in it, that means that every single implementation, every single instantiation, the shared pointer class will now use interlocked increments and decrements, even when you don't need them. Even if you've actually got everything within one thread, simply because you've said it's going to be multi-threaded, everybody's going to pay that little extra tax. And it's non-trivial. But it gets more fun. Okay, so first thing is it's quite easy for vector. I can go ahead. I can do a shared pointer of value type. I can use that for arrays as well as individual values. That's fine. The only problem is I can't take advantage of using make shared, which basically creates the object with a reference count, because it doesn't allow you to do that. You can't say, I want to make an array version of this, please. Which is a shame. It means, okay, so I create an extra object. So I've now got two allocations instead of one that I have before. And that works fine. We pay a little bit of tax here and there. And if we're sharing between threads, then that's brilliant because we also get peace of mind for that little bit of taxation. That's fine. Everything works. Everything's truly immutable. And it's all good. However, there is the note of caution. Nothing in life is perfect. We have a bit of an issue here. I've just gone and replaced that raw pointer with a shared pointer that does reference counting. If you remember, a nice big list in memory looking like a tree. And there are some things that are referenced by two and there are some things that are referenced by one and so on. And when a particular link goes out of scope or something, reference count drops by one. That's great. What happens if they all drop by one? Imagine I create a list. I fill it up with some number, how many? Fill up with some value. I don't really care. I'm going to insert at the front because I can pop front, push front rather. I'm going to insert something there. Nobody else, I'm not going to share this with anybody. I'm not going to pass it to anybody. I'm not going to do anything else with it. This is just one object and the chain object holds the head link. That holds the next link, the next link, the next link. Everybody's reference count is one. And then I hit the closing curly. On destruction, the first destructor will be called because, well, the first destructor is going to say, hey, guess what? Your reference count has just dropped to zero. I'm going to delete you and there's this beautiful recursive cascade. You end up having a recursive destructor call. It depends on your machine, but you're not looking at being able to hold a list of more than about a thousand or two thousand before you blow the stack. Oops. In other words, yay for garbage collection. Now, if you're sitting there going, oh, yeah, yeah, but I'm a Proposy++ program. I know how to work around this. Then I've just highlighted, and that just shows us we have a problem. I never question anybody's ability to work around something. I'm interested in working with, and actually this one is going to take a little bit of extra work, which is a shame. So we can't use it straight out the box, which is a shame. Now, a lot of what I've said has been in the context of assuming something about concurrency. So let's talk about concurrency. Now, funny thing, I did this a few years ago, about two or three workshops where I asked people just for fun. I'd say, I'm going to do a word association game. I'm going to give you a word, and I want the first word that you think of. And these days, the results might be different. So I'm going to treasure the past. And times I ran it worked absolutely perfectly. I'd say concurrency, and people would say threads. And then I'd say threads, and they'd say locks or synchronization. It's kind of interesting. And this is even when people are kind of a little more aware. It's so deeply rooted in there. Concurrency means threading. Threading means I'm going to lock stuff. And I ask people, why are you locking stuff so it can be safe? OK. So you're locking it so it can be safe. Yeah, why are you using concurrency so it can be fast? OK. You do know that a lock is the antithread. Brilliant quote, all computers wait at the same speed. Always keep that in mind when you've got all those calls busy. Oh, yes, this many gigahertz. Yeah, we're all waiting. And this is the point. We've got a computational model that doesn't really make sense. Now, I've said to various people, you need to program thinking without locks. And one person, I'm glad he said this because I have the feeling that somebody else may not have heard him. But when I said that in one workshop, one person said, what, you mean we should take the locks out of our code? No, no, no, no, no, no, no, no. You need to compose it from scratch without thinking about locks. Yeah, but then we'll get problems, which as witnessed by this rather brilliant quote, which I can't read out. Because of that. And I said, no, no, no, the problem is you have composed your code from the perspective that you are changing state. And then, as Bartosz Malewski noted, shared memory is like a canvas where threads collaborate in painting images. Except they stand on opposite sides of the canvas and use guns rather than brushes. And the only way they can avoid killing each other is if they shout, duck, before opening fire. Yeah, so, I mean, this is other observation. David Butenhoff, responsible for kind of the classic POSIX threads book, also mentioned about locks. He said, you know, we made a big mistake calling them mutexes and locks and stuff like that. He said, we should have called them bottlenecks. Because then people, you know, because when people say, I'm going to put bottleneck right here in the code. It's just like, you know, words matter, words really matter. But there is this issue. There's two things, is that we have these associations. But we have these associations for a reason, because our approach has been predicated on an assumption that comes from single-threaded, single-memory procedural programming. And it's permeated every programming language since. And, you know, every mainstream programming language. And I noticed this. There was a real shift, 1990s to about 2000, the early 2000s. In 1990s, all the books on concurrency, and this is right across the board, C through to Java, whatever people were writing, it was all about state change. In fact, you can actually see that going back to the work in the 60s and 70s on this. It was all about how do we synchronize state change. It was never how do we eliminate state change or what way of thinking or organizing our code would allow that. And then there was a kind of a shift where a lot of the old styles and conventions started going away as people started realizing, you know what, there's a way of thinking about this. So this is a diagram I drew up, first time about three years ago, and I found it immensely useful. So it's been committed to PowerPoint. Two axes, it's a quadrant diagram, and you know there's going to be a bad quadrant, because there always is. But we've divided the universe into four. We've got two axes, mutability and sharing. And the one that we really care about or care about avoiding, clearly it's not obvious here, so I'm going to make it really obvious. Let's use red. In fact, that's just really, that's the synchronization quadrant. This is where you want to steer clear of. But most people write their code in this space. This is where we have objects that change state and are shared between threads. If we have objects that are not shared, in other words two paths of execution do not follow, go through the same piece of code, then it turns out you can mutate what you want, and it doesn't matter. The privacy of a function, for example, feel free to mutate the state, because nobody's ever going to care. An object that is only accessed asynchronously and only has one piece of work fed to it at a time, same deal. On the other hand, we can go all the way over here and say, well, what about making our objects immutable? If they don't change, then I can share them as much as I want. It doesn't make any difference. But it's when I bring the two together that we get the pain. That's where we get the pain. And yet, by default, this is where people program. When you look at the quadrant diagram, it's kind of like, well, actually, why don't we spend more time out here? Now, there's a number of different approaches that we can take. So Russell Winder observed clearly message passing leads to better scalability in parallel systems. Instead of using threads and shared memory as our programming model, we can use processes and message passing. Process here just means a protected independent state with executing code, not necessarily an operating system process. And we see this embodied in a number of languages, Erlang and Occam before it. And I did a bunch of Occam many years ago, and I found that really very helpful in terms of how to think about things. Very successful mechanism, very easy to scale things, very easy to compose things. Now, Occam in particular is based on CSP model from Tony Hoare. And you can take a really simple example. Let's go back to our friend FizzBuzz. So we've got FizzBuzz. We're going to maintain a separation of concerns. We're going to create a FizzBuzzer, which is going to interact and it's going to field requests and give responses. The fundamental construct here is the channel, or the queue, but the language of CSP and indeed the language of go. If you look into go as a language, then it's channel. The idea is I'm simply going to set up two channels. This is a function. The function is the unit of abstraction here. And then I simply receive what I'm receiving. Then I can calculate and send back. We have a really, really simple stream model. Of course, there is synchronization going on, but it's nothing to do with the FizzBuzzer, FizzBuzz, or indeed the client itself, who simply wires things up by saying, right, I've got two channels. I've got a function, FizzBuzzer. I'm going to bind that without and back and I'm going to set this off buzzing. And then I'm going to loop through and send through requests for one through a hundred, pick up the result and print it out. And that's it. And as you can see, of course, there is synchronization going on here, but the synchronization is incredibly discrete. It's out of the way. There's no longer the programmers responsibility to mess it up. And this very, very simple model rather than saying, hey, everybody's sharing all of the objects all of the time. So this does indeed relate to, relate back to something a number of years ago, I studied this actor-based language, ABCL, and the actor model computation is not identical, but is certainly related to this kind of thinking. But I'm not going to get enough time to go into that in any detail. But I would like to sort of say, well, we have a question sometimes that if I want to pick up the results of something, how do I pick up the results of a computation? What if I'm not just streaming evaluations? In other words, what if I've actually, rather than asking, give me this, I'm going to send you a request, I want, and send me results when you have them, rather than treating that as two separate processes running, what if I'm actually trying to use something asynchronous? How do I pick up the result? This is where futures fit in. Futures are virtual proxies. They've been around in different programming languages and programming libraries for a while. But this idea, a virtual data object, give it to the client, they only provide a value when the computation is complete. The client can choose to block on it until a value is ready, or they can choose to poll whether or not it's ready or not, whether it is the value there. Now, what's nice about this approach, and actually see how we can render this in C++11, what I'm going to do here is we've taken a different view rather than a long-running thread. We say our function, whatever it is, we launch it asynchronously, this is almost a go routine style in that sense, we launch it asynchronously, we pick up its result, and what happens here is we wrap this. The idea here is that nobody sits around doing explicit locking, and what we're after is picking up, we're after this idea of separating out. That function can go and have as many side effects as it wants, as long as there's nothing to do with the code that I'm working in. The thread management, we don't do any thread management, it is just launched as an asynchronous function, quite literally. We pick up the result when we want to, we can block here on this io.get. I'm going to say this is the standard, does a lot of good stuff, but I'm going to go back to a proposal that I made a number of years ago, which I much preferred syntactically, where what we actually had was thread was a verb, not an object. You thread a function and it yields something that is a future, but called a joiner because that's what you do with it, and that itself is a function, so you can then pass it on to somebody else. So my mild obsession with functional programming ideas was visible in this, because I wanted everything to be a function. And the idea is what I get back is a function that then I can then call that will give me the result. So I give you, so this is a proper higher order programming. Harry, that's not the way that the future is gone. This is what we've got, and that gets us fairly close to that idea of asynchronous execution. Why does asynchronous execution matter? Well, it allows us ultimately to share what we're doing, but without interfering. It allows us to say, I want you to execute something independently of what I'm working on. I don't want to care about your execution policy. As long as you keep your state to yourself, then, and you give me an easy way to get the results back, that's what I want. Far too often, people have launched threads across data structures without thinking about it. They've gone and said, right, we've got a thread, we've got a shared data structure, we're going to put locks on it, and the whole code base is jammed up, both from a development perspective and a runtime perspective around this idea. Rather than thinking, how can I keep things apart? People have ended up pushing them together too soon. We need a composable model. And on that note, I will finish, and I'll take questions afterwards. Thank you very much. I'm not really working thin. Scratch my shoulder. It's like I'm working from... When this is over, Nothing you will be so right. I'll be one. If you love me, you will be tonight. But what's the problem? You can hide all those issues. Suddenly this guy you vote on it all with a knife right there. I can do all sorts. At the end of yourнак The whole section is free. You say that working is what I'm not supposed to do And I say ain't it right if I can't guess we love you I'm tired of thinking of what my wish was supposed to be Well, soon enough darling, this love would be reality How could you leave a girl, cause love for us wasn't meant to be Well, then you must be seeing some other guy instead of me I think that's why you got me working day and night, yeah, and I'll be working Friends are not to me tonight I'm working It's what a man's supposed to do And I say you ain't right If I can just be loved to you I can't believe girl
 Right, okay, I've just saved you from some very, very mellow music.  Okay, so, this is what I'm going to talk about.  Well, I'm going to talk a bit about this because as I was putting together the slides on the flight this afternoon,  I realized I had far too much material for this talk, and I thought, okay, I'm going to have to subset it.  So, I will, in some cases, I will talk, I will, because this is C++, I will use pointers to refer to other things.  I will not include the whole thing. I will use that level of indirection that I feel is my privilege.  So, this is, I guess this is as opposed to dysfunctional C++, which is a talk on C++ style, and I'm not doing that one today.  Although this clearly has an impact on the style.  Let me think. Anything else? Who's seen me give a talk before, just so I know how many jokes I can reuse?  Okay, reuse is a good thing, just so we're all clear on that one.  Right, Kevin and Henny, I've got my name on a couple of books there, and probably better name for 97 Things Every Program I Should Know,  but I'm not going to be talking about these things.  But I will start off with a quote from one of the contributors to 97 Things.  That man there, Michael Feathers. A few years back, he made this very good observation.  Object orientation makes code understandable by encapsulating moving parts.  Functional programming makes code understandable by minimizing moving parts.  It's a very, slightly different philosophy.  Now, already, if you're astute, you will see that these two are not necessarily in contradiction,  but there is a very large overlapping space, and it turns out that C++ can inhabit this space as well as or as badly as it does other spaces.  And I want to explore that.  Now, in preparing this talk, a perfect piece of timing.  Yesterday, somebody tweeted this, a blog from Facebook about how they'd built,  and it's gone about building Facebook moments, and the timing was perfect,  because to keep our C++ API boundary simple, we adopted one-way data flow.  I would like to talk about that at length, but that may be one of the things I'm going to shorten.  The API consists of methods to perform fire and forget mutations,  and methods to compute view models required by specific views.  Now, some of that's going to go a little bit outside into the architectural space that surrounds this, but it all follows.  To keep the code understandable, we write functional style code converting raw data objects into immutable view models by default.  As we identify performance bottlenecks through profiling, we added caches to avoid recomputing unchanged intermediate results.  What I find interesting about this is that they have specifically pursued an architectural style and said,  this is the style we would like to build this in.  This is the style we would like to code in, and if there are problems,  instead of hacking the poor thing to pieces, as it happens in so many code bases,  what we will do is we will preserve the model and support it, find out where it needs to support.  In other words, build it so that it is easy to work with this stuff.  In other words, that very clear idea, rather than a morpher's mass of code,  you have an infrastructure that doesn't merely push bits around,  but it actually supports specific styles and qualities of the code.  The resulting functional code is easy to maintain without sacrificing performance.  Those two phrases in one sentence, that's always good to hear.  So what do we mean by functional programming?  Well, this is a tag cloud that I kind of been using for the last couple of years.  It's a lot.  I mean, this is the thing.  Functional programming covers a lot of things.  I'm not going to cover all of these things.  Some of them simply cannot be expressed in C++.  Some of them have a natural limit.  So for example, with recursion, actually we will cover recursion briefly a bit later,  but there's no tail recursion, tail call optimization in C++,  and that actually means that there's a certain things you cannot express conveniently.  Pattern matching is not reg X's, and it's a little bit outside the space.  One could say the whole of the language is a big monad and have a beer over that.  I strongly suggest if you wish to understand monads, lots of alcohol.  Lots of alcohol.  I think I achieved an understanding of monads once when I had lots of alcohol,  and I've been unable to recover that understanding since.  It is lying on the floor of a hotel room somewhere.  However, we will talk about this kind of more declarative approach,  higher order functions, pure functions, immutability, landers, and so on.  I'm going to start with a very simple example, a very humble example,  because some folks from Down Under have been tweeting,  that I know are in Oslo at the moment, have been tweeting,  and sort of like what kind of weather is this?  It's supposed to be summer here in the Northern Hemisphere.  It's just like, well, I can say having just come from Southern England,  yeah, it's warmer in Southern England by about three degrees.  So yeah, that's totally sunburn weather.  So we have two seasons basically in much of Northern Europe,  grey and construction season.  And because of that, when people talk about air conditioning,  they're normally talking about offices.  So I use the heating system example rather than anything else.  The heating system, you want to turn it on, you want to turn it off.  Nice and simple.  We want to do it on a timer,  so I'm going to create a convenient timer abstraction.  I can pass in the time of day, I'm going to go ahead  and I'm going to say, well, obviously I've read about this kind of thing.  I need to perform an action, and I need to apply an action to an object  independently and asynchronously from the very decision to do that.  How do I decouple the decision that I want to do that from actually doing it?  Well, I'm going to use the command pattern.  So I'm going to go straight for it, and I'm going to have one of these.  Oh, it's all classic Gang of Four stuff.  And then we go ahead and we start implementing it.  And it's just like, okay, this is the code for turning on.  And that's without adding any ritualistic enterprise banners or other noise.  And then there's the turn, oh, actually wait a minute,  it's just minor, minor fix.  This is the great thing about the PowerPoint Monad.  Let's just fix that.  Yeah, there we go.  That's what I needed.  I think this qualifies as live coding.  There we go.  And there we go.  So that's what I'm fixing.  It might look like I've just done copy and paste.  I couldn't possibly comment.  Because unfortunately, that is the feature that you're going to end up with.  With this style, it's a very copy and paste approach.  So to bring that into perspective, you're going to end up with lots of stuff like this.  Copy, paste, copy, paste.  And this is just a very simple thing.  If you look at it, it's mostly programming language noise.  We're doing a lot of work to support style.  Some people say, wow, this is problem with objects.  It's not.  It's problem with doing objects in a sucky way.  However, a lot of people in C++ won't look at it like that.  They will say, oh, you know what?  Within C++, there is another language trying to get out.  And it's called C.  So this is far too much code.  I'm going to just go and use function pointers.  I'm going to pass in a function pointer for an action to execute.  Then I'm going to pass in the context data with it.  And then I'm going to get one to execute on the other.  So it's just like, yep, so this is it.  Void pointers.  So void pointer is a way of selling the compiler.  Thanks.  Thanks for all your help.  But I'll take you from here.  Trust me on this one.  Don't need to tell me about types.  It's trust the programmer time.  And so we go ahead and we've got that.  And this is nice because everything come down to sort of one-liners.  The only problem is that there is a tacit agreement between,  there's a contract here that is difficult to enforce  within a language that has typing.  In a language that is dynamically typed,  this is curiously enough not a problem in the same way.  Because it turns out that if I try and do the wrong thing  with an object in a language that is dynamically typed,  the language tells me in a useful way that I can do something about.  As opposed to wandering off and doing mysterious things to bytes  that I really shouldn't be entitled to do.  If I do not pass in a thing that can be cast to a heating system,  all bets are off.  And it gets very exciting.  So this is not the kind of stuff.  The brevity we like, but the kind of the syntax noise,  and sometimes people go, oh, that's OK.  You can just use a C-style cast.  No, no, no, no, no.  Casts should be ugly and big and explicit.  One, you can grep for them.  And two, it's a big warning sign saying, look here.  And I've actually had one person say,  I don't like using those casts because all of my code,  you get two levels of casting.  Reinterpreted cast and casting.  I said, that's your code trying to tell you that it sucks.  Listen to your code.  OK.  So, OK, what we're going to do is we're going to say, ah, right.  We're going to encapsulate a function concept of some kind  and make it a complete one.  In other words, I'm going to say, I need a thing  that looks like a function.  So I'm going to go over a little bit to the sort of looser side of things.  I merely need to be able to call it as something  that doesn't take any arguments and returns.  Nothing.  I'm going to say, right, OK, that's fine.  I don't actually care that it's a function.  It merely supports a function protocol.  That's it.  It can be a function object.  And we can do a whole load of really neat things with that  once we've got that.  The only thing that we discover is we don't actually need to define a function  as we did with the C-style.  We certainly don't need to define a class as we did with kind of  misapplication of the gang of four.  So I can now create two objects on and off.  This is when I want the time on.  This is when I want it off.  And I'm going to bind the very action itself turning on,  which I already have in the heating system.  In other words, we already have the functionality.  We don't need to wrap it.  I'm going to bind it immediately.  At the object level.  So I can do this.  So bind is basically a higher order function that takes a function  or something function like and yields a thing that can be executed as a function.  So this is all good.  That is now in the C++ standard.  And I might have ported that one from boost code if I think about that one.  So let me just be strictly politically correct here.  There we go.  I'll keep the police off my back.  And but then obviously people are like, yeah, I can't get what you're doing.  But then we've got lambdas.  So it's even easier at that point.  We just pass in a piece of code that is a function object,  but that's the language doing it for us.  Pass it in and we're done.  So in other words, we haven't had to create any intermediate type level abstractions.  We haven't had to create or declare other function abstractions.  We haven't had to compose on the fly.  And it's this compositionality that is the key to any style that we want.  So we could say, well, you know, this is really very, you know, this is C++ 11  and this is all very 21st century except we need to remind ourselves  that Lambda calculus is actually older.  William Cook identified it as 1941 in rather good presentation and paper  on understanding data abstraction revisited.  But I did a bit more digging around and it turns out it's 1932.  So C++ 11 now allows you to program like it was 80 years ago.  Yay.  On the other hand, there are some glorious pieces in that syntax,  some of the syntax decisions.  So if you've not really messed about with lambdas,  I'd just like to point out that that is valid C++.  And in fact, so is this because this executes that valid C++.  This is something that takes no arguments, returns nothing, captures nothing,  and does nothing perfectly.  It's a very cohesive concept.  This one executes it and therefore does nothing.  Huh?  With any luck, yes, yes.  But it now gives your cat new and exciting opportunities for running across your keyboard  and actually yielding a valid code base.  All of which, you know, what is a program?  Nicholas Verth answered this one for us many years ago.  Algorithms for Stata Structure Equals Programs.  Now, the thing here is that normally for a lot of people,  that means historically, I'm going to take my algorithm and data structures  and then mash them all together, and that's my program.  Now, actually, the idea here is we would like to separate these things out.  This kind of composition style thinking.  Now, what we've actually seen already with just being able to treat functions  as first class objects, that is you can argue, and both people and both sides do,  which is why it's generally better to get yourself a seat to the side  and watch both sides going at each other,  because I think that the previous solution was a very good sort of functionally inspired solution  or it was a very good object oriented solution.  Both apply.  But here's a different perspective.  Let's take this a bit further.  This kind of inspiring thought has been algorithms are a way of doing something.  Data structures are merely what we do them with.  The most obvious space in which this is separated in C++ is the STL.  This was Alex Stepanov's original goal, basically, to be able to say,  I wish to separate out the abstractions of representation from the choice of algorithm that I've got,  and I wish to keep these separate, but in a way that is composable and allows me the efficiency.  So, in honour of the fact that a couple of years back with Anders Noras at this conference, in fact,  we did a whole bunch of stuff on functional programming messing about with languages.  I thought I'd use one of the examples that I introduced in that one.  It depends how good your memory is, but the world was going to end in 2011, twice, actually.  The date advertised, and then when Harold Camping discovered that the date had not actually transpired  as the end of the world, he said, no, no, no, I meant six months time in October or so,  and that didn't happen either.  But then we had the end of 2012 because apparently the Mayan calendar was going to run out.  Nobody ever worries about the fact that the regular calendar runs out in December and then cycles back.  It uses modular arithmetic.  It turns out the Mayans were onto this one as well.  So it didn't end in 2012, and it didn't end at the beginning of last year,  which is supposed to be Ragnarok last February.  That didn't work out either.  However, this one was memorable because I was actually in New York.  It was Friday the 13th.  This is the site of the former World Trade Center,  and if you're going to advertise the end of the world, this is a great way to do it.  Stand there with a billboard on Friday the 13th, right next to this iconic and sad location,  and there you have it.  So let's find out.  Friday the 13th, what do we know about it?  Paris-Gavie-Decaturia phobia is the fear of Friday the 13th,  so if you learn nothing else today, that's useful.  And we need, for a certain class of the population, we need to find out when is this going to be.  So we go away and we hack some C, and we use struct Tm.  We do all kinds of stuff, and it's kind of all there.  The only highlight is perhaps that we have daily sex.  But, you know, you're kind of running around this loop looking for this stuff and looking for the next answer.  Now, this works, but it's a bit messy.  You've got the usual kind of hieroglyphic noise.  There is something that we can do with this from a C++ perspective,  and it's actually sort of a separation.  Back to our friends at the Landers.  I'd love to tidy up struct Tm, but I thought I'd leave that one outside the scope of this problem.  Find if, from here, so I want to start from today, or actually tomorrow,  then I'm going to have a token that is infinity.  This is the best way to represent infinity, something that you can never reach.  This is how we do this.  The easiest way to deal with infinite lists, and this is something functional programmers do all the time,  is you make sure you don't have all of the list at once.  Infinity is incredibly easy to deal with if you start at the beginning.  If you try and hold it all at once, you're screwed.  But if you say, from now until beyond the end of time, then we're okay,  because it turns out we will find Friday the 13th before that.  You're guaranteed, if you go through it, you're guaranteed there's a couple every 500 days.  So what we've done is apply a filter to this one.  This is just a placeholder, and we've introduced a day iterator.  This idea of using iterators, we tend to think of as a very classic object-oriented solution,  but in another sense, it's actually a really good way of looking at lazy evaluation.  I wish to consume the content of a container, physical or abstract,  but I don't wish to do it all at once.  I wish to do it one element at a time.  I want to work from the head through to the tail, and then I will take the head of that tail and so on,  and I will do this, and on demand, values will appear as I need them.  This is the basic idea behind an iterator, although people don't tend to think of it like that.  But that allows you an ordered simple access.  Now, in the next C++ standard, C++ 17, they're coming thick and fast,  C++ 11, C++ 14, then there's 17.  The next C++ standard will introduce a range concept that will allow us to tidy a little bit of this up  and actually use a much more pipeline-style notation to compose these things.  Unfortunately, this is one of the reasons that, although I remember being very excited by STL iterators,  because I used to think that operator overloading was really cool, and actually I still kind of do,  the problem is that not everybody thinks like that, and so you have to go away and write stuff like this to wrap it up.  So there's a bit of boilerplate, unfortunately, but this is a supporting abstraction.  If you're only going to do it once in a piece of code, then you might be better off doing that,  but the minute you do it twice, I think you're better off doing that.  In other words, I am going to give you the tools from which to compose these elements,  and then you can go and search for the, turns out Friday the 13th is geographically dependent.  Some people don't like Tuesdays.  For other people, 17th is bad, so you want to generalize this at that level.  So suddenly I've got a way of doing this.  Now, given this is a language of the obscure corners, and I want to talk about this idea of immutability  and not having side effects, there's a kind of interesting piece of the language.  A couple of you have seen this before.  This is an interesting historical note.  Irvin Unruh, Siemens, we used to work for Siemens, the compiler division, like all great works of art.  This is untitled.  He discovered, let me put it this way, this piece of code doesn't compile.  It's a whole load of template stuff, and it doesn't compile.  And you might be thinking that's not exceptional.  People often create templated code that doesn't compile. Big deal.  Yeah, but when this one fails to compile, it prints out the first few prime numbers as part of its compilation message.  Now, that I don't get normally from this kind of code.  And what Irvin had discovered was that C++ templates are chewing complete.  It's one of those little accidents that wasn't the original plan.  It turns out anything that you can compute can be computed with them.  And this gave rise to template metaprogramming, which has turned out to be anything but temporary.  It is a way that many C++ programmers will secure their job by writing code that people just will look at and go,  I have no idea what that is.  I really don't understand what it does at compile time.  And then it's become so commoditized and sophisticated that people have been creating libraries for years.  In Boost, there is a template metaprogramming library that Adam Peterson used to solve one of the harder problems  that we know in software development, FizzBuzz.  And again, this piece of code does not compile.  And its compilation message is indeed FizzBuzz.  One, two, Fizz, four, Fizz, seven, eight, Fizz, buzz, eleven.  That's a great compilation message.  Now, why am I showing this?  One, it's frivolous, it's fun, and two, it's pure functional programming.  There are no side effects.  At compile time, you do not have state that you can manipulate.  At compile time, you have an execution model that is based on, if you like, a pure value model.  And functions, they're not functions in the, certainly not what I just showed you,  are not functions in the classic sense.  They are kind of meta functions.  And Fizz is masquerading as if they were functions, they're doing computations on types or on compile time values.  Now, it turns out that you can actually do useful stuff with template metaprogramming and have it compile.  But C++11 went a step further and allowed us to do the stuff at compile time and have it compile,  which is kind of useful.  Again, not the most useful piece of code, but I can say that something that has no side effect,  therefore, is a constant at compile time and actually have that expressed directly.  Nothing with side effects is allowed in there.  There are certain constraints on what you can put in a constant X for a function,  which have been loosened a little bit with C++14.  But the idea here is that you are able to use relatively ordinary C++ code rather than kind of weird out template metaprogramming  or resorting to macros to achieve, to be able to use this to express yourself.  And I think this is the key idea, to express yourself and say,  I want that value and I would like it computed because either it needs to be a compile time constant  or I do not wish to have a runtime computation cost associated with it.  And therefore, it would be nice if it were done this way.  And that I don't go off and have to pre-calculate it off to the side.  I want it in the code.  I want the code to express that as clearly as I would any other functional composition that I would use.  So that one actually addresses that problem, which kind of leads us to this idea.  This kind of classic quote from Lucius Carey, an unfortunate figure in the English Civil War,  who left us with a rather useful quote,  when it is not necessary to change, it is necessary not to change.  And we know pretty much that within C++, the main reason that, the main way people express this unchangingness  is through the const keyword.  Now, it goes a bit further than that.  I mean, there's not simply just const correctness.  But const is basically a promise that is, well, it's C++, you can violate it quite easily.  We want something that's a little bit deeper.  We want to go much, much deeper than this.  We really want to say, we don't want things to change.  Now, a lot of people think it is kind of a right that an object should be able to change state,  and that if I have a piece of state, therefore it is changeable.  There is a kind of question here that is pushed at us by functional programming.  Are you entitled to change state?  Does that actually make sense?  Now, there are a couple of other things that kind of go with const.  One of them is reference.  Pass things by reference, make sure they don't change.  But const in this sense is only a read-only promise.  So we need to be very careful with that when we start saying,  actually, I want something to be truly immutable.  C++11, we've also got r-value references, which also support this idea  that maybe I can actually copy things around,  rather than merely pass them around as references that are read-only.  I can actually say, here, have a copy of something,  even if it's a vector that's this big, and I can pass it to you,  and that's a cheap operation.  If you've not looked into r-value references, I strongly recommend it.  They are one of those features in the language that is sure to allow people  that know what they are to keep their jobs against people that don't know what they are.  It's much harder than a lot of other ideas floating around at one level,  but once you understand why they tick, why they work,  then it kind of makes a lot of sense.  But you have to have sort of an optimization head about you.  It's very much for the person providing the abstractions.  Now, I want to take this and contrast this with these two basic approaches.  I'll take a description from a pose of four.  So very commonly, a number of languages, we make these observations.  References to value objects are commonly distributed, stored in fields,  as stored as data members.  Have a state change to a value caused by one object can have unexpected and unwanted side effects  for any other object sharing the same value instance.  This is a kind of a common problem.  The minute you have any kind of aliasing and you combine it with state change,  this becomes an issue.  And C++ has no shortage of aliasing mechanisms.  Copying the value can reduce the synchronization overhead,  so we would care about this in a threaded environment.  This matters, but I'm going to say even without threading,  aliasing can produce enough surprises to keep you on your toes.  But you've also got an object creation overhead.  Copying is not for free.  It turns out that in many cases, copying is the cost that we need to address.  And this ultimately gives rise to the idea of immutable values.  Therefore, define a value object whose instances are immutable.  Now, this technique is used extensively in reference-based languages such as Java and C-Sharp  and basically saying, I don't want to change that object, therefore, we can share it freely.  Because I cannot actually change the state of it, it doesn't matter what you do with it  because the one thing you can't do is something that's going to change my perception of that object.  This is kind of anathema to a lot of C++ developers  who regard the idea of assignment as a fundamental right.  And we can kind of compromise a little bit.  It's also not that idiomatic because it spends a...  There's a lot of assumptions about heap usage here that are not shared in C++.  So there's another technique that we're more likely to use.  I'll skip the blurb.  Copy value.  C++, I get copying as part of the language.  I don't get that in a number of other languages.  If I pass an object back to you, you get a reference to that object.  If you want to copy, you have to ask for it.  It's unfortunate because the syntax, you have to add syntax  and you have to remember to add syntax.  So this is the bit you get for free.  This is the thing the language does for you for free.  So let's go and hack around with kind of one of those examples that people always wheel out.  I certainly do.  A date example, year, month and day.  There is only one true ordering in case you're wondering.  There are three orderings on the planet.  And there is only one correct one.  And there's one that's kind of correct.  And then there's another one that reminds us why there's an Atlantic Ocean.  And I've left out the r-value versions.  The idea is that we're getting the copy operations for free.  This is kind of hard-wired into C++ as a DNA.  And it's not necessarily a bad thing, although people sometimes find themselves fighting against it  because they work in a different style.  They're trying to do a sort of Java style C++, which is not entirely successful.  And they go ahead, and without even thinking, in fact they probably got it in their editor,  they go ahead and they're kind of like, yeah, I'm going to type a getter,  and then there's a setter because all getters have a friend, a setter.  They have a buddy system, it turns out.  And I just want to say, no, no, no, no, no, no, no, no.  This is not a good thing. This is a bad thing.  In fact, we want to question that.  So let's get rid of that assumption.  The idea of individual field sets for something that has a complex invariant like a date  makes no sense whatsoever.  You need to set it all at once or not at all.  So the first thing we do is restrict the channel of change.  So we might provide a set operation that does appropriate validation,  and then we can go ahead and do sets.  Okay.  But actually, we got one of these for free.  We've already got it.  It's called the assignment operator.  It does it. It does the right thing.  It basically means that if you construct a date correctly,  you need to do an extra set of checks, as I would have done with set.  So for example, the validation here, this has to validate the new state.  And if the new state is incorrect, I presume we may throw an exception,  and leave the old state intact.  Or if we're programming without that kind of mindset,  we will just set it and say, well, you're on your own.  It's an invalid object.  But here we're saying, no, no, no, we're going to actually use this,  which will do the validation.  So you localize the validation in one place, the point of creation.  That is what a constructor is there for.  It is there to give you a valid object.  Once you've got a valid object, you can pass it around.  You can take copies of it for free, basically.  So we've got that.  Now, we've got a few other syntax choices we can mess about with.  I'll leave it to you to sort of decide which one you want to go for.  But there's one more refinement I'm going to make to this class.  Honestly, people, what is it with the get?  I'm a native English speaker, and I'm here to tell you that get, something, is imperative.  If you're trying to get functional, don't use imperative naming.  That's the first thing.  And what does get imply?  A lot of you ask a lot of programmers who speak a different language,  and I'm also talking about people who speak English as a first language.  Programmers suddenly forget that they already knew a language.  And I say, what does get imply?  And they say it implies it's a query.  No, it doesn't.  Really, it doesn't.  So let me think.  Today, I got up to get a flight.  A few years ago, let me think, what did I do?  I got married.  I went to the cash machine today to get money.  In every single one of these, there was a big, profound state change.  Now, if you can show me a cash machine that doesn't, you know,  have that little side effect of reducing my bank balance, I want to use it.  But get means I am going to change your state.  So next time somebody defends this as a naming convention,  you say, you cannot have a const getter because, by definition,  a getter is not a const thing.  It is a state-changing thing.  That's what it means in English.  So we're also going to have this nice side effect.  Oh, no.  But it's okay.  It's in the PowerPoint monad, this nice side effect of, oh, sensible names.  It just means year, month, day, month.  If you want to try and affect a functional style, then don't use imperative naming.  Now, this point about values is interesting because values form kind of a staple ingredient of this space  and this functional space.  The idea is that we are trading not so much in objects with identity, but in values.  And as we know, mathematical values are surprisingly unchanging.  So if I take five, there is nothing I can do to it to make it any other number.  If I ask to add one to it, I don't get back five modified, I get back six.  Everybody else using five keeps using the same five.  Now, in C++, we do this by copying things around and saying the state of those bits represents that value  and there are a set of operators we may affiliate with them.  But it also ties in more deeply.  This is a number of years ago, oh, get the templates there.  I had a column in C++ report very briefly,  but I talked about substitutability and we often talk about substitutability with respect to the LISC-OFF substitution principle.  And I basically pointed out that actually that's a very narrow view of what substitutability implies.  And we can look at it from the point of view of conversions.  You can substitute, in some cases, you can mix one numeric type with another  or you can provide your own user-defined type and have it mix easily with existing types  and then you can support using conversions, similarly, using overloading  so that it can participate in the same kinds of expressions as other types  and it is therefore substitutable, particularly in the context of, say, templates.  And then there's the standard interpretation of LISC-OFF, which is inheritance,  but the other one is to substitute something with respect to change or absence of change.  And this is the bit where it gets interesting, is this idea of referential transparency  is again going to support what we're doing.  So the referential transparency idea, Edward Garson sort of pointed this one out  in 97 Things Every Programme Should Know,  very desirable property implies functions consistently yield the same results  given the same input, irrespective of where and when they are invoked.  That is, function evaluation depends less, ideally not at all, on the side effects of mutable state.  If you go back to the Facebook quote at the beginning of the talk,  you will notice that what they did is they basically say,  okay, they wanted to have referential transparency.  If something was slow, they would cache values in order to achieve that effect.  And always the idea is on the outside, you're going to create abstractions  that are consistent and their state is durable  and it looks like they're recalculating it every time, but this is an optimization.  You give yourself the opportunity to optimize.  A very simple way of looking at this in item potence is Bertrand Meyer pointed out,  asking a question should not change the answer and nor should asking it twice.  There is this idea that my functions should represent pure computation  and those ones should be very clear and separate from the ones that have side effects.  In any large system, you're going to need these space of side effects.  But the way I would try to appeal to you to think about it  is instead of thinking here is a big mass of code  and there's bits of it that have no side effects and I've got const over there  and my friend, we had a chat down the pub and we've decided const over there  and there's a few other things and we got rid of the word get in this place  instead of this kind of patchwork architecture.  What I'm suggesting here is that you carefully zone out the code base.  You figure out which are the parts of the code base where I need the moving parts  and which are the parts where I don't and actually be very strict in enforcing these  and say the style in this part of code is very strictly to be pure functional  or close to pure functional to give the illusion of that  and we will endeavor to keep that style in this space.  In other spaces, we may not follow that style particularly we're dealing with existing APIs  and existing code but to have a very clear separation rather than kind of a muddled hodgepodge.  Be very, very clear where are the more functional pieces of the code  because that allows you to reason about it.  That's one of the reasons they say, they were saying it's nice and maintainable  because it's a lot easier to just reason about stuff.  You don't have to keep ahead full of side effects.  Now as an aside, one of the other things I'm going to say is when you adopt a  stricter more function and functional style with more immutable state and clearer functions  and objects that represent values and more value like,  you also end up with a lot easier or a lot less mocking.  Some people absolutely love mocking.  They get up in the morning and they kind of like, okay, where's my nearest mock object?  I need my mocks.  It's just like really programming is not about mocking.  Mobs have a role but they are not the role that a lot of people put them to,  which is everything.  So you might say, well, this is all very well for things like date  and very fine-grained representational types.  But what about containers?  It's all very well to say, you know, what is inside the book is what matters.  What is inside the containers, what matters.  But what about the actual container itself?  How am I going to make these guys immutable?  Okay, well, let's imagine a little thought experiment.  Create the FTL, Functional Template Library.  What am I going to go for?  Well, all the value types are going to be const.  The iterators, they're going to be const  because there is no point in having a const iterator because you cannot non-constit.  I'm going to have a whole bunch of queries.  I'm going to support assignment, but I'm going to treat that purely as the only state modification.  I'm going to treat that as a rebinding of state  rather than actually modifying an existing object.  It's a pure rebinding.  Now, if I'm fixing things at construction time,  there's a couple of little things that I can get out of this.  Oh, yes, in my simplification, I have avoided the nightmare that is allocators.  For those of you who've not really had any experience with allocators, keep it that way.  Okay, they're kind of like an experiment gone horribly, horribly wrong.  It's a kind of Jurassic Park of code.  And there have been some velociraptor refinements in recent standards,  but really it's just making the best of a bad job.  Life is much simpler without them.  Besides which, if I want to have a collection of immutable stuff,  one of the things I'm going to need is to really take control of memory from the container's point of view,  not some memory allocators that doesn't know what I'm doing.  And so we can immediately have this little advantage.  I'm going to go for a set here.  My sets are ordered, and I'm going to say,  I'm going to take advantage of some syntax here.  I'm going to initialize this set to these values.  And there's duplicate 9's and duplicate 2, so it'll come out.  So the sequencing will come out 245789, and we have a size of 6.  I can query it.  I can, from beginning to end, using an iterator, I can find values in it.  Count occurrences preferably use lower bound and equal range to find things.  And I have a very simple representation.  I have simply an array of the values.  And that is shareable.  When I copy that set to somebody else, they get exactly the same set.  We're actually sharing it under the hood.  So I can pass this around.  Once initialized, it's fixed.  And this is great. This is nice and easy.  And likewise, I can create an array,  kind of a version of the array that we find in C++11.  And again, similar kind of concepts.  I can subscript it now. I can ask it front and back.  I can even get its data, as long as I respect the const promise.  But this is C++, so you can do what the hell you want.  And again, I've got an underlying contiguous block.  Now, the nice thing about this, again, the same notation,  but the nice thing about this is that it seems to see,  you'll see that suddenly our default for a lot of immutable stuff  is actually arrays.  Now, I remember reading a lot of books a number of years ago saying,  you shouldn't use arrays for everything and this, that, and the other.  They're a terrible data structure.  Well, since then, we've discovered that stuff like cache locality  actually matters.  And arrays are brilliant.  And also, a lot of people think that a certain array sucks,  so therefore, arrays not as evil as people made them out to be.  However, there is one constraint on this being practical,  which is the fact that I am constrained to always have the same values.  And you're thinking, well, hang on, I want to change things.  How am I going to do this stuff?  Turns out we have an answer.  And I'm only going to show you a very small piece of this answer.  Persistent data structures.  Persistent data structure is a data structure that always preserves  the various versions of itself when it is modified.  Such data structures are effectively immutable,  as their operations do not visibly update the structure in place,  but instead always yield a new updated structure.  And the idea there is your structure in one sense can be considered kind of  versioned. You point to the bits and somebody else has a view of it.  And don't get it confused with persistent storage.  Now, we can have a very modest example of this if I do a kind of a vector version.  So here's a kind of vector in FTL style.  And one thing to note, let's zoom in on the pop front and pop back.  This kind of justifies Steppanov's decision to originally make them void returning.  Here, what we're doing is we are not actually popping the front,  popping the back.  What we're doing is we are returning the vector that would have resulted  from popping the front and popping the back,  which makes me think that the naming convention is a bit off,  so I'm going to go for that.  So you're asking it a question.  The question for the vector is what would you look like if I took you at the  front of you off or the back of you?  Return me that.  Now, if we go back to this, you can see the way this is going to be implemented.  Very simply, as we're sharing this array, this true underlying array in memory,  this vector facade is basically sitting there going, all right,  okay, I've got a couple of iterators, pointers basically.  I've got a couple of pointers to that.  If you would like to pop one end or other, I will return me,  but actually I'm going to move one of these back.  The original element is exactly where it is.  The original user of that is exactly where it is.  So I've kept this kind of thematically related by calling it vector.  Pushing is a no-no.  That's not going to happen.  Not for this kind of structure, but it's a very simple idea there.  You've got a data structure from which you can consume elements, but nobody else can.  One of the classic ones for this, where you can start adding stuff,  and now we're going to have to move away from friendly cache locality,  is to walk back through time.  The original Lisp actually got this one right  and actually had a very deep immutable model built into it.  To the point that a few years ago, I actually wrote an article  which was basically based on a pure obsession with Lisp.  I still have a deep fondness for the Lisp.  It's simple, elegant, and something with which all developers should have an infatuation  at least once in their programming life.  I was inspired to try and STL-ize or rather Lisp-ize an STL list.  My conclusion was I called it Lisp.  It's the best I can manage at the time.  I still think it's quite funny. You don't have to share in that humor,  but that's your fault, not mine.  It looks a bit like this.  Same kind of thinking, but all the operations are on the front.  We've got underlying links, your classic linked list,  but here we no longer modify elements within the list.  You can now keep pushing and popping.  This gives you the perfect stack for those that really want to recreate  the classic computer science examples.  The idea is that as time goes by,  what you will end up with is effectively a tree if you were to look in memory.  This person thinks they've got a list with these elements,  and another person thinks they've got a list with these elements.  It happens to share the representation at the back end and so on.  You end up with sharing the underlying state.  One of the nice things that I can do here that I find I cannot do  with the same kind of confidence in certain other languages  is actually pay attention to the constness,  because I can say we are sharing these elements,  and I'm just going to turn the dials up and say in this library,  when we say const we mean const.  Whereas I can't say that for a lot of other languages.  I just have to say play nicely and don't modify things.  Here I can actually get a bit of compiler support.  We could say, we're sharing those.  Those are not going to change.  If they change, then it's somebody doing something inappropriate,  just as if they were mem copying instead of copy constructing.  But I've got that kind of basic structure.  Now that's as far into the persistent data structures as I'm going to go.  There are whole models for hash tables and B-trees and all kinds of stuff.  It's great.  But if you are, if you do program in C++,  rather than just being a tourist here,  you ended up in completely the wrong room,  but we're far too polite to leave,  there should be something that's annoying you and nagging you ever so slightly.  I haven't talked about memory management at all.  At all at all.  It's great having all these shared data structures.  How are we going to do this?  Who's going to clean up, especially with this sharing?  So it turns out we can go back in time.  It turns out that the tragedy of Hamlet, Prince of Denmark,  was actually about memory management as a play.  Who knew?  It's taken centuries to discover this.  Shakespeare was indeed a programmer.  And we see that there are two different perspectives.  So here Hamlet says,  Yay, from the table of my memory, I'll wipe away all trivial font records.  What he's talking about here is garbage collection.  Okay?  It's just like...  And Bjarne said, okay, so this is C++11.  Garbage collection is optional.  That is a garbage collector is not a compulsory part of an implementation.  Hmm.  So that's going to make it really difficult to kind of rely on as a library feature.  Here, I've built this whole library on garbage collection.  Okay.  And could you tell me what garbage collection?  There are three levels at which you can be running garbage collection.  The one you want, the only one that will work, is this one.  Anything else does not work.  So now you either have an assertion failure and not a lot of program.  You say, well, yeah, it works perfectly if you have a garbage collector.  Yeah, but the runtime we're using doesn't have a garbage collector.  It's like, ah, screwed then.  Okay, okay.  So clearly Hamlet is not going to offer us the answer,  but a failure might, it is in my memory locked and you yourself shall keep the key of it.  Yep, we're back to reference counting.  It's okay.  The library does a bit for us, but it's worth going back in time to Robert Murray's quite brilliant book.  It's an often overlooked, but it kind of stands head and shoulders above a lot of the other stuff  that was coming out in the early 90s, C++ strategies and tactics.  And he made the observation back then.  Just very, very simple.  Everybody got really into reference counting.  A used counting class is more complicated than a non-used counted equivalent.  And all of this horsing around with used counts takes a significant amount of processing time.  This is the thing that a lot of people overlook when they think, oh, garbage collection can't be that efficient.  How efficient is it to be using the minute you have a multi-straded piece of C++ code and you use shared pointer in it,  that means that every single implementation, every single instantiation, the shared pointer class will now use  interlocked increments and decrements, even when you don't need them.  Even if you've actually got everything within one thread, simply because you've said it's going to be multi-threaded,  everybody's going to pay that little extra tax.  And it's non-trivial.  But it gets more fun.  Okay, so first thing is it's quite easy for vector.  I can go ahead.  I can do a shared pointer of value type.  I can use that for arrays as well as individual values.  That's fine.  The only problem is I can't take advantage of using make shared, which basically creates the object with a reference count,  because it doesn't allow you to do that.  You can't say, I want to make an array version of this, please.  Which is a shame.  It means, okay, so I create an extra object.  So I've now got two allocations instead of one that I have before.  And that works fine.  We pay a little bit of tax here and there.  And if we're sharing between threads, then that's brilliant because we also get peace of mind for that little bit of taxation.  That's fine.  Everything works.  Everything's truly immutable.  And it's all good.  However, there is the note of caution.  Nothing in life is perfect.  We have a bit of an issue here.  I've just gone and replaced that raw pointer with a shared pointer that does reference counting.  If you remember, a nice big list in memory looking like a tree.  And there are some things that are referenced by two and there are some things that are referenced by one and so on.  And when a particular link goes out of scope or something, reference count drops by one.  That's great.  What happens if they all drop by one?  Imagine I create a list.  I fill it up with some number, how many?  Fill up with some value.  I don't really care.  I'm going to insert at the front because I can pop front, push front rather.  I'm going to insert something there.  Nobody else, I'm not going to share this with anybody.  I'm not going to pass it to anybody.  I'm not going to do anything else with it.  This is just one object and the chain object holds the head link.  That holds the next link, the next link, the next link.  Everybody's reference count is one.  And then I hit the closing curly.  On destruction, the first destructor will be called because, well, the first destructor is going to say, hey, guess what?  Your reference count has just dropped to zero.  I'm going to delete you and there's this beautiful recursive cascade.  You end up having a recursive destructor call.  It depends on your machine, but you're not looking at being able to hold a list of more than about a thousand or two thousand before you blow the stack.  Oops.  In other words, yay for garbage collection.  Now, if you're sitting there going, oh, yeah, yeah, but I'm a Proposy++ program.  I know how to work around this.  Then I've just highlighted, and that just shows us we have a problem.  I never question anybody's ability to work around something.  I'm interested in working with, and actually this one is going to take a little bit of extra work, which is a shame.  So we can't use it straight out the box, which is a shame.  Now, a lot of what I've said has been in the context of assuming something about concurrency.  So let's talk about concurrency.  Now, funny thing, I did this a few years ago, about two or three workshops where I asked people just for fun.  I'd say, I'm going to do a word association game.  I'm going to give you a word, and I want the first word that you think of.  And these days, the results might be different.  So I'm going to treasure the past.  And times I ran it worked absolutely perfectly.  I'd say concurrency, and people would say threads.  And then I'd say threads, and they'd say locks or synchronization.  It's kind of interesting.  And this is even when people are kind of a little more aware.  It's so deeply rooted in there.  Concurrency means threading.  Threading means I'm going to lock stuff.  And I ask people, why are you locking stuff so it can be safe?  OK.  So you're locking it so it can be safe.  Yeah, why are you using concurrency so it can be fast?  OK.  You do know that a lock is the antithread.  Brilliant quote, all computers wait at the same speed.  Always keep that in mind when you've got all those calls busy.  Oh, yes, this many gigahertz.  Yeah, we're all waiting.  And this is the point.  We've got a computational model that doesn't really make sense.  Now, I've said to various people, you need to program thinking without locks.  And one person, I'm glad he said this because I have the feeling that somebody else may not have heard him.  But when I said that in one workshop, one person said,  what, you mean we should take the locks out of our code?  No, no, no, no, no, no, no, no.  You need to compose it from scratch without thinking about locks.  Yeah, but then we'll get problems, which as witnessed by this rather brilliant quote, which I can't read out.  Because of that.  And I said, no, no, no, the problem is you have composed your code from the perspective that you are changing state.  And then, as Bartosz Malewski noted, shared memory is like a canvas where threads collaborate in painting images.  Except they stand on opposite sides of the canvas and use guns rather than brushes.  And the only way they can avoid killing each other is if they shout, duck, before opening fire.  Yeah, so, I mean, this is other observation.  David Butenhoff, responsible for kind of the classic POSIX threads book, also mentioned about locks.  He said, you know, we made a big mistake calling them mutexes and locks and stuff like that.  He said, we should have called them bottlenecks.  Because then people, you know, because when people say, I'm going to put bottleneck right here in the code.  It's just like, you know, words matter, words really matter.  But there is this issue.  There's two things, is that we have these associations.  But we have these associations for a reason, because our approach has been predicated on an assumption that comes from single-threaded,  single-memory procedural programming. And it's permeated every programming language since.  And, you know, every mainstream programming language.  And I noticed this. There was a real shift, 1990s to about 2000, the early 2000s.  In 1990s, all the books on concurrency, and this is right across the board, C through to Java,  whatever people were writing, it was all about state change.  In fact, you can actually see that going back to the work in the 60s and 70s on this.  It was all about how do we synchronize state change.  It was never how do we eliminate state change or what way of thinking or organizing our code would allow that.  And then there was a kind of a shift where a lot of the old styles and conventions started going away as people started realizing,  you know what, there's a way of thinking about this.  So this is a diagram I drew up, first time about three years ago, and I found it immensely useful.  So it's been committed to PowerPoint.  Two axes, it's a quadrant diagram, and you know there's going to be a bad quadrant, because there always is.  But we've divided the universe into four.  We've got two axes, mutability and sharing.  And the one that we really care about or care about avoiding, clearly it's not obvious here, so I'm going to make it really obvious.  Let's use red. In fact, that's just really, that's the synchronization quadrant.  This is where you want to steer clear of.  But most people write their code in this space.  This is where we have objects that change state and are shared between threads.  If we have objects that are not shared, in other words two paths of execution do not follow, go through the same piece of code,  then it turns out you can mutate what you want, and it doesn't matter.  The privacy of a function, for example, feel free to mutate the state, because nobody's ever going to care.  An object that is only accessed asynchronously and only has one piece of work fed to it at a time, same deal.  On the other hand, we can go all the way over here and say, well, what about making our objects immutable?  If they don't change, then I can share them as much as I want. It doesn't make any difference.  But it's when I bring the two together that we get the pain. That's where we get the pain.  And yet, by default, this is where people program.  When you look at the quadrant diagram, it's kind of like, well, actually, why don't we spend more time out here?  Now, there's a number of different approaches that we can take.  So Russell Winder observed clearly message passing leads to better scalability in parallel systems.  Instead of using threads and shared memory as our programming model, we can use processes and message passing.  Process here just means a protected independent state with executing code, not necessarily an operating system process.  And we see this embodied in a number of languages, Erlang and Occam before it.  And I did a bunch of Occam many years ago, and I found that really very helpful in terms of how to think about things.  Very successful mechanism, very easy to scale things, very easy to compose things.  Now, Occam in particular is based on CSP model from Tony Hoare.  And you can take a really simple example. Let's go back to our friend FizzBuzz.  So we've got FizzBuzz. We're going to maintain a separation of concerns.  We're going to create a FizzBuzzer, which is going to interact and it's going to field requests and give responses.  The fundamental construct here is the channel, or the queue, but the language of CSP and indeed the language of go.  If you look into go as a language, then it's channel.  The idea is I'm simply going to set up two channels.  This is a function. The function is the unit of abstraction here.  And then I simply receive what I'm receiving. Then I can calculate and send back.  We have a really, really simple stream model.  Of course, there is synchronization going on, but it's nothing to do with the FizzBuzzer, FizzBuzz, or indeed the client itself,  who simply wires things up by saying, right, I've got two channels.  I've got a function, FizzBuzzer.  I'm going to bind that without and back and I'm going to set this off buzzing.  And then I'm going to loop through and send through requests for one through a hundred, pick up the result and print it out.  And that's it.  And as you can see, of course, there is synchronization going on here, but the synchronization is incredibly discrete.  It's out of the way.  There's no longer the programmers responsibility to mess it up.  And this very, very simple model rather than saying, hey, everybody's sharing all of the objects all of the time.  So this does indeed relate to, relate back to something a number of years ago, I studied this actor-based language, ABCL,  and the actor model computation is not identical, but is certainly related to this kind of thinking.  But I'm not going to get enough time to go into that in any detail.  But I would like to sort of say, well, we have a question sometimes that if I want to pick up the results of something,  how do I pick up the results of a computation?  What if I'm not just streaming evaluations?  In other words, what if I've actually, rather than asking, give me this, I'm going to send you a request,  I want, and send me results when you have them, rather than treating that as two separate processes running,  what if I'm actually trying to use something asynchronous? How do I pick up the result?  This is where futures fit in.  Futures are virtual proxies.  They've been around in different programming languages and programming libraries for a while.  But this idea, a virtual data object, give it to the client, they only provide a value when the computation is complete.  The client can choose to block on it until a value is ready, or they can choose to poll whether or not it's ready or not,  whether it is the value there.  Now, what's nice about this approach, and actually see how we can render this in C++11,  what I'm going to do here is we've taken a different view rather than a long-running thread.  We say our function, whatever it is, we launch it asynchronously,  this is almost a go routine style in that sense, we launch it asynchronously, we pick up its result,  and what happens here is we wrap this.  The idea here is that nobody sits around doing explicit locking,  and what we're after is picking up, we're after this idea of separating out.  That function can go and have as many side effects as it wants,  as long as there's nothing to do with the code that I'm working in.  The thread management, we don't do any thread management,  it is just launched as an asynchronous function, quite literally.  We pick up the result when we want to, we can block here on this io.get.  I'm going to say this is the standard, does a lot of good stuff,  but I'm going to go back to a proposal that I made a number of years ago,  which I much preferred syntactically, where what we actually had was thread was a verb, not an object.  You thread a function and it yields something that is a future, but called a joiner because that's what you do with it,  and that itself is a function, so you can then pass it on to somebody else.  So my mild obsession with functional programming ideas was visible in this,  because I wanted everything to be a function.  And the idea is what I get back is a function that then I can then call that will give me the result.  So I give you, so this is a proper higher order programming.  Harry, that's not the way that the future is gone.  This is what we've got, and that gets us fairly close to that idea of asynchronous execution.  Why does asynchronous execution matter?  Well, it allows us ultimately to share what we're doing, but without interfering.  It allows us to say, I want you to execute something independently of what I'm working on.  I don't want to care about your execution policy.  As long as you keep your state to yourself, then, and you give me an easy way to get the results back, that's what I want.  Far too often, people have launched threads across data structures without thinking about it.  They've gone and said, right, we've got a thread, we've got a shared data structure, we're going to put locks on it,  and the whole code base is jammed up, both from a development perspective and a runtime perspective around this idea.  Rather than thinking, how can I keep things apart?  People have ended up pushing them together too soon.  We need a composable model.  And on that note, I will finish, and I'll take questions afterwards.  Thank you very much.  I'm not really working thin.  Scratch my shoulder.  It's like I'm working from...  When this is over,  Nothing you will be so right.  I'll be one.  If you love me, you will be tonight.  But what's the problem?  You can hide all those issues.  Suddenly this guy you vote on it all with a knife right there.  I can do all sorts.  At the end of yourнак  The whole section is free.  You say that working is what I'm not supposed to do  And I say ain't it right if I can't guess we love you  I'm tired of thinking of what my wish was supposed to be  Well, soon enough darling, this love would be reality  How could you leave a girl, cause love for us wasn't meant to be  Well, then you must be seeing some other guy instead of me  I think that's why you got me working day and night, yeah, and I'll be working  Friends are not to me tonight  I'm working  It's what a man's supposed to do  And I say you ain't right  If I can just be loved to you  I can't believe girl
Functional_C___-_Kevlin_Henney_0_1667.png Functional_C___-_Kevlin_Henney_1668_1763.png Functional_C___-_Kevlin_Henney_1764_2111.png Functional_C___-_Kevlin_Henney_2112_3119.png Functional_C___-_Kevlin_Henney_3120_5831.png Functional_C___-_Kevlin_Henney_5832_6071.png Functional_C___-_Kevlin_Henney_6072_6143.png Functional_C___-_Kevlin_Henney_6144_7547.png Functional_C___-_Kevlin_Henney_7548_12455.png Functional_C___-_Kevlin_Henney_12456_14363.png Functional_C___-_Kevlin_Henney_14364_17555.png Functional_C___-_Kevlin_Henney_17556_18263.png Functional_C___-_Kevlin_Henney_18264_21563.png Functional_C___-_Kevlin_Henney_21564_23159.png Functional_C___-_Kevlin_Henney_23160_23627.png Functional_C___-_Kevlin_Henney_23628_24275.png Functional_C___-_Kevlin_Henney_24276_27767.png Functional_C___-_Kevlin_Henney_27768_27839.png Functional_C___-_Kevlin_Henney_27840_28703.png Functional_C___-_Kevlin_Henney_28704_30287.png Functional_C___-_Kevlin_Henney_30288_30863.png Functional_C___-_Kevlin_Henney_30864_31235.png Functional_C___-_Kevlin_Henney_31236_32495.png Functional_C___-_Kevlin_Henney_32496_33479.png Functional_C___-_Kevlin_Henney_33480_33899.png Functional_C___-_Kevlin_Henney_33900_34451.png Functional_C___-_Kevlin_Henney_34452_37895.png Functional_C___-_Kevlin_Henney_37896_39071.png Functional_C___-_Kevlin_Henney_39072_40331.png Functional_C___-_Kevlin_Henney_40332_40391.png Functional_C___-_Kevlin_Henney_40392_41039.png Functional_C___-_Kevlin_Henney_41040_45155.png Functional_C___-_Kevlin_Henney_45156_50123.png Functional_C___-_Kevlin_Henney_50124_50183.png Functional_C___-_Kevlin_Henney_50184_51455.png Functional_C___-_Kevlin_Henney_51456_54959.png Functional_C___-_Kevlin_Henney_54960_56219.png Functional_C___-_Kevlin_Henney_56220_57527.png Functional_C___-_Kevlin_Henney_57528_57635.png Functional_C___-_Kevlin_Henney_57636_58799.png Functional_C___-_Kevlin_Henney_58800_58967.png Functional_C___-_Kevlin_Henney_58968_59423.png Functional_C___-_Kevlin_Henney_59424_60251.png Functional_C___-_Kevlin_Henney_60252_60587.png Functional_C___-_Kevlin_Henney_60588_61499.png Functional_C___-_Kevlin_Henney_61500_62375.png Functional_C___-_Kevlin_Henney_62376_62651.png Functional_C___-_Kevlin_Henney_62652_63851.png Functional_C___-_Kevlin_Henney_63852_64031.png Functional_C___-_Kevlin_Henney_64032_64295.png Functional_C___-_Kevlin_Henney_64296_65195.png Functional_C___-_Kevlin_Henney_65196_65759.png Functional_C___-_Kevlin_Henney_65760_67931.png Functional_C___-_Kevlin_Henney_67932_70103.png Functional_C___-_Kevlin_Henney_70104_71771.png Functional_C___-_Kevlin_Henney_71772_72335.png Functional_C___-_Kevlin_Henney_72336_73967.png Functional_C___-_Kevlin_Henney_73968_76559.png Functional_C___-_Kevlin_Henney_76560_84443.png Functional_C___-_Kevlin_Henney_84444_85307.png Functional_C___-_Kevlin_Henney_85308_85499.png Functional_C___-_Kevlin_Henney_85500_85727.png Functional_C___-_Kevlin_Henney_85728_86711.png Functional_C___-_Kevlin_Henney_86712_87623.png Functional_C___-_Kevlin_Henney_87624_88859.png Functional_C___-_Kevlin_Henney_88860_88907.png Functional_C___-_Kevlin_Henney_88908_89699.png Functional_C___-_Kevlin_Henney_89700_92219.png Functional_C___-_Kevlin_Henney_92220_93347.png Functional_C___-_Kevlin_Henney_93348_93755.png Functional_C___-_Kevlin_Henney_93756_99539.png
Right, okay, I've just saved you from some very, very mellow music. Okay, so, this is what I'm going to talk about. Well, I'm going to talk a bit about this because as I was putting together the slides on the flight this afternoon, I realized I had far too much material for this talk, and I thought, okay, I'm going to have to subset it. So, I will, in some cases, I will talk, I will, because this is C++, I will use pointers to refer to other things. I will not include the whole thing. I will use that level of indirection that I feel is my privilege. So, this is, I guess this is as opposed to dysfunctional C++, which is a talk on C++ style, and I'm not doing that one today. Although this clearly has an impact on the style. Let me think. Anything else? Who's seen me give a talk before, just so I know how many jokes I can reuse? Okay, reuse is a good thing, just so we're all clear on that one. Right, Kevin and Henny, I've got my name on a couple of books there, and probably better name for 97 Things Every Program I Should Know, but I'm not going to be talking about these things. But I will start off with a quote from one of the contributors to 97 Things. That man there, Michael Feathers. A few years back, he made this very good observation. Object orientation makes code understandable by encapsulating moving parts. Functional programming makes code understandable by minimizing moving parts. It's a very, slightly different philosophy. Now, already, if you're astute, you will see that these two are not necessarily in contradiction, but there is a very large overlapping space, and it turns out that C++ can inhabit this space as well as or as badly as it does other spaces. And I want to explore that. Now, in preparing this talk, a perfect piece of timing. Yesterday, somebody tweeted this, a blog from Facebook about how they'd built, and it's gone about building Facebook moments, and the timing was perfect, because to keep our C++ API boundary simple, we adopted one-way data flow. I would like to talk about that at length, but that may be one of the things I'm going to shorten. The API consists of methods to perform fire and forget mutations, and methods to compute view models required by specific views. Now, some of that's going to go a little bit outside into the architectural space that surrounds this, but it all follows. To keep the code understandable, we write functional style code converting raw data objects into immutable view models by default. As we identify performance bottlenecks through profiling, we added caches to avoid recomputing unchanged intermediate results. What I find interesting about this is that they have specifically pursued an architectural style and said, this is the style we would like to build this in. This is the style we would like to code in, and if there are problems, instead of hacking the poor thing to pieces, as it happens in so many code bases, what we will do is we will preserve the model and support it, find out where it needs to support. In other words, build it so that it is easy to work with this stuff. In other words, that very clear idea, rather than a morpher's mass of code, you have an infrastructure that doesn't merely push bits around, but it actually supports specific styles and qualities of the code. The resulting functional code is easy to maintain without sacrificing performance. Those two phrases in one sentence, that's always good to hear. So what do we mean by functional programming? Well, this is a tag cloud that I kind of been using for the last couple of years. It's a lot. I mean, this is the thing. Functional programming covers a lot of things. I'm not going to cover all of these things. Some of them simply cannot be expressed in C++. Some of them have a natural limit. So for example, with recursion, actually we will cover recursion briefly a bit later, but there's no tail recursion, tail call optimization in C++, and that actually means that there's a certain things you cannot express conveniently. Pattern matching is not reg X's, and it's a little bit outside the space. One could say the whole of the language is a big monad and have a beer over that. I strongly suggest if you wish to understand monads, lots of alcohol. Lots of alcohol. I think I achieved an understanding of monads once when I had lots of alcohol, and I've been unable to recover that understanding since. It is lying on the floor of a hotel room somewhere. However, we will talk about this kind of more declarative approach, higher order functions, pure functions, immutability, landers, and so on. I'm going to start with a very simple example, a very humble example, because some folks from Down Under have been tweeting, that I know are in Oslo at the moment, have been tweeting, and sort of like what kind of weather is this? It's supposed to be summer here in the Northern Hemisphere. It's just like, well, I can say having just come from Southern England, yeah, it's warmer in Southern England by about three degrees. So yeah, that's totally sunburn weather. So we have two seasons basically in much of Northern Europe, grey and construction season. And because of that, when people talk about air conditioning, they're normally talking about offices. So I use the heating system example rather than anything else. The heating system, you want to turn it on, you want to turn it off. Nice and simple. We want to do it on a timer, so I'm going to create a convenient timer abstraction. I can pass in the time of day, I'm going to go ahead and I'm going to say, well, obviously I've read about this kind of thing. I need to perform an action, and I need to apply an action to an object independently and asynchronously from the very decision to do that. How do I decouple the decision that I want to do that from actually doing it? Well, I'm going to use the command pattern. So I'm going to go straight for it, and I'm going to have one of these. Oh, it's all classic Gang of Four stuff. And then we go ahead and we start implementing it. And it's just like, okay, this is the code for turning on. And that's without adding any ritualistic enterprise banners or other noise. And then there's the turn, oh, actually wait a minute, it's just minor, minor fix. This is the great thing about the PowerPoint Monad. Let's just fix that. Yeah, there we go. That's what I needed. I think this qualifies as live coding. There we go. And there we go. So that's what I'm fixing. It might look like I've just done copy and paste. I couldn't possibly comment. Because unfortunately, that is the feature that you're going to end up with. With this style, it's a very copy and paste approach. So to bring that into perspective, you're going to end up with lots of stuff like this. Copy, paste, copy, paste. And this is just a very simple thing. If you look at it, it's mostly programming language noise. We're doing a lot of work to support style. Some people say, wow, this is problem with objects. It's not. It's problem with doing objects in a sucky way. However, a lot of people in C++ won't look at it like that. They will say, oh, you know what? Within C++, there is another language trying to get out. And it's called C. So this is far too much code. I'm going to just go and use function pointers. I'm going to pass in a function pointer for an action to execute. Then I'm going to pass in the context data with it. And then I'm going to get one to execute on the other. So it's just like, yep, so this is it. Void pointers. So void pointer is a way of selling the compiler. Thanks. Thanks for all your help. But I'll take you from here. Trust me on this one. Don't need to tell me about types. It's trust the programmer time. And so we go ahead and we've got that. And this is nice because everything come down to sort of one-liners. The only problem is that there is a tacit agreement between, there's a contract here that is difficult to enforce within a language that has typing. In a language that is dynamically typed, this is curiously enough not a problem in the same way. Because it turns out that if I try and do the wrong thing with an object in a language that is dynamically typed, the language tells me in a useful way that I can do something about. As opposed to wandering off and doing mysterious things to bytes that I really shouldn't be entitled to do. If I do not pass in a thing that can be cast to a heating system, all bets are off. And it gets very exciting. So this is not the kind of stuff. The brevity we like, but the kind of the syntax noise, and sometimes people go, oh, that's OK. You can just use a C-style cast. No, no, no, no, no. Casts should be ugly and big and explicit. One, you can grep for them. And two, it's a big warning sign saying, look here. And I've actually had one person say, I don't like using those casts because all of my code, you get two levels of casting. Reinterpreted cast and casting. I said, that's your code trying to tell you that it sucks. Listen to your code. OK. So, OK, what we're going to do is we're going to say, ah, right. We're going to encapsulate a function concept of some kind and make it a complete one. In other words, I'm going to say, I need a thing that looks like a function. So I'm going to go over a little bit to the sort of looser side of things. I merely need to be able to call it as something that doesn't take any arguments and returns. Nothing. I'm going to say, right, OK, that's fine. I don't actually care that it's a function. It merely supports a function protocol. That's it. It can be a function object. And we can do a whole load of really neat things with that once we've got that. The only thing that we discover is we don't actually need to define a function as we did with the C-style. We certainly don't need to define a class as we did with kind of misapplication of the gang of four. So I can now create two objects on and off. This is when I want the time on. This is when I want it off. And I'm going to bind the very action itself turning on, which I already have in the heating system. In other words, we already have the functionality. We don't need to wrap it. I'm going to bind it immediately. At the object level. So I can do this. So bind is basically a higher order function that takes a function or something function like and yields a thing that can be executed as a function. So this is all good. That is now in the C++ standard. And I might have ported that one from boost code if I think about that one. So let me just be strictly politically correct here. There we go. I'll keep the police off my back. And but then obviously people are like, yeah, I can't get what you're doing. But then we've got lambdas. So it's even easier at that point. We just pass in a piece of code that is a function object, but that's the language doing it for us. Pass it in and we're done. So in other words, we haven't had to create any intermediate type level abstractions. We haven't had to create or declare other function abstractions. We haven't had to compose on the fly. And it's this compositionality that is the key to any style that we want. So we could say, well, you know, this is really very, you know, this is C++ 11 and this is all very 21st century except we need to remind ourselves that Lambda calculus is actually older. William Cook identified it as 1941 in rather good presentation and paper on understanding data abstraction revisited. But I did a bit more digging around and it turns out it's 1932. So C++ 11 now allows you to program like it was 80 years ago. Yay. On the other hand, there are some glorious pieces in that syntax, some of the syntax decisions. So if you've not really messed about with lambdas, I'd just like to point out that that is valid C++. And in fact, so is this because this executes that valid C++. This is something that takes no arguments, returns nothing, captures nothing, and does nothing perfectly. It's a very cohesive concept. This one executes it and therefore does nothing. Huh? With any luck, yes, yes. But it now gives your cat new and exciting opportunities for running across your keyboard and actually yielding a valid code base. All of which, you know, what is a program? Nicholas Verth answered this one for us many years ago. Algorithms for Stata Structure Equals Programs. Now, the thing here is that normally for a lot of people, that means historically, I'm going to take my algorithm and data structures and then mash them all together, and that's my program. Now, actually, the idea here is we would like to separate these things out. This kind of composition style thinking. Now, what we've actually seen already with just being able to treat functions as first class objects, that is you can argue, and both people and both sides do, which is why it's generally better to get yourself a seat to the side and watch both sides going at each other, because I think that the previous solution was a very good sort of functionally inspired solution or it was a very good object oriented solution. Both apply. But here's a different perspective. Let's take this a bit further. This kind of inspiring thought has been algorithms are a way of doing something. Data structures are merely what we do them with. The most obvious space in which this is separated in C++ is the STL. This was Alex Stepanov's original goal, basically, to be able to say, I wish to separate out the abstractions of representation from the choice of algorithm that I've got, and I wish to keep these separate, but in a way that is composable and allows me the efficiency. So, in honour of the fact that a couple of years back with Anders Noras at this conference, in fact, we did a whole bunch of stuff on functional programming messing about with languages. I thought I'd use one of the examples that I introduced in that one. It depends how good your memory is, but the world was going to end in 2011, twice, actually. The date advertised, and then when Harold Camping discovered that the date had not actually transpired as the end of the world, he said, no, no, no, I meant six months time in October or so, and that didn't happen either. But then we had the end of 2012 because apparently the Mayan calendar was going to run out. Nobody ever worries about the fact that the regular calendar runs out in December and then cycles back. It uses modular arithmetic. It turns out the Mayans were onto this one as well. So it didn't end in 2012, and it didn't end at the beginning of last year, which is supposed to be Ragnarok last February. That didn't work out either. However, this one was memorable because I was actually in New York. It was Friday the 13th. This is the site of the former World Trade Center, and if you're going to advertise the end of the world, this is a great way to do it. Stand there with a billboard on Friday the 13th, right next to this iconic and sad location, and there you have it. So let's find out. Friday the 13th, what do we know about it? Paris-Gavie-Decaturia phobia is the fear of Friday the 13th, so if you learn nothing else today, that's useful. And we need, for a certain class of the population, we need to find out when is this going to be. So we go away and we hack some C, and we use struct Tm. We do all kinds of stuff, and it's kind of all there. The only highlight is perhaps that we have daily sex. But, you know, you're kind of running around this loop looking for this stuff and looking for the next answer. Now, this works, but it's a bit messy. You've got the usual kind of hieroglyphic noise. There is something that we can do with this from a C++ perspective, and it's actually sort of a separation. Back to our friends at the Landers. I'd love to tidy up struct Tm, but I thought I'd leave that one outside the scope of this problem. Find if, from here, so I want to start from today, or actually tomorrow, then I'm going to have a token that is infinity. This is the best way to represent infinity, something that you can never reach. This is how we do this. The easiest way to deal with infinite lists, and this is something functional programmers do all the time, is you make sure you don't have all of the list at once. Infinity is incredibly easy to deal with if you start at the beginning. If you try and hold it all at once, you're screwed. But if you say, from now until beyond the end of time, then we're okay, because it turns out we will find Friday the 13th before that. You're guaranteed, if you go through it, you're guaranteed there's a couple every 500 days. So what we've done is apply a filter to this one. This is just a placeholder, and we've introduced a day iterator. This idea of using iterators, we tend to think of as a very classic object-oriented solution, but in another sense, it's actually a really good way of looking at lazy evaluation. I wish to consume the content of a container, physical or abstract, but I don't wish to do it all at once. I wish to do it one element at a time. I want to work from the head through to the tail, and then I will take the head of that tail and so on, and I will do this, and on demand, values will appear as I need them. This is the basic idea behind an iterator, although people don't tend to think of it like that. But that allows you an ordered simple access. Now, in the next C++ standard, C++ 17, they're coming thick and fast, C++ 11, C++ 14, then there's 17. The next C++ standard will introduce a range concept that will allow us to tidy a little bit of this up and actually use a much more pipeline-style notation to compose these things. Unfortunately, this is one of the reasons that, although I remember being very excited by STL iterators, because I used to think that operator overloading was really cool, and actually I still kind of do, the problem is that not everybody thinks like that, and so you have to go away and write stuff like this to wrap it up. So there's a bit of boilerplate, unfortunately, but this is a supporting abstraction. If you're only going to do it once in a piece of code, then you might be better off doing that, but the minute you do it twice, I think you're better off doing that. In other words, I am going to give you the tools from which to compose these elements, and then you can go and search for the, turns out Friday the 13th is geographically dependent. Some people don't like Tuesdays. For other people, 17th is bad, so you want to generalize this at that level. So suddenly I've got a way of doing this. Now, given this is a language of the obscure corners, and I want to talk about this idea of immutability and not having side effects, there's a kind of interesting piece of the language. A couple of you have seen this before. This is an interesting historical note. Irvin Unruh, Siemens, we used to work for Siemens, the compiler division, like all great works of art. This is untitled. He discovered, let me put it this way, this piece of code doesn't compile. It's a whole load of template stuff, and it doesn't compile. And you might be thinking that's not exceptional. People often create templated code that doesn't compile. Big deal. Yeah, but when this one fails to compile, it prints out the first few prime numbers as part of its compilation message. Now, that I don't get normally from this kind of code. And what Irvin had discovered was that C++ templates are chewing complete. It's one of those little accidents that wasn't the original plan. It turns out anything that you can compute can be computed with them. And this gave rise to template metaprogramming, which has turned out to be anything but temporary. It is a way that many C++ programmers will secure their job by writing code that people just will look at and go, I have no idea what that is. I really don't understand what it does at compile time. And then it's become so commoditized and sophisticated that people have been creating libraries for years. In Boost, there is a template metaprogramming library that Adam Peterson used to solve one of the harder problems that we know in software development, FizzBuzz. And again, this piece of code does not compile. And its compilation message is indeed FizzBuzz. One, two, Fizz, four, Fizz, seven, eight, Fizz, buzz, eleven. That's a great compilation message. Now, why am I showing this? One, it's frivolous, it's fun, and two, it's pure functional programming. There are no side effects. At compile time, you do not have state that you can manipulate. At compile time, you have an execution model that is based on, if you like, a pure value model. And functions, they're not functions in the, certainly not what I just showed you, are not functions in the classic sense. They are kind of meta functions. And Fizz is masquerading as if they were functions, they're doing computations on types or on compile time values. Now, it turns out that you can actually do useful stuff with template metaprogramming and have it compile. But C++11 went a step further and allowed us to do the stuff at compile time and have it compile, which is kind of useful. Again, not the most useful piece of code, but I can say that something that has no side effect, therefore, is a constant at compile time and actually have that expressed directly. Nothing with side effects is allowed in there. There are certain constraints on what you can put in a constant X for a function, which have been loosened a little bit with C++14. But the idea here is that you are able to use relatively ordinary C++ code rather than kind of weird out template metaprogramming or resorting to macros to achieve, to be able to use this to express yourself. And I think this is the key idea, to express yourself and say, I want that value and I would like it computed because either it needs to be a compile time constant or I do not wish to have a runtime computation cost associated with it. And therefore, it would be nice if it were done this way. And that I don't go off and have to pre-calculate it off to the side. I want it in the code. I want the code to express that as clearly as I would any other functional composition that I would use. So that one actually addresses that problem, which kind of leads us to this idea. This kind of classic quote from Lucius Carey, an unfortunate figure in the English Civil War, who left us with a rather useful quote, when it is not necessary to change, it is necessary not to change. And we know pretty much that within C++, the main reason that, the main way people express this unchangingness is through the const keyword. Now, it goes a bit further than that. I mean, there's not simply just const correctness. But const is basically a promise that is, well, it's C++, you can violate it quite easily. We want something that's a little bit deeper. We want to go much, much deeper than this. We really want to say, we don't want things to change. Now, a lot of people think it is kind of a right that an object should be able to change state, and that if I have a piece of state, therefore it is changeable. There is a kind of question here that is pushed at us by functional programming. Are you entitled to change state? Does that actually make sense? Now, there are a couple of other things that kind of go with const. One of them is reference. Pass things by reference, make sure they don't change. But const in this sense is only a read-only promise. So we need to be very careful with that when we start saying, actually, I want something to be truly immutable. C++11, we've also got r-value references, which also support this idea that maybe I can actually copy things around, rather than merely pass them around as references that are read-only. I can actually say, here, have a copy of something, even if it's a vector that's this big, and I can pass it to you, and that's a cheap operation. If you've not looked into r-value references, I strongly recommend it. They are one of those features in the language that is sure to allow people that know what they are to keep their jobs against people that don't know what they are. It's much harder than a lot of other ideas floating around at one level, but once you understand why they tick, why they work, then it kind of makes a lot of sense. But you have to have sort of an optimization head about you. It's very much for the person providing the abstractions. Now, I want to take this and contrast this with these two basic approaches. I'll take a description from a pose of four. So very commonly, a number of languages, we make these observations. References to value objects are commonly distributed, stored in fields, as stored as data members. Have a state change to a value caused by one object can have unexpected and unwanted side effects for any other object sharing the same value instance. This is a kind of a common problem. The minute you have any kind of aliasing and you combine it with state change, this becomes an issue. And C++ has no shortage of aliasing mechanisms. Copying the value can reduce the synchronization overhead, so we would care about this in a threaded environment. This matters, but I'm going to say even without threading, aliasing can produce enough surprises to keep you on your toes. But you've also got an object creation overhead. Copying is not for free. It turns out that in many cases, copying is the cost that we need to address. And this ultimately gives rise to the idea of immutable values. Therefore, define a value object whose instances are immutable. Now, this technique is used extensively in reference-based languages such as Java and C-Sharp and basically saying, I don't want to change that object, therefore, we can share it freely. Because I cannot actually change the state of it, it doesn't matter what you do with it because the one thing you can't do is something that's going to change my perception of that object. This is kind of anathema to a lot of C++ developers who regard the idea of assignment as a fundamental right. And we can kind of compromise a little bit. It's also not that idiomatic because it spends a... There's a lot of assumptions about heap usage here that are not shared in C++. So there's another technique that we're more likely to use. I'll skip the blurb. Copy value. C++, I get copying as part of the language. I don't get that in a number of other languages. If I pass an object back to you, you get a reference to that object. If you want to copy, you have to ask for it. It's unfortunate because the syntax, you have to add syntax and you have to remember to add syntax. So this is the bit you get for free. This is the thing the language does for you for free. So let's go and hack around with kind of one of those examples that people always wheel out. I certainly do. A date example, year, month and day. There is only one true ordering in case you're wondering. There are three orderings on the planet. And there is only one correct one. And there's one that's kind of correct. And then there's another one that reminds us why there's an Atlantic Ocean. And I've left out the r-value versions. The idea is that we're getting the copy operations for free. This is kind of hard-wired into C++ as a DNA. And it's not necessarily a bad thing, although people sometimes find themselves fighting against it because they work in a different style. They're trying to do a sort of Java style C++, which is not entirely successful. And they go ahead, and without even thinking, in fact they probably got it in their editor, they go ahead and they're kind of like, yeah, I'm going to type a getter, and then there's a setter because all getters have a friend, a setter. They have a buddy system, it turns out. And I just want to say, no, no, no, no, no, no, no, no. This is not a good thing. This is a bad thing. In fact, we want to question that. So let's get rid of that assumption. The idea of individual field sets for something that has a complex invariant like a date makes no sense whatsoever. You need to set it all at once or not at all. So the first thing we do is restrict the channel of change. So we might provide a set operation that does appropriate validation, and then we can go ahead and do sets. Okay. But actually, we got one of these for free. We've already got it. It's called the assignment operator. It does it. It does the right thing. It basically means that if you construct a date correctly, you need to do an extra set of checks, as I would have done with set. So for example, the validation here, this has to validate the new state. And if the new state is incorrect, I presume we may throw an exception, and leave the old state intact. Or if we're programming without that kind of mindset, we will just set it and say, well, you're on your own. It's an invalid object. But here we're saying, no, no, no, we're going to actually use this, which will do the validation. So you localize the validation in one place, the point of creation. That is what a constructor is there for. It is there to give you a valid object. Once you've got a valid object, you can pass it around. You can take copies of it for free, basically. So we've got that. Now, we've got a few other syntax choices we can mess about with. I'll leave it to you to sort of decide which one you want to go for. But there's one more refinement I'm going to make to this class. Honestly, people, what is it with the get? I'm a native English speaker, and I'm here to tell you that get, something, is imperative. If you're trying to get functional, don't use imperative naming. That's the first thing. And what does get imply? A lot of you ask a lot of programmers who speak a different language, and I'm also talking about people who speak English as a first language. Programmers suddenly forget that they already knew a language. And I say, what does get imply? And they say it implies it's a query. No, it doesn't. Really, it doesn't. So let me think. Today, I got up to get a flight. A few years ago, let me think, what did I do? I got married. I went to the cash machine today to get money. In every single one of these, there was a big, profound state change. Now, if you can show me a cash machine that doesn't, you know, have that little side effect of reducing my bank balance, I want to use it. But get means I am going to change your state. So next time somebody defends this as a naming convention, you say, you cannot have a const getter because, by definition, a getter is not a const thing. It is a state-changing thing. That's what it means in English. So we're also going to have this nice side effect. Oh, no. But it's okay. It's in the PowerPoint monad, this nice side effect of, oh, sensible names. It just means year, month, day, month. If you want to try and affect a functional style, then don't use imperative naming. Now, this point about values is interesting because values form kind of a staple ingredient of this space and this functional space. The idea is that we are trading not so much in objects with identity, but in values. And as we know, mathematical values are surprisingly unchanging. So if I take five, there is nothing I can do to it to make it any other number. If I ask to add one to it, I don't get back five modified, I get back six. Everybody else using five keeps using the same five. Now, in C++, we do this by copying things around and saying the state of those bits represents that value and there are a set of operators we may affiliate with them. But it also ties in more deeply. This is a number of years ago, oh, get the templates there. I had a column in C++ report very briefly, but I talked about substitutability and we often talk about substitutability with respect to the LISC-OFF substitution principle. And I basically pointed out that actually that's a very narrow view of what substitutability implies. And we can look at it from the point of view of conversions. You can substitute, in some cases, you can mix one numeric type with another or you can provide your own user-defined type and have it mix easily with existing types and then you can support using conversions, similarly, using overloading so that it can participate in the same kinds of expressions as other types and it is therefore substitutable, particularly in the context of, say, templates. And then there's the standard interpretation of LISC-OFF, which is inheritance, but the other one is to substitute something with respect to change or absence of change. And this is the bit where it gets interesting, is this idea of referential transparency is again going to support what we're doing. So the referential transparency idea, Edward Garson sort of pointed this one out in 97 Things Every Programme Should Know, very desirable property implies functions consistently yield the same results given the same input, irrespective of where and when they are invoked. That is, function evaluation depends less, ideally not at all, on the side effects of mutable state. If you go back to the Facebook quote at the beginning of the talk, you will notice that what they did is they basically say, okay, they wanted to have referential transparency. If something was slow, they would cache values in order to achieve that effect. And always the idea is on the outside, you're going to create abstractions that are consistent and their state is durable and it looks like they're recalculating it every time, but this is an optimization. You give yourself the opportunity to optimize. A very simple way of looking at this in item potence is Bertrand Meyer pointed out, asking a question should not change the answer and nor should asking it twice. There is this idea that my functions should represent pure computation and those ones should be very clear and separate from the ones that have side effects. In any large system, you're going to need these space of side effects. But the way I would try to appeal to you to think about it is instead of thinking here is a big mass of code and there's bits of it that have no side effects and I've got const over there and my friend, we had a chat down the pub and we've decided const over there and there's a few other things and we got rid of the word get in this place instead of this kind of patchwork architecture. What I'm suggesting here is that you carefully zone out the code base. You figure out which are the parts of the code base where I need the moving parts and which are the parts where I don't and actually be very strict in enforcing these and say the style in this part of code is very strictly to be pure functional or close to pure functional to give the illusion of that and we will endeavor to keep that style in this space. In other spaces, we may not follow that style particularly we're dealing with existing APIs and existing code but to have a very clear separation rather than kind of a muddled hodgepodge. Be very, very clear where are the more functional pieces of the code because that allows you to reason about it. That's one of the reasons they say, they were saying it's nice and maintainable because it's a lot easier to just reason about stuff. You don't have to keep ahead full of side effects. Now as an aside, one of the other things I'm going to say is when you adopt a stricter more function and functional style with more immutable state and clearer functions and objects that represent values and more value like, you also end up with a lot easier or a lot less mocking. Some people absolutely love mocking. They get up in the morning and they kind of like, okay, where's my nearest mock object? I need my mocks. It's just like really programming is not about mocking. Mobs have a role but they are not the role that a lot of people put them to, which is everything. So you might say, well, this is all very well for things like date and very fine-grained representational types. But what about containers? It's all very well to say, you know, what is inside the book is what matters. What is inside the containers, what matters. But what about the actual container itself? How am I going to make these guys immutable? Okay, well, let's imagine a little thought experiment. Create the FTL, Functional Template Library. What am I going to go for? Well, all the value types are going to be const. The iterators, they're going to be const because there is no point in having a const iterator because you cannot non-constit. I'm going to have a whole bunch of queries. I'm going to support assignment, but I'm going to treat that purely as the only state modification. I'm going to treat that as a rebinding of state rather than actually modifying an existing object. It's a pure rebinding. Now, if I'm fixing things at construction time, there's a couple of little things that I can get out of this. Oh, yes, in my simplification, I have avoided the nightmare that is allocators. For those of you who've not really had any experience with allocators, keep it that way. Okay, they're kind of like an experiment gone horribly, horribly wrong. It's a kind of Jurassic Park of code. And there have been some velociraptor refinements in recent standards, but really it's just making the best of a bad job. Life is much simpler without them. Besides which, if I want to have a collection of immutable stuff, one of the things I'm going to need is to really take control of memory from the container's point of view, not some memory allocators that doesn't know what I'm doing. And so we can immediately have this little advantage. I'm going to go for a set here. My sets are ordered, and I'm going to say, I'm going to take advantage of some syntax here. I'm going to initialize this set to these values. And there's duplicate 9's and duplicate 2, so it'll come out. So the sequencing will come out 245789, and we have a size of 6. I can query it. I can, from beginning to end, using an iterator, I can find values in it. Count occurrences preferably use lower bound and equal range to find things. And I have a very simple representation. I have simply an array of the values. And that is shareable. When I copy that set to somebody else, they get exactly the same set. We're actually sharing it under the hood. So I can pass this around. Once initialized, it's fixed. And this is great. This is nice and easy. And likewise, I can create an array, kind of a version of the array that we find in C++11. And again, similar kind of concepts. I can subscript it now. I can ask it front and back. I can even get its data, as long as I respect the const promise. But this is C++, so you can do what the hell you want. And again, I've got an underlying contiguous block. Now, the nice thing about this, again, the same notation, but the nice thing about this is that it seems to see, you'll see that suddenly our default for a lot of immutable stuff is actually arrays. Now, I remember reading a lot of books a number of years ago saying, you shouldn't use arrays for everything and this, that, and the other. They're a terrible data structure. Well, since then, we've discovered that stuff like cache locality actually matters. And arrays are brilliant. And also, a lot of people think that a certain array sucks, so therefore, arrays not as evil as people made them out to be. However, there is one constraint on this being practical, which is the fact that I am constrained to always have the same values. And you're thinking, well, hang on, I want to change things. How am I going to do this stuff? Turns out we have an answer. And I'm only going to show you a very small piece of this answer. Persistent data structures. Persistent data structure is a data structure that always preserves the various versions of itself when it is modified. Such data structures are effectively immutable, as their operations do not visibly update the structure in place, but instead always yield a new updated structure. And the idea there is your structure in one sense can be considered kind of versioned. You point to the bits and somebody else has a view of it. And don't get it confused with persistent storage. Now, we can have a very modest example of this if I do a kind of a vector version. So here's a kind of vector in FTL style. And one thing to note, let's zoom in on the pop front and pop back. This kind of justifies Steppanov's decision to originally make them void returning. Here, what we're doing is we are not actually popping the front, popping the back. What we're doing is we are returning the vector that would have resulted from popping the front and popping the back, which makes me think that the naming convention is a bit off, so I'm going to go for that. So you're asking it a question. The question for the vector is what would you look like if I took you at the front of you off or the back of you? Return me that. Now, if we go back to this, you can see the way this is going to be implemented. Very simply, as we're sharing this array, this true underlying array in memory, this vector facade is basically sitting there going, all right, okay, I've got a couple of iterators, pointers basically. I've got a couple of pointers to that. If you would like to pop one end or other, I will return me, but actually I'm going to move one of these back. The original element is exactly where it is. The original user of that is exactly where it is. So I've kept this kind of thematically related by calling it vector. Pushing is a no-no. That's not going to happen. Not for this kind of structure, but it's a very simple idea there. You've got a data structure from which you can consume elements, but nobody else can. One of the classic ones for this, where you can start adding stuff, and now we're going to have to move away from friendly cache locality, is to walk back through time. The original Lisp actually got this one right and actually had a very deep immutable model built into it. To the point that a few years ago, I actually wrote an article which was basically based on a pure obsession with Lisp. I still have a deep fondness for the Lisp. It's simple, elegant, and something with which all developers should have an infatuation at least once in their programming life. I was inspired to try and STL-ize or rather Lisp-ize an STL list. My conclusion was I called it Lisp. It's the best I can manage at the time. I still think it's quite funny. You don't have to share in that humor, but that's your fault, not mine. It looks a bit like this. Same kind of thinking, but all the operations are on the front. We've got underlying links, your classic linked list, but here we no longer modify elements within the list. You can now keep pushing and popping. This gives you the perfect stack for those that really want to recreate the classic computer science examples. The idea is that as time goes by, what you will end up with is effectively a tree if you were to look in memory. This person thinks they've got a list with these elements, and another person thinks they've got a list with these elements. It happens to share the representation at the back end and so on. You end up with sharing the underlying state. One of the nice things that I can do here that I find I cannot do with the same kind of confidence in certain other languages is actually pay attention to the constness, because I can say we are sharing these elements, and I'm just going to turn the dials up and say in this library, when we say const we mean const. Whereas I can't say that for a lot of other languages. I just have to say play nicely and don't modify things. Here I can actually get a bit of compiler support. We could say, we're sharing those. Those are not going to change. If they change, then it's somebody doing something inappropriate, just as if they were mem copying instead of copy constructing. But I've got that kind of basic structure. Now that's as far into the persistent data structures as I'm going to go. There are whole models for hash tables and B-trees and all kinds of stuff. It's great. But if you are, if you do program in C++, rather than just being a tourist here, you ended up in completely the wrong room, but we're far too polite to leave, there should be something that's annoying you and nagging you ever so slightly. I haven't talked about memory management at all. At all at all. It's great having all these shared data structures. How are we going to do this? Who's going to clean up, especially with this sharing? So it turns out we can go back in time. It turns out that the tragedy of Hamlet, Prince of Denmark, was actually about memory management as a play. Who knew? It's taken centuries to discover this. Shakespeare was indeed a programmer. And we see that there are two different perspectives. So here Hamlet says, Yay, from the table of my memory, I'll wipe away all trivial font records. What he's talking about here is garbage collection. Okay? It's just like... And Bjarne said, okay, so this is C++11. Garbage collection is optional. That is a garbage collector is not a compulsory part of an implementation. Hmm. So that's going to make it really difficult to kind of rely on as a library feature. Here, I've built this whole library on garbage collection. Okay. And could you tell me what garbage collection? There are three levels at which you can be running garbage collection. The one you want, the only one that will work, is this one. Anything else does not work. So now you either have an assertion failure and not a lot of program. You say, well, yeah, it works perfectly if you have a garbage collector. Yeah, but the runtime we're using doesn't have a garbage collector. It's like, ah, screwed then. Okay, okay. So clearly Hamlet is not going to offer us the answer, but a failure might, it is in my memory locked and you yourself shall keep the key of it. Yep, we're back to reference counting. It's okay. The library does a bit for us, but it's worth going back in time to Robert Murray's quite brilliant book. It's an often overlooked, but it kind of stands head and shoulders above a lot of the other stuff that was coming out in the early 90s, C++ strategies and tactics. And he made the observation back then. Just very, very simple. Everybody got really into reference counting. A used counting class is more complicated than a non-used counted equivalent. And all of this horsing around with used counts takes a significant amount of processing time. This is the thing that a lot of people overlook when they think, oh, garbage collection can't be that efficient. How efficient is it to be using the minute you have a multi-straded piece of C++ code and you use shared pointer in it, that means that every single implementation, every single instantiation, the shared pointer class will now use interlocked increments and decrements, even when you don't need them. Even if you've actually got everything within one thread, simply because you've said it's going to be multi-threaded, everybody's going to pay that little extra tax. And it's non-trivial. But it gets more fun. Okay, so first thing is it's quite easy for vector. I can go ahead. I can do a shared pointer of value type. I can use that for arrays as well as individual values. That's fine. The only problem is I can't take advantage of using make shared, which basically creates the object with a reference count, because it doesn't allow you to do that. You can't say, I want to make an array version of this, please. Which is a shame. It means, okay, so I create an extra object. So I've now got two allocations instead of one that I have before. And that works fine. We pay a little bit of tax here and there. And if we're sharing between threads, then that's brilliant because we also get peace of mind for that little bit of taxation. That's fine. Everything works. Everything's truly immutable. And it's all good. However, there is the note of caution. Nothing in life is perfect. We have a bit of an issue here. I've just gone and replaced that raw pointer with a shared pointer that does reference counting. If you remember, a nice big list in memory looking like a tree. And there are some things that are referenced by two and there are some things that are referenced by one and so on. And when a particular link goes out of scope or something, reference count drops by one. That's great. What happens if they all drop by one? Imagine I create a list. I fill it up with some number, how many? Fill up with some value. I don't really care. I'm going to insert at the front because I can pop front, push front rather. I'm going to insert something there. Nobody else, I'm not going to share this with anybody. I'm not going to pass it to anybody. I'm not going to do anything else with it. This is just one object and the chain object holds the head link. That holds the next link, the next link, the next link. Everybody's reference count is one. And then I hit the closing curly. On destruction, the first destructor will be called because, well, the first destructor is going to say, hey, guess what? Your reference count has just dropped to zero. I'm going to delete you and there's this beautiful recursive cascade. You end up having a recursive destructor call. It depends on your machine, but you're not looking at being able to hold a list of more than about a thousand or two thousand before you blow the stack. Oops. In other words, yay for garbage collection. Now, if you're sitting there going, oh, yeah, yeah, but I'm a Proposy++ program. I know how to work around this. Then I've just highlighted, and that just shows us we have a problem. I never question anybody's ability to work around something. I'm interested in working with, and actually this one is going to take a little bit of extra work, which is a shame. So we can't use it straight out the box, which is a shame. Now, a lot of what I've said has been in the context of assuming something about concurrency. So let's talk about concurrency. Now, funny thing, I did this a few years ago, about two or three workshops where I asked people just for fun. I'd say, I'm going to do a word association game. I'm going to give you a word, and I want the first word that you think of. And these days, the results might be different. So I'm going to treasure the past. And times I ran it worked absolutely perfectly. I'd say concurrency, and people would say threads. And then I'd say threads, and they'd say locks or synchronization. It's kind of interesting. And this is even when people are kind of a little more aware. It's so deeply rooted in there. Concurrency means threading. Threading means I'm going to lock stuff. And I ask people, why are you locking stuff so it can be safe? OK. So you're locking it so it can be safe. Yeah, why are you using concurrency so it can be fast? OK. You do know that a lock is the antithread. Brilliant quote, all computers wait at the same speed. Always keep that in mind when you've got all those calls busy. Oh, yes, this many gigahertz. Yeah, we're all waiting. And this is the point. We've got a computational model that doesn't really make sense. Now, I've said to various people, you need to program thinking without locks. And one person, I'm glad he said this because I have the feeling that somebody else may not have heard him. But when I said that in one workshop, one person said, what, you mean we should take the locks out of our code? No, no, no, no, no, no, no, no. You need to compose it from scratch without thinking about locks. Yeah, but then we'll get problems, which as witnessed by this rather brilliant quote, which I can't read out. Because of that. And I said, no, no, no, the problem is you have composed your code from the perspective that you are changing state. And then, as Bartosz Malewski noted, shared memory is like a canvas where threads collaborate in painting images. Except they stand on opposite sides of the canvas and use guns rather than brushes. And the only way they can avoid killing each other is if they shout, duck, before opening fire. Yeah, so, I mean, this is other observation. David Butenhoff, responsible for kind of the classic POSIX threads book, also mentioned about locks. He said, you know, we made a big mistake calling them mutexes and locks and stuff like that. He said, we should have called them bottlenecks. Because then people, you know, because when people say, I'm going to put bottleneck right here in the code. It's just like, you know, words matter, words really matter. But there is this issue. There's two things, is that we have these associations. But we have these associations for a reason, because our approach has been predicated on an assumption that comes from single-threaded, single-memory procedural programming. And it's permeated every programming language since. And, you know, every mainstream programming language. And I noticed this. There was a real shift, 1990s to about 2000, the early 2000s. In 1990s, all the books on concurrency, and this is right across the board, C through to Java, whatever people were writing, it was all about state change. In fact, you can actually see that going back to the work in the 60s and 70s on this. It was all about how do we synchronize state change. It was never how do we eliminate state change or what way of thinking or organizing our code would allow that. And then there was a kind of a shift where a lot of the old styles and conventions started going away as people started realizing, you know what, there's a way of thinking about this. So this is a diagram I drew up, first time about three years ago, and I found it immensely useful. So it's been committed to PowerPoint. Two axes, it's a quadrant diagram, and you know there's going to be a bad quadrant, because there always is. But we've divided the universe into four. We've got two axes, mutability and sharing. And the one that we really care about or care about avoiding, clearly it's not obvious here, so I'm going to make it really obvious. Let's use red. In fact, that's just really, that's the synchronization quadrant. This is where you want to steer clear of. But most people write their code in this space. This is where we have objects that change state and are shared between threads. If we have objects that are not shared, in other words two paths of execution do not follow, go through the same piece of code, then it turns out you can mutate what you want, and it doesn't matter. The privacy of a function, for example, feel free to mutate the state, because nobody's ever going to care. An object that is only accessed asynchronously and only has one piece of work fed to it at a time, same deal. On the other hand, we can go all the way over here and say, well, what about making our objects immutable? If they don't change, then I can share them as much as I want. It doesn't make any difference. But it's when I bring the two together that we get the pain. That's where we get the pain. And yet, by default, this is where people program. When you look at the quadrant diagram, it's kind of like, well, actually, why don't we spend more time out here? Now, there's a number of different approaches that we can take. So Russell Winder observed clearly message passing leads to better scalability in parallel systems. Instead of using threads and shared memory as our programming model, we can use processes and message passing. Process here just means a protected independent state with executing code, not necessarily an operating system process. And we see this embodied in a number of languages, Erlang and Occam before it. And I did a bunch of Occam many years ago, and I found that really very helpful in terms of how to think about things. Very successful mechanism, very easy to scale things, very easy to compose things. Now, Occam in particular is based on CSP model from Tony Hoare. And you can take a really simple example. Let's go back to our friend FizzBuzz. So we've got FizzBuzz. We're going to maintain a separation of concerns. We're going to create a FizzBuzzer, which is going to interact and it's going to field requests and give responses. The fundamental construct here is the channel, or the queue, but the language of CSP and indeed the language of go. If you look into go as a language, then it's channel. The idea is I'm simply going to set up two channels. This is a function. The function is the unit of abstraction here. And then I simply receive what I'm receiving. Then I can calculate and send back. We have a really, really simple stream model. Of course, there is synchronization going on, but it's nothing to do with the FizzBuzzer, FizzBuzz, or indeed the client itself, who simply wires things up by saying, right, I've got two channels. I've got a function, FizzBuzzer. I'm going to bind that without and back and I'm going to set this off buzzing. And then I'm going to loop through and send through requests for one through a hundred, pick up the result and print it out. And that's it. And as you can see, of course, there is synchronization going on here, but the synchronization is incredibly discrete. It's out of the way. There's no longer the programmers responsibility to mess it up. And this very, very simple model rather than saying, hey, everybody's sharing all of the objects all of the time. So this does indeed relate to, relate back to something a number of years ago, I studied this actor-based language, ABCL, and the actor model computation is not identical, but is certainly related to this kind of thinking. But I'm not going to get enough time to go into that in any detail. But I would like to sort of say, well, we have a question sometimes that if I want to pick up the results of something, how do I pick up the results of a computation? What if I'm not just streaming evaluations? In other words, what if I've actually, rather than asking, give me this, I'm going to send you a request, I want, and send me results when you have them, rather than treating that as two separate processes running, what if I'm actually trying to use something asynchronous? How do I pick up the result? This is where futures fit in. Futures are virtual proxies. They've been around in different programming languages and programming libraries for a while. But this idea, a virtual data object, give it to the client, they only provide a value when the computation is complete. The client can choose to block on it until a value is ready, or they can choose to poll whether or not it's ready or not, whether it is the value there. Now, what's nice about this approach, and actually see how we can render this in C++11, what I'm going to do here is we've taken a different view rather than a long-running thread. We say our function, whatever it is, we launch it asynchronously, this is almost a go routine style in that sense, we launch it asynchronously, we pick up its result, and what happens here is we wrap this. The idea here is that nobody sits around doing explicit locking, and what we're after is picking up, we're after this idea of separating out. That function can go and have as many side effects as it wants, as long as there's nothing to do with the code that I'm working in. The thread management, we don't do any thread management, it is just launched as an asynchronous function, quite literally. We pick up the result when we want to, we can block here on this io.get. I'm going to say this is the standard, does a lot of good stuff, but I'm going to go back to a proposal that I made a number of years ago, which I much preferred syntactically, where what we actually had was thread was a verb, not an object. You thread a function and it yields something that is a future, but called a joiner because that's what you do with it, and that itself is a function, so you can then pass it on to somebody else. So my mild obsession with functional programming ideas was visible in this, because I wanted everything to be a function. And the idea is what I get back is a function that then I can then call that will give me the result. So I give you, so this is a proper higher order programming. Harry, that's not the way that the future is gone. This is what we've got, and that gets us fairly close to that idea of asynchronous execution. Why does asynchronous execution matter? Well, it allows us ultimately to share what we're doing, but without interfering. It allows us to say, I want you to execute something independently of what I'm working on. I don't want to care about your execution policy. As long as you keep your state to yourself, then, and you give me an easy way to get the results back, that's what I want. Far too often, people have launched threads across data structures without thinking about it. They've gone and said, right, we've got a thread, we've got a shared data structure, we're going to put locks on it, and the whole code base is jammed up, both from a development perspective and a runtime perspective around this idea. Rather than thinking, how can I keep things apart? People have ended up pushing them together too soon. We need a composable model. And on that note, I will finish, and I'll take questions afterwards. Thank you very much. I'm not really working thin. Scratch my shoulder. It's like I'm working from... When this is over, Nothing you will be so right. I'll be one. If you love me, you will be tonight. But what's the problem? You can hide all those issues. Suddenly this guy you vote on it all with a knife right there. I can do all sorts. At the end of yourнак The whole section is free. You say that working is what I'm not supposed to do And I say ain't it right if I can't guess we love you I'm tired of thinking of what my wish was supposed to be Well, soon enough darling, this love would be reality How could you leave a girl, cause love for us wasn't meant to be Well, then you must be seeing some other guy instead of me I think that's why you got me working day and night, yeah, and I'll be working Friends are not to me tonight I'm working It's what a man's supposed to do And I say you ain't right If I can just be loved to you I can't believe girl
is, I guess this is as opposed to dysfunctional about that at length, but that may be one of the It's a lot. I mean, this is the thing. Functional language trying to get out. And it's called C. So in a useful way that I can do something about. As thing that can be executed as a function. So this algorithm and data structures and then mash them in C++ is the STL. This was Alex Stepanov's want to talk about this idea of immutability and they're not functions in the, certainly not what functional composition that I would use. So that go with const. One of them is reference. Pass change the state of it, it doesn't matter what of C++ developers who regard the idea of that we find in C++11. And again, similar kind of you do program in C++, rather than just being a of. And these days, the results might be a big mistake calling them mutexes and locks and a way of thinking about this. So this is a function. The function is the unit of abstraction functional programming ideas was visible in this,