Functional Programming in C++ (2013) | Hacker News Reader

Functional Programming in C++ (2013)

web.archive.org

This is from 2013, and the original title is "Functional Programming in C++". Moreover, Carmack never makes a statement that functional programming is the future anywhere in this article. The closest he says is "Formal systems and automated reasoning about software will be increasingly important in the future," which is a markedly different sentiment.

That said, the problem of not understanding possible code states does not seem to be purely a result of the internal software structure, but how it interacts with outside components, including the OS (if any).

There is a combinatorial explosion of the state space as a program's dependencies increase. As such, the most practical way to deal with this is crash-only software whereby components do not perform complicated error recovery, but are simply fenced and restarted to known good states with persistence used to ensure that the component can return to its prior point of operation quickly.

FP is useful for writing software like this, but not necessarily pure FP or even a single paradigm.

Thanks re the title. Submitters: the HN guidelines explicitly ask you not to rewrite titles like this, unless they are misleading or linkbait.

https://news.ycombinator.com/newsguidelines.html

(Submitted title was 'John Carmack: Why functional programming is the future'.)

https://news.ycombinator.com/submit should have a link to https://news.ycombinator.com/newsguidelines.html. (Edit:) I know there is a link in the footer of every other page, but when you open the submit form in great excitement, it's easy to forget about that (as demonstrated by this submission).

I just can't get behind all of this. Sure, its great to be able to reason clearly because you can see your whole state, but its exhausting always carrying your context around like a hobo with a huge backpack full of junk. Am I mistaken?

Exhausting is being in this situation:

  object Foo {

    var x: Int = 0

    def bar(y: Int) = x + y

  }

And trying to figure out what bar will return at any given point.

Are you somehow not in control of how x is being changed? You seem to have said that literally any statefulness is "exhausting".

Anyone, anywhere could modify x, which is what makes reasoning about this code difficult. When your entire program is a collection of mutable state that can be mutated by any piece of code, understanding what's going on becomes really difficult if not impossible. One thing that people are adopting from FP is to limit what is mutable, and when possible make state explicit.

That isn't true. I don't understand why you can't use a language that offers encapsulation.

What convinced me that avoiding mutations as much as possible was having to deal with code like that (in java):

    public class MyBigClass() {
        private int a;
        private int b;

        //hundreds of lines of code

        private int calculateSomething() {
            //do something
            a = a+1;
            return b*b;
        }

        //hundreds lines of code

        private int calculateSomethingElse() {
            int c = calculateSomething();
            return a+c;
        }

        //hundreds of lines of code
        public returnSomething() {
            return calculateSomethingElse();
        } 
    }

In this example. It's hard because you have to remember constantly which functions are changing your classes before you use them, and if you haven't written the functions, it's very easy to introduce a bug by involuntarily modify the states using the function calculateSomething, just wanting its output and not the modification of a.

That demonstrates some design flaws of Java, yeah, because your "private" variables are effectively just globals anyway.

The guy who is not using encapsulation at all this year will be making similar mistakes (massively long bodies, proliferation of unnecessary entities, etc.) if he switches to functional programming next year. It's not a panacea.

I'm afraid this doesn't demonstrate that any tiny bit of statefulness is "exhausting."

The monad type-class operations carry the context around for you. You can just write in imperative-seeming do-notation. The difficult part is trying to combine monads.

Here's what I don't get with Monads, why I've not felt the need to create a Monad-like system in my (non Haskell) code.

The 'world' is carried on the back of one parameter, right? So if I want to run a function taking two parameters in a particular 'world', which parameter is the Monad? If both of them are, what if they disagree which world is used?

Perhaps I haven't reached the fabled epiphany of monads, but they seem to be just implicit state attached to a single value, and only a single value. I'm not sure what this implicit stuff is better than a system where you are explicitly passing the 'world' that each function needs.

Why is

roll(dieSides: Random<int>) -> int

Clearer than

roll(random: Random, int dieSides) -> int

I get the passing of a world out of a function with a single value

getNumber() -> IO<int>

or using the extra implicit state to represent other possible values, like

Maybe<int>

but, using it to carry around state? That seems to me to be unnecessarily implicit.

What am I missing?

In a language with immutable values and pure functions, roll always returns the same number from the same generator. If you want to call roll twice and get different numbers, the first call needs to return a new generator (with an updated seed) to pass to the second call. Rather than having to write something like

  do
    (x, g2) <- roll g1
    (y, g3) <- roll g2
    (z, g4) <- roll g3

it's convenient to have plumbing that hides all those single-use g values.

Thanks. So the issue is that Monads save us having multiple returns? That makes sense.

That's one of the things monads do, but they can do more. A monad is defined by an underlying type (roughly, some kind of "container"), and two functions (putting an object in the container, and creating a new container by applying a function to the contained object). That's all a monad actually is. It simply turns out that given those relatively simply building blocks, you can do all sorts of neato things with them, like encapsulating state, error handling, chaining actions together, etc.

An example of a monad which has really nothing necessarily to do with mutable state are Promises in JavaScript. The container, of course, is a Promise, and the two functions I described are `resolve` and `then`.

Right, and some of that makes sense to me. It makes sense in some cases (Maybe was the example I gave, a Promised value another) to tie such things directly to a single typed value. But what I was querying was, is this implicitness a good move in general.

In particular the issue I was addressing was the encapsulation of an arbitrary state with a single typed value. It's been remarked elsewhere that 'mixing' monads is a problem: I guess that's always been the thing I've felt haven't made them work replicating as a coding pattern. I tend to prefer explicit over implicit state.

> I tend to prefer explicit over implicit state.

I guess it depends on your definitions, but monadic state is just as explicit as any other.

    myMonadicFunction :: String -> State Int String
    myMonadicFunction string = do
      currentVal <- get
      put (currentVal + length string)
      return (reverse string)

It's just as clear as what you'd have in an imperative programming language.

I'm convinced the main reason monads aren't common in other languages is that most languages just don't have strong enough type systems to support them explicitly. Implicitly they can be found here or there, such as with promises, or just the fact that the semantics of many imperative languages can be viewed as a monad. But of course, probably the biggest reason is that people who are used to mutable state don't see the need. It's one of those things whose value becomes apparent with use.

Thanks, I really appreciate your responses.

What's to stop you passing a struct or object with the two monadic functions attached, or ignore the function requirement (for the case of state) and pass the struct with the state and result in it? The benefit being that you can package up more than just one value in that (immutable) structure along with the 'specialness'. I don't see why that is less typesafe.

I'm having a tough time trying to understand what you're proposing. First of all, in Haskell there's no real concept of having functions "attached" to objects (in the OO sense). The closest analogue is a type class, which relates a type to a set of functions. For monad, that looks like

    class Monad m where
      return :: a -> m a
      (>>=)  :: m a -> (a -> m b) -> m b

And it's up to the particular instance to determine how those functions are implemented. For example,

    instance Monad Maybe where
      return :: a -> Maybe a
      return x = Just x

      (>>=) :: Maybe a -> (a -> Maybe b) -> Maybe b
      maybe >>= f = case maybe of 
        Nothing -> Nothing
        Just x -> f x

The definition of the State type, and its corresponding Monad instance, is a little more involved (I suggest this blog post for an explanation [1]):

    newtype State s a = State { runState :: s -> (a, s) }

    instance Monad (State a) where
    return x = State $ \s -> (x, s)
    m >>= k = State $ \s -> let (a, s') = runState m s
                            in runState (k a) s'

I'm honestly not quite sure what you mean by the rest of it (for example, "ignoring the function requirement", "specialness" etc). But the bottom line is that you can do any typesafe thing you want to, within the rules of how the language works.

[1]: http://brandon.si/code/the-state-monad-a-tutorial-for-the-co...

Thanks again.

Sorry, I wasn't talking about Haskell. Following the OP I was talking about the merits of using these concepts or structures in other languages (C++, as per the OP, in particular). Of course, in a language with strong support and syntax for a particular pattern, you should rely on that pattern. But beyond that, it can be useful to use a pattern in other languages. Carmack is talking about writing C++ in a more functional style. I've written OO plain C, for example, when that pattern has made sense, and much of my C++ is heavily influenced by my experience with Scheme.

My point was that I don't get the emphasis on Monads, as a concept, for the range of things it gets emphasised for. In a language which has core syntactic and semantic support, and there are few alternatives, then of course it has to be used widely. But that's a different argument to saying it is an intrinsically good solution for those cases. I might be missing something, but as an architectural pattern in general it doesn't seem appealing. Not enough to reimplement in another language.

That's the context to my comment on typesafety. You said that other languages aren't typesafe enough. I was suggesting that, implementing a monad as a structure or an object would be typesafe, so I couldn't see what was insufficient.

Don't think of "a monad" as a thing. Think of "monad" as "a way you can threat things": you can treat things monadically by implementing the monad operations for them, such that they obey the monad laws.

So do I. It's a pattern. But you don't create things a particular way for no reason. My point is about being able to see the point.

I get the sense that there are people who think Monads are a fundamentally powerful pattern for structuring software. And I don't get that. And I'd like to, because if I'm missing something, it could mean I improve my code architecture.

Monad's qualify as a 'that's an interesting way to get around its self-imposed restrictions' moment when learning Haskell (which I've not used with any seriousness) for me. So I don't get the fuss. I'm not saying that I don't see the logic of those restrictions, nor that I don't see why you'd want to voluntarily code with similar restrictions in other languages. More than, if you're going to write something that has to work around those restrictions in another language, I've no idea why you'd necessarily chose Monads.

Or, put another way, what use are Monads in non Haskell code?

Well, sort of. One of the big focuses of functional programming is _minimizing_ state; in other words, only what must be passed around should be. Sure, you'll end up having a large context that the entire program operates in, but having to pass around a context incentivizes passing around the minimal amount of context to sub-parts (functions) in the program. You don't need the whole global state? Great; only pass around a small part of it to that part of the program. You don't need the whole context all the time so you don't pass the whole thing around all the time.

Kinda. There are tricks to make it less burdensome.

One of the tricks is the use of monads in Haskell. Monads are really just a small set of functions that operate in a certain way (that "satisfies the monadic laws") on a type.

What that gives you is (among many other things) a way to carry an implicit "world" around with you without needing to refer to it all the time.

One use for such a "world" would be a seed for a random number generator so different parts of your program can use their own, isolated streams of random numbers (nice for determinism, testing, debugging, etc), even if they execute asynchronously because Haskell is a "lazy" language where code doesn't necessarily get evaluated unless it really needs to.

Another use is for the "world" to actually represent the real world -- all of it -- so the I/O interactions happen in the right order. That's very important in a language where the evaluation order is so "loose" as it is in Haskell.

There are other tricks as well. One of them is to have lots of small transformation functions that don't need to understand all of the world, just their little bit of it. You create the big world transformations by composing the smaller transformations. The data structures you use are slightly different: you don't want to modify your data structures, you want to create new ones all the time, i.e. inserting an object into a tree shouldn't modify the tree but return a completely new tree with the new object in it WHILE KEEPING THE OLD TREE AROUND UNCHANGED. This doesn't have to be as expensive as it sounds, in fact, it can be quite cheap. Data structures where you can do this cheaply are called persistent data structures and they work really well with a functional programming style.

(They don't have to implemented purely functionally internally as long as they present a pure interface.)

https://en.wikipedia.org/wiki/Persistent_data_structure

Persistent data structures can also be confluent, which means that they use sharing internally if two versions of a data structure end up being logically the same. Tarjan and Sleator have some really nice papers on that -- well worth reading, even if you don't care one bit about functional programming.

This isn't a strict definition, but I just think of it as turning the usual model inside out. You always have a state that you're modifying, if you're doing functional or imperative programming (or a mix). Usually you're "inside" the state, changing it via pokes and prods from within. (Think global/shared state typical of C/C++ programs) In FP you pass around a big ball of state and no modification happens outside of it (there is no global or shared state, or at least access to it is tightly controlled if it's not a pure language). The functions live 'outside' the state, so to speak. Programming this way was, to me, one of the major revelations of learning the functional style.

One difficulty with functional style c++ is just how verbose it is. Every time I tried to use std::transform (the equivalent of "map") I had to delete it and rewrite as a loop because it was just too hard to read. Functional style on a large scale is still possible.

The article is not about the functional C++ you mention. It is about using pure functions (functions that do not modify global context).

I get that. But the two ideas are very closely related. See also my final sentence.

I'm really hopeful that Concepts will dramatically reduce the amount of code needed for std::transform. Imagine no begin() or end(). It would suddenly become less verbose than the classic for loop.

That problem is due to the STL not being built around iterators/ranges. I don't see how concepts enter into it (though contra Andrei Alexandrescu, I'm still a big believer in concepts).

It really irks me that the std algorithms library seems to have been designed without any consideration for usability given how much I would love to rely heavily on the generic algorithms it contains. For example consider the simple task of testing to see if an element exists in a container:

    if (std::find(container.begin(), container.end(), element) != container.end())

My fingers are now cramping and my eyes are crossing trying to read that. It beggars belief that overloads don't exist which take an entire range which is all I want to do 99% of the time.

Well the containers that have fast lookup (set, map and their unordered_ and multi_ counterparts), all have efficient .find() member functions. The general philosophy of the idealised STL is not to provide you with anything you can compose efficiently yourself.

A 3-4 line template will will give you a terse boolean contains() method, but it won't give you any big-O guarantees, and having such a thing would encourage very inefficient patterns (like calling contains() and then doing a find() if it's true, which effectively does the lookup twice). Why introduce a weak abstraction? If you're forced to write it yourself you're more likely to understand the implications.

Alex Stepanov, who wrote the original STL, is very much a believer in fundamental indivisible building blocks like iterators and algorithms and careful API design. To grok more about why things are the way they are, I recommend watching his "Efficient Programming with Components" lectures[0]. Over the course he builds up, in excruciating detail, an implementation of merge sort, reasoning about, and discussing with his students, the implications of almost every line of code.

And yes, Stepanov complains about the lack of terseness and expressiveness in C++ as well.

[0] https://www.youtube.com/playlist?list=PLHxtyCq_WDLXryyw91lah...

There is a legitimate complaint with that specific example, though: having to write .begin() and .end() is obnoxious instead of using more modern iterators/ranges.

well the slightly more concise way of writing it is this:

    auto e = end(container);
    if (e == std::find(begin(container), e, element)) { ... }

...but yeah, it sucks. If I were doing this though, i'd to be encapsulating things in to a higher level abstraction. Seeing std::find in more than 1 place in a file is a red light for me.

Holy cow, thank you so much for the lectures!

Much the those issues are addressed in various boost libraries. There is one which wraps all the algorithms and containers in range classes so that all the f(c.begin(), c.end(), g) silliness gets replaced with f(c, g). There is another one which makes it easy to create streams of transforming and mapping functions with a F1 -> F2 -> F3 interface.

On an unrelated note, sad to see altdevblogaday has gone away :( Sure the pages are cached somewhere, but the posts always made for interesting reading.

Couldn't agree more. It went away shortly after I discovered it, and although there's a lot of awesome information in the archives, it's a shame no new content is being added.

I've noticed hackers/self taught prefer functional programming styles and CS degree holders prefer the more common style.

i think people probably just prefer whatever paradigm they used first or currently are comfortable with. I have a cs degree and we were taught scala at my school and now I use it everyday.

I used BASIC first, then Z80 machine code, then Pascal, then 8086 machine code, then C.

I really like functional programming, especially in Standard ML and Haskell. I didn't learn ML until I'd been programming for about 15 years.

Edit: beadder grammer.

I woudln't say 'prefer' but it's a heavy influence on your view of the world. I think imperative programming fit our biological needs and reflex. We want to see results and effects. Functional programmers are up high in the world of platonic ideals. They delay effects by composing abstract logics and then ask for a result. No newbie wanna suffer that, but no newb want to suffer mutable state bug hunts either.. the learning excitement just shadow this issue for a while, and I bet somewhere deep inside, we're all mathematician in the closet.

I'm self-taught and while I can see the formal appeal of functional programming, I'm a low-level coder that implicitly reduces state to bare-metal registers and cache in GPUs and embedded systems. Since I'm already sweating bits over state down to the byte-level, I just don't see what FP would improve on this.

The big improvements often come from better algorithms and data structures.

Using a function style or a higher-level language sometimes makes it easier to modify the program (and hence use a better algorithm).

I remember people swearing by assembly language back in the 80's, thinking C would make their programs slow and bloated. In reality, it was usually the other way around because C code is much more malleable than assembly. You might want to give FP a second look.

There is a very active attempt to make GPUs FP-friendly called C++AMP. And for streaming transformation tasks, it's a nice abstraction.

https://en.wikipedia.org/wiki/C%2B%2B_AMP

However, my best algorithms are stylistically equivalent to a map-reduce with combiners entirely in GPU-space. The map tasks themselves carry all the scope I need. They are independent units of work executed by independent warps (synchronized groups of 32 GPU threads) whose results need to be reduced to floating point numbers. That reduction is done with 64-bit fixed point atomic ops (my combiners) because:

1) This insures the sum is deterministic

2) Ever since Kepler (GK104), it's much faster than reduction buffers and uses a fraction of the memory

3) It's possible because I can precompute the expected dynamic range and adjust the fixed point exponent accordingly

Now given that, do you see a functional programming equivalent that significantly improves on this design? I haven't yet.

map-reduce is already functional, isn't it?

Who cares if you implement the combining with atomic ops or by sending data to a process that does the combining or whether you stuff the data in a buffer and then reduce it afterwards?

(Of course you might care for performance reasons -- but conceptually it's the same thing.)

Yes, it is true conceptually, but:

1) "Who cares" is not the sort of thing you want to say to someone who cares about performance because:

2) Sending the data to buffers for subsequent reduction was the first implementation (2009). But it was a memory hog and a 5% or so slowdown to perform the reduction subsequently rather than concurrently with Atomic Ops and 64-bit Fixed Point (2012).

But I guess what we're arriving at is that this is essentially a functional design using imperative code? I can live with that.

> But I guess what we're arriving at is that this is essentially a functional design using imperative code? I can live with that.

Yep. That's precisely what it is.

Here's the relationship. How can you guarantee your low-level code is correct? Here's one way. You have a language like Idris create a DSL that targets the machine you want. You can model what the set of correct programs in your domain look like, and then produce correct code. That's why functional programming in general, and dependent-type programming in particular, is useful for low-level problem domains.

That's not a problem. The application in question was a redesign of an MPI FORTRAN implementation that can produce the same outputs to within FPRE. To verify the low-level code, we just run in double-precision and make sure it matches to 1 part in 10e-9 so across 200+ daily conformance tests. Production mode runs in single-precision with 64-bit Fixed Point accumulation. And that's also been demonstrated to have numerical stability nearly equivalent to running in full double-precision.

It's not a problem for you, but it's a problem generally. That's why so many people are working to solve it.

I don't think this applies to you. The main message of the article/blog is that 1) Humans can't keep track of states well and 2) Machines can't create temporary states efficiently and since you're already keeping track of states manually and working at the low enough level where you're maintaining your temporary states, you don't apply.

I thought functional programming[1] was associated with ivory tower CS researchers/enthusiasts? I guess it's been turned on its head for some reason.

[1] At least the Haskell/ML kind.

The underlying concept will surface once you've had a chance to debug program states and that you realize you can't keep track of all program states. I had no idea about functional programming but soon realized that I was going for the same thing when trying my best to not keep instance variables in my objects.

You misunderstand me. I wasn't trying to diss FP but rather the naysayers who try to associate people who like FP with certain groups.

Self-taught programmers are far too diverse to make any value judgment like this.

Hackers, and I'll assume all those vaguely tracing their lineage from MIT, have never been associated with FP. There has always been a fascination with Lisp, but that's the extent of it. In practice, most of their software legacy has been in firmly imperative and procedural languages, but with touches of a Lisp here and there.

It's precisely CS and academia where functional programming has been thriving. John Backus' research on function-level programming, Robin Milner on ML, David Turner on Miranda from which Haskell is almost a direct successor, etc.

So on the whole, I have the exact opposite impression that you do.

Meh, maybe the people whose first-ever programming experience was CS 101 prefer OOP, at least at first, because it is all they may have ever seen [1]. But Haskell and Lisps, among others, are widely admired and used in academia. Even if it isn't taught directly, most reasonably engaged CS students come away with an appreciation for FP and its core concepts.

I think this preference has more to do with the individual's past experiences and future goals than it does with his/her level of formal CS education.

[1] Although even this varies greatly from school to school, the school where I got my MS used OCaml in the undergrad algorithms course for awhile. My undergrad algorithms course used C, so again no OOP.

A "CS degree" covers everything from a Java School to a proper (semi-mathematical) Comp Sci education.

If you learn type theory and semantics you also learn functional programming (and will probably like it, even if you don't use it much in practice).

If all the world is a Java VM to you, then... well, you might have a different view of the world.

really? functional has long been the domain of computer scientists.

Functional languages seems to be one of the hardest things for people without a CS background to pickup in my experience.

I think I disagree with this. It seems natural to start to code with a functional style as you become a better developer. I worked on scala for quite a while, and took a detour to write Java. The Java that I wrote was way more readable and testable than any of the imperative code I wrote before learning FP well.

I have a CS degree and I prefer immutable data structures and pure functions. If anything, I believe it might be the other way around, since holding a CS degree means you've had a FP course and you're more aware of the implications of multithreading, immutability and side effects. "Self taught"s are more likely to have an education from online tutorials, which are fairly shallow.

Reply on news.ycombinator.com